미트 인 더 미들 공격

이 섹션에는 여러 가지 문제가 있습니다.개선을 돕거나 토크 페이지에서 이러한 문제에 대해 논의해 주십시오.(이러한 템플릿메시지를 삭제하는 방법과 타이밍에 대해 설명합니다) 이 기사는 검증할 수 있는 주요 주제에 언급되거나 관련되지 않은 자료의 합성을 포함할 수 있다. 관련 토론은 토크 페이지에서 확인할 수 있습니다.(2013년 5월) (이 템플릿메시지 삭제 방법 및 삭제 시기 확인) 이 글은 검증을 위해 추가 인용문이 필요합니다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선하는 데 도움을 주십시오. 조달되지 않은 자재는 제거될 수 있습니다.출처 찾기 : '중간자 공격'– 뉴스 · 신문 · 서적 · 학자 · JSTOR (2009년 3월) (이 템플릿 메시지 삭제 방법 및 삭제 시기 확인) (이 템플릿메시지를 삭제하는 방법과 타이밍을 확인합니다)

Meet-in-the-Middle 공격(^[1]MITM)은 기존의 플레인텍스트 공격으로서 여러 암호화 조작을 순차적으로 실행하는 암호화 방식에 대한 일반적인 시공간 트레이드오프 암호화 공격입니다.MITM 공격은 Double DES가 사용되지 않는 주요 이유이며, 2개의 공간과 2개의^{112 [2][3]}조작을 가진⁵⁶ 공격자가 트리플 DES 키(168비트)를 강제할 수 있는 주된 이유입니다.

묘사

블록 암호의 보안을 강화하려면 여러 키를 사용하여 데이터를 여러 번 암호화해야 합니다.k비트 키로 데이터를 n번 암호화하면 가능한 모든 키 조합(단순한 brute-force)에 대한 완전한 검색은 2번의 시행이^n·k 필요하기 때문에 데이터가 암호화되는 횟수에 따라 여러 암호화 방식의 보안이 배가되거나 심지어 n배가 된다고 생각할 수 있습니다.

MITM은 암호화 또는 복호화의 중간값을 저장하고 이를 사용하여 복호화 키를 강제하는 데 필요한 시간을 단축함으로써 여러 암호화를 사용하는 보안상의 이점을 약화시키는 일반적인 공격입니다.이것에 의해, Meet-in-the-Middle 공격(MITM)은 일반적인 시공간 트레이드 오프 암호^[4] 공격이 됩니다.

MITM 공격은 여러 함수(또는 블록 암호)의 구성 범위(암호)와 도메인(플레인 텍스트)을 모두 사용하여 키를 찾으려 합니다.이것에 의해, 최초의 함수를 통과하는 순방향 매핑(역방향 이미지)은, 말 그대로, 컴포지트의 중간에서 회합하는 것과 같습니다.ed 함수예를 들어, Double DES는 2개의 다른 56비트 키를 사용하여 데이터를 암호화하지만, Double DES는 2개의 암호화 및 복호화 조작으로 해제할⁵⁷ 수 있습니다.

Multidimension MITM(MD-MITM; 다차원 MITM)은 위에서 설명한 것과 같은 여러 가지 동시 MITM 공격을 조합하여 사용합니다.이 경우 회의는 구성된 함수의 여러 위치에서 이루어집니다.

역사

Diffie와 Hellman은 1977년 ^[5]블록 암호의 가상의 확장에 대한 중간자 공격 방식을 처음 제안했다.이들의 공격은 시공간의 트레이드오프를 사용하여 이중 암호화 체계를 깨는 데 필요한 시간의 2배에 불과했습니다.

2011년, 보주와 광공은 다차원 중간 미팅 공격을 조사하여 블록 암호 GOST, KTANTAN 및 ^[6]Humningbird-2에 대한 새로운 공격을 제시하였습니다.

Meet-in-the-middle (1D-MITM)

