3

以下のリンクから記事を読んだ後：

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 コードが必要です。

2 番目の例も壊れており、このブログ投稿の主題です。メッセージの後にキーを追加すると、推測できない秘密が最後にあるため、データでハッシュを駆動し続けることができなくなります。

作成者の主張を証明しようとして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 !");
        }

ハッシュ方法の両方について記事で著者が主張していることをハッシュし、理解し、証明できる特定の例を提供することで、誰かがこれについて私を導くことができますか? 提供されたヘルプに事前に感謝します。

4

2 に答える 2

12

一歩後退しましょう。まず、 とはどういう意味H(k|m)ですか? そして、これは何のためですか？

ここでの目標は次のとおりです。Alice と Bob は秘密鍵を共有します。彼らがそれをどのように共有しているかはわかりません。どういうわけか、アリスとボブは秘密鍵について合意しましたが、他の誰もそれを知りません。

Alice は Bob にメッセージを送信したいと考えています。アリスは誰かがメッセージを読むことができるかどうかは気にしませんが、アリスがメッセージを書いたことをボブが知っていることを非常に気にかけます。

彼らは次のスキームを思いつきます。Alice は、秘密鍵とそれに続く残りのメッセージで構成されるメッセージを作成します。その後、彼女はすべてをハッシュします。次に、秘密鍵を含まないメッセージをハッシュと共にボブに送信します。

Bob は、メッセージが Alice からのものであることを確認しようとします。彼は秘密鍵をメッセージの前に置き、それをハッシュします。Bob が同じハッシュを取得した場合、Bob は、メッセージを作成した人が秘密鍵を持っていることを知っています。彼はそれが自分ではないことを知っているので、アリスだったに違いありません.

このスキームは安全ではありません。マロリーは、ボブに偽のメッセージを送って、アリスからだと思い込ませようとしています。

ある日、アリスは自分の秘密鍵「123SesameStreet」とメッセージ「Dear Bob, I love you!」を受け取り、それらを「123SesameStreetDear Bob, I love you!」に追加します。彼女はそれを「398942358092」にハッシュし、ハッシュとメッセージ「Dear Bob, I love you!」を送信します。ボブに。

マロリーは、ボブに到達する前にメッセージを傍受します。マロリーは秘密鍵を知りませんが、メッセージとハッシュは知っています。マロリーは、状態が 398942358092 になるように SHA1 アルゴリズムをセットアップし、「冗談です、私はあなたが嫌い​​です!」という文字を実行し、92358023934 からハッシュを取得します。ここで、マロリーは新しいハッシュとメッセージ「親愛なるボブ、私はあなたを愛しています」を送信します。 ！ 冗談です、大嫌いです！」ボブに。

これはどのくらい正確に機能しますか？これが取引です。基本的に、SHA1 は次の非常に単純化されたスケッチのように機能します。

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

つまり、ゼロから始めます。次に、最初の文字と数値 0 をハッシュします。次に、そのハッシュを2 番目の文字でハッシュします。これにより、新しいハッシュが作成されます。次に、それを3 番目の文字でハッシュして、3 番目のハッシュを作成します。文字がなくなるまでそれを続けます。最後に作成したハッシュは、メッセージ全体のハッシュです。

実際の SHA1 アルゴリズムでは、1 文字よりも大きなブロックと int よりも大きな状態が使用されますが、基本的にはそのようになります。前の状態を次の状態の入力として使用して、一度に 1 ブロックずつ一連の状態を変換します。

「ここに文字列 M があります。また、文字列 KM にはハッシュ H(K|M) があります。」Kがわからない場合でも、任意の Z に対して KMZ のハッシュ H(K|M|Z) を計算できることは明らかです。あなたはただ言う：

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

K を知らなくても、結果は H(K|M|Z) です。

それで、あなたはこれがどうなるかを見ます。Bob は秘密鍵をメッセージの先頭に追加し、SHA1 アルゴリズムを実行して、正しいハッシュを取得します。したがって、メッセージの半分がマロリーからのものであるにもかかわらず、彼はメッセージがアリスからのものであることを確認しました。

そのため、キーは最後に配置する必要があります。メッセージの前ではなく、後にキーを配置する必要があります。と思うでしょう。キー ファースト スキームの場合のように攻撃は自明ではありませんが、それでも安全ではないことがわかります。H(m|k)スキームもダメです。

なぜだめですか？

