중간 일치 공격

**중간 일치 공격**(Meet-in-the-middle attack, **MITM**)은 알려진 평문 공격의 일종으로, 여러 암호화 연산을 순차적으로 수행하는 암호화 방식에 대한 일반적인 시간-공간 트레이드오프 암호학적 공격이다. MITM 공격은 이중 DES가 사용되지 않는 주된 이유이며, 삼중 DES 키(168비트)가 256의 공간과 2112의 연산으로 공격자에 의해 무차별 대입될 수 있는 이유이다.

## 설명
블록 암호의 보안을 개선하려고 할 때, 여러 키를 사용하여 데이터를 여러 번 암호화하는 것은 매력적인 아이디어이다. 데이터가 k-비트 키로 n번 암호화될 경우, 모든 가능한 키 조합에 대한 완전 탐색(단순 무차별 대입)은 2n·k번의 시도가 필요하므로, 이는 다중 암호화 방식의 보안을 두 배 또는 n배로 늘린다고 생각할 수 있다.

MITM 공격은 암호화 또는 해독의 중간 값을 저장하고 이를 활용하여 해독 키를 무차별 대입하는 데 필요한 시간을 줄임으로써 다중 암호화 사용의 보안 이점을 약화시키는 일반적인 공격이다. 이는 중간 일치 공격(MITM)을 일반적인 시간-공간 트레이드오프 암호학적 공격으로 만든다.

MITM 공격은 여러 함수(또는 블록 암호)의 구성에서 첫 번째 함수를 통한 순방향 매핑이 마지막 함수를 통한 역방향 매핑(역상)과 동일하여 구성 함수의 중간에서 말 그대로 만나는 방식으로 키를 찾으려 한다. 예를 들어, 이중 DES는 두 개의 다른 56비트 키로 데이터를 암호화하지만, 이중 DES는 257번의 암호화 및 해독 연산으로 해독될 수 있다.

다차원 MITM(MD-MITM)은 위에서 설명한 여러 동시 MITM 공격의 조합을 사용하며, 만남은 구성 함수의 여러 위치에서 발생한다.

## 역사
휫필드 디피와 마틴 헬먼은 1977년 블록 암호의 가상적인 확장에 대해 중간 일치 공격을 처음 제안했다.
그들의 공격은 시간-공간 트레이드오프를 사용하여 단일 암호화 체계를 해독하는 데 필요한 시간의 두 배만으로 이중 암호화 체계를 해독했다.

2011년에 보 주와 광 공은 다차원 중간 일치 공격을 조사하고 GOST, KTANTAN 및 Hummingbird-2 블록 암호에 대한 새로운 공격을 제시했다.

## 중간 일치 공격 (1D-MITM)
주어진 평문 P와 암호문 C에 대해 다음과 같은 특성을 가진 암호화 체계를 공격하려 한다고 가정하자:
:\begin{align}
                         C &= \mathit{ENC}_{k_2}(\mathit{ENC}_{k_1}(P)) \\
                         P &= \mathit{DEC}_{k_1}(\mathit{DEC}_{k_2}(C)) \\
\end{align}

여기서 ENC는 암호화 함수, DEC는 ENC−1 (역 매핑)으로 정의된 해독 함수이며 k1과 k2는 두 개의 키이다.

이 암호화 체계를 무차별 대입하는 순진한 접근 방식은 가능한 모든 k2로 암호문을 해독하고, 각 중간 출력을 가능한 모든 k1으로 해독하는 것으로, 총 2|k1| × 2|k2| (또는 2|k1|+|k2|) 연산이 필요하다.

중간 일치 공격은 더 효율적인 접근 방식을 사용한다. C를 k2로 해독하면 다음 등식을 얻는다:
:\begin{align}
                         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{align}

공격자는 모든 k1 값에 대해 ENCk1(P)를 계산하고, 가능한 모든 k2 값에 대해 DECk2(C)를 계산할 수 있으며, 총 2|k1| + 2|k2| (k1과 k2의 크기가 같으면 2|k1|+1) 연산이 필요하다. ENCk1(P) 연산의 결과 중 하나가 DECk2(C) 연산의 결과와 일치하면 k1과 k2의 쌍이 올바른 키일 수 있다. 이 잠재적으로 올바른 키를 후보 키라고 한다. 공격자는 두 번째 평문 및 암호문 테스트 세트를 사용하여 어떤 후보 키가 올바른지 판단할 수 있다.

MITM 공격은 데이터 암호화 표준 (DES)이 이중 DES가 아닌 트리플 DES로 대체된 이유 중 하나이다. 공격자는 MITM 공격을 사용하여 257 연산과 256 공간으로 이중 DES를 무차별 대입할 수 있어 DES에 비해 약간의 개선에 불과하다. 트리플 DES는 "세 배 길이" (168비트) 키를 사용하며 256 공간과 2112 연산으로 중간 일치 공격에 취약하지만, 키 공간의 크기 때문에 안전하다고 간주된다.

섬네일|upright=1.5|1D-MITM 공격의 그림

