LLMは対称暗号を破れない
LLMs won't break symmetric crypto (bfswa.blog)
要約
AnthropicがLLMを用いて発見した暗号解読攻撃は、ポスト量子署名方式やAESの限定的なバージョンに対しては意味のある成果を示しましたが、確立された対称暗号方式を破るには至りませんでした。筆者は、対称暗号が意図的に「複雑」に設計されており、LLMが新たな攻撃手法を発見する可能性は低いと論じています。LLMは、暗号解読手法の形式化や、分析が不十分な分野でのバグ発見に役立つと期待されています。
全文翻訳
LLMは対称暗号を破れない
7月28日、AnthropicはLLM「Claude Mythos」を用いて発見された新しい暗号解読攻撃を発表しました。
-
NISTの「追加デジタル署名」標準化プロジェクトの候補であるポスト量子署名方式HAWKに対する鍵回復攻撃。おもちゃ版であるHAWK-256の64ビットセキュリティは実質的に破られますが、新しい攻撃は実用的ではありません。しかし、HAWK-512の推定セキュリティレベルを目標の128ビットから最大108ビット、推測では81ビットにまで低下させる(論文のAppendix C参照)ため、HAWKのセキュリティに対する意味のあるブレークです。
-
7ラウンドAES-128に対する改善された鍵回復攻撃。完全版は10ラウンドですが、この攻撃は計算量が膨大であり、驚くことではなく、AESに対する脅威は全くありません。しかし、AESに関する新しい暗号解読結果は稀であるため、発見方法に関わらず注目に値します。むしろ、Mythosが完全版AESに対するものよりも強力な攻撃を発見できなかったというネガティブな結果の方が重要かもしれません。
AnthropicはAES攻撃の論文の中で、「LLM支援型暗号研究の方向性をさらに探求することは興味深いと考えています。特に、開発された攻撃が計算量的に実装が困難であり、言語モデルが複数のアプローチの組み合わせを通じてその正当性を示す必要があるようなケースです。特に重要だと考える方向性の1つは、暗号コミュニティで使用されている攻撃技術を形式化することです。」と述べています。
私もそれに同意します。特に最後の声明は重要です。対称暗号の解読には、より統一された記述フレームワークと抽象化が必要です。多くの論文が、本質的に他の論文と同じことを行っているにもかかわらず、場当たり的な形式化やカスタム表記、用語を使用しています。
また、LLMは暗号解読攻撃の計算量推定やセキュリティ証明におけるエラーを発見すると予想しています。今年の初め、私はLLMにEUROCRYPT 2026の論文のセキュリティ証明のバグを見つけるように依頼したところ、ほとんどの証明に問題が見つかりました(証明自体は間違っていなくても、証明の過程に誤りがあることを示していました)。
Anthropicは、AES、ChaCha、BLAKEなどのNISTコンペティションに提出されたアルゴリズム(ポスト量子方式を含む)のフルラウンドおよび削減ラウンドバージョンに対する暗号解読タスクで構成されるLLMベンチマークであるCryptanalysisBenchの作成にも協力しました。
暗号解読に詳しくない場合、LLMがAES、ChaCha、SHA-3、および現在使用されているその他の対称アルゴリズムを破ることができるのではないかと疑問に思うのは無理もありません。友人が私に尋ねたように、「MythosがBLAKE3を破るのではないかと心配していませんか?」 私は心配していません。
より広範には、LLMはいかなる確立された暗号方式も破ることはなく、Too Much Cryptoの仮説を反証することもないと確信しています。
優れた記事の中で、Matthew Greenは次のように述べています(私の注釈付き)。「私たちの対称暗号(ブロック/ストリーム暗号、ハッシュ関数、MACも含む)は非常に複雑(再び、「統一理論」はない)で堅牢です(経験的にそうであり、これについては後述)。農夫がトラクターを流砂地帯に運び出し、セメントで埋める様子を想像してください。対称暗号設計とはそういうものです。それは、適用が速く簡単(通常はラウンドの操作)である構造を意図的に考案しますが、解きほぐすのは非常に複雑で困難です(ラウンドを繰り返すにつれて)。多くの新しい知能時間(raw intelligence-hours)を追加しても、これが魔法のように改善されることはおそらくないでしょう。」
マットが言うところの複雑さと構造について、そしてこれらがLLMがSHA-3やBLAKE3に対する実用的な衝突攻撃を発見できない主な理由であることについて、詳しく説明したいと思います。
では、なぜLLMは対称暗号を破れないのでしょうか? ほぼ(完全にではないが)任意順で説明します。
-
高レベル構造が安全であること: ここで言うのは、ブロック暗号のGCMやCTRモード、ハッシュ関数のスポンジ構造のようなモード of operation です。また、ほとんど対称方式の中核をなす鍵付きまたは鍵なし置換のラウンドベース構造も含まれます(ただし、Poly1305のようにラウンドベースではないものもあります)。
-
数学的構造がないこと: 実際の数学的問題やほとんどの公開鍵方式とは異なり、対称暗号は一般的に、数理構造内のクリーンな変換として記述できません。数理構造は、還元ベースのセキュリティ証明を可能にするだけでなく、暗号解読に悪用される可能性もあります(例外は、ZK証明システムやFHEで使用されるPoseidonのような算術化指向プリミティブ、特に代数ハッシュ関数です。もう一つの例外は、RSAライクな操作に基づいたハッシュ関数であるVSHで、衝突耐性は証明されましたが、原像耐性はないことが判明し、構造の諸刃の剣を示しました)。ハッシュ関数やブロック暗号を設計する際、攻撃者がその計算を、見かけ上無意味な一連の基本操作よりも単純なものとして記述できるような構造、対称性、またはパターンを排除することが目標となります。例えば、BLAKE3は基本的にXOR、モジュラ加算、ビットローテーションの長いシーケンスです。それを説明する他の方法はありません。推論したり、高レベルの構造を考えたりする明らかな空間がありません。XORはモジュラ加算に対する線形性を破壊し、モジュラ加算はXORに対する線形性を破壊します。スポンジ構造のnビット置換をGF(2)ⁿ上の双射として考えると、GF(2)上の多変数方程式系としてのその表現は、顕著な構造を持たないと予想されます。最大次数、高密度の単項式などです。他の体上での表現についても同様であるはずです。これがマットの言う「複雑さ」の考え方です。
-
主に差分暗号解読であること: 線形暗号解読、長方形攻撃、ブーメラン攻撃、積分攻撃、キューブ攻撃、スライド攻撃、およびほとんどの暗号解読トリックは、すべて差分暗号解読の一形態です。これらは、「入力にこの差分(ある演算子、通常はXORに関して)を適用すると、[暗号のコンポーネント]の出力が理想的/期待されるケースから統計的に逸脱する」という形式の入出力パターンを利用します。例えば、SHA-1の衝突攻撃は、ある差分が例外的に高い確率を持つことを利用しましたが、不可能な差分技術は確率ゼロの差分を利用します。対称プリミティブのモードが(証明済みで)安全である場合、差分暗号解読以外にできることはほとんどありません。この領域はすでに広範囲に調査されており、LLMが全く新しいクラスの攻撃を発見する可能性は低いです。
-
差分暗号解読は(少なくとも部分的に)経験的であること: 多くのケースで、暗号解読者はそのバイアスの正確な理由を理解せずに実験を実行して統計的バイアスを発見します。2⁻¹⁰のような比較的大きなバイアスを観測した後、信頼できる測定にはサンプル数が多すぎるが、攻撃に利用できる可能性のある、より小さなバイアスの存在を推測することがあります。LLMがそのような実験を実行できないとは主張しませんが、それらを設計、実行、解釈する必要があるため、タスクはより困難になります。
-
時間と試練を経ていること: これらの設計は何千時間もの暗号解読による精査を受けており、そのほとんどは成功せず、したがって公表されていません。研究者たちは、人間の創意工夫、創造性、および膨大な計算能力を、バイアスのある統計を見つけ出し、自動分析や時には形式検証を実行するために適用してきました。そして彼らが見つけたものは何でしょうか?ほとんど予測可能な結果として、削減ラウンドバリアントは破りやすく、ラウンドが追加されるにつれてアルゴリズムの強度は劇的に増加するということです。
友人がコメントしたように、「安全でない対称暗号が存在したのは、ある種の歴史的な偶然です。」対称暗号は私たちのセキュリティシステムの中で最も強力な部分です。したがって、LLMトークンは、分析が不十分なポスト量子標準化候補を含む、他の場所のバグを見つけるために使う方がはるかに有益です。
Featured image: Peter Bruebel, The Fall of the Rebel Angels (detail)