중간자 공격과 시간-메모리 절충

MITM 공격은 암호를 두 부분으로 나누어 각각 독립적으로 공격합니다. 공격자는 한쪽 끝에서 표를 만든 다음 다른 쪽 끝에서 일치 항목을 검색합니다. O(2^n) 메모리를 사용하는 대신 공격 복잡도를 O(2^{2n})에서 O(2^n)으로 줄입니다.

Double-DES는 DES를 두 번 적용합니다: C = DES_{K2}(DES_{K1}(P)). 키 공간은 2^{112}입니다. MITM 공격에서는 가능한 모든 2^{56}개의 K1 값에 대해 DES_{K1}(P)를 계산하여 저장합니다. 가능한 모든 2^{56}개의 K2 값에 대해 DES_{K2}^{-1}(C)를 계산하고 표에서 조회합니다. 일치 항목 → (K1, K2) 후보입니다. 총 작업량은 2^{57}에 불과합니다.

1단계: 가능한 모든 K1으로 평문 P를 암호화하여 T[DES_{K1}(P)] = K1인 표를 만듭니다. 2단계: 각 K2에 대해 암호문 C를 복호화합니다: v = DES^{-1}_{K2}(C). v ∈ T인지 확인합니다. T[v] = K1이 존재하면 두 번째 평문-암호문 쌍에서 (K1, K2)를 검증합니다. 예상되는 오탐 일치는 1~2개이므로 폐기합니다.

Triple-DES(3DES)는 K1, K2, K3 세 개의 키를 사용합니다: C = DES_{K3}(DES^{-1}_{K2}(DES_{K1}(P))). MITM은 여전히 적용되지만 효과는 더 약합니다. 두 키 3DES(K3=K1)는 작업량 2^{112}로 감소합니다. 세 키 3DES에는 2^{112}의 MITM 공격이 존재하므로, 키가 168비트인데도 3DES의 유효 보안 수준이 약 112비트에 불과한 이유를 설명할 수 있습니다.

Hellman(1980): 오프라인 키 검색을 빠르게 하기 위해 (start_point, end_point) 체인의 표를 미리 계산합니다. 대상 해시 또는 암호문이 주어지면 Hellman 표에서 이를 포함하는 체인을 검색합니다. 절충 관계: P = N(시간 × 메모리 = 공간 상수). 무지개 표의 기반이 되는 방법입니다.

무지개 표(Oechslin, 2003)는 각 체인 위치에서 서로 다른 축약 함수를 사용하여 Hellman 표를 개선하고, 오탐(병합된 체인)을 제거합니다. 솔트가 없는 비밀번호 해시를 해독하는 데 효율적입니다. 조회에는 O(표 크기/체인 길이)의 시간이 걸립니다.

솔트는 해싱 전에 비밀번호 앞에 붙이는 무작위 값입니다: H(salt||password). 서로 다른 솔트를 사용하면 같은 비밀번호라도 서로 다른 해시가 생성되므로, 다른 솔트를 사용했다면 "password"에 대한 무지개 표는 아무 소용이 없습니다. 솔트는 해시와 함께 저장해야 합니다.

AES-128(10라운드)에 대한 MITM 공격은 5라운드에서 나눕니다. 5라운드를 정방향으로 암호화하고 5라운드를 역방향으로 복호화하여 중간에서 만납니다. 알려진 최선의 공격인 쌍선형 공격은 2^{128}을 2^{126.1}로 줄이지만 실용적이지 않습니다. 그러나 AES에 MITM 방식에 대한 보안 여유가 없다는 점을 보여 줍니다.

Merkle-Damgard 해시에서는 일부 구성에 대해 MITM으로 완전 탐색보다 빠르게 프리이미지를 찾을 수 있습니다. 공격 방법은 IV에서 시작하는 메시지 블록으로 표를 만들고 대상 해시에서 역방향으로 검색하는 것입니다. 전체 라운드의 SHA-256에 대해서는 여전히 ~2^{255}이므로 완전 탐색보다 나아지지 않습니다.

분할 공격은 MITM을 r방향 분할로 일반화합니다. 암호를 3방향으로 나누는 경우 라운드의 1/3을 정방향으로 암호화하고, 체인의 중간에서 만난 다음, 1/3을 역방향으로 복호화합니다. O(2^{n*2/3}) 시간과 O(2^{n/3}) 메모리가 필요하므로 더욱 균형 잡힌 절충이 가능합니다.

프로토콜에서는 엔트로피가 높은 비밀번호에서 KDF로 파생한 긴 키를 사용하거나(열거할 수 있는 키 공간을 줄임), 키가 장치를 벗어나지 않는 하드웨어 토큰(FIDO2)을 사용하거나, 공개 키 인증을 사용하여(열거할 공유 비밀이 없음) MITM 공격을 방지할 수 있습니다.

Double-DES(2배 DES, 결합 키 112비트)의 MITM 공격에 대한 유효 보안 수준은 얼마입니까?

MITM 공격은 암호를 절반으로 나누어 2^n 메모리를 사용하는 대신 시간을 2^{2n}에서 2^n으로 줄입니다. Double-DES를 무력화하며, 3DES는 완화되지만 유효 보안 수준은 112비트입니다. 무지개 표는 비밀번호 해독에 MITM 논리를 사용하며 솔트를 사용하면 이를 막을 수 있습니다. 다음 주제: 타이밍 공격과 부채널 공격입니다.