新しい衝突攻撃が容赦なく SHA1 アルゴリズムを攻撃します。 SHA256を使用しているBTCは震えているのでしょうか?

3年前、研究者らがSHA1に対する世界初の衝突攻撃に成功した後、GoogleはSHA1暗号ハッシュアルゴリズムが正式に廃止されたと宣言した。火曜日には、別の研究グループが、これまでよりはるかに強力な新たな攻撃方法を発表し、すでに一度消滅したSHA1の死骸を容赦なく打ちのめした。

新しい衝突手法により、攻撃者はより多くの選択肢と柔軟性を得ることができ、PGP暗号化キーの作成が可能になった。また、研究者らが火曜日に発表したデータによると、攻撃にかかるコストはわずか4万5000ドルだった。対照的に、2017年に公開された攻撃では、特定の所定の文書プレフィックスを偽造することはできず、当時の攻撃コストは攻撃者の実行速度に応じて11万ドルから56万ドルの範囲と推定されました。

（写真提供：ジョン・アドラー）

新しい攻撃は大幅に強力になり、効果は約 10 倍になります。

Google は SHA1 が廃止されたと発表したのに、なぜ人々はまだこのハッシュ アルゴリズムを使っているのか、と思うかもしれません。

実際、それは今でも当てはまります。 SHA1 の使用量は過去 5 年間で減少していますが、完全に排除されるまでにはまだまだ時間がかかります。

現時点では、SHA1 は、GnuPG のレガシー 1.4 ブランチで PGP キーを検証するためのデフォルトのハッシュ関数のままです (GnuPG は、電子メールやファイルの暗号化に使用される PGP アプリケーションのオープン ソースの後継です)。

広く使用されている管理ソフトウェア システムである Git は、データの整合性を確保するために依然として SHA1 に依存しています。 HTTPS 暗号化に依存する多くの非 Web アプリケーションは、引き続き SHA1 証明書を受け入れます。

今週ニューヨークで開催された暗号化セミナーで、研究者らが、SHA1 がほとんど使用されなかったり、下位互換性のためだけに使用されたりしても、ユーザーは攻撃の脅威にさらされることになる、と警告し、SHA1 ハッシュ アルゴリズムはできるだけ早く完全に廃止すべきだと強調したのも不思議ではありません。

ハッシュ関数とは何ですか?

簡単に言えば、ハッシュはメッセージ、ファイル、またはその他の種類のデジタル入力の暗号化された指紋であり、従来の指紋と同様に一意である必要があります。ハッシュはメッセージ ダイジェストとも呼ばれ、暗号化キー、電子メール、その他の種類のメッセージが特定の人物または組織に属していることを確認し、攻撃者が偽造入力を作成することを防ぐ上で重要な役割を果たします。これらのデジタル指紋は、メッセージがハッシュ アルゴリズムまたは関数に入力されたときに生成される、固定された数字と文字のシーケンスの形式で提供されます。

ハッシュ アルゴリズムの全体的なセキュリティは、同じフィンガープリントを生成する 2 つ以上の異なる入力を見つけられるかどうかにかかっています。ビット長 n の関数では、ブルートフォース攻撃者が衝突を見つける前に 2^(n/2) の入力をテストする必要があります (誕生日のパラドックスとして知られる数学的概念により、必要な推測回数が大幅に削減されます)。十分なビット長と衝突耐性を備えたハッシュ関数は、衝突を発生させるために攻撃者が実行不可能な時間と計算リソースを投資する必要があるため、安全です。 2^(n/2) 回未満の試行で衝突が見つかった場合、ハッシュ関数は壊れていると見なされます。

128 ビットの MD5 ハッシュ関数は、解読された初期の広く使用されていたハッシュ関数です。研究者らは 1996 年にはすでに MD5 に衝突の危険性を生じさせる欠陥があると警告していたが、MD5 ハッシュ関数は 20 年以上にわたってソフトウェアおよび Web 認証の重要な部分であり続けた。

その後、2008 年に研究者は MD5 衝突を利用して、任意に選択したネットワーク用の HTTPS 証明書を作成しました。このデモンストレーションにより、ブラウザが信頼する証明機関は最終的に MD5 ハッシュ関数を放棄するようになりましたが、このアルゴリズムは今でも他の目的で広く使用されています。

SHA1 は MD5 と驚くほど類似した経路をたどることが示されました。 MD5 の廃止後、2004 年に Wang Xiaoyun 教授らによって SHA1 に衝突欠陥があることが証明されました。しかし、衝突耐性が優れていることと、新しいアルゴリズムへの切り替えが難しいことから、SHA1 は 2015 年以降も広く使用されています。

SHA1が初めて衝突攻撃を受けた

2017 年、研究者らは SHA1 に対する世界初の衝突攻撃を実証しました。これは、異なるコンテンツを表示しているにもかかわらず、同じ SHA1 ハッシュを持つ 2 つの PDF ファイルの形式で提供されます。この攻撃を仕掛けた研究者らによると、当時の暗号学者らが古典的な衝突攻撃と呼んでいたこの攻撃をアマゾンのクラウドコンピューティング・プラットフォームで実行するのにかかった費用はわずか11万ドルだったという。これは、同一プレフィックス衝突攻撃とも呼ばれ、2 つの入力が同じ所定のプレフィックスまたは先頭を持ち、その後に異なるデータが続く場合に発生します。 2 つの入力が明らかに異なっていても、ファイルに追加のデータが添付されている場合は、同じ値にハッシュされる可能性があります。言い換えると、ハッシュ関数 H の場合、2 つの異なるメッセージ M1 と M2 は同じハッシュ出力、つまり H(M1) = H(M2) になります。

