按：最近几天各种网站被曝库的事件让咱大跌眼镜。密码最基本的存储方式是取hash，但是CSDN直到09年才搞…… 然而hash的问题也有很多，求碰撞的能力也在逐渐提高。下面打算提出一种改进的密码存储方式。最基本的思想见于epi.clyce在人人上分享的资料，但是我没看具体的实现，知道它是需要破解者消耗时间的而已。我尚没有进行详细研究我的算法就匆忙发出来，希望大家一起进行。
先看代码，用PHP实现的：
function myhash($source,$key=”){
$hash = hash_hmac(‘whirlpool’,$source,$key);
$match = substr($hash,0,5);
$padding0 = md5(rand());
$padding1 = 0;
while(substr($got = sha1(“$hash$padding0$padding1″),0,5)!=$match){
$padding1++;
}
return array(“checkstr”=>substr($got,5),”padding”=>”$padding0$padding1″);
}
function verify($source,$key,$chkstr,$padding){
$hash = hash_hmac(‘whirlpool’,$source,$key);
$match = substr($hash,0,5);
$sechash = sha1(“$hash$padding”);
return ($sechash == “$match$chkstr”);
}
print_r($hashresult = myhash(“test”,”key”));
print_r(verify(“test”,”key”,$hashresult['checkstr'],$hashresult['padding']));代码分两部分，myhash函数用于生成一组接受用户密码后需要存储的参数(checkstr,padding)。
verify函数用于接受用户稍后给出的输入，然后根据数据库或者什么中记录的(checkstr,padding)信息验证用户的输入是否是之前记录过的信息。
myhash函数的原理如下：
- 根据用户输入，使用HMAC方法生成对应此输入的hash（记作
H）。 - 取
H的前5字节，记作F。 - 生成一个可以根据一定规律迭代变化的参数
P，使得计算P+H的 SHA1值时，能存在某个P，使得S=SHA1(P+H)的前5字节等于F。 这一段实际上是借鉴了hashcash算法中的耗时方案。5字符=20位，为了生成满足这个条件的P，需要平均计算2^19次SHA1才可以找到一个。这就消耗了大量的时间（数个毫秒至数百毫秒，最多一秒，但是不会太短）。 - 将S去除前5字节的数据记作
checkstr，满足条件的P记作padding，记录下来以备稍后验证之用。
verify验证函数的原理：
- 同样，根据用户输入，取HMAC，记作
H。 - 同样，取H的前5字节，记作
F。 - 根据记录的
(checkstr,padding)，计算S’=SHA1(H+padding) - 验证
S’==H+checkstr。
原理讲解完毕。下面我简要分析一下。
首先，myhash函数消耗的时间远远大于verify验证函数消耗的时间。这是可以容忍的，因为网站登录的请求一般大于注册请求。控制注册请求的负载也有很多方法。
其次，根据数据库中的(checkstr,padding)值能否推出可以登录的密码？我认为困难：
根据刚才的验证机制，我们看到，padding是贴在用户输入的首次hash后面，进行第二次hash的字符串。必须满足如下“方程”：
SHA1(padding+HMAC)==HMAC[0:5]+checkstr（认为padding和checkstr是常数）
才可能登录。也就是说，试图登录而不知道密码的人，必须构造一个密码，使得它通过了HMAC函数（值得注意的是，这里采用了whirlpool进行HMAC方法，这个算法的输出长度与SHA-512相当；此外，对于不同的新注册用户，HMAC的另一个参数key也完全可以不同。不同key下的HMAC函数简直相当于不同的散列函数，对于破解者的要求还有提高）后，满足如上条件。具体这种概率有多少，我也不清楚，直观上似乎比构造碰撞的概率低（因为checkstr几乎具有和SHA1一样的长度——实际上是少了5个字节——而且SHA1相当于是加了salt=padding的）。这里请大家分析。 分类：电工电子及信息技术, 研究
刚才想了一下，
SHA1(padding+HMAC)==HMAC[0:5]+checkstr（认为padding和checkstr是常数）
这个方程大致可以这样估计吧：我们考虑先以HMAC为变量，那么碰撞出一个以checkstr为结尾的字符串就相对困难。这需要碰撞140比特。但是构建出这样的字符串后，还需要挑出HMAC前20比特满足要求的。这接近碰撞160比特了。但是这还不够，因为解出的是HMAC，不是用户的密码。由已知的HMACKey解出用户密码，还需要一定工作。
但是没想通，hashcash那种生成的碰撞在这里有什么用呢？看来是没用了？我们完全可以随便挑选一个padding，得到checkstr，然后把这一对存储到数据库啊。看来本文解方程的思想还好，但是前面有点鸡肋。用SHA1保护HMAC不过就：
SHA1（HMAC）==Data_Recorded这样就可以了……或者是HMAC_2(HMAC_1)==DATA_RECORDED，两种不同的HMAC……不过如此而已。