중간 일치 공격

중간자 공격 **중간 일치 공격**(Meet-in-the-middle attack, **MITM**)은 알려진 평문 공격의 일종으로,title=Crypto-IT 여러 암호화 연산을 순차적으로 수행하는 암호화 방식에 대한 일반적인 시간-공간 트레이드오프 암호학적 공격이다. MITM 공격은 이중 DES가 사용되지 않는 주된 이유이며, 삼중 DES 키(168비트)가 256의 공간과 2112의 연산으로 공격자에 의해 무차별 대입될 수 있는 이유이다.
# 설명
블록 암호의 보안을 개선하려고 할 때, 여러 키를 사용하여 데이터를 여러 번 암호화하는 것은 매력적인 아이디어이다. 데이터가 k-비트 키로 n번 암호화될 경우, 모든 가능한 키 조합에 대한 완전 탐색(단순 무차별 대입)은 2n·k번의 시도가 필요하므로, 이는 다중 암호화 방식의 보안을 두 배 또는 n배로 늘린다고 생각할 수 있다. MITM 공격은 암호화 또는 해독의 중간 값을 저장하고 이를 활용하여 해독 키를 무차별 대입하는 데 필요한 시간을 줄임으로써 다중 암호화 사용의 보안 이점을 약화시키는 일반적인 공격이다. 이는 중간 일치 공격(MITM)을 일반적인 시간-공간 트레이드오프 암호학적 공격으로 만든다. MITM 공격은 여러 함수(또는 블록 암호)의 구성에서 첫 번째 함수를 통한 순방향 매핑이 마지막 함수를 통한 역방향 매핑(역상)과 동일하여 구성 함수의 중간에서 말 그대로 만나는 방식으로 키를 찾으려 한다. 예를 들어, 이중 DES는 두 개의 다른 56비트 키로 데이터를 암호화하지만, 이중 DES는 257번의 암호화 및 해독 연산으로 해독될 수 있다. 다차원 MITM(MD-MITM)은 위에서 설명한 여러 동시 MITM 공격의 조합을 사용하며, 만남은 구성 함수의 여러 위치에서 발생한다.
# 역사
휫필드 디피와 마틴 헬먼은 1977년 블록 암호의 가상적인 확장에 대해 중간 일치 공격을 처음 제안했다.dh-exh url=https://www-ee.stanford.edu/~hellman/publications/27.pdf 그들의 공격은 시간-공간 트레이드오프를 사용하여 단일 암호화 체계를 해독하는 데 필요한 시간의 두 배만으로 이중 암호화 체계를 해독했다. 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 연산으로 중간 일치 공격에 취약하지만, 키 공간의 크기 때문에 안전하다고 간주된다.url=http://stephanemoore.com/pdf/meetinthemiddle.pdfurl-status=dead 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의 쌍을 새로운 (P,C) 쌍에 대해 테스트하여 유효성을 확인한다. 이 새로운 쌍에서 키 쌍이 작동하지 않으면 새로운 (P,C) 쌍에 대해 MITM을 다시 수행한다.
## MITM 복잡도
키 크기가 k인 경우, 이 공격은 2k+1번의 암호화(및 해독)와 O(2k)의 메모리를 사용하여 순방향 계산 결과를 순람표에 저장하는 반면, 순진한 공격은 22·k번의 암호화와 O(1)의 공간이 필요하다.
# 다차원 중간 일치 공격 (MD-MITM)
1D-MITM은 효율적일 수 있지만, 더 정교한 공격인 **다차원 중간 일치 공격**(**MD-MITM**)이 개발되었다. 이는 다른 키로 2회 이상 암호화된 데이터에 선호된다. (시퀀스의 한 곳에서) 중간에서 만나는 대신, MD-MITM 공격은 암호의 여러 위치에서 순방향 및 역방향 계산을 사용하여 여러 특정 중간 상태에 도달하려고 시도한다.url-access=subscription 공격이 블록 암호에 가해져야 한다고 가정하자. 여기서 암호화 및 해독은 이전과 같이 정의된다. : 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가 동일한 블록 암호를 반복 사용하여 여러 번 암호화된다. 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 date=May 2015 :: 그리고 각 \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 에 대한 각 가능한 추측에 대해 다음을 계산한다: \mathit{SubCipher}_{n+1}=\mathit{ENC}_{f_n+1}(k_{f_n+1},s_n) \qquad\forall k_{f_{n+1 \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^{|k_{f_1}|}+2^{|k_{b_{n+1|}+2^{|s_1|}⋅(2^{|k_{b_1}|}+2^{|k_{f_2}|}+2^{|s_2|}⋅(2^{|k_{b_2}|}+2^{|k_{f_3}|}+\cdots))이다. 메모리 복잡도와 관련하여, T_2,T_3,... ,T_n이 첫 번째로 구축된 후보 값 테이블 T_1보다 훨씬 작다는 것을 쉽게 알 수 있다. i가 증가함에 따라 T_i에 포함된 후보 값은 더 많은 조건을 만족해야 하므로 최종 목적지 T_n으로 통과하는 후보는 더 적을 것이다. MD-MITM의 메모리 복잡도 상한은 다음과 같다. : 2^{|k_{f_1}|}+2^{|k_{b_{n+1|}+2^{|k|-|s_n|}\cdots 여기서 k는 전체 키(결합된 키)의 길이를 나타낸다. 데이터 복잡도는 잘못된 키가 통과할 확률(오류 양성)에 따라 달라지며, 이는 1/2^{|l|}이다. 여기서 l은 첫 번째 MITM 단계의 중간 상태이다. 중간 상태의 크기와 블록 크기는 종종 같다! 첫 번째 MITM 단계 후에 테스트를 위해 남아있는 키의 수도 고려하면 2^{|k|}/2^{|l|}이다. 따라서 첫 번째 MITM 단계 후에는 2^{|k|-b} \cdot 2^{-b} = 2^{|k|-2b}가 되며, 여기서 |b|는 블록 크기이다. 키의 최종 후보 값이 새로운 평문/암호문 쌍에 대해 테스트될 때마다 통과할 키의 수는 키가 통과할 확률 1/2^{|b|}을 곱한 값이 된다. 무차별 대입 테스트(새로운 (P,C)-쌍에 대해 후보 키를 테스트하는 것)의 시간 복잡도는 2^{|k|-b}+2^{|k|-2b}+2^{|k|-3b}+2^{|k|-4b}\cdots 이며, 지수에서 b의 배수가 증가할수록 숫자는 0에 수렴한다. 데이터 복잡도에 대한 결론은 유사한 추론에 의해 약 \lceil|k|/n\rceil개의 (P,C)-쌍으로 제한된다. 아래는 2D-MITM이 어떻게 장착되는지에 대한 구체적인 예이다:
# 2D-MITM의 일반적인 예
이것은 블록 암호 암호화에 2D-MITM이 어떻게 장착되는지에 대한 일반적인 설명이다. 2차원 MITM(2D-MITM)에서는 평문의 다중 암호화 내에서 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^{|k_{f_1}|} + 2^{|k_{b_2}|} + 2^{|s|} \cdot \left(2^{|k_{b_1}|} + 2^{|k_{f_2}|}\right) 여기서 |⋅|는 길이를 나타낸다. 주요 메모리 소비는 A와 B 집합의 구성에 의해 제한되며, T는 다른 것들보다 훨씬 작다. 데이터 복잡도는 MD-MITM 복잡도 하위 섹션을 참조하라.