この記事は Marc Stevens（CWI Amsterdam）、Elie Bursztein（Google）、Pierre Karpman（CWI Amsterdam）、Ange Albertini（Google）、Yarik Markov（Google）、Alex Petit Bianco（Google）、Clement Baisse（Google）による Google Security Blog の記事 "Announcing the first SHA1 collision" を元に翻訳・加筆したものです。詳しくは元記事をご覧ください。

SHA-1 などの暗号化ハッシュ関数は、暗号を使用するデベロッパーの万能ツールです。ハッシュは、ブラウザのセキュリティ、コード レポジトリの管理、ストレージの重複ファイルの検出などに活用されています。ハッシュ関数は、巨大なデータを圧縮して小さなメッセージ ダイジェストを生成します。計算処理によって 2 つのメッセージから同じダイジェストが生成できてしまうことは、幅広く普及する暗号的条件としては不適切です。しかし、この条件は、ハッシュ関数の数学的根拠に対する疑問や計算能力の進歩によって、時間とともに満たされなくなる可能性があります。

現在、SHA-1 が初めて導入されてから 20 年以上が経過しています。本日（*原文公開当時）は、衝突を発生させる現実的なテクニックが初めて発見されたことをお知らせします。この発見は、アムステルダムの CWI Institute と Google の 2 年間の共同研究による成果です。以下に、衝突を発生させた方法について簡単に記載します。また、攻撃の証拠として、内容が異なるにもかかわらず同じ SHA-1 ハッシュを持つ 2 つの PDF を公開しています。

今回の発見は、技術コミュニティにとって SHA-1 の利用を終わらせることの必要性を強調するものです。Google は、何年にもわたって SHA-1 の利用中止（特に TLS 証明書に署名する際の利用の中止）を呼びかけてきました。2014 年初めには、Chrome チームが SHA-1 の利用を段階的に廃止することを発表しました。今回公開した現実的な SHA-1 への攻撃方法をもって、このプロトコルがもはや安全ではないことを強く認識していただけることを願っています。

業界は、SHA-256 などの安全な代替技術への移行を大至急行う必要に迫られています。今回の SHA-1 への攻撃方法の発見によって、そのことを認識していただけることを期待します。

暗号化ハッシュの衝突とは
衝突の発生とは、上記のように、異なる 2 つのデータ（ドキュメント、バイナリ、ウェブサイトの証明書など）をハッシュ化した際に、同じダイジェストが生成されることです。安全なハッシュ関数では、実際に衝突が起きることはあってはなりません。しかし、SHA-1 のようにハッシュ アルゴリズムに欠陥がある場合、豊富な資金を持つ攻撃者は衝突を故意に発生させることができます。攻撃者はその衝突を利用して、ハッシュを信頼するシステムを欺き、本来のファイルの代わりに悪意のあるファイルを侵入させることができます。たとえば、まったく内容が異なる 2 つの保険契約書などです。

SHA-1 衝突の発見

 2013 年、Marc Stevens は、SHA-1 衝突を起こす理論的な手法をまとめた論文を発表しました。今回の取り組みは、特別な PDF プレフィックスを作成するところから始まりました。これを使うと、見た目が異なるにもかかわらず、ハッシュ化によって同じ SHA-1 ダイジェストが生成される 2 つのドキュメントを作成できます。この攻撃理論を実現するにあたっては、いくつかの新たな難題を克服する必要がありました。次に、Google の技術関連の専門家やクラウド インフラストラクチャを活用して、衝突の計算を行いました。この計算は、今まで行われたものの中でも最大規模の計算の 1 つです。

この計算がどのくらいの規模だったかは、次の数字から理解していただけるのではないかと思います。

  • 合計 900 京（9,223,372,036,854,775,808）回以上の SHA1 計算
  • 攻撃の第 1 フェーズを完了するために、6,500 年分の CPU 計算
  • 第 2 フェーズを完了するために、110 年分の GPU 計算

この数はとても巨大なもののように見えますが、SHA-1 shattered 攻撃は、現実的ではない総当たり攻撃よりも 10 万倍高速です。

SHA-1 衝突攻撃のリスク緩和

今後は、セキュリティ関係者にとって SHA-256 や SHA-3 などの安全な暗号化ハッシュに移行することが急務になります。Google の脆弱性公開ポリシーに従い、コードは 90 日後に公開されます。このコードは、ある前提条件のもとで 2 つの異なるイメージが与えられた場合、ハッシュ化によって同じ SHA-1 チェックサムが生成される 2 つの PDF を作成するものです。実際にこの攻撃手法が利用されることがないよう、Gmail や GSuite ユーザー向けに今回の PDF 衝突テクニックを検知するための保護機構を追加しました。さらに、無償の検出システムも公開しています。

SHA-1 攻撃や今回の研究の技術的な要点に関する詳しい情報は、こちらからご覧ください。

チームについて

本成果は、CWI Institute と Google のセキュリティ、プライバシーおよび不正利用対策研究グループの長期間にわたる協力に基づくものです。

Marc Stevens と Elie Bursztein は、Google のインフラストラクチャを使い、 Marc が考案した SHA-1 に対する暗号解読攻撃を実際に行うために、共同で作業を行いました。Ange Albertini は PDF 攻撃を考案し、Pierre Karpman は暗号解読と GPU の実装を行い、Yarik Markov は分散 GPU コードを担当し、Alex Petit Bianco は Google ユーザーを保護する衝突検知ツールの実装を行いました。Clement Baisse は計算の信頼性確認を担当しました。




Posted by Eiji Kitamura - Developer Relations Team