補間攻撃

暗号学において、補間攻撃はブロック暗号に対する暗号解読攻撃の一種です。

ブロック暗号に対する2 つの攻撃、差分解読法と線形解読法が発表された後、差分攻撃と線形攻撃に対して安全であることが証明されたいくつかの新しいブロック暗号が導入されました。これらの中には、 KN 暗号やSHARK暗号などの反復ブロック暗号もありました。しかし、トーマス・ヤコブセンとラース・クヌーセンは 1990 年代後半に、補間攻撃と呼ばれる新しい攻撃を導入することで、これらの暗号は簡単に破られることを示しました。

この攻撃では、代数関数を使用してS ボックスを表します。これは単純な2 次関数、またはガロア体上の多項式または有理関数です。その係数は、既知の平文をデータ ポイントとして使用して、標準的なラグランジュ補間手法で決定できます。または、選択された平文を使用して方程式を簡略化し、攻撃を最適化することもできます。

最も単純なバージョンでは、補間攻撃は暗号文を平文の多項式として表現します。多項式の未知の係数の数が比較的少ない場合、平文/暗号文 (p/c) のペアのコレクションを使用して多項式を再構築できます。多項式が再構築されると、攻撃者は秘密鍵を正確に知らなくても暗号化の表現を得ることができます。

補間攻撃は秘密鍵を復元するためにも使用できます。

例を挙げて方法を説明するのが最も簡単です。

反復暗号を次のように表す。

${\displaystyle c_{i}=(c_{i-1}\oplus k_{i})^{3},}$

ここで、 は平文、はラウンドの出力、は秘密ラウンド鍵（何らかの鍵スケジュールによって秘密鍵から導出される）、ラウンド反復暗号の場合、は暗号文です。 ${\displaystyle c_{0}}$${\displaystyle c_{i}}$${\displaystyle i^{th}}$${\displaystyle k_{i}}$${\displaystyle i^{th}}$${\displaystyle K}$${\displaystyle r}$${\displaystyle c_{r}}$

2 ラウンドの暗号を考えてみましょう。 はメッセージを表し、 は暗号文を表します。 ${\displaystyle x}$${\displaystyle c}$

すると、第1ラウンドの出力は次のようになる。

${\displaystyle c_{1}=(x+k_{1})^{3}=(x^{2}+k_{1}^{2})(x+k_{1})=x^{3}+k_{1}^{2}x+x^{2}k_{1}+k_{1}^{3},}$

そして第2ラウンドの出力は

${\displaystyle c_{2}=c=(c_{1}+k_{2})^{3}=(x^{3}+k_{1}^{2}x+x^{2}k_{1}+k_{1}^{3}+k_{2})^{3}}$

${\displaystyle =x^{9}+x^{8}k_{1}+x^{6}k_{2}+x^{4}k_{1}^{2}k_{2}+x^{3}k_{2}^{2}+x^{2}(k_{1}k_{2}^{2}+k_{1}^{4}k_{2})+x(k_{1}^{2}k_{2}^{2}+k_{1}^{8})+k_{1}^{3}k_{2}^{2}+k_{1}^{9}+k_{2}^{3},}$

暗号文を平文の多項式として表すと、

${\displaystyle p(x)=a_{1}x^{9}+a_{2}x^{8}+a_{3}x^{6}+a_{4}x^{4}+a_{5}x^{3}+a_{6}x^{2}+a_{7}x+a_{8},}$

ここで、はキーに依存する定数です。 ${\displaystyle a_{i}}$

多項式 の未知の係数の数と同じ数の平文/暗号文のペアを使用して、多項式 を構築できます。これは、たとえばラグランジュ補間によって実行できます (ラグランジュ多項式を参照)。未知の係数が決定されると、秘密鍵 を知らなくても暗号化の表現が得られます。 ${\displaystyle p(x)}$${\displaystyle p(x)}$${\displaystyle K}$

ビットのブロック暗号を考えると、平文の可能性がある、つまり異なるペアが存在することになります。に未知の係数があるとします。多項式内の未知の係数の数と同じ数のペアが必要なので、 の場合にのみ補間攻撃が存在します。 ${\displaystyle m}$${\displaystyle 2^{m}}$${\displaystyle 2^{m}}$${\displaystyle p/c}$${\displaystyle n}$${\displaystyle p(x)}$${\displaystyle p/c}$${\displaystyle n\leq 2^{m}}$

ペアを使用して多項式を構築する時間は、必要な平文を暗号化する時間に比べて短いと仮定します。には未知の係数があるとします。この場合、この攻撃の時間計算量は となり、既知の異なるペアが必要になります。 ${\displaystyle p(x)}$${\displaystyle p/c}$${\displaystyle n}$${\displaystyle p(x)}$${\displaystyle n}$${\displaystyle n}$${\displaystyle p/c}$

