7.4 对单向Hash函数的生日攻击

    对单向Hash函数有两种穷举攻击的方法。 第一种是最明显的：给定消息的Hash函数H（M），破译者逐个生成其他文件M‘，以使H（M）= H（M’）。第二种攻击方法更巧妙：攻击者寻找两个随机的消息：M，M‘，并使H（M）=H（M’）。这就是所谓的冲突攻击法（Collision Attack）。这比第一种方法来得容易。

    生日悖论是一个标准的统计问题。房子里面应有多少人才有可能使至少一人与你生日相同？答案是253。既然这样，那么应该有多少人才能使他们中至少两个人的生日相同呢？答案出人意料地低：23人。对于仅有23个人的屋里，在屋里仍有253个不同对的人。

    寻找特定生日的某人类似于第一种方法；而寻找两个随机的具有相同生日的两个人则是第二种攻击。第二种方法通常被称为生日攻击（Birthday Attack）。

    假设一个单向Hash函数是安全的，并且攻击它最好的方法是穷举攻击。假定其输出为m比特，那么寻找一个消息，使其单向函数值与给定函数值相同则需要计算2m次；而寻找两个消息具有相同的hash值仅需要试验2m/2个随机的消息。每秒能hash运算一百万次的计算机得花600,000年才能找到第二个消息与给定的64-比特hash值相匹配。同样的机器可以在大约一个小时里找到一对有相同的hash值的消息。

    这就意味着如果你对生日攻击非常担心，那么你所选择的hash函数值其长度应该是你本以为可以的两倍。例如，如果你想让他们成功破译你的系统的可能低于1/280，那么应该使用160-比特的单向Hash函数。