時間/メモリ/データのトレードオフ攻撃

時間/メモリ/データ トレードオフ攻撃は、暗号攻撃の一種で、攻撃者は空間と時間のトレードオフに似た状況を実現しようとしますが、攻撃者が利用できるデータの量を表すデータという追加のパラメータを使用します。攻撃者は、これらのパラメータの 1 つまたは 2 つをバランスさせるか減らして、他の 1 つまたは 2 つを優先します。このタイプの攻撃は非常に難しいため、使用されている暗号や暗号化方式のほとんどは、この攻撃に対抗するようには設計されていません。^{[引用が必要]}

対称暗号システムに対するトレードオフ攻撃は、1980年にマーティン・ヘルマンが時間とメモリのトレードオフ法を提案したことに遡ります。この方法では、可能なキーの時間とメモリはトレードオフ曲線で関連付けられます。^{[1]その後、1995年にバベッジとゴリックは、}ストリーム暗号に対する別のトレードオフ攻撃を考案しました。この攻撃では、新しい境界が に対して となり、出力データは暗号解読者がリアルタイムで利用できるようになっています。^{[2] [3]}${\displaystyle N}$${\displaystyle T}$${\displaystyle M}$${\displaystyle T{M^{2}}={N^{2}}}$${\displaystyle 1\leq T\leq N}$${\displaystyle TM=N}$${\displaystyle 1\leq T\leq D}$${\displaystyle D}$

この攻撃は、一般的な暗号解読の時間とメモリのトレードオフ攻撃の特別なバージョンであり、次の 2 つの主なフェーズがあります。

1. 前処理:
   このフェーズでは、攻撃者は暗号システムの構造を調査し、その結果を大きなテーブルに記録することができます。これには長い時間がかかる場合があります。
2. リアルタイム:このフェーズでは、暗号解読者は特定の未知のキーから取得した実際のデータを受け取ります。次に、このデータを 前処理
   フェーズで事前に計算されたテーブルと併用して、できるだけ短時間で特定のキーを見つけようとします。

時間/メモリ/データのトレードオフ攻撃には、次のパラメータがあります。

${\displaystyle N}$検索空間のサイズ

${\displaystyle P}$前処理段階に必要な時間

${\displaystyle T}$リアルタイムフェーズに必要な時間

${\displaystyle M}$攻撃者が利用できるメモリの量

${\displaystyle D}$攻撃者が利用できるリアルタイムデータの量

ブロック暗号の場合、可能なキーの総数を とし、可能な平文と暗号文の数を と仮定します。また、与えられたデータは、特定の平文の対応する部分の単一の暗号文ブロックであるとします。キーから暗号文へのマッピングを点空間上のランダム置換関数と見なし、この関数が可逆である場合、この関数の逆関数を見つける必要があります。この関数を逆関数にする Hellman の手法: ${\displaystyle N}$${\displaystyle N}$${\displaystyle x}$${\displaystyle y}$${\displaystyle f}$${\displaystyle N}$${\displaystyle f}$${\displaystyle {f}^{-1}(y)=x}$

前処理段階中

ランダムな開始点に対して関数を回数反復して構築される長方形行列で点空間をカバーしてみます。開始点は行列の左端の列で、終了点は右端の列です。次に、開始点と終了点のペアを終了点の値の昇順で格納します。${\displaystyle N}$${\displaystyle m\times t}$${\displaystyle f}$${\displaystyle m}$${\displaystyle N}$${\displaystyle t}$

これで、1 つの行列だけでは空間全体をカバーできなくなります。しかし、行列に行を追加すると、回復された点が複数回含まれる巨大な行列になります。そこで、行列にまったく異なる点が含まれる場合の臨界値を見つけます。開始点から終了点までの最初のパスがすべて点で互いに素であり、それらの前のパスの 1 つと少なくとも 1 つの共通点を持つ次のパスには、点がちょうど含まれるとします。これら 2 つのセットのと の点は、 であることが確実な場合、誕生日のパラドックスによって互いに素になります。これは、行列停止規則を適用することで実現します。${\displaystyle N}$${\displaystyle m}$${\displaystyle m}$${\displaystyle m}$${\displaystyle mt}$${\displaystyle t}$${\displaystyle mt}$${\displaystyle t}$${\displaystyle t\cdot mt\leq N}$${\displaystyle m{t}^{2}=N}$