多くの場合、この方法の方が効率的です。やり方は次のとおりです。

ブロック長 のラウンド反復暗号が与えられた場合、のラウンド後の暗号の出力をとします。 の値を平文の多項式 として、暗号文の多項式 として表します。を経由した の式とし、 を経由した の式とします。多項式は、ラウンド まで暗号の反復式を使用して順方向に計算することで得られ、多項式は、 ラウンド からラウンド まで暗号の反復式から逆方向に計算することで得られます。 ${\displaystyle r}$${\displaystyle m}$${\displaystyle z}$${\displaystyle s}$${\displaystyle s<r}$${\displaystyle z}$${\displaystyle x}$${\displaystyle c}$${\displaystyle g(x)\in GF(2^{m})[x]}$${\displaystyle z}$${\displaystyle x}$${\displaystyle h(c)\in GF(2^{m})[c]}$${\displaystyle z}$${\displaystyle c}$${\displaystyle g(x)}$${\displaystyle s}$${\displaystyle h(c)}$${\displaystyle r}$${\displaystyle s+1}$

つまり、

${\displaystyle g(x)=h(c),}$

と の両方が係数の数が少ない多項式である場合、未知の係数について方程式を解くことができます。 ${\displaystyle g}$${\displaystyle h}$

は係数で表すことができ、は係数で表すことができると仮定します。この場合、この方程式を行列方程式として設定して解くには、既知の異なるペアが必要になります。ただし、この行列方程式は、乗算と加算まで解くことができます。したがって、一意でゼロ以外の解を確実に得るには、最高次数に対応する係数を 1 に設定し、定数項を 0 に設定します。したがって、 既知の異なるペアが必要です。したがって、この攻撃の時間計算量は で、既知の異なるペアが必要です。 ${\displaystyle g(x)}$${\displaystyle p}$${\displaystyle h(c)}$${\displaystyle q}$${\displaystyle p+q}$${\displaystyle p/c}$${\displaystyle p+q-2}$${\displaystyle p/c}$${\displaystyle p+q-2}$${\displaystyle p+q-2}$${\displaystyle p/c}$

Meet-In-The-Middle アプローチでは、係数の合計数は通常、通常の方法を使用する場合よりも少なくなります。これにより、 必要なペアの数が少なくなるため、この方法はより効率的になります。 ${\displaystyle p/c}$

補間攻撃を使用して秘密鍵を復元することもできます。 ${\displaystyle K}$

ブロック長 の ラウンド反復暗号の最後のラウンドを削除すると、暗号の出力は になります。この暗号を縮小暗号と呼びます。その考え方は、最後のラウンドの鍵 を推測し、1 ラウンドを復号して縮小暗号の出力を取得するというものです。次に、推測を検証するために、通常の方法または Meet-In-The-Middle 方法のいずれかを使用して、縮小暗号に補間攻撃を使用します。その方法は次のとおりです。 ${\displaystyle r}$${\displaystyle m}$${\displaystyle {\tilde {y}}=c_{r-1}}$${\displaystyle k_{r}}$${\displaystyle {\tilde {y}}}$

通常の方法では、簡約された暗号の出力を平文の多項式として表します。多項式を と呼びます。次に、係数で表すことができれば、既知の異なるペアを使用して多項式を構築できます。最終ラウンドの鍵の推測を検証するには、1つの追加のペアを使用して、次の式が成り立つかどうかを 確認します。${\displaystyle {\tilde {y}}}$${\displaystyle x}$${\displaystyle p(x)\in GF(2^{m})[x]}$${\displaystyle p(x)}$${\displaystyle n}$${\displaystyle n}$${\displaystyle p/c}$${\displaystyle p/c}$

${\displaystyle p(x)={\チルダ {y}}.}$

はいの場合、最後のラウンドのキーの推測は高い確率で正しいことになります。いいえの場合、キーをもう一度推測します。

Meet-In-The-Middle法では、ラウンドの出力を平文の多項式と縮小暗号の出力の多項式として表します。多項式をと と呼び、それぞれと係数で表します。次に、既知の異なるペアを使用して係数を見つけることができます。最後のラウンドの鍵の推測を検証するには、次の条件が満たされるかどうかをもう1つのペア で確認します。${\displaystyle z}$${\displaystyle s<r}$${\displaystyle x}$${\displaystyle {\tilde {y}}}$${\displaystyle g(x)}$${\displaystyle h({\チルダ {y}})}$${\displaystyle p}$${\displaystyle q}$${\displaystyle q+p-2}$${\displaystyle p/c}$${\displaystyle p/c}$

