帰ってきた「しっぽのさきっちょ」

しっぽのさきっちょ: 2015-10-22 付 (2017-02-25 更新)

SHA-1 衝突問題: 廃止の前倒し

no extension

SHA-1 の廃止プロセスが前倒しになるかもしれない。

おさらい: SHA-1 衝突問題

そもそもの発端は,2004年に複数の hash 関数において高い確率で hash 値を衝突(collision)させる攻略法が発表されたことだった。

その後の研究で SHA-1 も攻略可能であることが分かってきて暗号技術の周辺は大騒動になった。

Hash 値の衝突問題

暗号技術における hash 関数とは,以下の機能を持ったアルゴリズムである

  1. 任意のデータ列を一定の長さのデータ列(hash 値)に「要約」する
  2. Hash 値から元のデータ列を推測できない
  3. ひとつの hash 値に対して複数のデータ列が(実時間で)見つからない

Hash 関数はメッセージ認証符号(Message Authentication Code; MAC)や電子署名(digital signature)の中核技術のひとつであり,データの「完全性(Integrity)」を担保する重要な要素である。 特に3番目の「ひとつの hash 値に対して複数のデータ列が(実時間で)見つからない」という機能が破られると,その hash 関数では完全性を担保できなくなってしまう。 これを「Hash 値の衝突問題」という。

よくできた hash 関数であれば, hash 値のビット長を $n$ とすると,衝突の確率は $1 / 2^{\frac{n}{2}}$ であると言われている。 SHA-1 の hash 値の長さは $160\,\mathrm{bits}$ なので,衝突の確率は $1 / 2^{80}$ になるはずだが,実際にはそれよりもずっと大きい $1 / 2^{69}$ で可能,というのが当時の問題だった。

2010年問題

これを受けて, SHA-1 を2010年までに廃止し SHA-2 (SHA-224/256/364/512) に移行する措置がとられた。 これが暗号技術における「2010年問題」である1

ただ,現状では(特に legacy system において)アルゴリズムの置き換えがなかなか進まなかったことと SHA-1 の攻略があまり進展しなかったことにより,この期限は2013年まで延長された。 現在の SHA アルゴリズムの評価と有効期限は以下のとおり。

Security
Strength
Digital
Signatures and
hash-only
applications
HMAC Key Derivation
Functions
Random
Number
Generation
80 SHA-1, SHA-224, SHA-512/224, SHA-256, SHA-512/256, SHA-384, SHA-512 SHA-1, SHA-224, SHA-512/224, SHA-256, SHA-512/256, SHA-384, SHA-512 SHA-1, SHA-224, SHA-512/224, SHA-256, SHA-512/256, SHA-384, SHA-512 SHA-1, SHA-224, SHA-512/224, SHA-256, SHA-512/256, SHA-384, SHA-512
112 SHA-224, SHA-512/224, SHA-256, SHA-512/256, SHA-384, SHA-512 SHA-1, SHA-224, SHA-512/224, SHA-256, SHA-512/256, SHA-384, SHA-512 SHA-1, SHA-224, SHA-512/224, SHA-256, SHA-512/256, SHA-384, SHA-512 SHA-1, SHA-224, SHA-512/224, SHA-256, SHA-512/256, SHA-384, SHA-512
128 SHA-256, SHA-512/256, SHA-384, SHA-512 SHA-1, SHA-224, SHA-512/224, SHA-256, SHA-512/256, SHA-384, SHA-512 SHA-1, SHA-224, SHA-512/224, SHA-256, SHA-512/256, SHA-384, SHA-512 SHA-1, SHA-224, SHA-512/224, SHA-256, SHA-512/256, SHA-384, SHA-512
192 SHA-384, SHA-512 SHA-224, SHA-512/224, SHA-256, SHA-512/256, SHA-384, SHA-512 SHA-224, SHA-512/224, SHA-256, SHA-512/256, SHA-384, SHA-512 SHA-224, SHA-512/224, SHA-256, SHA-512/256, SHA-384, SHA-512
256 SHA-512 SHA-256, SHA-512/256, SHA-384, SHA-512 SHA-256, SHA-512/256, SHA-384, SHA-512 SHA-256, SHA-512/256, SHA-384, SHA-512
Hash function that can be used to provide the targeted security strengths (via SP800-57 Part 1 (Revision 3) )
Security Strength 2011 through 2013 2014 through 2030 2031 and Beyond
80 Applying Deprecated Disallowed
Processing Legacy use
112Applying AcceptableAcceptableDisallowed
Processing Legacy use
128 Applying/ProcessingAcceptable Acceptable Acceptable
192 Acceptable Acceptable Acceptable
256 Acceptable Acceptable Acceptable
Security-strength time frames (via SP800-57 Part 1 (Revision 3) )

しかし現状は全くスケジュールどおりではなく, SHA-1 を使った証明書の発行が停止され始めたのはようやく昨年末頃からだ。 一方,主要ブラウザは2017年以降 SHA-1 を使った証明書を無効にする計画を発表している。

SHA-1 Freestart Collision

ところが最近になって SHA-1 の攻略について進展があった。

これは SHA-1 のアルゴリズム上の更なる危殆化を指すものではないが,最新の計算リソースを効率的に使って,いわば「力任せ」(って言うと御幣があるけど)で攻略している。 GPU をふんだんに使った専用ハードウェアやクラウド・サービスなどを組み合わせることにより,近い将来に実用的なコストで SHA-1 攻略が可能になると指摘されている。

Concretely, we estimate the SHA-1 collision cost today (i.e., Fall 2015) between 75K\$ and 120K\$ renting Amazon EC2 cloud computing over a few months. By contrast, security expert Bruce Schneier previously projected (based on calculations from Jesse Walker) the SHA-1 collision cost to be ~173K\$ by 2018. Note that he deems this to be within the resources of a criminal syndicate. Large corporations and governments may possess even greater resources and may not require Amazon EC2.
via The Shappening: freestart collisions for SHA-1

Mozilla では SHA-1 を使った証明書の無効化を2016年7月以降に前倒しすることを検討している。

GPU ベースのシステムやクラウド・サービス等による巨大計算リソースを使った攻撃は,指摘はありつつも,あまり重視されていなかった。 しかし,今回の例に見るように,攻撃手法として現実的な脅威になりつつある。 状況によっては SHA-1 以外でもセキュリティ・リスクの見直しを迫られるかもしれない。

関連記事

関連図書

photo
暗号技術入門 第3版 秘密の国のアリス
結城 浩
SBクリエイティブ 2015-08-25
評価

自作エミュレータで学ぶx86アーキテクチャ コンピュータが動く仕組みを徹底理解! 数学ガールの秘密ノート/丸い三角関数 数学ガールの秘密ノート/微分を追いかけて 情報セキュリティ白書2015: サイバーセキュリティ新時代:あらゆる変化へ柔軟な対応を 数学ガールの秘密ノート/数列の広場

第3版出た! てか,もう Kindle 版出てるのか。紙の本買うのはやまったかなぁ。 SHA-3 や BitCoin/BlockChain など新しい知見や技術要素を大幅追加。暗号技術を使うだけならこれ1冊でとりあえず無問題。

reviewed by Spiegel on 2015-09-20 (powered by G-Tools)


  1. 他にも $1024\,\mathrm{bits}$ 以下の鍵長の RSA 公開鍵を廃止する,などの措置が盛り込まれていた。 [return]