분할 정복 (Divide and Conquer)

분할 정복(Divide and Conquer)은 복잡한 문제를 여러 부분으로 나누어 각 부분을 해결함으로써 전체 문제를 해결하는 일반적인 개념입니다. 각 부분은 전체보다 자연스럽게 단순합니다. 이는 대부분의 암호 시스템이 덜 복잡한 부분으로 구성되어 있기 때문에 암호 시스템에서 특히 위험합니다. 공격자가 암호를 서로 독립적으로 공격할 수 있는 부분으로 쪼갤 수 있다면 전체를 한 번에 깨는 것보다 훨씬 적은 노력으로 해독할 수 있습니다. 실제로 암호 설계의 주요 역할은 작은 부분들을 분리할 수 없는 더 큰 복잡한 시스템으로 결합하는 것입니다.

공격 전략으로서의 분할 정복

핵심은 작업량의 차이입니다. 키가 k비트이면 전수 조사에는 약 2^k번의 시도가 필요합니다. 그런데 키를 k₁비트와 k₂비트의 두 부분으로 나누고 각 부분이 맞았는지를 따로 확인할 수 있다면, 작업량은 2^k₁ + 2^k₂로 줄어듭니다. 128비트 키를 64비트 두 조각으로 나눠 공격할 수 있다면 2¹²⁸이 아니라 약 2⁶⁵번의 시도로 충분해집니다.

대표적인 예

• 중간 일치 공격(meet-in-the-middle): DES를 서로 다른 두 키로 두 번 적용한 이중 DES는 키 길이가 112비트이지만, 공격자는 평문을 첫 번째 키로 암호화한 결과와 암호문을 두 번째 키로 복호화한 결과를 중간에서 맞춰 봅니다. 그 결과 약 2⁵⁷번의 연산(과 큰 메모리)으로 키를 찾을 수 있어, 112비트가 아닌 56비트 수준의 안전성에 머뭅니다. 그래서 실무에서는 삼중 DES가 쓰였습니다.
• 상관 공격: 여러 개의 LFSR(선형 되먹임 시프트 레지스터) 출력을 결합하는 스트림 암호에서, 출력이 특정 LFSR 하나와 통계적으로 상관되어 있으면 그 LFSR의 초기값만 따로 추측해 맞출 수 있습니다. 레지스터를 하나씩 공략하므로 전체 키를 한꺼번에 찾을 필요가 없습니다.
• 부채널 공격: 전력 소비나 처리 시간 같은 물리 정보를 이용하는 공격은 흔히 키를 한 바이트씩 따로 추정합니다. AES-128 키를 16바이트 각각 2⁸가지 후보 안에서 맞히면, 2¹²⁸이 아닌 16 × 2⁸ 수준의 작업으로 키를 복원할 수 있습니다.

암호 설계의 역할

암호 설계자의 과제는 공격자가 이런 분할 지점을 찾지 못하게 하는 것입니다.

• 확산과 혼돈: 키와 평문의 각 비트가 출력의 많은 비트에 복잡하게 영향을 주도록 치환과 순열을 여러 라운드 반복합니다(섀넌의 확산·혼돈 원리). 그러면 키의 일부만 맞혔는지를 출력에서 따로 확인할 수 없습니다.
• 안전한 결합: 치환, 순열 같은 단순한 구성 요소는 각각 약점이 있을 수 있으므로, 부분을 따로 공격해서는 전체를 깨기 어려운 방식으로 결합합니다.
• 분할 지점 점검: 설계와 분석 단계에서 독립적으로 공격 가능한 부분이 없는지 확인하고, 구현 단계에서는 부채널 대응책(상수 시간 연산, 마스킹 등)을 적용합니다.

일반적인 문제 해결 기법과의 구분

컴퓨터 과학에서 분할 정복은 병합 정렬처럼 문제를 나누어 효율적으로 푸는 알고리즘 설계 기법이기도 합니다. 암호 설계자도 구성 요소를 나누어 설계하고 분석합니다. 다만 암호학 용어로서 분할 정복은 주로 공격자가 시스템을 독립적인 부분으로 나누어 공략하는 전략을 뜻하며, 좋은 암호는 이런 분할을 허용하지 않습니다.