それでも、を持つ行列は空間全体の一部をカバーします。空間全体をカバーする を生成するには、次のように定義される の変形を使用します。および は、^[1]のビットの並べ替えなどの操作によって簡単に実現できます(詳細については元の論文を参照してください)。 また、合計の前処理時間は であることがわかります。 また、開始点と終了点のペアのみを保存すればよく、のペアの行列がそれぞれ存在するため、${\displaystyle m\times t}$${\displaystyle m{t}^{2}=N}$${\displaystyle mt/N=1/t}$${\displaystyle t}$${\displaystyle f}$${\displaystyle {f}_{i}(x)={h}_{i}(f(x))}$${\displaystyle {h}_{i}}$${\displaystyle f(x)}$ ${\displaystyle P\approx N}$${\displaystyle M=mt}$${\displaystyle t}$${\displaystyle m}$

リアルタイムフェーズ中

を見つけるために必要な計算の合計はです。これは、1 つの行列でカバーされる可能性があり、各試行で何らかの の評価が必要になるため、反転を試行する必要があるためです。最適なトレードオフ曲線は、行列停止規則を使用して取得され、の選択が得られます。 およびは、各リソースのコストに依存します。${\displaystyle f^{-1}(y)}$${\displaystyle T=t^{2}}$${\displaystyle t}$${\displaystyle t}$${\displaystyle f_{i}}$${\displaystyle m{t}^{2}=N}$${\displaystyle T{M^{2}}={N^{2}},P=N,D=1}$${\displaystyle T}$${\displaystyle M}$

Hellman によれば、ブロック暗号が、その鍵から暗号文へのマッピングが点空間上のランダムな順列関数であるという特性を持ち、これが可逆である場合、トレードオフ関係ははるかに改善されます。 ${\displaystyle f}$${\displaystyle N}$${\displaystyle f}$${\displaystyle TM=N}$

ストリーム暗号の場合、はビット ジェネレーターの内部状態の数によって指定されます。これは、キーの数とは異なる可能性があります。 は、ジェネレーターから生成された最初の疑似ランダム ビットの数です。最後に、攻撃者の目標は、ビット ジェネレーターの実際の内部状態の 1 つを見つけて、この時点からジェネレーターを実行してキーの残りの部分を生成できるようにすることです。状態から出力プレフィックスへのマッピングによって、ビット ジェネレーターの可能な内部状態のそれぞれを、その状態からジェネレーターを実行して取得した最初のビットで構成される対応する文字列に関連付けます。この前のマッピングは、ポイントの共通空間上のランダム関数と見なされます。この関数を反転するために、攻撃者は次のことを確立します。 ${\displaystyle N}$${\displaystyle D}$${\displaystyle N}$${\displaystyle log(N)}$${\displaystyle f(x)=y}$${\displaystyle x}$${\displaystyle y}$${\displaystyle N}$

1. 前処理フェーズでは、ランダムな状態を選択し、対応する出力プレフィックスを計算します。${\displaystyle M}$${\displaystyle {x}_{i}}$${\displaystyle {y}_{i}}$
2. 大きなテーブルにペアを昇順で保存します。${\displaystyle ({x}_{i},{y}_{i})}$${\displaystyle {y}_{i}}$
3. リアルタイムフェーズでは、ビットが生成されました。それらから、長さの連続するビットのすべての可能な組み合わせを計算します。${\displaystyle D+log(N)-1}$${\displaystyle D}$${\displaystyle {y}_{1},{y}_{2},...,{y}_{D},}$${\displaystyle log(N)}$
4. 生成されたテーブル内でそれぞれを検索します。これには長い時間がかかります。${\displaystyle {y}_{i}}$
5. ヒットした場合、これはビット ジェネレーターの内部状態に対応し、そこからジェネレーターを実行してキーの残りの部分を取得できます。${\displaystyle {y}_{i}}$${\displaystyle {x}_{i}}$
6. 誕生日のパラドックスにより、点を含む空間の 2 つの部分集合は、それらのサイズの積が より大きい場合、交差を持つことが保証されます。${\displaystyle N}$${\displaystyle N}$

バースデー攻撃からのこの結果は、攻撃時間と前処理時間を伴う条件 を与えますが、これはトレードオフ曲線 上の特定の点にすぎません。リアルタイムで利用可能なデータの一部を無視し、からに縮小できれば、この関係を一般化することができ、一般的なトレードオフ曲線は最終的におよび を伴うようになります。 ${\displaystyle DM=N}$${\displaystyle T=D}$${\displaystyle P=M}$${\displaystyle TM=N}$${\displaystyle T}$${\displaystyle T=D}$${\displaystyle 1}$${\displaystyle TM=N}$${\displaystyle 1\leq T\leq D}$${\displaystyle P=M}$