マロリーがメッセージ M と H(M|K) であるハッシュ H を傍受したとします。ここで、K は秘密鍵です。彼女はメッセージが届かないようにします。

Mallory は H(M) を簡単に計算します。難しいのは、H(N) = H(M) となる有害なメッセージ N をマロリーが推測することです。彼女がどのようにそれを行うのかはまだわかりませんが、そのような技術が存在すると広く信じられていますが、まだ見つかっていません.

Mallory は、前と同じ理由で、H(N|K) が H(M|K) と同じであることを知っています。

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

H(N|K) を計算します。マロリーは、H(N|K) が H(M|K) となるようなメッセージ N を作成するために、K を知る必要はありません。

したがって、マロリーは N と H(M|K) / H(N|K) をボブに送信します。これらは同じものです。ボブは N に K を追加し、メッセージが実際にはマロリーからのものであるにもかかわらず、アリスからのものであることを確認します。

ひどくなる。マロリーが、アリスとボブの間で渡された 100 万のメッセージ M1、M2、... と 100 万のハッシュ H(M1|K)、H(M2|K)、... をキャプチャしたとします。マロリーは、H(N)が H(M1)、H(M2)、H(M3) のいずれかに一致するメッセージ N を作成する必要があります...彼女の仕事は 100 万倍簡単になりました。彼女は、H(N) が H(M1234) と一致するようなメッセージ N を見つけ、N と H(M1234|K) をボブに送信します。ボブは、そのハッシュを以前に見たことがあることに気付かず、これがアリスからのメッセージであると信じています。

ひどくなる。スキームを少し変更して、どのように悪化するかを見てみましょう。キャロルは、アリス経由でボブに送りたいメッセージを持っています。メッセージ M は、「やあ、ボブ、こちらはキャロルです。来週、あなたと私とアリスで一緒にランチを食べましょう。アリスが同意すれば、彼女はこのメッセージを彼女のオーセンティケータとともにあなたに送信します。」キャロルは秘密鍵 K を知りませんが、アリスは知っています。アリスはメッセージ M に同意するので、H(M|K) を計算し、M と H(M|K) をボブに送信します。

ここで、マロリーは問題を引き起こしたいので、H(B) が H(D) と等しく、アリスが B に同意するが同意しないような 2 つのメッセージ B (無害) と D (危険) を検索します。これは、アリスからの特定のメッセージに一致するメッセージ N を検索するよりもはるかに簡単です。これは、マロリーが両方のメッセージを選択できるようになったためです。衝突を見つける作業は桁違いに簡単です。

Mallory はこれら 2 つのメッセージを見つけ、B を Alice に送信します。Alice はメッセージに同意し、H(B|K) を計算して、H(B|K) と B を Bob に送信します。Mallory はメッセージ B を傍受し、それを D に置き換えます。H(B|K) と H(D|K) は、前と同じ理由で同じです。ボブはメッセージ D を受信し、H(D|K) が送信されたハッシュと一致することを確認します。したがって、アリスがメッセージを承認していなくても、アリスがメッセージを承認したことがわかります。

SHA1 でそのような衝突を確実に生成する方法をまだ見つけた人はいませんが、ほぼ全員がこの問題を解決できると信じています。

この話の最初の教訓は、これらの手法のいずれもメッセージの検証者として使用しないことです。1 つ目は簡単に壊れてしまい、2 つ目は私たちが生きているうちに壊れる可能性があります。

2 番目の教訓は、潜在的な攻撃者が秘密鍵で処理しようとしているメッセージを選択することを決して許可しないことです。

于 2011-10-25T06:28:01.560 に答える
2

この主張のソースであるhttp://rdist.root.org/2009/10/29/stop-using-unsafe-keyed-hashes-use-hmac/をリンクすることができます。

このハッシング スキームは必要以上に弱いと述べられており、実際に SHA-1 で破ることができるというわけではありません。

このスキームは、基礎となるハッシュ関数に弱点がある場合にのみ脆弱です (最初の攻撃では 2 番目のプリイメージ、2 番目の攻撃では衝突)。私が覚えている限りでは、SHA-1 はどちらに対しても実用的な脆弱性を発見していませんが、MD5 は 2 番目の攻撃のコンテキストで壊れています。

衝突はハッシュ関数で最も簡単に発見できる脆弱性であるため、必要な場合を除き、衝突攻撃に対して脆弱ではない構造を使用することをお勧めします。そのため、HMAC が推奨されます。

于 2011-10-25T07:29:46.040 に答える