简单查询哈希算法

Question

简单查询哈希算法

c#hashcryptographysha

3

阅读以下链接中列出的文章后：

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

我现在正在尝试证明和理解下面列出的哈希值为什么不安全，程序员不应该使用。

H(k || m) --> SHA1("secret-key" + "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 !");
        }

请问有人能通过提供一个具体的例子来指导我，让我可以进行哈希并理解并证明作者在文章中对这两种哈希方法所声称的内容吗？非常感谢提供任何帮助。

- user1012147

1

回复：“我已经在C#中编写了一个简单的哈希函数，试图证明作者所声称的内容，但无论我添加/填充消息的前面/后面，似乎都无法做到这一点”--请用简单的语言精确地解释您认为作者所声称的内容。您可能无法证明作者所声称的内容，因为您没有正确理解该声明。您的代码似乎与所做的声明毫不相关。 - Eric Lippert

感谢您的输入。实际上，我正在使用这些算法，并在阅读本文后考虑使用HMAC，因为目前使用的两种算法是不安全的？因此，我编写了上面列出的简单C#代码。据我所知，在不知道密钥的情况下，攻击者可以以某种方式得到认证，这就是我试图证明的。总之，我试图理解和证明为什么使用这两种方法是不安全的？ - user1012147

由于SHA算法的块和迭代结构以及缺少其他最终步骤，所有SHA函数都容易受到长度扩展和部分消息冲突攻击的影响。这些攻击使攻击者可以伪造一条消息，仅由带有密钥哈希的签名 - SHA（message || key）或SHA（key || message）- 通过在不知道密钥的情况下扩展消息并重新计算哈希来实现。防止这些攻击的最简单方法是进行两次哈希运算 - SHAd(message) = SHA(SHA(0b || message))（0b - 零块，长度等于哈希函数的块大小）。需要解释吗？ - user1012147

2个回答

2

您可以链接到http://rdist.root.org/2009/10/29/stop-using-unsafe-keyed-hashes-use-hmac/，这是这个说法的来源。

它说这种哈希方案比它需要的更弱，而不是它可以用SHA-1实际破解。

只有在基础哈希函数存在任何弱点（第一次攻击的第二个预像和第二个碰撞）时，此方案才会受到攻击。据我所知，SHA-1没有被发现有任何实际漏洞，而MD5在第二次攻击的情况下已经被破解。

由于碰撞是哈希函数中最容易发现的漏洞，除非必要，否则使用不容易受到碰撞攻击的构造是一个好主意。这就是为什么推荐使用HMAC的原因。

- CodesInChaos

感谢您提供的输入。在之前的研究中，我已经遇到了那个方面。 - user1012147

SHA-1目前还没有被破解，但已经接近了。如果你要使用哈希算法，SHA-2会更安全。 - Brian

MD5存在问题，可以精确地进行这种攻击，并且被用来伪造SSL证书。虽然SHA1基于与MD5相同的构造（Merkle-Damgaard），这意味着它在未来可能会出现类似的问题。您应该使用SHA2系列算法之一，RIPEMD160或Whirlpool。请参阅：http://en.wikipedia.org/wiki/MD5#Collision_vulnerabilities - Polynomial

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Eric Lippert · Accepted Answer

让我们退一步。首先，什么是H(k|m)？这是用来做什么的？

目标如下：Alice和Bob共享一个秘密密钥。我们不知道他们如何分享它。不过某种方式下，Alice和Bob已经就一个秘密密钥达成了协议，而且没有其他人知道这个密钥。

Alice希望向Bob发送一条消息。Alice不介意任何人能否读到这条消息，但是Alice非常在意Bob知道这条消息是她写的。

他们想出了以下方案。Alice将创建一个包含秘密密钥和其余消息的消息。然后她会对整个消息进行哈希处理。然后，她将不包括秘密密钥的消息连同哈希值一起传输给Bob。

Bob会尝试验证该消息是否来自Alice。他会将秘密密钥放在消息前面并对其进行哈希处理。如果Bob得到相同的哈希输出，则Bob知道制作该消息的人持有秘密密钥。他知道这不是他的，所以肯定是Alice的。

