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

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

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

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

Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD : 発端となった論文。この中で SHA-0 も攻略可能であることが示されている

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

Hash 値の衝突問題

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

任意のデータ列を一定の長さのデータ列（hash 値）に「要約」する
Hash 値から元のデータ列を推測できない
ひとつの 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年問題」である¹。

ただ，現状では（特に 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
$\lt 112$	Processing	Legacy use
$112$	Applying	Acceptable	Disallowed
$112$	Processing	Acceptable	Legacy use
$128$	Applying/Processing	Acceptable	Acceptable
$192$		Acceptable	Acceptable
$256$		Acceptable	Acceptable

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.

via The Shappening: freestart collisions for SHA-1

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

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

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

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

Hash 値の衝突問題

2010年問題

SHA-1 Freestart Collision

関連記事

関連図書

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

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

Hash 値の衝突問題

2010年問題

SHA-1 Freestart Collision

関連記事

関連図書

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