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 Other
Applications Requiring Collision
Resistance
HMAC, KMAC,
Key Derivation Functions,
Random Bit Generation
$\le 8$0 SHA-1  
$112$ SHA-224, SHA-512/224, SHA3-224  
$128$ SHA-256, SHA-512/256, SHA3-256 SHA-1, KMAC128
$192$ SHA-384, SHA3-384 SHA-224, SHA-512/224, SHA3-224
$\ge 256$ SHA-512, SHA3-512 SHA-256, SHA-512/256, SHA-384, SHA-512, SHA3-256, SHA3-384, SHA3-512, KMAC256
Maximum security strengths for hash and hash-based functions (via SP 800-57 Part 1 Revision 5 5.6.1.2)
Security Strength Through
2030
2031 and
Beyond
$\lt 112$Applying Disallowed
Processing Legacy use
$112$ Applying AcceptableDisallowed
Processing Legacy use
$128$ Applying/ProcessingAcceptableAcceptable
$192$ AcceptableAcceptable
$256$ AcceptableAcceptable
Security-strength time frames (via SP 800-57 Part 1 Revision 5 5.6.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.

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

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

関連記事

関連図書

photo
暗号技術入門 第3版 秘密の国のアリス
結城 浩 (著)
SBクリエイティブ 2015-08-25 (Release 2015-09-17)
Kindle版
B015643CPE (ASIN)
評価     

SHA-3 や Bitcoin/Blockchain など新しい知見や技術要素を大幅追加。暗号技術を使うだけならこれ1冊でとりあえず無問題。

reviewed by Spiegel on 2015-09-20 (powered by PA-APIv5)


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