### MITM 알고리즘
다음 사항을 계산한다.
*\mathit{SubCipher}_1=\mathit{ENC}_{f_1}(k_{f_1},P),\; \forall  k_{f_1} \in  K :
*: 그리고 각 \mathit{SubCipher}_{1} 을 해당  k_{f_1} 과 함께 집합 A에 저장한다.
*\mathit{SubCipher}_1=\mathit{DEC}_{b_1}(k_{b_1},C),\; \forall k_{b_1} \in K :
*: 그리고 각 새로운 \mathit{SubCipher}_1 을 집합 A와 비교한다.

일치하는 항목이 발견되면 k_{f_1},k_{b_1}을 테이블 T에 후보 키 쌍으로 보관한다. T의 쌍을 새로운  쌍에 대해 테스트하여 유효성을 확인한다. 이 새로운 쌍에서 키 쌍이 작동하지 않으면 새로운  쌍에 대해 MITM을 다시 수행한다.

### MITM 복잡도
키 크기가 k인 경우, 이 공격은 2k+1번의 암호화(및 해독)와 O(2k)의 메모리를 사용하여 순방향 계산 결과를 순람표에 저장하는 반면, 순진한 공격은 22·k번의 암호화와 O(1)의 공간이 필요하다.

## 다차원 중간 일치 공격 (MD-MITM)
1D-MITM은 효율적일 수 있지만, 더 정교한 공격인 **다차원 중간 일치 공격**(**MD-MITM**)이 개발되었다.
이는 다른 키로 2회 이상 암호화된 데이터에 선호된다.
(시퀀스의 한 곳에서) 중간에서 만나는 대신, MD-MITM 공격은 암호의 여러 위치에서 순방향 및 역방향 계산을 사용하여 여러 특정 중간 상태에 도달하려고 시도한다.

공격이 블록 암호에 가해져야 한다고 가정하자. 여기서 암호화 및 해독은 이전과 같이 정의된다.

:  C=\mathit{ENC}_{k_n}(\mathit{ENC}_{k_{n-1}}(...(\mathit{ENC}_{k_1}(P))...)) 
:  P=\mathit{DEC}_{k_1}(\mathit{DEC}_{k_2}(...(\mathit{DEC}_{k_n}(C))...))
즉, 평문 P가 동일한 블록 암호를 반복 사용하여 여러 번 암호화된다.

섬네일|center|upright=4|MD-MITM 공격의 그림

MD-MITM은 GOST 블록 암호를 비롯한 여러 암호의 암호 해독에 사용되었으며, 3D-MITM이 해당 공격의 시간 복잡도를 크게 줄이는 것으로 나타났다.

### MD-MITM 알고리즘

다음 사항을 계산한다:
:;  \mathit{SubCipher}_1=\mathit{ENC}_{f_1}(k_{f_1},P)\qquad\forall k_{f_1}  \in K 
:: 그리고 각 \mathit{SubCipher}_1을 해당 k_{f_1}과 함께 집합 H_1에 저장한다.

:;  \mathit{SubCipher}_{n+1}=\mathit{DEC}_{b_{n+1}}(k_{b_{n+1}},C) \qquad\forall k_{b_{n+1}}  \in K 
:: 그리고 각 \mathit{SubCipher}_{n+1}을 해당 k_{b_{n+1}}과 함께 집합 H_{n+1}에 저장한다.
중간 상태 s_1에 대한 각 가능한 추측에 대해 다음을 계산한다:

:;  \mathit{SubCipher}_1=\mathit{DEC}_{b_1}(k_{b_1},s_1) \qquad\forall k_{b_1}  \in K
:: 그리고 이  \mathit{SubCipher}_1 과 집합  H_1  간의 각 일치에 대해,  k_{b_1} 과  k_{f_1} 을 새로운 집합  T_1 에 저장한다.

:;  \mathit{SubCipher}_2=\mathit{ENC}_{f_2}(k_{f_2},s_1) \qquad\forall k_{f_2}  \in K 
:: 그리고 각  \mathit{SubCipher}_2 를 해당  k_{f_2} 와 함께 집합  H_2에 저장한다.
: 중간 상태  s_2 에 대한 각 가능한 추측에 대해 다음을 계산한다:
:*  \mathit{SubCipher}_2=\mathit{DEC}_{b_2}(k_{b_2},s_2) \qquad\forall k_{b_2}  \in K 
:*: 그리고 이  \mathit{SubCipher}_2 와 집합  H_2  간의 각 일치에 대해,  T_1 과도 일치하는지 확인한 다음 서브 키의 조합을 새로운 집합  T_2 에 함께 저장한다.
:* 중간 상태  s_n 에 대한 각 가능한 추측에 대해 다음을 계산한다:
 \in K 그리고 이 \mathit{SubCipher}_{n+1}과 집합 H_{n+1} 간의 각 일치에 대해,
T_n과도 일치하는지 확인한다. 만약 그렇다면:"
}}
찾아낸 서브 키의 조합 (k_{f_1},k_{b_1},k_{f_2},k_{b_2}, ... ,k_{f_{n+1}},k_{b_{n+1}})을 다른 평문/암호문 쌍에 적용하여 키의 정확성을 확인한다.

