ホーム > 情報セキュリティ > SHA-1が破られた？

SHA-1が破られた？

2005 年 2 月 16 日 コメントをどうぞ コメント

Schneier氏のブログSchneier on Securityに各種暗号（署名）システム等に広く利用されているハッシュ関数SHA-1がXiaoyun Wang, Yiqun Lisa Yin, Hongbo Yu という中国Shandong University を中心とする研究グループによって破られたとの論文が出回っているという投稿が行われた。

full SHA-1に対しブルートフォースによるした場合の2の80乗オペレーションよりも少ない2の69乗オペレーションによるコリジョンの検出

（内容について誤解を招くおそれがあったため記述を修正 2/16）

SHA-0に対する2の39乗オペレーションでのコリジョンの検出

58-round SHA-1に対する2の33乗オペレーションでのコリジョンの検出

がなされたそうだ。詳細については現段階においては確認はとれていないが論文そのものは入手されている模様。MD5はすでにコリジョンが検出され危険性が指摘されているし、SHA-1はNISTが2010年までには段階的にフェードアウトさせる予定だったために、今回の発表の内容次第では現行の暗号(署名)を用いた各種システムの入れ替えを前倒ししなくてはならなくなる可能性もある。

詳細は追って公表するとのこと。

【参考情報】
SHA-1 Broken(Schneier on Security)
http://www.schneier.com/blog/archives/2005/02/sha1_broken.html

カテゴリー: 情報セキュリティ タグ:
  1. Thinking Network Security
    2005 年 2 月 16 日 23:54 | #1
    返信 | 引用

    SHA-1破られた？

    単純にコリジョンをブルートフォースで見つけただけなら、まだ入れ替えまで考えなくてもよさそう。代替品としてはSHA-256あたりなんでしょうか。

    http:…

  2. re-in-car-na-tion
    2005 年 2 月 17 日 00:39 | #2
    返信 | 引用

    SHA1破れたり

    SHA-1が破られた？ 269回の試行で同一ハッシュを生成できた様子。 MD5が…

  3. し は¨て ん
    2005 年 2 月 17 日 03:41 | #3
    返信 | 引用

    > (although it doesn’t affect applications such as HMAC where collisions aren’t important).

    HMAC(-SHA1)は、影響を受けない考えてよい？

  4. keiji
    2005 年 2 月 17 日 09:14 | #4
    返信 | 引用

    HMACの場合、鍵を知らない限り有効なハッシュを算出できないので、コリジョンの検出がこの程度容易になったとしても影響はないという意味かなぁと思いますが・・・。

  5. LunaTear
    2005 年 2 月 17 日 16:00 | #5
    返信 | 引用

    SHA-1にも風穴?

    SHA-1が破られた？：武田圭史↓の予定通り攻略法が見つかったようです。スラッシュドット ジャパン | SHA-0、MD5、 MD4にコリジョン発見、reduc…

  6. し は¨て ん
    2005 年 2 月 18 日 01:13 | #6
    返信 | 引用

    はい。おっしゃる通りと思います。すいません。
    ところで、論文はもう入手されました？

  7. keiji
    2005 年 2 月 18 日 01:39 | #7
    返信 | 引用

    そんな、すみませんてことはないですよ。
    コメントありがとうございました。

    論文ですが、残念ながら入手できていません。おそらく、まだ正式なものではなくて一部の人にレビューを依頼している段階かと思います。いずれどこかで正式に発表されるのではないでしょうか。
    そういう意味ではSchneier氏の発表はちょっと反則のような気もしますが。

  8. しばてん
    2005 年 2 月 18 日 03:37 | #8
    返信 | 引用

    てっきり、どこかで話したものだと思っていました。

    シュナイアー氏のブログのエントリに、こんなコメントも:
    > @Bruce
    > I don’t know if you saw the Cryptographer’s Panel today, but Avi Shamir mentioned the Chinese team’s report and the need for better hashing.
    >
    > Posted by: Davi Ottenheimer at February 15, 2005 10:34 PM

  9. keiji
    2005 年 2 月 18 日 05:37 | #9
    返信 | 引用

    サンフランシスコで開催中のRSAカンファレンスに集まった人たちの間でこのペーパーが出回っているようですね。
    でパネルの中で少しこの話がでたのかと思います。

    CNETには「３ページのリサーチノートが・・・」と書かれていましたね。

    http://news.com.com/Researchers+Digital+encryption+standard+flawed/2100-1002_3-5579881.html?part=rss&tag=5575731&subj=news

  10. しばてん
    2005 年 2 月 18 日 21:00 | #10
    返信 | 引用

    http://www.theregister.co.uk/2005/02/17/sha1_hashing_broken/

    > Still, in practical terms, things are not as bad as they might seem. Collisions are irrelevant in a number of crypto implementations, …

    Exploitable な collision が見付かる訳ではない？？？

    Full paper 待ちですな。

  11. しばてん
    2005 年 2 月 18 日 21:41 | #11
    返信 | 引用
  12. keiji
    2005 年 2 月 18 日 23:45 | #12
    返信 | 引用

    http://theory.csail.mit.edu/~yiqun/shanote.pdf

    これが出回った現物のようですね。
    えらくあっさりしていますね。

    full SHA-1の実際のコリジョンはまだ見つかっていないようですが、時間の問題でしょうね。

  13. 武田圭史
    2005 年 2 月 19 日 00:11 | #13
    返信 | 引用

    「SHA-1が破られた」と言うリサーチノートの現物

    これのようです。

  14. ウェブテクニック
    2005 年 2 月 21 日 09:22 | #14
    返信 | 引用

    SHA1に脆弱性

    SHA1に脆弱性が見つかったようだ。　SHA1に関する詳しい説明はしないが、ある…

  1. トラックバックはまだありません。

CAPTCHA