SHAttered attack (SHA-1コリジョン発見)

暗号アルゴリズムのうちデジタル署名などの用途で利用されているハッシュ関数のひとつ、SHA-1 のコリジョン(衝突)が報告されました。

今回見つけられた攻撃手法は SHAtterd attack と名付けられました^[1]SHAttered attack https://shattered.it/ https://shattered.io/^[2]Google Security Blog, Announcing the first SHA1 collision https://security.googleblog.com/2017/02/announcing-first-sha1-collision.html。(暗号学的)ハッシュ関数は、異なるデータを異なる固定長データに圧縮することが保証されています。SHA-1 は160ビットの出力長を持つことから、2^80程度という膨大な SHA-1 計算を行わないとハッシュ後データのコリジョンが起きないように設計することで、安全かつ高速なハッシュ処理を可能にしています。

過去にもハッシュ関数のひとつである MD5 にコリジョン攻撃が公開されたことで、MD5 の利用は危険であると認識されている事例がありました。また、SHA-1 も2005年の時点で脆弱であるという論文が公開されており、その後暗号解析が進められ、2013年には2^61程度の SHA-1 計算でコリジョンが発見可能^[3]Marc Stevens, Pierre Karpman and Thomas Peyrin, “Freestart Collision for Full SHA-1” (Original Publication:EUROCRYPT2016) https://eprint.iacr.org/2015/967と報告されました(この論文の筆頭著者は SHAttered attack と同じ Marc Stevens^[4]Marc Stevens https://marc-stevens.nl/ です)。近年、クラウドの普及等で一時的かつ手軽に膨大な計算能力を有する環境が整ったことから、2018年には173,000米ドル程度でコリジョンを見つけるためのリソースを購入可能になるという報告もあり、SHA-1 のコリジョン発見は時間の問題と考えられてきました。

あれ？ これまでにも SHA-1 コリジョン見つかってたじゃん？ と思われる皆様は、昨年の Freestart 衝突攻撃と混同されているのかもしれません。SHA-1 は80サブルーチンの逐次処理(この様子を80段と呼びます)で構成されていますが、それよりも(例えば73段など)段数を少なくした「SHA-1 の亜種アルゴリズム」を考えて、その亜種を攻撃対象として暗号解析を行うことがあります。一方で、フルラウンドである80段の構成はそのままにして、SHA-1 特有の「初期値を変更してもよい」という制限を緩和した攻撃も存在し、これらを Freestart 衝突攻撃と呼んでいます。2016年に SHA-1 フルラウンドの Freestart 衝突攻撃が報告されていますが、特殊な環境下でのもので、実際の SHA-1 利用への直接的な影響はありませんでした。

今回のレポートでは SHA-1 コリジョン発見に至る理論的背景や実装方法が報告されていますが、意味のない2つのデータに対するコリジョンではなく、2つの PDF ファイルのコリジョン、つまり意味のあるデータに対する SHA-1 コリジョンの事例が含まれています。意味のない BLOB データに対するコリジョンではなく、意味あるデータに対する改ざん攻撃が露呈したことで大きなインパクトがある報告となりました。

一方で、この攻撃を成功させる際には2^63 SHA-1 処理程度の計算量が必要であると見積もられており、これは現時点で6,500個の CPU を1年間充当するほどのものです。これを実現可能な範囲であると見るかどうかは判断が分かれますが、これだけコストをかけてコリジョンを計算するに値する攻撃対象は限られてきます。まず思いつくのは SSL/TLS で広く利用されている X.509 サーバ証明書のデジタル署名に SHA-1 が利用されているケースですが、認証機関(サーバ証明書発行機関)も主要ブラウザも SHA-2 に移行がほぼ終わった段階であることから、大きな混乱につながることはないと考えられます。一方で、意味のない BLOB データのコリジョンは2^60台で計算可能であることが知られていたにもかかわらず10年弱放置されていたことを鑑みると、大きなリソースを持っている組織ではもっと以前から証明書改ざんができた可能性も捨てきれません。この問題については Public Key Pinning 等、ブラウザ側でそれを防ぐ技術が広まったことから、一般ユーザにおいては大きな脅威にはならないかもしれません。

サーバ証明書以外にも、存在保証やタイムスタンプ、署名者保証などのために SHA-1 が広く使われていた時期に作成された文書の検証に影響することが考えられます。SHAttered attack の原論文^[5]Marc Stevens, Elie Bursztein, Pierre Karpman, Ange Albertini, Yarik Markov, “The first collision for full SHA-1” https://shattered.it/static/shattered.pdfでは、PDF 文書内の JPEG データ^[6]https://shattered.io/static/pdf_format.pngのいわゆるダミー部分に用いたテクニックが紹介されています。2008年末に公開された MD5 コリジョンを用いた中間 CA 証明書偽造攻撃^[7]MD5 considered harmful today https://www.win.tue.nl/hashclash/rogue-ca/でも、レンダリング時に無視される、もしくは影響のないダミー部分を利用することで探索空間を確保していました。そのため PDF 以外の署名フォーマットにどの程度影響が出るか把握できない状況ですが、少なくとも SHA-1 を利用していた時代の PDF 署名が政府機関から公開されたままであることが確認されています。この問題に関しては PAdES^[8]ETSI TS 102 778-1, Part 1: PAdES Overview – a framework document for PAdES http://www.etsi.org/deliver/etsi_ts/102700_102799/10277801/01.01.01_60/ts_10277801v010101p.pdf に代表される長期保存署名技術で延命することができますが、検証する側の環境は広く整っていない点が課題です。

以前より SHA-1 は既に安全ではないと認識されており、政府システム等においても移行計画が着実に進められています。また、最新の CRYPTREC 暗号リスト^[9]CRYPTREC暗号リスト(電子政府推奨暗号リスト) https://www.cryptrec.go.jp/list.htmlでも戦力外通知にあたる運用監視暗号にカテゴライズされ、移行を推奨しています。今回の報告は暗号業界においては非常に大きなインパクトがありましたが、想定される脅威に対する事前対策・事前準備が進められていたため、実社会への影響は限定的であると考えられます。