알고리즘에서 중첩된 요소를 주목하자. sj의 모든 가능한 값에 대한 추측은 이전 sj-1에 대한 각 추측에 대해 수행된다.
이는 이 MD-MITM 공격의 전체 시간 복잡도에 기하급수적 복잡도의 요소를 구성한다.

### MD-MITM 복잡도
무차별 대입 없이 이 공격의 시간 복잡도는 2^+2^+2^⋅(2^+2^+2^⋅(2^+2^+\cdots))이다.

메모리 복잡도와 관련하여, T_2,T_3,... ,T_n이 첫 번째로 구축된 후보 값 테이블 T_1보다 훨씬 작다는 것을 쉽게 알 수 있다. i가 증가함에 따라 T_i에 포함된 후보 값은 더 많은 조건을 만족해야 하므로 최종 목적지 T_n으로 통과하는 후보는 더 적을 것이다.

MD-MITM의 메모리 복잡도 상한은 다음과 같다.

: 2^+2^+2^\cdots

여기서 는 전체 키(결합된 키)의 길이를 나타낸다.

데이터 복잡도는 잘못된 키가 통과할 확률(오류 양성)에 따라 달라지며, 이는 1/2^이다. 여기서 은 첫 번째 MITM 단계의 중간 상태이다. 중간 상태의 크기와 블록 크기는 종종 같다!
첫 번째 MITM 단계 후에 테스트를 위해 남아있는 키의 수도 고려하면 2^/2^이다.

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

키의 최종 후보 값이 새로운 평문/암호문 쌍에 대해 테스트될 때마다 통과할 키의 수는 키가 통과할 확률 1/2^을 곱한 값이 된다.

무차별 대입 테스트(새로운 -쌍에 대해 후보 키를 테스트하는 것)의 시간 복잡도는 2^{|k|-b}+2^{|k|-2b}+2^{|k|-3b}+2^{|k|-4b}\cdots
이며, 지수에서 b의 배수가 증가할수록 숫자는 0에 수렴한다.

데이터 복잡도에 대한 결론은 유사한 추론에 의해 약 \lceil|k|/n\rceil개의 -쌍으로 제한된다.

아래는 2D-MITM이 어떻게 장착되는지에 대한 구체적인 예이다:

## 2D-MITM의 일반적인 예

이것은 블록 암호 암호화에 2D-MITM이 어떻게 장착되는지에 대한 일반적인 설명이다.

2차원 MITM(2D-MITM)에서는 평문의 다중 암호화 내에서 2개의 중간 상태에 도달하는 방식이다. 아래 그림을 참조하라:

섬네일|upright=2|2D-MITM 공격의 그림

### 2D-MITM 알고리즘
다음 사항을 계산한다:
:;  \mathit{SubCipher}_1=\mathit{ENC}_{f_1}(k_{f_1},P) \qquad \forall k_{f_1}  \in K 
:: 그리고 각  \mathit{SubCipher}_1 을 해당  k_{f_1} 과 함께 집합 A에 저장한다.
:;  \mathit{SubCipher}_2=\mathit{DEC}_{b_2}(k_{b_2},C) \qquad \forall k_{b_2}  \in K 
:: 그리고 각  \mathit{SubCipher}_2 를 해당  k_{b_2} 와 함께 집합 B에 저장한다.

\mathit{SubCipher}_1과 \mathit{SubCipher}_2 사이의 중간 상태 s에 대한 각 가능한 추측에 대해 다음을 계산한다:

*   \mathit{SubCipher}_1=\mathit{DEC}_{b_1}(k_{b_1},s) \qquad \forall k_{b_1}  \in K 
*: 그리고 이 \mathit{SubCipher}_1과 집합 A 간의 각 일치에 대해, k_{b_1}과 k_{f_1}을 새로운 집합 T에 저장한다.
*  \mathit{SubCipher}_2=\mathit{ENC}_{f_2}(k_{f_2},s)  \qquad \forall k_{f_2}  \in K 
*: 그리고 이 \mathit{SubCipher}_2와 집합 B 간의 각 일치에 대해, T와도 일치하는지 확인한다.
*: 만약 그렇다면:

찾아낸 서브 키의 조합 (k_{f_1},k_{b_1},k_{f_2},k_{b_2})을 다른 평문/암호문 쌍에 적용하여 키의 정확성을 확인한다.

### 2D-MITM 복잡도
무차별 대입 없이 이 공격의 시간 복잡도는
: 2^ + 2^ + 2^ \cdot \left(2^ + 2^\right)
여기서 |⋅|는 길이를 나타낸다.

주요 메모리 소비는 A와 B 집합의 구성에 의해 제한되며, T는 다른 것들보다 훨씬 작다.

데이터 복잡도는 MD-MITM 복잡도 하위 섹션을 참조하라.

## 같이 보기
* 생일 공격
* 무선 보안
* 암호학

## 각주

분류:암호 공격