同一プレフィックス衝突攻撃は非常に強力で、ハッシュ関数のセキュリティに致命的となる可能性がありますが、攻撃者に対する威力も限られています。より強力な衝突の形態は選択プレフィックス攻撃と呼ばれ、2008 年に HTTPS 証明書システムに対する MD5 攻撃、2012 年に Microsoft の更新メカニズムに対する MD5 攻撃を可能にしました。コンテンツ配信ネットワーク Cloudflare の暗号化責任者である Nick Sullivan 氏は、2015 年の記事でこの選択プレフィックス衝突攻撃について詳しく説明しました。

PGP/GnuPG 選択プレフィックス衝突攻撃シミュレーション

火曜日に発生した衝突攻撃は、SHA1 に対する最初の既知の選択プレフィックス衝突攻撃でした。その有効性を証明するために、フランスのINRIAとシンガポールの南洋理工大学の研究者Gaëtan Leurent氏とThomas Peyrin氏は、それぞれこの衝突方法を使用してPGP/GnuPGシミュレーション攻撃を実行しました。彼らは論文の中で次のように説明しています。

「プレフィックスは、異なるサイズのキーを持つ 2 つの PGP ID (1 つは RSA-8192、もう 1 つは RSA-6144) のヘッダーに対応するように選択されます。OpenPGP と JPEG 形式の特性を利用することで、2 つの公開キーを作成できます。キー A は被害者の名前、キー B は攻撃者の名前と画像です。これにより、攻撃者のキーと画像を含む ID 証明書は、被害者のキーと名前を含む ID 証明書と同じ SHA-1 ハッシュを持ちます。その結果、攻撃者は第三者 (信頼の Web または CA) にキーと画像の署名を要求し、署名をキー A に転送できます。署名は衝突により有効のままですが、攻撃者は被害者の名前を使用してキー A を制御し、第三者によって署名されています。その結果、攻撃者は被害者になりすまし、被害者の名前で任意のドキュメントに署名できます。」

研究者らは、攻撃をさらに実証する論文の中で、メッセージ A とメッセージ B の両方を提供しました。異なるユーザー ID プレフィックスが含まれているにもかかわらず、それらはすべて同じ SHA1 ハッシュ 8ac60ba76f1999a1ab70223f225aefdc78d4ddc0 にマッピングされます。

これにより、SHA1 ハッシュ アルゴリズムへの攻撃効率が約 10 倍に大幅に向上します。より正確には、GTX 970 GPU で実行した場合、新しい攻撃により、同一プレフィックス衝突攻撃のコストが 2^(64.7) から 2^(61.2) に削減され、選択プレフィックス衝突攻撃のコストが 2^(67.1) から 2^(63.4) に削減されます。

研究者らは、オンラインでレンタルした 900 個の Nvidia GTX 1060 GPU のクラスターに対して 2 か月にわたって攻撃を実行したと伝えられている。

レンタル クラスターは、Amazon Web Services やその他の競合クラウド サービスよりも経済的な選択肢であると言われています。数か月前、彼らが実行した攻撃には 74,000 ドルのコストがかかっていましたが、最適化の実装とコンピューティング コストの継続的な低下により、現在では同じ攻撃をわずか 45,000 ドルで実行でき、2025 年までには攻撃の実行コストが 10,000 ドルに下がると予想されています。そのため、2009 年以来 MD5 に対して利用可能であった選択プレフィックス攻撃は、現在では SHA1 にも適用され、時間の経過とともにコストが下がるだけであると結論付けました。

SHA1 はようやく安らかに眠れるようになりましたが、ビットコインで使用されている SHA 256 はどうなるのでしょうか?

研究者らは、最も影響を受けた以下のソフトウェア開発者に調査結果を非公開で報告しました。

1. GnuPG は、2019 年 1 月以降に作成された SHA1 ベースの ID 署名を無効にする対抗策を 11 月に実装することで対応しました。

2. PGP キーを発行する認証局 CAcert は、SHA1 をまだ使用しており、今後は SHA1 から移行する予定であることを認めました。

3. 暗号化ライブラリである OpenSSL は SHA1 証明書を引き続き受け入れており、開発者は SHA1 を無効にすることを検討していると回答しました。

SHA1 ハッシュ アルゴリズムに依存するアプリケーションやプロトコルが依然として多数存在するため、研究者は影響を受けるすべての開発者に連絡を取ることができません。攻撃が悪用されるのを防ぐため、衝突の詳細の多くを一時的に保存しました。

ジョンズ・ホプキンス大学の暗号学教授マット・グリーン氏は、この発見は印象的で、SHA1アルゴリズムがもはや安全ではないという事実を浮き彫りにしているとコメントした。彼はインタビューでこう語った。

「安全なハッシュ関数の場合、10 倍のスピードアップはそれほど大きな影響はないはずですが、崩壊に極めて近い状態になると、この効率性の向上は大きな影響を及ぼします。特に、マイニング ハードウェアが多数存在する場合はそうです。1 つの靴が落ちたら、今度は次の靴が落ちてくるのです。」

翻訳者のコメント: 現在ビットコインで使用されている SHA 256 ハッシュアルゴリズムは依然として非常に安全ですが、いつかビットコインもハッシュアルゴリズムを変更する時期が来るでしょう。その時点で、暗号通貨と開発者のコ​​ミュニティはすぐに合意に達し、ハードフォークを通じて SHA 256 をより強力なハッシュ アルゴリズムに置き換えることになります (注: ビットコインのコード管理者である Pieter Wuille 氏は、最初に最新の SHA1 衝突研究を転送しており、開発者が非常に懸念していることがわかります)。