2000 年に導入されたこの斬新なアイデアは、Hellman 攻撃と Babbage-and-Golic のトレードオフ攻撃を組み合わせて、ストリーム暗号の暗号解析に対してより優れた境界を持つ新しいトレードオフ曲線を実現するというものです。^[4] Hellman のブロック暗号手法は、内部状態から出力プレフィックスへのマッピングである関数 の複数のバリエーションから取得した行列を介して点空間をカバーするという同じアイデアを使用することで、ストリーム暗号に適用できます。ストリーム暗号に対するこのトレードオフ攻撃は、指定された出力プレフィックスのいずれかが をカバーする行列のいずれかに見つかった場合に成功することを思い出してください。これにより、から までの行列によってカバーされる点の数が から までの点に削減されます。これは、から までの行列の数を可能な限り大きく保ちながら削減することによって行われます (ただし、これには少なくとも 1 つのテーブルが必要です)。この新しい攻撃では、 になります。これは、までの行列の数を に削減し、前処理時間 も同じにしたためです。攻撃に必要なリアルタイムは、行列の数、各反復の長さ、および攻撃時に利用可能なデータ ポイントの数の積です。 ${\displaystyle N}$${\displaystyle f_{i}}$${\displaystyle f}$${\displaystyle D}$${\displaystyle N}$${\displaystyle N}$${\displaystyle N/D}$${\displaystyle t}$${\displaystyle t/D}$${\displaystyle m}$${\displaystyle t\geq D}$${\displaystyle M=mt/D}$${\displaystyle t/D}$${\displaystyle P=N/D}$${\displaystyle T=(t/D)\cdot t\cdot D=t^{2}}$

最終的に、行列停止規則を再度使用して、 のトレードオフ曲線を取得します( のため) 。 ${\displaystyle TM^{2}D^{2}=t^{2}\cdot (m^{2}t^{2}/D^{2})\cdot D^{2}=m^{2}t^{4}=N^{2}}$${\displaystyle D^{2}\leq T\leq N}$${\displaystyle t\geq D}$

Biryukov、Shamir、およびWagnerによって発明されたこの攻撃は、一部のストリーム暗号の特定の機能、つまりビットジェネレーターが次の出力ビットを生成する前に内部状態がほとんど変化しないという機能に依存しています。^[5]したがって、小さな値に対してゼロビットを 生成する特別な状態を低コストで列挙できます。しかし、多数の出力ビットに特定の値を強制すると、この列挙プロセスは非常にコストがかかり困難になります。ここで、ストリーム暗号のサンプリング耐性を、そのような列挙を可能にする最大値と定義できます。 ${\displaystyle k}$${\displaystyle k}$${\displaystyle R=2^{-k}}$${\displaystyle k}$

ストリーム暗号が状態 であり、各状態がビットのフルネームと、出力シーケンス ビットの最初のビットである対応する出力名を持つとします。このストリーム暗号にサンプリング耐性 がある場合、効率的な列挙はビットの短縮名を使用してジェネレータの特殊状態を定義できます。短縮名を持つ各特殊状態には、最初の先頭ビットを削除した後の特殊状態の出力シーケンスである ビットの対応する短縮出力名があります。これで、縮小されたポイント空間上の新しいマッピングを定義でき、このマッピングは元のマッピングと同等です。 とすると、攻撃者が利用できるリアルタイム データには、それらの特殊状態の出力が少なくとも 1 つ含まれていることが保証されます。それ以外の場合は、特殊状態の定義を緩和して、より多くのポイントを含めます。 を に置き換え、 Shamir と Biryukov による新しい時間/メモリ/データ トレードオフ攻撃でとすると、を持つ同じトレードオフ曲線が得られます。これは実際には改善であり、は まで小さくなる可能性があるため、の下限を緩和でき、攻撃を高速化できることを意味します。この手法では、特別なポイントのみにアクセスするため、から までの高コストのディスク アクセス操作の回数が削減され、高コストのディスク操作の回数が削減されるため攻撃が高速化されます。 ${\displaystyle N=2^{n}}$${\displaystyle n}$${\displaystyle n}$${\displaystyle R=2^{-k}}$${\displaystyle n-k}$${\displaystyle n-k}$ ${\displaystyle n-k}$${\displaystyle k}$${\displaystyle NR=2^{n-k}}$${\displaystyle DR\geq 1}$${\displaystyle D}$${\displaystyle DR}$${\displaystyle N}$${\displaystyle NR}$${\displaystyle TM^{2}D^{2}=N^{2}}$${\displaystyle (DR)^{2}\leq T\leq NR}$${\displaystyle T}$${\displaystyle (DR)^{2}}$${\displaystyle 1}$${\displaystyle t}$${\displaystyle tR}$${\displaystyle DR}$