一般的な空間と時間のトレードオフ暗号攻撃
中間者攻撃（MITM）は既知平文攻撃であり [ 1 ] 、 複数 の暗号化操作を順番に実行することに依存する暗号化方式に対する 一般的な 空間と時間のトレードオフ暗号攻撃です。MITM攻撃は、 ダブルDES が使用されない主な理由であり、 トリプルDESキー（168ビット）が2 56の 空間と2 112の 操作 で攻撃者によって ブルート フォース攻撃される可能性がある 主な理由 です[2] 。
説明 ブロック暗号のセキュリティを向上させる場合、複数のキーを使用してデータを複数回暗号化するというアイデアが考えられます。データが暗号化される回数に応じて、複数の暗号化方式のセキュリティが 2 倍、あるいは n倍になると考える人もいるかもしれません。これは、データが k ビットのキーで n 回暗号化された場合、すべての可能なキーの組み合わせを徹底的に検索する (単純なブルート フォース) には 2 n · k 回の 試行が必要になるためです 。
MITMは、暗号化または復号化の中間値を保存し、それらを使用して復号化キーをブルートフォース [ 説明が必要 ] するために必要な時間を改善することにより、複数の暗号化を使用することによるセキュリティ上の利点を弱める一般的な攻撃です。これにより、中間者攻撃(MITM)は一般的な空間と時間のトレードオフ 暗号 [3] 攻撃になります。
MITM 攻撃は、複数の関数 (またはブロック暗号) の組み合わせの範囲 (暗号文) とドメイン (平文) の両方を使用してキーを見つけようとします。最初の関数を介した順方向マッピングが最後の関数を介した逆方向マッピング (逆イメージ) と同じになり、文字通り、構成された関数の真ん中で 出会うようになります。たとえば、Double DES は 2 つの異なる 56 ビット キーを使用してデータを暗号化しますが、Double DES は 2 57 回の 暗号化と復号化の操作で解読できます 。
多次元 MITM (MD-MITM) は、上記で説明したように、複数の同時 MITM 攻撃の組み合わせを使用し、構成された関数内の複数の位置で会議が行われます。
歴史 ディフィー と ヘルマンは 1977年に、仮想的な ブロック暗号 の拡張に対する中間者攻撃を初めて提案しました。 [4]
彼らの攻撃は、 空間と時間のトレードオフを 利用して、単一の暗号化方式を破るのに必要な時間の2倍で二重暗号化方式を破りました。
2011年、Bo Zhuと Guang Gongは 多次元のmeet-in-the-middle攻撃 を調査し 、ブロック暗号 GOST 、KTANTAN、Hummingbird-2に対する新しい攻撃を提示した。 [5]
中間者間交渉 (1D-MITM) 与えられた平文 P と暗号文 C に対して、次の特性を持つ暗号化方式を攻撃したいとします。
C
=
E
N
C
k
2
(
E
N
C
k
1
(
P
)
)
P
=
D
E
C
k
1
(
D
E
C
k
2
(
C
)
)
{\displaystyle {\begin{aligned}C&={\mathit {ENC}}_{k_{2}}({\mathit {ENC}}_{k_{1}}(P))\\P&={\mathit {DEC}}_{k_{1}}({\mathit {DEC}}_{k_{2}}(C))\\\end{aligned}}}
ここで、 ENC は暗号化関数、 DEC は ENC −1 (逆マッピング) として定義される復号化関数、 k 1 と k 2 は 2 つのキーです。
この暗号化方式をブルートフォース攻撃する単純な方法は、暗号文をあらゆる可能な k 2 で復号化し、中間出力のそれぞれをあらゆる可能な k 1 で復号化して、合計 2 |k 1 | × 2 |k 2 | (または 2 |k 1 |+|k 2 | ) 回の演算を実行することです。
中間者攻撃はより効率的なアプローチを使用します。 C を k 2 で復号すると 、次の等価性が得られます。
C
=
E
N
C
k
2
(
E
N
C
k
1
(
P
)
)
D
E
C
k
2
(
C
)
=
D
E
C
k
2
(
E
N
C
k
2
[
E
N
C
k
1
(
P
)
]
)
D
E
C
k
2
(
C
)
=
E
N
C
k
1
(
P
)
{\displaystyle {\begin{aligned}C&={\mathit {ENC}}_{k_{2}}({\mathit {ENC}}_{k_{1}}(P))\\{\mathit {DEC}}_{k_{2}}(C)&={\mathit {DEC}}_{k_{2}}({\mathit {ENC}}_{k_{2}}[{\mathit {ENC}}_{k_{1}}(P)])\\{\mathit {DEC}}_{k_{2}}(C)&={\mathit {ENC}}_{k_{1}}(P)\\\end{aligned}}}
攻撃者は、 k 1 のすべての値に対して ENC k 1 ( P ) を、 k 2 のすべての可能な値に対して DEC k 2 ( C ) を計算し、合計 2 |k 1 | + 2 |k 2 | (または、 k 1 と k 2 のサイズが同じ場合は2 |k 1 |+1 ) の操作を実行できます。 ENC k 1 ( P ) 操作のいずれかの結果が DEC k 2 ( C ) 操作の結果と一致する場合、 k 1 と k 2 のペアは 正しいキーである可能性があります。この正しい可能性のあるキーは 候補キー と呼ばれます。攻撃者は、平文と暗号文の 2 番目のテスト セットを使用して候補キーをテストすることにより、どの候補キーが正しいかを判断できます。
MITM 攻撃は、データ暗号化規格 (DES) が Double DES ではなく Triple DESに置き換えられた 理由の 1 つです。攻撃者は MITM 攻撃を使用して、2 57 回の 演算と 2 56 の 空間で Double DES をブルートフォース攻撃することができ、DES よりわずかに改善されただけです。 [5] Triple DES は「3 倍の長さ」(168 ビット) のキーを使用し、2 56 の 空間と 2 112 回の演算で中間者攻撃に対しても脆弱です が、キー空間のサイズにより安全であると考えられています。 [2] [6]
1D-MITM攻撃の図解
MITMアルゴリズム 以下を計算します。
S
u
b
C
i
p
h
e
r
1
=
E
N
C
f
1
(
k
f
1
,
P
)
,
∀
k
f
1
∈
K
{\displaystyle {\mathit {SubCipher}}_{1}={\mathit {ENC}}_{f_{1}}(k_{f_{1}},P),\;\forall k_{f_{1}}\in K}
:
それぞれを対応する セットAに 保存する
S
u
b
C
i
p
h
e
r
1
{\displaystyle {\mathit {SubCipher}}_{1}}
k
f
1
{\displaystyle k_{f_{1}}}
S
u
b
C
i
p
h
e
r
1
=
D
E
C
b
1
(
k
b
1
,
C
)
,
∀
k
b
1
∈
K
{\displaystyle {\mathit {SubCipher}}_{1}={\mathit {DEC}}_{b_{1}}(k_{b_{1}},C),\;\forall k_{b_{1}}\in K}
:
そして、それぞれの新しいものを セットAと比較する
S
u
b
C
i
p
h
e
r
1
{\displaystyle {\mathit {SubCipher}}_{1}}
一致が見つかったら、 候補のキーペアをテーブル T に保持します。 T内のペアを新しい のペアでテストして 、有効性を確認します。この新しいペアでキーペアが機能しない場合は、新しい のペアで再度 MITM を実行します。
k
f
1
,
k
b
1
{\displaystyle k_{f_{1}},k_{b_{1}}}
(
P
,
C
)
{\displaystyle (P,C)}
(
P
,
C
)
{\displaystyle (P,C)}
MITMの複雑さ キーサイズが k の場合、この攻撃では、2 k +1 回の 暗号化（および復号化）と、 順方向計算の結果を 参照テーブルに格納するための O (2 k ) のメモリのみが使用されます。これは、2 2· k 回の暗号化と O (1) のスペースを必要とする単純な攻撃とは対照的です 。
多次元MITM（MD-MITM） 1D-MITMは効率的ですが、より洗練された攻撃が開発されています。 多次元中間者攻撃 （略して MD-MITM） です。これは、データが異なるキーで2つ以上の暗号化を使用して暗号化されている場合に適しています。中間者攻撃（シーケンスの1か所）ではなく、MD-MITM攻撃は、暗号内の複数の位置で前方計算と後方計算を使用して、いくつかの特定の中間状態に到達しようとします。 [5]
暗号化と復号化が前と同じように定義されているブロック暗号に対して攻撃を実行する必要があると仮定します。
C
=
E
N
C
k
n
(
E
N
C
k
n
−
1
(
.
.
.
(
E
N
C
k
1
(
P
)
)
.
.
.
)
)
{\displaystyle C={\mathit {ENC}}_{k_{n}}({\mathit {ENC}}_{k_{n-1}}(...({\mathit {ENC}}_{k_{1}}(P))...))}
P
=
D
E
C
k
1
(
D
E
C
k
2
(
.
.
.
(
D
E
C
k
n
(
C
)
)
.
.
.
)
)
{\displaystyle P={\mathit {DEC}}_{k_{1}}({\mathit {DEC}}_{k_{2}}(...({\mathit {DEC}}_{k_{n}}(C))...))}
つまり、平文Pは同じブロック暗号の繰り返しを使用して複数回暗号化される。
MD-MITM攻撃の図解 MD-MITMは、 GOSTブロック暗号 の解読に使用されており 、3D-MITMによって攻撃にかかる時間計算量が大幅に削減されることが示されています。 [5]
MD-MITMアルゴリズム 以下を計算します。
S
u
b
C
i
p
h
e
r
1
=
E
N
C
f
1
(
k
f
1
,
P
)
∀
k
f
1
∈
K
{\displaystyle {\mathit {SubCipher}}_{1}={\mathit {ENC}}_{f_{1}}(k_{f_{1}},P)\qquad \forall k_{f_{1}}\in K}
それぞれを対応するものと セットで 保存します 。
S
u
b
C
i
p
h
e
r
1
{\displaystyle {\mathit {SubCipher}}_{1}}
k
f
1
{\displaystyle k_{f_{1}}}
H
1
{\displaystyle H_{1}}
S
u
b
C
i
p
h
e
r
n
+
1
=
D
E
C
b
n
+
1
(
k
b
n
+
1
,
C
)
∀
k
b
n
+
1
∈
K
{\displaystyle {\mathit {SubCipher}}_{n+1}={\mathit {DEC}}_{b_{n+1}}(k_{b_{n+1}},C)\qquad \forall k_{b_{n+1}}\in K}
それぞれを対応するものと セットで 保存します 。
S
u
b
C
i
p
h
e
r
n
+
1
{\displaystyle {\mathit {SubCipher}}_{n+1}}
k
b
n
+
1
{\displaystyle k_{b_{n+1}}}
H
n
+
1
{\displaystyle H_{n+1}}
中間状態に関する可能性のある推測ごとに、 以下を計算します。
s
1
{\displaystyle s_{1}}
S
u
b
C
i
p
h
e
r
1
=
D
E
C
b
1
(
k
b
1
,
s
1
)
∀
k
b
1
∈
K
{\displaystyle {\mathit {SubCipher}}_{1}={\mathit {DEC}}_{b_{1}}(k_{b_{1}},s_{1})\qquad \forall k_{b_{1}}\in K}
そして、これとセット の間の各一致について 、 新しいセットに と を保存します 。
S
u
b
C
i
p
h
e
r
1
{\displaystyle {\mathit {SubCipher}}_{1}}
H
1
{\displaystyle H_{1}}
k
b
1
{\displaystyle k_{b_{1}}}
k
f
1
{\displaystyle k_{f_{1}}}
T
1
{\displaystyle T_{1}}
S
u
b
C
i
p
h
e
r
2
=
E
N
C
f
2
(
k
f
2
,
s
1
)
∀
k
f
2
∈
K
{\displaystyle {\mathit {SubCipher}}_{2}={\mathit {ENC}}_{f_{2}}(k_{f_{2}},s_{1})\qquad \forall k_{f_{2}}\in K}
[ 確認が必要 ] それぞれを対応するものと セットで 保存します 。
S
u
b
C
i
p
h
e
r
2
{\displaystyle {\mathit {SubCipher}}_{2}}
k
f
2
{\displaystyle k_{f_{2}}}
H
2
{\displaystyle H_{2}}
中間状態に関する可能性のある推測ごとに、 以下を計算します。
s
2
{\displaystyle s_{2}}
S
u
b
C
i
p
h
e
r
2
=
D
E
C
b
2
(
k
b
2
,
s
2
)
∀
k
b
2
∈
K
{\displaystyle {\mathit {SubCipher}}_{2}={\mathit {DEC}}_{b_{2}}(k_{b_{2}},s_{2})\qquad \forall k_{b_{2}}\in K}
そして、これと集合 の間の各一致について 、
S
u
b
C
i
p
h
e
r
2
{\displaystyle {\mathit {SubCipher}}_{2}}
H
2
{\displaystyle H_{2}}
一致する サブキーの組み合わせを新しいセットにまとめて保存します 。
T
1
{\displaystyle T_{1}}
T
2
{\displaystyle T_{2}}
中間状態に関する可能性のある推測ごとに、 以下を計算します。
s
n
{\displaystyle s_{n}}
S
u
b
C
i
p
h
e
r
n
=
D
E
C
b
n
(
k
b
n
,
s
n
)
∀
k
b
n
∈
K
{\displaystyle {\mathit {SubCipher}}_{n}={\mathit {DEC}}_{b_{n}}(k_{b_{n}},s_{n})\qquad \forall k_{b_{n}}\in K}
そして、これとセット の 間の各一致について 、 と一致するかどうかも確認し 、 と を 新しいセット に保存します 。
S
u
b
C
i
p
h
e
r
n
{\displaystyle {\mathit {SubCipher}}_{n}}
H
n
{\displaystyle H_{n}}
T
n
−
1
{\displaystyle T_{n-1}}
k
b
n
{\displaystyle k_{b_{n}}}
k
f
n
{\displaystyle k_{f_{n}}}
T
n
{\displaystyle T_{n}}
S
u
b
C
i
p
h
e
r
n
+
1
=
E
N
C
f
n
+
1
(
k
f
n
+
1
,
s
n
)
∀
k
f
n
+
1
∈
K
{\displaystyle {\mathit {SubCipher}}_{n+1}={\mathit {ENC}}_{f_{n}+1}(k_{f_{n}+1},s_{n})\qquad \forall k_{f_{n+1}}\in K}
そして、これと集合 の 間の各一致について 、 と一致するかどうかも確認します 。この場合、次のようになります。"
S
u
b
C
i
p
h
e
r
n
+
1
{\displaystyle {\mathit {SubCipher}}_{n+1}}
H
n
+
1
{\displaystyle H_{n+1}}
T
n
{\displaystyle T_{n}}
見つかったサブキーの組み合わせを 別の平文/暗号文のペアで使用して、キーの正確性を検証します。
(
k
f
1
,
k
b
1
,
k
f
2
,
k
b
2
,
.
.
.
,
k
f
n
+
1
,
k
b
n
+
1
)
{\displaystyle (k_{f_{1}},k_{b_{1}},k_{f_{2}},k_{b_{2}},...,k_{f_{n+1}},k_{b_{n+1}})}
アルゴリズムのネストされた要素に注意してください。 s j のすべての可能な値の推測は、前の s j -1 の推測ごとに実行されます。これは、この MD-MITM 攻撃の全体的な時間複雑度に対する指数関数的な複雑さの要素を構成します。
MD-MITM の複雑さ ブルートフォースを使わないこの攻撃の時間計算量は、 ⋅ ⋅
2
|
k
f
1
|
+
2
|
k
b
n
+
1
|
+
2
|
s
1
|
{\displaystyle 2^{|k_{f_{1}}|}+2^{|k_{b_{n+1}}|}+2^{|s_{1}|}}
(
2
|
k
b
1
|
+
2
|
k
f
2
|
+
2
|
s
2
|
{\displaystyle (2^{|k_{b_{1}}|}+2^{|k_{f_{2}}|}+2^{|s_{2}|}}
(
2
|
k
b
2
|
+
2
|
k
f
3
|
+
⋯
)
)
{\displaystyle (2^{|k_{b_{2}}|}+2^{|k_{f_{3}}|}+\cdots ))}
メモリの複雑さに関しては、 が最初に構築された候補値のテーブルよりもはるかに小さいこと が簡単にわかります 。i が増加すると、 に含まれる候補値が 満たす必要がある条件が増えるため、最終宛先に渡される候補の数は少なくなります 。
T
2
,
T
3
,
.
.
.
,
T
n
{\displaystyle T_{2},T_{3},...,T_{n}}
T
1
{\displaystyle T_{1}}
T
i
{\displaystyle T_{i}}
T
n
{\displaystyle T_{n}}
MD-MITMのメモリ複雑度の上限は
2
|
k
f
1
|
+
2
|
k
b
n
+
1
|
+
2
|
k
|
−
|
s
n
|
⋯
{\displaystyle 2^{|k_{f_{1}}|}+2^{|k_{b_{n+1}}|}+2^{|k|-|s_{n}|}\cdots }
ここで、 k は キー全体の長さ（結合後）を表します。
データの複雑さは、間違ったキーが通過する確率（偽陽性を得る確率）に依存します。ここで 、 l は 最初の MITM フェーズの中間状態です。中間状態のサイズとブロック サイズは多くの場合同じです。最初の MITM フェーズ後にテスト用に残されるキーの数も考慮すると、それは です 。
1
/
2
|
l
|
{\displaystyle 1/2^{|l|}}
2
|
k
|
/
2
|
l
|
{\displaystyle 2^{|k|}/2^{|l|}}
したがって、最初の MITM フェーズの後には 、 （ブロック サイズ）が存在します。
2
|
k
|
−
b
⋅
2
−
b
=
2
|
k
|
−
2
b
{\displaystyle 2^{|k|-b}\cdot 2^{-b}=2^{|k|-2b}}
|
b
|
{\displaystyle |b|}
キーの最終候補値が新しい平文/暗号文のペアでテストされるたびに、合格するキーの数に、キーが合格する確率が掛けられます 。
1
/
2
|
b
|
{\displaystyle 1/2^{|b|}}
ブルートフォーステストの部分（新しい
(
P
,
C
)
{\displaystyle (P,C)}
ペアの候補キーをテストする）には時間計算量があり
、明らかに指数の b の倍数が増えるにつれて、数はゼロに近づきます。
2
|
k
|
−
b
+
2
|
k
|
−
2
b
+
2
|
k
|
−
3
b
+
2
|
k
|
−
4
b
⋯
{\displaystyle 2^{|k|-b}+2^{|k|-2b}+2^{|k|-3b}+2^{|k|-4b}\cdots }
データの複雑さに関する結論は、同様の推論により、 ペアに関する結論によって制限されます。
⌈
|
k
|
/
n
⌉
{\displaystyle \lceil |k|/n\rceil }
(
P
,
C
)
{\displaystyle (P,C)}
以下は、2D-MITM の取り付け方法の具体的な例です。
2D-MITMの一般的な例 これは、2D-MITM がブロック暗号暗号化にどのように実装されるかについての一般的な説明です。
2 次元 MITM (2D-MITM) では、平文の多重暗号化内で 2 つの中間状態に到達する方法が採用されています。下の図を参照してください。
2D-MITM攻撃の図解
2D-MITMアルゴリズム 以下を計算します。
S
u
b
C
i
p
h
e
r
1
=
E
N
C
f
1
(
k
f
1
,
P
)
∀
k
f
1
∈
K
{\displaystyle {\mathit {SubCipher}}_{1}={\mathit {ENC}}_{f_{1}}(k_{f_{1}},P)\qquad \forall k_{f_{1}}\in K}
それぞれを対応する セットAに 保存する
S
u
b
C
i
p
h
e
r
1
{\displaystyle {\mathit {SubCipher}}_{1}}
k
f
1
{\displaystyle k_{f_{1}}}
S
u
b
C
i
p
h
e
r
2
=
D
E
C
b
2
(
k
b
2
,
C
)
∀
k
b
2
∈
K
{\displaystyle {\mathit {SubCipher}}_{2}={\mathit {DEC}}_{b_{2}}(k_{b_{2}},C)\qquad \forall k_{b_{2}}\in K}
それぞれを対応するものとまとめて セット B に 保存します。
S
u
b
C
i
p
h
e
r
2
{\displaystyle {\mathit {SubCipher}}_{2}}
k
b
2
{\displaystyle k_{b_{2}}}
と の間の 中間状態 s に関する可能な推測ごとに、
以下を計算します。
S
u
b
C
i
p
h
e
r
1
{\displaystyle {\mathit {SubCipher}}_{1}}
S
u
b
C
i
p
h
e
r
2
{\displaystyle {\mathit {SubCipher}}_{2}}
S
u
b
C
i
p
h
e
r
1
=
D
E
C
b
1
(
k
b
1
,
s
)
∀
k
b
1
∈
K
{\displaystyle {\mathit {SubCipher}}_{1}={\mathit {DEC}}_{b_{1}}(k_{b_{1}},s)\qquad \forall k_{b_{1}}\in K}
そして、これとセット A の間の各一致について、 新しいセット T に 保存します。
S
u
b
C
i
p
h
e
r
1
{\displaystyle {\mathit {SubCipher}}_{1}}
k
b
1
{\displaystyle k_{b_{1}}}
k
f
1
{\displaystyle k_{f_{1}}}
S
u
b
C
i
p
h
e
r
2
=
E
N
C
f
2
(
k
f
2
,
s
)
∀
k
f
2
∈
K
{\displaystyle {\mathit {SubCipher}}_{2}={\mathit {ENC}}_{f_{2}}(k_{f_{2}},s)\qquad \forall k_{f_{2}}\in K}
そして、これと集合B の間の各一致について、それがTと一致するかどうかもチェックする。
S
u
b
C
i
p
h
e
r
2
{\displaystyle {\mathit {SubCipher}}_{2}}
この場合、次のようになります。 見つかったサブキーの組み合わせを 別の平文/暗号文のペアで使用して、キーの正確性を検証します。
(
k
f
1
,
k
b
1
,
k
f
2
,
k
b
2
)
{\displaystyle (k_{f_{1}},k_{b_{1}},k_{f_{2}},k_{b_{2}})}
2D-MITM の複雑さ ブルートフォースを使わないこの攻撃の時間計算量は、
2
|
k
f
1
|
+
2
|
k
b
2
|
+
2
|
s
|
⋅
(
2
|
k
b
1
|
+
2
|
k
f
2
|
)
{\displaystyle 2^{|k_{f_{1}}|}+2^{|k_{b_{2}}|}+2^{|s|}\cdot \left(2^{|k_{b_{1}}|}+2^{|k_{f_{2}}|}\right)}
ここで、|⋅| は長さを表します。
メインメモリの消費量は、 T が他のものよりはるかに小さい セット A と B の構成によって制限されます。
データの複雑さについては、MD-MITM の複雑さに関するサブセクションを参照してください。
参照
参考文献
^ 「Crypto-IT」. ^ ab Moore, Stephane (2010 年 11 月 16 日)。「Meet-in-the-Middle 攻撃」 (PDF) : 2。 ^ victoria, jaynor. "victoria15". victoria14 . 2021年7月14日時点のオリジナルよりアーカイブ。 2021年 7月14日 閲覧 。 ^ ^ Diffie, Whitfield; Hellman, Martin E. (1977 年 6 月)。「NBS データ暗号化標準の徹底的な暗号解析」 (PDF) 。 コンピュータ 。10 (6): 74–84。doi : 10.1109 /CM.1977.217750。S2CID 2412454 。 ^ abcd Zhu, Bo; Gong, Guang (2014). 「多次元ミートインザミドル攻撃とKATAN32/48/64への応用」。 暗号 と通信 。6 :313–333。doi : 10.1007/s12095-014-0102-9 – Springer Link経由。 ^ Blondeau, Céline. 「講義 3: ブロック暗号」 (PDF) . CS-E4320 暗号化とデータセキュリティ . 2018 年 2 月 23 日の オリジナル (PDF)からアーカイブ。2018 年 2 月 22 日 閲覧 。
![{\displaystyle {\begin{aligned}C&={\mathit {ENC}}_{k_{2}}({\mathit {ENC}}_{k_{1}}(P))\\{\mathit {DEC}}_{k_{2}}(C)&={\mathit {DEC}}_{k_{2}}({\mathit {ENC}}_{k_{2}}[{\mathit {ENC}}_{k_{1}}(P)])\\{\mathit {DEC}}_{k_{2}}(C)&={\mathit {ENC}}_{k_{1}}(P)\\\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/549ca6b05f8687821656d9f2f43a9ca214e9da9c)
