衝突の発生とは、上記のように、異なる 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 のセキュリティ、プライバシーおよび不正利用対策研究グループの長期間にわたる協力に基づくものです。
Posted by
Eiji Kitamura - Developer Relations Team
