简单查询哈希算法

Question

阅读下面链接的文章后:

http://news.ycombinator.com/item?id=910203

我现在正在努力证明并理解为什么下面列出的哈希是不安全的,不应该由程序员练习.

H(k || m) - > SHA1("秘密密钥"+"name = bob,withdraw = $ 200")

H(m || k) - > SHA1("name = bob,withdraw = $ 200"+"secret-key")

正如文章所述,第一个例子完全是致命的.SHA1(以及MD5和许多其他哈希)是共享一个名为Merkle-Damgaard的通用设计的机器,这意味着它们以块长度块处理消息,并使用这些块来置换内部状态.输出SHA1是该状态的"最终"内容.但实际上没有什么能够"完成"SHA1状态; 如果您在线上看到SHA1值,您可以继续使用额外数据启动Merkle-Damgaard机器.这意味着您可以使用任意数据添加到新的消息中,这些数据会显示为真实的.这种攻击非常容易实施; 它需要大约20行Ruby代码.

第二个例子也被打破了,这是这篇博文的主题.如果你在消息之后加上键,你就不能继续用数据驱动哈希,因为你无法猜到的秘密就在它的末尾.

我在C#中编写了一个简单的哈希函数,试图证明作者声称的内容,但无论我添加/填充或在消息的后面/前面,无论如何我都无法做到这一点.

        string strRet;
        // hash contains the SHA 1 value of SHA1 (key + temp)
        string hash = "ce0037fbbff7a1b68b5794bd73dcc7d63338f115";

        try
        {
            string key = "password";
            string temp = "name=bob,withdraw=$200";

            for (int i = 0; i < 1000; i++)
            {
                byte[] buffer = Encoding.ASCII.GetBytes(temp);
                SHA1CryptoServiceProvider cryptoTransformSHA1 = new SHA1CryptoServiceProvider();
                strRet = BitConverter.ToString(cryptoTransformSHA1.ComputeHash(buffer)).Replace("-", "");
                strRet = strRet.ToLower();
                MessageBox.Show(strRet);

                if (strRet.Equals(hash))
                {
                    MessageBox.Show("Hash are equal !");
                    MessageBox.Show(temp);
                }

                temp = key + temp + "2";
            }

            MessageBox.Show("The End !");

        }
        catch (Exception)
        {
            MessageBox.Show("There is a Error !");
        }

有人可以通过提供一个指定的示例来指导我,我可以散列,理解并证明作者在文章中对两种哈希方法的主张.提前感谢您提供的任何帮助.

Answer 1

我们退一步吧.首先,我们的意思是H(k|m)什么？这是为了什么？

这里的目标如下.Alice和Bob共享一个密钥.他们如何分享,我们不知道.不知何故,爱丽丝和鲍勃已经同意了一个秘密密钥,没有人知道它.

Alice希望向Bob发送消息.Alice不在乎是否有人可以阅读该消息,但Alice非常关心Bob知道Alice写了消息.

他们提出了以下方案.Alice将创建一条消息,其中包含密钥,后跟消息的其余部分.然后她将散列整个事情.然后,她将没有密钥的消息与哈希一起发送给Bob.

Bob尝试验证消息是否来自Alice.他将密钥放在邮件前面并对其进行哈希处理.如果Bob获得相同的哈希值,那么Bob知道任何人都使该消息拥有了密钥.他知道这不是他,所以一定是爱丽丝.

这个方案并不安全.马洛里希望向鲍勃发送一条虚假信息并诱使他认为这是来自爱丽丝.

有一天,爱丽丝带着她的秘密钥匙"123SesameStreet"和一条消息"亲爱的鲍勃,我爱你!",她将他们一起追加到"123SesameStreet亲爱的鲍勃,我爱你!" 她哈希到"398942358092"并发送哈希和消息"亲爱的鲍勃,我爱你!" 给鲍勃

Mallory在收到Bob之前截获了该消息.Mallory不知道密钥,但她确实知道消息和哈希.Mallory将SHA1算法设置为状态398942358092,然后运行"Just kidding I hate you!"字符,并获取92358023934的哈希值.现在Mallory发送新哈希和消息"亲爱的Bob,我爱你开个玩笑我讨厌你!" 给鲍勃

这有多精确？这是交易.基本上,SHA1就像这个过于简化的草图:

int hash = 0;
foreach(char c in message)
    hash = MakeNextHash(hash, c);

也就是说,你从零开始.然后你散列第一个字符和数字0.然后用第二个字符散列该散列.这会产生一个新的哈希值.然后用第三个字符散列它,以产生第三个散列.继续这样做,直到你的角色用完为止; 你做的最后一个哈希是整个消息的哈希.

真正的SHA1算法使用大于单个字符的块,并且状态大于int,但基本上就是这样.它使用前一个状态作为下一个状态的输入,一次转换一堆状态.

所以,如果我告诉你"这里是一个字符串M.此外,字符串KM有哈希H(K | M)." 那么很明显,你可以计算出的散列H(K | M | Z)KMZ的任何Z,即使你不知道ķ.你只是说:

int hash = HKM;
foreach(char c in Z)
    hash = MakeNextHash(hash, c);

结果是H(K | M | Z),即使你不知道K.

所以,你看到这是怎么回事.Bob预先给出了消息的密钥,并通过SHA1算法运行它,然后他获得了正确的哈希值.所以他已经验证了消息来自Alice,当时消息的一半来自Mallory.

这就是为什么关键必须走到最后.您必须在消息之后放置密钥,而不是之前.你会想.事实证明,尽管攻击现在并不像关键优先计划那样微不足道,但它仍然不安全.该H(m|k)计划也没有好处.

为什么不？

假设Mallory拦截了消息M和散列H,即H(M | K),其中K是密钥.她阻止信息到达.

马洛里很容易计算H(M).困难的部分是Mallory推断出破坏性消息N,使得H(N)= H(M).她是如何做到的,我们还不知道,但人们普遍认为这种技术存在,我们还没有找到它.

马洛里知道H(N | K)与H(M | K)相同,与之前的推理相同 - 因为计算H(N | K)我们要做的是:

int hash = HN;
foreach(char c in key)
    ....

计算H(N | K).Mallory不需要知道K以便产生消息N,使得H(N | K)是H(M | K).

所以现在马洛里向鲍勃发送了N和H(M | K)/ H(N | K) - 他们是同一件事.Bob将K附加到N,并验证该消息来自Alice,而实际上它来自Mallory.

它变得更糟.假设马洛里已经捕获了一百万条消息M1,M2,......以及在爱丽丝和鲍勃之间传递的一百万个哈希H(M1 | K),H(M2 | K)...... Mallory需要制作一条消息N,使得H(N)与H(M1),H(M2),H(M3)中的任何一个匹配,......她的工作变得容易一百万次.她发现这样的消息N使得H(N)匹配,例如H(M1234),然后将N和H(M1234 | K)发送给Bob.Bob没有注意到他之前看过那个哈希,并且认为这是来自Alice的消息.

它变得更糟.让我们稍微改变一下方案,看看它会变得更糟.卡罗尔有一条消息,她希望通过爱丽丝发送给鲍勃.消息M是"嘿鲍勃,这是卡罗尔.让我和你以及爱丽丝下周一起共进午餐.如果爱丽丝同意,她会和她的身份验证员一起发给你这条消息." 卡罗尔不知道密钥K,但爱丽丝确实知道.Alice同意消息M,因此她计算H(M | K)并将M和H(M | K)发送给Bob.

现在马洛里想要制造麻烦,所以她搜索两条消息B(用于良性)和D(用于危险),使得H(B)等于H(D),并且这样Alice会同意B但是不会同意使用D.这比搜索与Alice 给定消息匹配的消息N容易得多,因为现在Mallory可以选择这两个消息.找到碰撞的工作比较容易.

Mallory找到这两条消息并将B发送给Alice.Alice同意该消息,计算H(B | K),并将H(B | K)和B发送给Bob.Mallory截取消息B并将其替换为D.H(B | K)和H(D | K)通过与之前相同的推理相同.Bob接收消息D并验证H(D | K)与他发送的哈希匹配,因此他知道Alice已批准该消息,即使她没有.

还没有人找到一种方法让SHA1可靠地产生这样的碰撞,但几乎所有人都相信我们会解决这个问题.

故事的第一个道理是不要将这些技术中的任何一种用作消息验证器.第一个是琐碎的,第二个可能在我们的一生中被打破.

第二个道德是永远不允许潜在的攻击者选择您将使用您的密钥处理的消息.