md5安全性及攻击方式.txt

md5加密算法

MD5 的安全性问题 

     MD5是一种在PGP中被用来单向变换用户口令和对信息签名的单向散列算法。 

     一种单向散列的强度体现在它能把任意的输入随机化到什么程度并且能产生唯一的输出。对单向散列的直接攻击可以分为普通直接攻击和“生日”攻击。 


对MD5的普通直接攻击 

    所谓直接攻击又叫野蛮攻击。攻击者为了找到一份和原始明文 m 散列结果相同的明文 m' ，就是 H(m)=H(m') 。普通直接攻击，顾名思义就是穷举可能的明文去产生一个和 H(m) 相同的散列结果。对MD5来说散列结果为128-bits，就是说如果攻击者有一台每秒尝试1,000,000,000条明文的机器需要算约10^22年，同时兴许会同时发现m本身:))。 


对MD5的生日攻击 

    生日攻击实际上只是为了找到两条能产生同样散列结果的明文。记得那个有名的概率生日问题吗？在 N 个人中至少有两个人生日相同的概率是多少？所谓生日攻击实际上只是用概率来指导散列冲突的发现，对于MD5来说如果尝试2^64条明文，那么它们之间至少有一对发生冲突的概率就是 50％。仅此而已，对当今的科技能力来说，它也是不可能的。一台上面谈到的机器平均需要运行585年才能找到一对，而且并不能马上变成实际的攻击成果。因为码长和速度的关系，对crypt(3)的生日攻击就成功得多。 


其他对MD5的攻击 

    微分攻击被证明对MD5的一次循环是有效的，但对全部4次循环无效。（微分攻击是通过比较分析有特定区别的明文在通过加密后的变化传播情况来攻击加密体系的。） 


    有一种成功的MD5攻击，不过它是对MD5代码本身做了手脚，是一种crack而不是hack更算不上cryptanalysis了。而且如果你做了PGP发行包的签名校验，是容易发现代码被替换过了的。 


口令长度和信息论 

    根据传统信息论，英语的每个8-bits字母的信息熵为1.3bits。如果口令足够长，MD5的结果就会足够随机。对 128-bits 的MD5输出来说，一个长达98个字符的口令将给出一个随机的密匙。 

     (8/1.3)*(128/8) = 98.46 chars 

    可是谁会用一个象下面这样长的口令呢？ 

        12345678901234567890123456789012345678901235678901234567890 
        1234567890123456789012345678 


    1.3 bits 的信息熵来自于英语语法的规律性这个事实，字母出现概率的不等造成了熵的减小。如果26个拉丁字母出现的概率均等，信息熵将会增至

      log(26)/log(2) = 4.7 bits 


    这样一个随机密匙所需口令长度就减为 27.23 chars 了，如果再加上大小写和几个符号还可以减少。关于选择口令的问题可以参考任何关于安全性的书籍，它们都适用，上面是关于PGP本身特色的部分。