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

余少標(biāo) 李陽(yáng) 韓占男 周雨涵 北方工業(yè)大學(xué)

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

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

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

1.1 PBKDF2算法簡(jiǎn)介：

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

圖1.PBDKF2算法核心偽代碼

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

1.2 快速口令派生算法

1.2.1 算法結(jié)構(gòu)改進(jìn)

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

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

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

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

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

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

1.2.2 多線程機(jī)制

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

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

1.2.3 線程隨機(jī)salt

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

1.3 測(cè)試結(jié)果

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

1.3.1 算法效率

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

計(jì)算1000次用時(shí)/秒PBKDF2算法 12秒本文的快速口令派生算法 4秒

1.3.2 算法安全性

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

2 結(jié)束語(yǔ)

口令是向系統(tǒng)提供唯一標(biāo)識(shí)個(gè)體身份的機(jī)制，只給個(gè)體所需信息的訪問權(quán)，從而達(dá)到保護(hù)個(gè)人隱私和敏感信息的作用。

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

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

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