基于PBKDF2算法的快速口令派生算法
2018-02-05余少标李阳韩占男周雨涵北方工业大学
余少标 李阳 韩占男 周雨涵 北方工业大学
通常用户口令都是可见字符的组合,长度也不固定,但密码算法对密钥的要求比较严格,工程实践中常用PKCS#5中定义的2种常用的由口令派生密钥的方法,从用户口令派生出所需密钥。然而PKCS#5中定义的两种常用的口令派生算法生成口令的效率不高,以PBKDF2算法为例,计算1000次约需要12秒。当需要在短时间内生成大量密钥时,PBKDF2算法是无法满足要求的。
针对以上问题,本文提出一种快速口令派生算法,基于PBKDF2算法的原理,改善其内部算法的结构并且添加多线程机制,同时加入随机数可以使得改良后的算法能在短时间内生成大量的安全密钥。
1 基于PBKDF2算法的快速口令派生算法
1.1 PBKDF2算法简介:
PBKDF2算法的输入为用户口令、盐(salt)、迭代次数和密钥长度,输出为随机密钥。算法工作原理通过hmac函数,将明文和salt作为hmac的输入参数,然后重复进行计算,最终产生密钥,伪代码如图1。
图1.PBDKF2算法核心伪代码
其中pwd为用户输入口令,salt为盐值,iterations为迭代次数,Klen为输出的密钥字节长度,hlen为hmac算法输出的字节长度。Ceil函数为向上取整函数,‘||’表示级联符号,即将两个字节串连接在一起,out[0 fi Klen]表示输出取out数组的前Klen位。
1.2 快速口令派生算法
1.2.1 算法结构改进
PBKDF2中,HMAC算法为原子操作,故无法对其进行优化。根据HMAC算法的原理,可以将一次HMAC运算等效替换为进行四次哈希运算。从而将原子操作从HMAC计算变为Hash计算,从而对其进行优化。
据此将第二次for循环重写为如下伪代码,其中PADDING表示填充函数,iPad与oPad为32字节的数组,iPad中每个字节均为0x36H,oPad中均为0x5CH:
图2.内层循环重写后的伪代码
分析可知,对于第二层循环,pwd的值是不变的,即K值是不会发生变化的,故图2中第1、2、4步实际上是重复的运算。所以将这三步运算转移到循环外,可以减少每次循环的计算量,优化后,每次循环中只需要进行2次Hash计算,所以代码的效率大大提高。
优化后完整伪代码如下(采用SM3算法作为hash函数):
图3.优化后完整源代码
1.2.2 多线程机制
算法所生成密钥的安全性依赖着大量的循环,较高的循环次数可以用于抵抗暴力攻击。如果使用多线程机制,采用多条线程共同分担计算任务,就可以大大减少需要的时间。
本算法的C语言实现中,通过C语言库函数调用可以获取机器的CPU核心数目,然后采用windows提供的API来创建双倍核心数目的线程,每条线程分得等量的任务。
1.2.3 线程随机salt
算法中,每条线程使用其序号,以及其计算的次数为随机种子生成随机数将该数作为salt,在后续的Hash计算中,使用salt可以抵抗字典攻击,提高了安全性。
1.3 测试结果
测试环境:win10 i7-2600 3.40GHz 8G内存 Visual Studio2009
1.3.1 算法效率
实验比较了提出的算法与PBKDF2算法的性能,本文的口令派生算法比PBKDF2算法效率提高了3倍以上。
计算1000次用时/秒PBKDF2算法 12秒本文的快速口令派生算法 4秒
1.3.2 算法安全性
实验考察在分析输出的16字节密钥中0-255字节的分布频率。统计1000次派生结果的字节分布,各字节出现的次数在50-70之间,接近期望值62.5。统计10000次派生结果的字节分布,各字节出现的次数在500-650之间,接近期望值625。因此,本算法每种字节的出现频率差距较小,分布均匀。
2 结束语
口令是向系统提供唯一标识个体身份的机制,只给个体所需信息的访问权,从而达到保护个人隐私和敏感信息的作用。
算法基于SM2/SM3/SM4算法的高效由口令派生密钥的函数,用来代替国际算法的口令派生函数。在此基础上,通过多线程并发计算实现了密钥的高效随机派生。口令派生函数在短时间内可以输出大量的密钥,且字节分布较均匀,可供计算机和通信系统的一般程序使用。具有一定的的灵活性以及安全性,可用来保护敏感信息。同时,该函数也具有一定的安全性,可应用于计算机和通信系统的一般程序,能够抵抗一定程度上的字典攻击以及暴力攻击。
[1] 于飞,李晓华,等. PBKDF2函数的一种快速实现[J],信息安全与通信保密,2013.
[2] Jeffrey Richter. Windows核心编程[M].北京:机械工业出版社,2008.