A Novel Memory-Efficient MitM Attack on Ascon-Hash

デジタル世界において、セキュリティはしばしば強固さと効率性の間の繊細なバランスに依存しています。工場内のセンサー、スマートメーター、医療用モニターなど、インターネット・オブ・シングス（IoT）を構成する数十億もの小型でバッテリー駆動のデバイスにとって、計算能力は乏しく、メモリに至ってはさらに希少です。これらのデバイスには、データを安全に保つのに十分な堅牢性を持ちつつ、バッテリーを消耗させたり小さなチップを使い果たしたりすることのない、軽量な暗号ツールが必要です。Asconは、この課題に対する主要な解決策であり、リソースが制限された環境向けに特別に設計された暗号化およびハッシュ関数のファミリーです。Asconの安全性を確保するため、研究者たちは、そのコードを解読するための最短経路を見つけ出そうと、高度な攻撃を用いて絶えずテストを行っています。この武器の中で最も強力なツールの一つが「中間一致攻撃（meet-in-the-middle attack）」です。これは、攻撃者が最終的な結果から逆方向に、そして開始点から順方向に作業を進め、真ん中で一致することを期待する戦略です。しかし、この戦略は伝統的に、数百万もの中間ステップを保存するために膨大な量のメモリを必要としてきました。その要件により、Asconが守ろうとしているまさにそのデバイスに対して、この攻撃を実行することはしばしば非現実的なものとなっていました。

研究チームは今回、この攻撃を実行するための新しい方法を開発し、必要なメモリ量を劇的に削減することで、軽量システムにとってより現実的なテストを可能にしました。Ascon-Hash関数に焦点を当てた研究において、著者らは、計算の速度を犠牲にすることなく、以前考えられていたよりも大幅に少ないストレージスペースを使用して、システムの簡略化されたバージョンに対して攻撃を実行できることを実証しました。問題を論理的制約の複雑なパズルとして扱うことで、彼らはデータを保存する必要が生じる前に、不要なデータをフィルタリングする方法を見出したのです。彼らの研究によれば、3ラウンド版のハッシュに対しては、メモリ要件を2^24の複雑さから2^14へと削減できます。4ラウンド版では、その削減はさらに劇的で、要件を2^34から2^12へと落とし込みます。この成果は、攻撃のコストを下げるだけでなく、リソースが限られた敵に直面した際のAsconの真の安全性について、より鋭く正確な姿を提示するものです。

研究者たちはまず、自動探索ツールを用いてAsconを打破しようとするこれまでの試みが、メモリ使用量の壁に突き当たっていたことを認めることから始めました。コンピュータは暗号化の正しい経路を見つけるスピードは上がっていましたが、そのプロセスは依然として、まるで迷路を解く際に、進んだ方向をすべて別々の紙に書き留めていくかのように、膨大な中間結果をメモリに保持することを要求していました。もし迷路が十分に大きければ、出口を見つける前に紙がなくなってしまうでしょう。チームは、解決の鍵は単に経路を速く見つけることではなく、何を書き留めるかについてより賢くなることであると気づきました。彼らは「充足可能性ソルバ（satisfiability solving）」と呼ばれる手法を用いました。これは、本質的には、複雑な論理文を真にする一連の条件をコンピュータに見つけさせる方法です。これにより、彼らは暗号化プロセスにおける、順方向と逆方向の計算が潜在的に合流できる特定のポイントをマッピングすることができました。

これらの潜在的な合流ポイントをマッピングした後、研究者らはデータのクリーンアップのために一連の代数的なフィルタを適用しました。彼らは、暗号化を支配する多くの制約が、単純な線形関係と、より複雑な非線形関係に分離できることに気づきました。線形部分は単純であり、標準的な数学的手法を用いて冗長な情報を排除することで簡略化でき、事実上、コンピュータが追跡すべき可能性のリストを縮小させることができました。非線形部分はより困難でしたが、チームはそれらを三角形の形状に再配置する手法を開発し、ある変数に基づいて他の変数を解くことを可能にしました。このプロセスにより、特定の変数を明示的に計算して保存する必要がなくなり、メモリのフットプリントをさらに削減できました。

最も重要な革新は、容易に簡略化できなかった残りの複雑な制約の扱い方にありました。研究者らは、あらゆる可能な結果を保存する代わりに、これらの残りの制約を利用して「残留インデックス（residual index）」、つまり一種のデジタルタグやラベルを作成しました。順方向の経路のリストを生成する際、それぞれの特性に基づいたタグを各経路に割り当てました。決定的なのは、逆方向の経路が順方向の経路と一致するためには、それらのタグが互換性を持っていなければならないという点です。これは、コンピュータがすべての順方向の経路をメモリに保持しておく必要はなく、逆方向の経路が到達し得るタグを持つものだけを保持すればよいことを意味します。彼らがテストした特定の構成において、このフィルタリングは非常に効果的であり、必要な順方向の経路のリスト全体を、たった一つの極めて小さなデータバケットへと削減しました。

この新しいアプローチによる結果は驚くべきものでした。Ascon-Hashの3ラウンド版に適用した場合、この手法は従来の攻撃と同じ速度を維持しながら、メモリ要件を2^24から2^14へと削減しました。4ラウンド版では、その削減はさらに深刻で、以前の最良の手法と比較して、メモリの必要量を複雑さ2^34から2^12へと大幅に削減しました。研究者らは、この積極的なフィルタリングによって有効な解が誤って破棄されていないことを検証しました。彼らは、残ったデータが暗号化システムの元のルールをすべて満たしていることを確認したのです。この研究は、暗号化の構造を注意深く分析し、これらの論理的フィルタを適用することで、以前考えられていた de わずかなリソースで深いセキュリティテストを実行できることを裏付けています。この成果は、リソース制限のある環境におけるAsconのセキュリティ・マージンが、より高い精度で評価されていることを示唆しており、私たちの接続された世界を守る暗号規格が、見た目通りに堅牢であることを保証しています。