AndRX暗号に対する差分ミートインザミドル攻撃の自動化モデル

この研究が重要な理由

スマートフォンを使ったり、オンラインで支払ったり、医療機器を接続したりするたびに、ブロック暗号と呼ばれる小さなデジタルの鍵が私たちのデータを保護しています。安全性の専門家はより安全な設計のためにこれらの鍵を破る試みを続けています。本論文は、人気のある軽量暗号ファミリに対する強力な攻撃手法を自動化する新しい方法を示しており、研究者がこれらのデジタル鍵の実際の強度を評価するのに役立ちます。

現代の解読はどう働くか

現代のブロック暗号は、秘密鍵で制御される多数の小さなステップ（ラウンド）でデータを撹乱します。暗号が真のランダム性のように振る舞うなら存在すべきでないパターンを探すことが安全性評価の基本です。代表的な手法に、入力の小さな変化が出力にどのように波及するかを追う差分解析と、暗号の両端から計算して中間で一致を探すミートインザミドル攻撃があります。各手法は単独では限界がありますが、両者を組み合わせると暗号構造をより鋭く検査できます。

二つの攻撃アイデアの融合

本研究は、差分ミートインザミドルと呼ばれるハイブリッド技術に着目しています。ここでは暗号を入力部、中間部、出力部の三つに分割します。中間部では、攻撃者はいくつかのラウンドを通じてランダムより高い頻度で現れる入力差と出力差のパターン、すなわち「差分識別器」を探索します。その周りで、攻撃者は開始側から部分的に暗号化を行い、終端側から部分的に復号を行い、鍵の中の選ばれた一部のビットだけを推測します。両方向が同じ内部状態で合致すると、推測は実際の鍵に一致する可能性が高まり、探索空間が狭まります。

手作業の技を自動化ツールに変える

このような複合攻撃を手作業で設計するのは非常に困難です。特に内部状態が64、96、128ビットといったビット指向の暗号では難易度が高くなります。著者らは制約プログラミングという方法を用いた自動化フレームワークを構築しました。これは複雑な論理条件を記述してソルバが有効な可能性を探索できるようにする手法です。まず、AND、回転、XORといった演算に基づく基本ブロックを通して差分がどのように伝播するかをAndRX設計族として符号化します。次に、各段にどの鍵ビットが影響するか、そして実際に推測しなければならないビットがいくつかをモデル化します。ソルバは暗号を入力・中間・出力部に切り分けるさまざまな方法を探索し、攻撃全体の労力を最小化する配置を選びます。

鍵空間を削る追加トリック

基本モデルに加えて、フレームワークはSIMONやSimeckのようなFeistelスタイルのAndRX暗号に特化した2つの最適化トリックを加えています。1つ目は等価サブキーの考え方で、ラウンド鍵の一部を数学的に前後にずらして、複数の異なる鍵ビットがあたかも同じように振る舞うようにするものです。これにより独立して考慮すべきビット数が減ります。2つ目は選択的鍵推測で、非線形なAND演算がその入力をどのように使うかを解析し、特定の条件下で1つの推測ビットが2つ分を代用できることを示します。著者らはさらに、完全には自動化していない2つの改善も記述しています：追加の時間を要せずに攻撃にもう1ラウンド付け加えられる並列分割と、必要な選択メッセージ数を減らすデータ削減法です。

ツールが実際の暗号に示すこと

手法を検証するため、研究者たちは自動モデルをSIMONおよびSimeckの全標準版に適用しました。これらはセンサや組み込みコントローラなど制約のある機器での利用が想定される軽量暗号の候補です。各バリアントについて、ツールは差分ミートインザミドル攻撃を見つけ、そのデータ量、時間、メモリのコストを推定します。多くの場合、これらの攻撃は従来のミートインザミドルや関連手法よりも多くのラウンドに到達し、しばしば既存のインポッシブル差分攻撃やゼロ相関攻撃を上回るラウンド数を達成します。例えば、ツールは128ビット版SIMON（鍵長256ビット）で最大51ラウンドに及ぶ攻撃を提示し、従来法の範囲を拡張しつつ全鍵探索よりは小さい労力に収めています。

将来の暗号設計への全体像

非専門家にとっての主要なメッセージは、SIMONやSimeckが実運用で「実用的に破られた」ということではなく、自動化ツールが手作業では見つけにくい微妙な弱点を探索できるほど強力になってきた、という点です。ここで紹介されたフレームワークはビットレベルで一般的に設計されており、原理的には他の暗号ファミリにも適用できます。新しいアルゴリズムが高度な複合攻撃にどう耐えるかを設計者が迅速に検証できるようにすることで、解析手法が高度化しても堅牢であり続ける暗号の構築という長期的な目標を支援します。

引用: Chakraborty, D., Sahoo, S., Nguyen, P.H. et al. An automated model for differential meet in the middle attacks on AndRX ciphers. Sci Rep 16, 14773 (2026). https://doi.org/10.1038/s41598-026-41390-w

キーワード: ブロック暗号解析, 差分ミートインザミドル, SIMON暗号, Simeck暗号, 制約プログラミング