按:最近几天各种网站被曝库的事件让咱大跌眼镜。密码最基本的存储方式是取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函数的原理如下:

  1. 根据用户输入,使用HMAC方法生成对应此输入的hash(记作H)。
  2. H的前5字节,记作F
  3. 生成一个可以根据一定规律迭代变化的参数P,使得计算P+H的 SHA1值时,能存在某个P,使得S=SHA1(P+H)的前5字节等于F。 这一段实际上是借鉴了hashcash算法中的耗时方案。5字符=20位,为了生成满足这个条件的P,需要平均计算2^19次SHA1才可以找到一个。这就消耗了大量的时间(数个毫秒至数百毫秒,最多一秒,但是不会太短)。
  4. 将S去除前5字节的数据记作checkstr,满足条件的P记作padding,记录下来以备稍后验证之用。

verify验证函数的原理:

  1. 同样,根据用户输入,取HMAC,记作H
  2. 同样,取H的前5字节,记作F
  3. 根据记录的(checkstr,padding),计算S’=SHA1(H+padding)
  4. 验证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……不过如此而已。