${\displaystyle g(x)=h({\tilde {y}}).}$

はいの場合、最後のラウンドのキーの推測は高い確率で正しいことになります。いいえの場合、キーをもう一度推測します。

正しい最終ラウンド キーが見つかったら、残りのラウンド キーについても同様の手順で続行できます。

長さ の秘密ラウンドキーを使用すると、異なるキーが存在します。各キーは、ランダムに選択された場合に正しい確率を持ちます。したがって、平均すると、正しいキーを見つけるまでに推測を行う必要があります。 ${\displaystyle m}$${\displaystyle 2^{m}}$${\displaystyle 1/2^{m}}$${\displaystyle 1/2\cdot 2^{m}}$

したがって、通常の方法では平均時間計算量が で、既知の異なるペアが必要となり、Meet-In-The-Middle 方法では平均時間計算量が で、既知の異なるペアが必要になります。 ${\displaystyle 2^{m-1}(n+1)}$${\displaystyle n+1}$${\displaystyle c/p}$${\displaystyle 2^{m-1}(p+q-1)}$${\displaystyle p+q-1}$${\displaystyle c/p}$

Meet-in-the-middle 攻撃は、逆関数を使用する S-box を攻撃する変形として使用できます。これは、 ビットの S-boxの場合、であるためです。 ${\displaystyle m}$${\displaystyle S:f(x)=x^{-1}=x^{2^{m}-2}}$${\displaystyle GF(2^{m})}$

ブロック暗号SHARK は、S-box を使用した SP ネットワークを使用します。この暗号は、少数のラウンドの後、差分解析および線形解析に対して耐性があります。しかし、1996 年に Thomas Jakobsen と Lars Knudsen によって補間攻撃を使用して破られました。ラウンドで並列の ビット S-box を使用するブロック サイズ ビットの SHARK バージョンを SHARK と表記します。Jakobsen と Knudsen は、約 の選択平文を使用した SHARK (64 ビット ブロック暗号) に対する補間攻撃 と、約の選択平文を使用した SHARK (128 ビット ブロック暗号)に対する補間攻撃が存在することを発見しました。 ${\displaystyle S:f(x)=x^{-1}}$${\displaystyle (n,m,r)}$${\displaystyle nm}$${\displaystyle n}$${\displaystyle m}$${\displaystyle r}$${\displaystyle (8,8,4)}$${\displaystyle 2^{21}}$${\displaystyle (8,16,7)}$${\displaystyle 2^{61}}$

また、トーマス・ヤコブセンは、リード・ソロモン符号の復号法を改良するために、マドゥ・スーダンのアルゴリズムを使用した補間攻撃の確率的バージョンを導入しました。この攻撃は、平文と暗号文の間の代数的関係が値の一部にしか当てはまらない場合でも機能します。

• Thomas Jakobsen、Lars Knudsen (1997 年 1 月)。ブロック暗号に対する補間攻撃( PDF / PostScript ) 。第 4 回高速ソフトウェア暗号化に関する国際ワークショップ(FSE '97)、LNCS 1267。ハイファ: Springer-Verlag。pp . 28–40。2007年 7 月 3 日閲覧。
• Thomas Jakobsen (1998 年 8 月 25 日)。「低次の確率的非線形関係を持つブロック暗号の暗号解析(PDF/PostScript)」。Advances in Cryptology — CRYPTO '98。カリフォルニア州サンタバーバラ: Springer-Verlag。pp. 212–222。2007年 7 月 6 日閲覧。( Google Videoでのプレゼンテーションのビデオ- Flashを使用)
• 森合志保、下山健、金子俊伸 (1999 年 3 月)。ブロック暗号の補間攻撃: SNAKE ( PDF)。FSE '99。ローマ: Springer-Verlag。pp. 275–289。doi :10.1007/3-540-48519-8_20。2022年 11 月 6 日閲覧。
• Amr M. Youssef、Guang Gong (2000 年 4 月)。ブロック暗号に対する補間攻撃について(PDF) FSE 2000。ニューヨーク市: S​​pringer-Verlag。pp. 109–120。2007年 7 月 6 日閲覧。
• 黒澤 薫、岩田 哲、Viet Duong Quang (2000 年 8 月)。ルート検索補間攻撃(PDF/PostScript) 。暗号化の特定分野に関する第 7 回国際ワークショップ(SAC 2000) の議事録。オンタリオ州ウォータールー: Springer-Verlag。pp. 303–314。2007年 7 月 6 日に閲覧。