線形暗号解析と近似テーブル

線形解読（Matsui、1993年）は、暗号において確率 p ≠ 1/2 で成立する線形近似（特定ビットのXOR）を見つける既知平文攻撃です。多数の平文と暗号文のペアを使うと、統計的な偏りから鍵のビットが明らかになります。

Sボックスの線形近似とは、選択した入力ビットの合計と選択した出力ビットの合計のXORが、確率pで0（mod 2）になることです。これは P[a·x XOR b·y = 0] = 1/2 + ε と表されます。a,bはビットマスクで、εはバイアスです（|ε| >> 0 が望ましい値です）。

LATは、各入力マスクaと出力マスクbについて、(a·x) XOR (b·S(x)) = 0 となる入力xの個数を数えます。2^{n-1}を引くとバイアスが得られます。優れたSボックスの |max_bias| = 1（確率1/2 ± 1/2^{n/2}）であり、可能な限り平坦です。

複数ラウンドにわたる独立した線形近似では、バイアスが乗算されます。ε_total = 2^{r-1} * ε_1 * ε_2 * ... * ε_r です。各ラウンドの近似によって実効バイアスは半分になります。多くのラウンドを経ると全体のバイアスは0に近づき、検出には指数関数的に多くのペアが必要になります。

rラウンド暗号を攻撃するには、r-1ラウンドにわたる線形トレイルεを見つけます。N = 1/ε^2 個の既知平文を収集します。最終ラウンド鍵バイトの各候補k'について、最終ラウンドを部分的にXOR復号し、線形近似がN/2回を超えて成立するかを確認します。正しいk'では正しいバイアスが現れます。

Matsuiは1993年、バイアス2^{-21.4}の14ラウンド線形近似を使って16ラウンドDESを攻撃しました。2^{43}個の既知平文が必要でした。第1段階で鍵の26ビットを復元し、残り30ビットを総当たり探索で求めました。これは、DES全体への総当たり攻撃より高速な初の実用的攻撃でした。

AESのSボックスにおけるLATエントリの最大値は、Sボックスあたり |ε| = 4/256 = 1/64 です。Wide Trail Strategyにより、4ラウンドの任意のトレイルでアクティブなSボックスが少なくとも25個になります。全体のバイアスは (1/64)^{25/2} ≈ 2^{-75} 以下です。2^{150}個の既知平文が必要となるため、実行不可能です。

差分解読：既知または選択した平文ペアを使い、出力差分を利用します。線形解読：既知平文を使い、統計的な線形近似を利用します。実用的な攻撃では、どちらも選択平文攻撃として実行されます。どちらも設計上の評価基準であり、Sボックスは両方に耐性を持つ必要があります（DDT最大値とLAT最大値がともに小さいこと）。

複数の線形近似を同時に使用して、データ計算量を削減します。NybergとLeanderはMatsuiの手法を拡張し、M個の近似を組み合わせることでデータ量を係数log(M)だけ削減しました。PRESENT、SIMON、その他の軽量暗号に適用されています。

ストリーム暗号に線形近似を適用し、キーストリームとLFSR出力の線形関数との相関を見つけます。この相関が0でなければ、総当たりより高速な鍵復元が可能になります。この考え方は、ストリーム暗号における非線形結合関数の設計にも影響を与えました。

積分解読（Knudsen-Wagner）では、特定のバイトが256個すべての値を取り、その他のバイトは固定された平文集合を選びます。数ラウンド後、特定の位置におけるすべての出力のXORは0になります（バランスします）。AESの構造を利用し、縮小ラウンド版のAESを効率的に破ります。

Piling-Up補題は、線形近似の組み合わせについて何を述べていますか？

線形解読は、Sボックスの偏りのある線形近似を見つけます。AESは、LATに関して最適化されたSボックスとWide Trailによってこれに耐性を持ちます。Matsuiは14ラウンドのトレイルを使い、2^43個の既知平文でDESを破りました。次は誕生日攻撃と衝突発見です。