중간 일치 공격

중간 일치 공격(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에 대해 다음과 같은 특성을 가진 암호화 체계를 공격하려 한다고 가정하자:

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

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

중간 일치 공격은 더 효율적인 접근 방식을 사용한다. C를 k2로 해독하면 다음 등식을 얻는다:

공격자는 모든 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 알고리즘 
다음 사항을 계산한다.
:
 그리고 각 을 해당 과 함께 집합 A에 저장한다.
:
 그리고 각 새로운 을 집합 A와 비교한다.

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

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

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

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



즉, 평문 P가 동일한 블록 암호를 반복 사용하여 여러 번 암호화된다.

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

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

 MD-MITM 알고리즘 

다음 사항을 계산한다:

 그리고 각 을 해당 과 함께 집합 에 저장한다.


 그리고 각 을 해당 과 함께 집합 에 저장한다.
중간 상태 에 대한 각 가능한 추측에 대해 다음을 계산한다:


 그리고 이 과 집합  간의 각 일치에 대해, 과 을 새로운 집합 에 저장한다.


 그리고 각 를 해당 와 함께 집합 에 저장한다.
 중간 상태 에 대한 각 가능한 추측에 대해 다음을 계산한다:

 그리고 이 와 집합  간의 각 일치에 대해, 과도 일치하는지 확인한 다음 서브 키의 조합을 새로운 집합 에 함께 저장한다.
 중간 상태 에 대한 각 가능한 추측에 대해 다음을 계산한다:

찾아낸 서브 키의 조합 을 다른 평문/암호문 쌍에 적용하여 키의 정확성을 확인한다.

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

 MD-MITM 복잡도 
무차별 대입 없이 이 공격의 시간 복잡도는 ⋅⋅이다.

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

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

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

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

따라서 첫 번째 MITM 단계 후에는 가 되며, 여기서 는 블록 크기이다.

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

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

데이터 복잡도에 대한 결론은 유사한 추론에 의해 약 개의 -쌍으로 제한된다.

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

 2D-MITM의 일반적인 예 

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

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

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

 2D-MITM 알고리즘 
다음 사항을 계산한다:

 그리고 각 을 해당 과 함께 집합 A에 저장한다.

 그리고 각 를 해당 와 함께 집합 B에 저장한다.

과  사이의 중간 상태 s에 대한 각 가능한 추측에 대해 다음을 계산한다:


 그리고 이 과 집합 A 간의 각 일치에 대해, 과 을 새로운 집합 T에 저장한다.

 그리고 이 와 집합 B 간의 각 일치에 대해, T와도 일치하는지 확인한다.
 만약 그렇다면:

찾아낸 서브 키의 조합 을 다른 평문/암호문 쌍에 적용하여 키의 정확성을 확인한다.

 2D-MITM 복잡도 
무차별 대입 없이 이 공격의 시간 복잡도는

여기서 |⋅|는 길이를 나타낸다.

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

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

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

 각주 

분류:암호 공격