基于PBKDF2算法的快速口令派生算法

余少標 李陽 韓占男 周雨涵 北方工業(yè)大學

通常用戶口令都是可見字符的組合，長度也不固定，但密碼算法對密鑰的要求比較嚴格，工程實踐中常用PKCS#5中定義的2種常用的由口令派生密鑰的方法，從用戶口令派生出所需密鑰。然而PKCS#5中定義的兩種常用的口令派生算法生成口令的效率不高，以PBKDF2算法為例，計算1000次約需要12秒。當需要在短時間內(nèi)生成大量密鑰時，PBKDF2算法是無法滿足要求的。

針對以上問題，本文提出一種快速口令派生算法，基于PBKDF2算法的原理，改善其內(nèi)部算法的結構并且添加多線程機制，同時加入隨機數(shù)可以使得改良后的算法能在短時間內(nèi)生成大量的安全密鑰。

1 基于PBKDF2算法的快速口令派生算法

1.1 PBKDF2算法簡介：

PBKDF2算法的輸入為用戶口令、鹽（salt）、迭代次數(shù)和密鑰長度，輸出為隨機密鑰。算法工作原理通過hmac函數(shù)，將明文和salt作為hmac的輸入?yún)?shù)，然后重復進行計算，最終產(chǎn)生密鑰，偽代碼如圖1。

圖1.PBDKF2算法核心偽代碼

其中pwd為用戶輸入口令，salt為鹽值，iterations為迭代次數(shù)，Klen為輸出的密鑰字節(jié)長度,hlen為hmac算法輸出的字節(jié)長度。Ceil函數(shù)為向上取整函數(shù)，‘||’表示級聯(lián)符號，即將兩個字節(jié)串連接在一起,out[0 fi Klen]表示輸出取out數(shù)組的前Klen位。

1.2 快速口令派生算法

1.2.1 算法結構改進

PBKDF2中，HMAC算法為原子操作，故無法對其進行優(yōu)化。根據(jù)HMAC算法的原理，可以將一次HMAC運算等效替換為進行四次哈希運算。從而將原子操作從HMAC計算變?yōu)镠ash計算,從而對其進行優(yōu)化。

據(jù)此將第二次for循環(huán)重寫為如下偽代碼，其中PADDING表示填充函數(shù)，iPad與oPad為32字節(jié)的數(shù)組，iPad中每個字節(jié)均為0x36H,oPad中均為0x5CH：

圖2.內(nèi)層循環(huán)重寫后的偽代碼

分析可知，對于第二層循環(huán)，pwd的值是不變的，即K值是不會發(fā)生變化的，故圖2中第1、2、4步實際上是重復的運算。所以將這三步運算轉移到循環(huán)外，可以減少每次循環(huán)的計算量，優(yōu)化后，每次循環(huán)中只需要進行2次Hash計算，所以代碼的效率大大提高。

優(yōu)化后完整偽代碼如下（采用SM3算法作為hash函數(shù)）：

圖3.優(yōu)化后完整源代碼

1.2.2 多線程機制

算法所生成密鑰的安全性依賴著大量的循環(huán)，較高的循環(huán)次數(shù)可以用于抵抗暴力攻擊。如果使用多線程機制，采用多條線程共同分擔計算任務，就可以大大減少需要的時間。

本算法的C語言實現(xiàn)中，通過C語言庫函數(shù)調(diào)用可以獲取機器的CPU核心數(shù)目，然后采用windows提供的API來創(chuàng)建雙倍核心數(shù)目的線程，每條線程分得等量的任務。

1.2.3 線程隨機salt

算法中，每條線程使用其序號，以及其計算的次數(shù)為隨機種子生成隨機數(shù)將該數(shù)作為salt，在后續(xù)的Hash計算中，使用salt可以抵抗字典攻擊，提高了安全性。

1.3 測試結果

測試環(huán)境：win10 i7-2600 3.40GHz 8G內(nèi)存 Visual Studio2009

1.3.1 算法效率

實驗比較了提出的算法與PBKDF2算法的性能，本文的口令派生算法比PBKDF2算法效率提高了3倍以上。

計算1000次用時/秒PBKDF2算法 12秒本文的快速口令派生算法 4秒

1.3.2 算法安全性

實驗考察在分析輸出的16字節(jié)密鑰中0-255字節(jié)的分布頻率。統(tǒng)計1000次派生結果的字節(jié)分布，各字節(jié)出現(xiàn)的次數(shù)在50-70之間，接近期望值62.5。統(tǒng)計10000次派生結果的字節(jié)分布，各字節(jié)出現(xiàn)的次數(shù)在500-650之間，接近期望值625。因此，本算法每種字節(jié)的出現(xiàn)頻率差距較小，分布均勻。

2 結束語

口令是向系統(tǒng)提供唯一標識個體身份的機制，只給個體所需信息的訪問權，從而達到保護個人隱私和敏感信息的作用。

算法基于SM2/SM3/SM4算法的高效由口令派生密鑰的函數(shù)，用來代替國際算法的口令派生函數(shù)。在此基礎上，通過多線程并發(fā)計算實現(xiàn)了密鑰的高效隨機派生。口令派生函數(shù)在短時間內(nèi)可以輸出大量的密鑰，且字節(jié)分布較均勻，可供計算機和通信系統(tǒng)的一般程序使用。具有一定的的靈活性以及安全性，可用來保護敏感信息。同時，該函數(shù)也具有一定的安全性，可應用于計算機和通信系統(tǒng)的一般程序，能夠抵抗一定程度上的字典攻擊以及暴力攻擊。

[1] 于飛,李曉華,等. PBKDF2函數(shù)的一種快速實現(xiàn)[J]，信息安全與通信保密，2013.

[2] Jeffrey Richter. Windows核心編程[M].北京：機械工業(yè)出版社，2008.