특정 평문 P 및 암호문 C에 대해 다음 특성을 가진 암호화 방식을 공격하려고 합니다.

$디스플레이 스타일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(역매핑)로⁻¹₁ 정의된 복호화 함수, k와₂ k는 2개의 키입니다.

이 암호화 스킴을 brute-force 하기 위한 간단한 접근법은 암호문을 k개마다₂ 복호화하고 중간 출력을 k개마다₁ 복호화하여 합계 2 × 2 ^k₂ (또는 ^{k₁ + k₂} 2)의 ^k₁ 연산을 하는 것입니다.

Meet-in-the-middle 공격은 보다 효율적인 접근 방식을 사용합니다.C를 k로₂ 복호화하면 다음과 같은 동등성을 얻을 수 있습니다.

$디스플레이 스타일C&=mathit {ENC}_{k_{2}}({\mathit {ENC}}_{k_{1}})(P)\\{\mathit {DEC}_{k_{2}}(C)&=mathmathit {DEC}_{k_{2}}({\mathit {ENC}_{k_{2}}[{\mathit {ENC}}_{k_{1}(P)])\\{\{\mathit {DEC}_{k_{2}}&{C}}}}}}{\mathit {\mathit {\mathit {\mathit}}}}}}}}}{{{{{{{{{{{{$

공격자는 k 및_k2 DEC₂(C)의₁ 모든 값에 대한 ENC(P ^k₂ )를 계산하여_k1 총 2+2(k와₂ k의 크기가 같은 경우₁ 2개 ^{k₁ +1})의 ^k₁ 연산을 수행할 수 있습니다.어느_k1 하나의 ENC(P) 동작의 결과가 DEC(C_k2) 동작의 결과와 일치하는 경우 k와 k의₁₂ 쌍이 올바른 키일 수 있습니다.이 잠재적으로 올바른 키를 후보 키라고 합니다.공격자는 평문과 암호문의 두 번째 테스트 세트를 사용하여 테스트함으로써 어떤 후보 키가 올바른지 판별할 수 있습니다.

MITM 공격은 Data Encryption Standard(DES; 데이터 암호화 규격)가 Double DES가 아닌 Triple DES로 대체된 이유 중 하나입니다.공격자는 MITM 공격을 사용하여 Double DES를 2개의 조작과⁵⁶ 2개의 공간으로 강제할⁵⁷ 수 있으므로 ^[7]DES보다 약간 개선됩니다.Triple DES는 '트리플 길이'(168비트) 키를 사용하며, 2공간과¹¹² 2연산으로 중간자⁵⁶ 미트 인 더 미들 공격에 취약하지만 키 공간의 ^[2][3]크기 때문에 안전한 것으로 간주됩니다.

MITM 알고리즘

다음을 계산합니다.

• ${\displaystyle {\mathit{S}}_{}}$ ${\displaystyle {\mathit{u}}_{}}$ ${\displaystyle {\mathit{C}}_{}}$ ${\displaystyle {\mathit{i}}_{}}$ ${\displaystyle {\mathit{p}}_{}}$ ${\displaystyle {\mathit{h}}_{}}$ ${\displaystyle {\mathit{e}}_{}}$ r ${\displaystyle 1_{\mathrm{}}}$ ${\displaystyle {}_{}}$ ${\displaystyle {\mathit{E}}_{}}$ N ${\displaystyle C_{{}_{}}}$ f${\displaystyle {{}_{}}_{}{{1\mathrm{}}_{}}_{}}$ ( ${\displaystyle {}_{}}$ ${\displaystyle {{f\mathrm{}}_{}}_{}1}$, P )${\displaystyle 、\mathrm{}}$ 「 ${\displaystyle {k{}_{}}_{}}$ f $style$ K display style$$（ \ $mathit$ { SubCipher }$_${ } =$math$ mathit ${ ENC$ } $} （$k$_$f _ { { 1$$} , P ） 、 \ $in 1$} 。

  $각{\displaystyle {\mathit{}}_{}}$ ${\displaystyle {\mathit{SU}}_{}}$ B ${\displaystyle {\mathit{C}}_{}}$ ${\displaystyle {\mathit{ip}}_{}}$ ${\displaystyle {\mathit{e}}_{}}$ ${\displaystyle {\mathit{r}}_{}}$ $({$})을$$ 대응하는 $k{\displaystyle {}_{}}$ ${\displaystyle {{f\mathrm{}}_{}}_{}}$1({$displaystyle k_{f_{1})$과 함께 세트 A에 저장합니다.

• $S$ ${\displaystyle {\mathit{u}}_{}}$ B ${\displaystyle {\mathit{C}}_{}}$ ${\displaystyle {\mathit{i}}_{}}$ ${\displaystyle {\mathit{p}}_{}}$ h ${\displaystyle {\mathit{e}}_{}}$ ${\displaystyle r_{\mathrm{}}}$ 1 ${\displaystyle {}_{}}$ ${\displaystyle {\mathit{}}_{}}$ ${\displaystyle {\mathit{E}}_{}}$ ${\displaystyle {\mathit{C}}_{}}$ ${\displaystyle {{1\mathrm{}}_{}}_{}}$( ${\displaystyle {}_{}}$ ${\displaystyle {b{}_{}}_{}{{}_{}}_{}1}$,${\displaystyle }$C ) ,${\displaystyle {{}_{}}_{}\forall \mathrm{}}$ ${\displaystyle k}$b 1${\$ K display style { \ $mathit$ { $SubCipher }$ _ { } =$displaymathit$ {$DEC } （ k$ _ {$b$_ { 1 } , C } , \ $in$ 1 ） 。

  각 $새로운{\displaystyle {\mathit{}}_{}}$ ${\displaystyle {\mathit{SU}}_{}}$ ${\displaystyle {\mathit{B}}_{}}$ C ${\displaystyle {\mathit{ip}}_{}}$ ${\displaystyle {\mathit{e}}_{}}$ ${\displaystyle r_{\mathrm{}}}$ 1$({$${1})$을 세트A와 비교합니다.

${\displaystyle {}_{}}$하는 것이 발견되면 k ${\displaystyle {{f\mathrm{}}_{}}_{}}$1, ${\displaystyle {k{}_{}}_{}}$ ${\displaystyle {{b\mathrm{}}_{}}_{}}$ 1 $(\$을 테이블T의 후보 키쌍으로 $유지$합니다.새${\displaystyle 쌍}({\displaystyle }$ P ,${\displaystyle C}$) \$displaystyle (P$, C) \displaystyle (P,$C)$ \ )의$$ T 쌍을 테스트하여 유효성을 확인합니다.키쌍이 이 새로운 쌍으로 동작하지 않으면 (${\displaystyle P,}$ $)\displaystyle (P, C$의${\displaystyle }$새로운 쌍으로 MITM을 다시 실행합니다.

MITM의 복잡성

keysize가 k인 경우 이 공격은 2개의 암호화(및 복호화)와 O(2^k) 메모리만을 사용하여^k+1 룩업테이블에 전송 계산 결과를 저장합니다.이는 O(1) 공간을 제외한 2개의 암호화를 필요로^2·k 하는 순진한 공격과는 대조적입니다.

다차원 MITM(MD-MITM)

이 섹션에는 독창적인 연구가 포함되어 있을 수 있습니다. 클레임을 확인하고 인라인 인용을 추가하여 개선해 주십시오. 독창적인 연구로만 구성된 진술은 삭제되어야 한다.(2013년 5월) (이 템플릿메시지 삭제 방법 및 삭제 시기 확인)

1D-MITM은 효율적일 수 있지만, 보다 고도의 공격이 개발되었습니다.다차원적인 중간자 미트 인 더 미들 공격(MD-MITM이라고도 함).이 방법은 서로 다른 키를 사용하여 3개 이상의 암호화를 사용하여 데이터를 암호화한 경우에 적합합니다.MD-MITM 공격은 중간(시퀀스 중 한 곳)에서 만나는 것이 아니라 암호 ^[6]내의 여러 위치에서 포워드 및 백워드 계산을 사용하여 여러 특정 중간 상태에 도달하려고 합니다.

공격이 블록 암호에 마운트되어야 한다고 가정합니다.여기서 암호화와 복호화는 전과 같이 정의됩니다.

${\displaystyle C=mathit {ENC}_{k_{n}}({\mathit {ENC}}_{k_{n-1})({\mathit {ENC}}_{k_{1}}(P)...)})}$

${\mathit {DEC}_{k_{1}}({\mathit {DEC}}_{k_{2}}) (...)({\mathit {DEC}}_{k_{n}}(C)...)})}$

즉, 평문 P는 동일한 블록 암호의 반복을 사용하여 여러 번 암호화됩니다.

MD-MITM은 GOST 블록 암호의 암호 해독에 사용되어 왔습니다.이 암호에서는 ^[6]3D-MITM에 의해 공격에 소요되는 시간이 대폭 단축되었습니다.

MD-MITM 알고리즘

이 섹션은 어떠한 출처도 인용하지 않습니다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 섹션의 개선에 도움을 주십시오. 조달되지 않은 자재는 제거될 수 있습니다.(2015년 5월) (이 템플릿메시지 삭제 방법 및 삭제 시기 확인)

다음을 계산합니다.

${\displaystyle {SubCipher}_{1}=mathit {ENC}_{f_{1},P)\qquad \forall k_{f_{1}\in K}$

$각{\displaystyle {\mathit{}}_{}}$ ${\displaystyle {\mathit{SU}}_{}}$ B ${\displaystyle {\mathit{C}}_{}}$ ${\displaystyle {\mathit{ip}}_{}}$ ${\displaystyle {\mathit{h}}_{}}$ ${\displaystyle r_{\mathrm{}}}$ 1$(\$과 대응하는 k ${\displaystyle {f{}_{}}_{}}$ $(\$을 H$$(\$displaystyle H_{$1$\})$ $세트$에 저장합니다.

${\displaystyle {SubCipher}_{n+1}=mathit {DEC}_{b_{n+1}}(K_{b_{n+1},C)\qquad \forall k_{b_{n+1}\in K}$

$각{\displaystyle {\mathit{}}_{}}$ ${\displaystyle {\mathit{SU}}_{}}$ B ${\displaystyle {\mathit{C}}_{}}$ ${\displaystyle {\mathit{ip}}_{}}$ ${\displaystyle {\mathit{h}}_{}}$ ${\displaystyle {\mathit{e}}_{\mathrm{r}}}$ + 1$$({$displaystyle {SubCipher}_{n+1})$과 대응하는 ${\displaystyle {k{}_{}}_{}}$ ${\displaystyle {b_{}}_{}}$n +$$ ({$displaystyle k_{b_{n+1})$을 H${\displaystyle n_{}}$ +$$ ({$displaystyle H_{n+1$ $세트$로 저장합니다.

중간 $상태{\displaystyle {}_{}}$ ${\displaystyle {s\mathrm{}}_{}}$ 1$(\$1})에$$ 대해 가능한 각 추측에 대해 다음을 계산합니다.

${\displaystyle {SubCipher}_{1}=mathit {DEC}_{b_{1}, s_{1}\qquad \forall k_{b_{1}\in K}$

$이{\displaystyle {\mathit{}}_{}}$ ${\displaystyle {\mathit{SU}}_{}}$ ${\displaystyle {\mathit{B}}_{}}$ ${\displaystyle {\mathit{C}}_{}}$ ${\displaystyle {\mathit{ip}}_{}}$ ${\displaystyle {\mathit{e}}_{}}$ r$$({$displaystyle {SubCipher}_{1$})과$$$$ $세트{\displaystyle {}_{}}$ H$$({$displaystyle H_{1$ 사이의 매치마다 k ${\displaystyle {b{}_{}}_{}}$({$displaystyle k_{b_1}})$과 ${\displaystyle {k{}_{}}_{}}$ ${\displaystyle {{f\mathrm{}}_{}}_{}}$ 1$({$$displaystyle k_$${$$f_1})$을 ${\displaystyle {새로운\mathrm{}}_{}}$ $T_1로 저장$합니다$.$

${\displaystyle {SubCipher}_{2}=submathit {ENC}_{f_{2},s_{1}\qquad \forall k_{f_{2}\in K}$^{[검증 필요]}

$각{\displaystyle {\mathit{}}_{}}$ ${\displaystyle {\mathit{SU}}_{}}$ ${\displaystyle {\mathit{B}}_{}}$ ${\displaystyle {\mathit{C}}_{}}$ ${\displaystyle {\mathit{ip}}_{}}$ ${\displaystyle {\mathit{h}}_{}}$ ${\displaystyle r_{\mathrm{}}}$ 2$(\$})와$$ $대응$하는 k ${\displaystyle {{f\mathrm{}}_{}}_{}}$2(\$displaystyle k_{f_{2}})$를 ${\displaystyle {H\mathrm{}}_{}}$2(\$displaystyle H_{2$ $세트$에 저장합니다.

중간 $상태{\displaystyle {}_{}}$ ${\displaystyle {s\mathrm{}}_{}}$ 2$({$에 대해 가능한 각 추측에 대해 다음을 계산합니다.

• $({displaystyle {SubCipher}_{2}=mathit {DEC}}_{b_{2},s_{2})\qquad \forall k_{b_{2}\in K})$

  $또한{\displaystyle {\mathit{}}_{}}$ 이 ${\displaystyle {\mathit{SU}}_{}}$ ${\displaystyle {\mathit{B}}_{}}$ ${\displaystyle {\mathit{C}}_{}}$ ${\displaystyle {\mathit{ip}}_{}}$ ${\displaystyle {\mathit{e}}_{}}$ r$({displaystyle$ {$SubCipher}}_{$2$$})와 세트 ${\displaystyle {H\mathrm{}}_{}}$2({$displaystyle H_{$2$\}\})$가 일치할 때마다

  $({$과 일치하여 서브키 조합을 새로운 $세트{\displaystyle {}_{}}$ $({$에 저장합니다.

• 중간 $상태{\displaystyle {}_{}}$ $(\$에 대해 가능한 각 추측에 대해 다음을 계산합니다.

검색된${\displaystyle }$서브키 ${\displaystyle {}_{}}$(${\displaystyle {k{}_{}}_{}{{}_{}}_{}}$f ${\displaystyle {1{}_{}}_{}}$, ${\displaystyle {{k\mathrm{}}_{}}_{}{}_{}}$ ${\displaystyle {1{}_{}}_{}}$, k${\displaystyle {{}_{}}_{}{{f\mathrm{}}_{}}_{}}$ ${\displaystyle {2{}_{}}_{}}$, k${\displaystyle {{}_{}}_{}{{b\mathrm{}}_{}}_{}}$2${\displaystyle }$, . , ${\displaystyle {k_{}}_{}}$ f${\displaystyle {{}_{}}_{}{}_{}{{}_{}}_{}}$+ ${\displaystyle {1_{}}_{}}$,${\displaystyle {{}_{}}_{}}$k ${\displaystyle {{\mathrm{b}}_{}}_{}}$ n${\displaystyle {{}_{}}_{}}$+$$1)을 사용합니다.{ $display$( k _ { $f$_ { 1$$} , $k$_ { $b$_ {$1}$ , k _ { f _ {2} , k _ {$b$_ { n } , k _ { n } , k _ { n$}$ 。

알고리즘에 중첩된 요소를 적어 둡니다.위의_j 모든 가능한 값에 대한 추측은 이전_j-1 s의 각 추측에 대해 수행됩니다.이는 이 MD-MITM 공격의 전체적인 시간 복잡성에 대해 기하급수적으로 복잡한 요소를 구성합니다.

MD-MITM의 복잡성

이 공격의 시간 복잡도는 ${\displaystyle {{2k{}_{}}_{}}^{}}$ f${\displaystyle {{{}_{}}_{}}^{}{{{1\mathrm{}}_{}}_{}}^{}}$ + ${\displaystyle {{2k{}_{}}_{}}^{}}$ b${\displaystyle {{n_{}}_{}}^{}}$ +${\displaystyle {{{}_{}}_{}}^{}{{1_{}}_{}}^{}}$ + ${\displaystyle {2{}_{}}^{}}$ s${\displaystyle {{}_{}}^{}}{\displaystyle {{1\mathrm{}}_{}}^{}}$ ({$style$$$2$^{ k_{f_{1}})$+ $2^{ k_{b_{n+1}}$ + 2$^{1}$} ${\displaystyle }$ ( $2$ ${\displaystyle {{k{}_{}}_{}}^{}}$ $b$1 + ${\displaystyle {2{}_{}}^{}}$ ${\displaystyle {{k{}_{}}_{}}^{}}$ f${\displaystyle {{{}_{}}_{}}^{}{{{2\mathrm{}}_{}}_{}}^{}}$ + $s$） $。$$^{ s_{2}$}} $$ ( ${\displaystyle {2{}_{}}^{}}$ ${\displaystyle {{k{}_{}}_{}{{}_{}}_{}}^{}{{{b\mathrm{}}_{}}_{}}^{}}$ ${\displaystyle {2{}_{}}^{}}$ + ${\displaystyle {{2{}_{}}_{}}^{}}$ k${\displaystyle {{{}_{}}_{}}^{}{{{f\mathrm{}}_{}}_{}}^{}}$ 3 + ${\displaystyle )}$) { $displaystyle$($2$^ { k$_$ { b _ { b _ {2$} }$ + $2$^ { k$_$ { f$_$ {$3}$} + \ $cdots$) }$$。

메모리의 복잡성에 대해서는, ${\displaystyle {T2\mathrm{}}_{}}$ ${\displaystyle {T3\mathrm{}}_{}}$ ${\displaystyle ...,}$ $($ T_${2}, T_{3})$을 쉽게 알 수 있습니다.$T_{n}$은(는) 처음 작성된 후보값 테이블보다 훨씬 작습니다.$({$ i가$$ 증가할수록 $({$$displaystyle$ $T_{i})$에 포함된 후보 값은 더 많은 조건을 충족해야 합니다.따라서 최종 $수신처{\displaystyle {}_{}}$ $({$에 전달되는 후보 수는 줄어듭니다.

은 MD-MITM으로 .

$2displaystyle 2^{k_{f_{12^{k_{b_{n+1}}+2^{k_{n_{cdots}})$

여기서 k는 키 전체의 길이(표준)를 나타냅니다.

데이터의 복잡성은 잘못된 키가 통과될 가능성(false positive)에 따라 달라집니다.${\displaystyle 즉{\mathrm{}}^{},}$ 1/${\displaystyle 2^{}}$l (\$displaystyle$1/$2^{ l$입니다.여기서 l은 첫 번째 MITM 단계의 중간 상태입니다.중간 상태의 크기와 블록 크기가 동일한 경우가 많습니다!또한 첫 번째 MITM 단계 이후 테스트에 남은 키의 수를 고려하면 $displaystyle$ 2$^{k}/2^{l$ $\}\})$입니다.

따라서 첫 번째 MITM 단계 이후에는 ${\displaystyle {2k}^{}}$ ${\displaystyle {-}^{}}$ ${\displaystyle b^{}{\mathrm{}}^{}}$2 - ${\displaystyle b^{}}$ $=$ ${\displaystyle {2k}^{}}$- ${\displaystyle {\mathrm{2b}}^{}}$(\$displaystyle$ 2$^{$k - b$}\cdot$ 2$^{-b$}=$2^{$k - $2b$ 이며, ${\displaystyle 여기}$서${\displaystyle }$b {\$display$ b $}$는 블록 크기이다.

키의 최종 후보 값이 새로운 평문/암호문 쌍으로 테스트될 때마다 통과하는 키의 수에 키가 ${\displaystyle 통과}$할 확률$displaystyle$ 1$/2^{ b$을 곱합니다.

브루트 포스 테스트(새로운 ${\displaystyle (P,}$ C$)$의 후보 키 테스트)의 부분({$displaystyle (P,C)}-$pairs$$, 시간 ${\displaystyle {복잡도}^{}{\mathrm{}}^{}}$ -${\displaystyle {}^{}{b}^{}}$ +${\displaystyle {\mathrm{2k}}^{}}$ - ${\displaystyle {\mathrm{}}^{}}$ +${\displaystyle {\mathrm{2k}}^{}}$ - ${\$ （ \ $displaystyle$ 2$^$ { k - b } + 2k - b + $2^$ { k - b${\displaystyle {}^{}}$} + 2^ { k - b } + 2 ^$2b$^ { k - b } + 2 ^ { k - 4$$b } ^ { k - { k - 4 b } } ) { k - { k - { k지수, 숫자는 0이 되는 경향이 있습니다.

데이터의 복잡성에 대한 결론은${\displaystyle }$"$"$ ({$displaystyle\lceil$ k$/n\rceil$${\displaystyle }$ ${\displaystyle P,}$ $)$ ({$displaystyle(P,C)}$ -pairs에$$ 의해 제한되는 유사한 추론에 의해 결정됩니다.

2D-MITM의 구체적인 설치 예를 다음에 나타냅니다.

2D-MITM의 일반적인 예

이것은 블록 암호 암호에 2D-MITM이 어떻게 마운트되는지에 대한 일반적인 설명입니다.

2차원 MITM(2D-MITM)에서는 이 방법은 평문의 다중 암호화 내에서2개의 중간 상태에 도달하는 것입니다.아래 그림을 참조해 주세요.

2D-MITM 알고리즘

다음을 계산합니다.

${\displaystyle {SubCipher}_{1}=mathit {ENC}_{f_{1},P)\qquad \forall k_{f_{1}\in K}$

$각{\displaystyle {\mathit{}}_{}}$ ${\displaystyle {\mathit{SU}}_{}}$ B ${\displaystyle {\mathit{C}}_{}}$ ${\displaystyle {\mathit{ip}}_{}}$ ${\displaystyle {\mathit{e}}_{}}$ ${\displaystyle {\mathit{r}}_{}}$ $({$})을$$ 대응하는 $k{\displaystyle {}_{}}$ ${\displaystyle {{f\mathrm{}}_{}}_{}}$1({$displaystyle k_{f_{1})$과 함께 세트 A에 저장합니다.

${\displaystyle {SubCipher}_{2}=submathit {DEC}_{b_{2},C)\qquad \forall k_{b_{2}\in K}$

$각{\displaystyle {\mathit{}}_{}}$ ${\displaystyle {\mathit{SU}}_{}}$ ${\displaystyle {\mathit{B}}_{}}$ ${\displaystyle {\mathit{C}}_{}}$ ${\displaystyle {\mathit{ip}}_{}}$ h ${\displaystyle {\mathit{e}}_{}}$ ${\displaystyle {\mathit{r}}_{}}$ $({$2})와$$ ${\displaystyle {대응}_{}}$하는 k$$ 2({$displaystyle k_{b_{$2}})를$$ 세트 B에 저장합니다.

${\displaystyle {\mathit{S}}_{}}$ ${\displaystyle {\mathit{u}}_{}}$ b ${\displaystyle {\mathit{C}}_{}}$ ${\displaystyle {\mathit{ip}}_{}}$ ${\displaystyle {\mathit{h}}_{}}$ e ${\displaystyle {\mathit{r}}_{}}$ ({$displaystyle$ {$SubCipher})_{1})$과 ${\displaystyle {\mathit{S}}_{}}$ ${\displaystyle {\mathit{u}}_{}}$ B ${\displaystyle {\mathit{C}}_{}}$$$${\displaystyle {\mathit{ip}}_{}}$ ${\displaystyle {\mathit{h}}_{}}$ e ${\displaystyle r_{\mathrm{}}}$2 ({$displaystyle {SubCipher}_{2}})$ 사이의$$ 중간 $상태$에 대해 가능한 각 추측에 대해 다음과 같이 계산합니다.

• ${\displaystyle {SubCipher}_{1}=mathit {DEC}_{b_{1}}(s)\qquad \forall k_{b_{1}\in K}$

  $이{\displaystyle {\mathit{}}_{}}$ ${\displaystyle {\mathit{SU}}_{}}$ B ${\displaystyle {\mathit{C}}_{}}$ ${\displaystyle {\mathit{ip}}_{}}$ ${\displaystyle {\mathit{e}}_{}}$ ${\displaystyle r_{\mathrm{}}}$ 1$({$1$$})과 세트 A 사이의 매치마다 k ${\displaystyle {{b\mathrm{}}_{}}_{}}$1({$displaystyle k_{b_1})$과 ${\displaystyle {k{}_{}}_{}}$ ${\displaystyle {{f\mathrm{}}_{}}_{}}$1({$displaystyle k_{f_1}})$을 새로운 세트 T에 저장합니다.

• ${\displaystyle {SubCipher}_{2}=mathit {ENC}_{f_{2}}(s)\qquad \forall k_{f_{2}}\in K}$

  $또한{\displaystyle {\mathit{}}_{}}$ 이 ${\displaystyle {\mathit{SU}}_{}}$ B ${\displaystyle {\mathit{C}}_{}}$ ${\displaystyle {\mathit{ip}}_{}}$ ${\displaystyle {\mathit{e}}_{}}$ r $({$와 세트B가 일치할 때마다 T와 일치하는지 여부를 확인합니다.

  이 경우:

발견된 서브키${\displaystyle }$조합(${\displaystyle {}_{}}$ ${\displaystyle {{f\mathrm{}}_{}}_{}}$1, k ${\displaystyle {b{}_{}}_{}{{1\mathrm{}}_{}}_{}}$, ${\displaystyle {}_{}}$ ${\displaystyle {f{}_{}}_{}{{2\mathrm{}}_{}}_{}}$, ${\displaystyle {k{}_{}}_{}}$ ${\displaystyle {{b\mathrm{}}_{}}_{}}$2$){style (k_{f_{1},k_{b_{1},k_{f_{2},k_{b_{2}})$을 사용하여 키가 올바른지 확인합니다.

2D-MITM의 복잡성

이 공격의 복잡성은 무차별적인 힘을 사용하지 않는 경우

${\displaystyle 2^{ k_{f_{1}} }+2^{ k_{b_{2}} }+2^{ s }\cdot \left(2^{ k_{b_{1}} }+2^{ k_{f_{2}} }\right)}$

where ⋅ denotes the length.

Main memory consumption is restricted by the construction of the sets A and B where T is much smaller than the others.

For data complexity see subsection on complexity for MD-MITM.

See also

• Birthday attack
• Wireless security
• Cryptography
• 3-subset meet-in-the-middle attack
• Partial-matching meet-in-the-middle attack

References