这个方案是不安全的。Mallory希望向Bob发送一条虚假消息，并使他认为消息来自Alice。

有一天，Alice取出她的秘密密钥"123SesameStreet"和一条消息"Dear Bob, I love you!"，然后将它们连接起来变成"123SesameStreetDear Bob, I love you!"。她对其进行哈希处理得到"398942358092"并将哈希值和消息"Dear Bob, I love you!"发送给Bob。

Mallory截获了这条消息，然而Mallory不知道秘密密钥，但是她知道消息和哈希值。Mallory设置SHA1算法的状态为398942358092，然后运行字符"Just kidding I hate you!"并得到一个输出哈希为92358023934。现在，Mallory向Bob发送了新的哈希和消息"Dear Bob, I love you! Just kidding I hate you!"。

这是如何工作的？基本上，SHA1的工作方式如下过于简化的描述：

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

换句话说，你从零开始。然后将第一个字符和数字0进行哈希运算，再用第二个字符与该哈希值进行哈希运算，得到一个新的哈希值。接着用第三个字符与那个新的哈希值进行哈希运算，以此类推，直到所有字符都被处理完；最后一个生成的哈希值就是整个消息的哈希值。

真正的SHA1算法使用的块比单个字符大，状态也比int类型大，但基本上就是这样。它一次转换一个块的状态，使用前一个状态作为下一个状态的输入。

因此，如果我告诉你“这是一个字符串M。此外，字符串KM具有哈希值H(K|M)。”那么很显然，即使你不知道K，你也可以计算出KMZ的哈希值H(K|M|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 是 H(M|K)，其中 K 是秘密密钥。她阻止消息到达。

Mallory 轻松地计算出 H(M)。难点在于 Mallory 推断出一个有害消息 N，使得 H(N) = H(M)。我们目前还不知道她是如何做到的，但广泛认为这种技术存在，只是我们还没有找到它。

由于进行 H(N|K) 计算的方式与之前相同，因此 Mallory 知道 H(N|K) 与 H(M|K) 相同。

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

为了计算 H(N|K)，Mallory 不需要知道 K，只需制作消息 N，使得 H(N|K) 等于 H(M|K)。

现在 Mallory 发送 N 和 H(M|K) / H(N|K)（它们是相同的）给 Bob。Bob 将 K 添加到 N 中，并验证消息来自 Alice，而实际上来自 Mallory。

更糟糕的是，假设 Mallory 捕获了一百万条消息 M1、M2、……和一百万个哈希 H(M1|K)、H(M2|K)、…… 它们在 Alice 和 Bob 之间传递。 Mallory 需要创建一条消息 N，使得 H(N) 与 H(M1)、H(M2)、H(M3)、…… 中的任何一个匹配。她的工作就变得容易了一百万倍。她找到这样的消息 N，使得 H(N) 与 H(M1234) 相匹配，然后发送 N 和 H(M1234|K) 给 Bob。Bob 没有注意到他之前见过这个哈希值，认为这是 Alice 的消息。

情况更糟。改变一下方案来看看会变得更糟。Carol 有一条消息，她希望通过 Alice 向 Bob 发送。该消息 M 是“嘿 Bob，我是 Carol。让我们下周一起吃午餐。如果 Alice 同意，她将使用身份验证器发送此消息。”Carol 不知道密钥 K，但 Alice 知道。Alice 同意了这条消息，因此她计算了 H(M|K) 并将 M 和 H(M|K) 发送给 Bob。

现在 Mallory 想要制造麻烦，所以她搜索两条消息 B（表示良性）和 D（表示危险），使得 H(B) 等于 H(D)，且 Alice 将同意 B，但不会同意 D。这比搜索与 Alice 的特定消息匹配的消息 N 容易得多，因为现在 Mallory 可以选择两个消息。找到碰撞的工作容易得多。

目前还没有找到一种可靠地产生这种碰撞的 SHA1 方法，但几乎所有人都相信我们将解决这个问题。

这个故事的第一个教训是不要使用这两种技术作为消息验证器，第一个方法很容易被破解，第二个方法可能会在我们的有生之年被破解。

第二个教训是永远不要让潜在攻击者选择您要处理的消息。