블록암호를 무너뜨리는 암호분석 기법과 설계 방어

평문과 암호문의 관계에서 시작되는 분석

블록암호를 공격하는 방법은 알고리즘의 약점을 찾고 키를 복구하는 데 초점을 둔다. 평문과 암호문 사이의 차이, 통계적 편향, 키 공간의 크기, 알고리즘 내부의 수학적 구조가 모두 분석 대상이 된다. 이런 공격 모델을 알아야 암호 시스템을 설계하거나 평가할 때 무엇을 방어해야 하는지 판단할 수 있다.

차이를 추적해 라운드 키를 좁히는 차분공격

Eli Biham과 Adi Shamir가 1990년에 개발한 차분공격(Differential Cryptanalysis)은 선택된 평문 공격(chosen-plaintext attack) 방식이다. 비트 차이가 있는 두 평문 블록을 만들고, 그 결과로 나온 암호문 블록의 비트 차이를 비교해 암호 내부 연산의 특성을 찾는다.

분석은 특정 비트 패턴 차이를 가진 평문 쌍을 선택하는 데서 시작한다. 각 평문을 암호화해 암호문 쌍을 얻은 뒤 차이 패턴을 분석하고, 통계적 방법으로 사용된 암호 키를 추론한다.

차분공격은 DES 같은 초기 블록암호에 특히 효과적이었고, DES를 개선한 3DES 및 AES와 같은 새 암호 알고리즘 개발을 촉진했다.

⤢✕

DES에서는 16라운드 전체 대신 약 247번의 암호화 작업으로 키를 찾아낼 수 있어 전수조사(256)보다 효율적이다.

선형 근사와 편향으로 키 비트를 찾는 방법

Mitsuru Matsui가 1993년에 개발한 선형공격(Linear Cryptanalysis)은 알려진 평문 공격(known-plaintext attack) 방식이다. 암호 알고리즘 내부의 비선형 구조를 선형적 근사로 모델링하고, 평문 비트와 암호문 비트 사이의 관계를 이용한다.

공격자는 대량의 알려진 평문-암호문 쌍을 수집한 다음 선형식을 적용한다. 여기서 나타나는 키 비트별 통계적 편향을 분석해 가장 가능성 높은 키 비트 조합을 추론한다. DES는 243개의 알려진 평문이 있으면 이 공격이 성공할 수 있어 전수조사보다 효율적이다.

⤢✕

키 공간을 모두 탐색하는 전수공격

Whitfield Diffie와 Martin Hellman은 1977년에 가능한 모든 키 조합을 시도하는 전수공격(Brute Force Attack)을 체계적으로 제안했다. 알려진 평문-암호문 쌍을 확보한 뒤 후보 키를 순차적으로 적용하고, 암호화 결과가 알려진 암호문과 일치하면 올바른 키로 판단한다.

전수공격의 복잡도는 키 공간 크기에 직접 비례한다. 현대 암호가 128비트 이상의 키를 사용하는 이유도 전수공격을 실질적으로 불가능하게 만들기 위해서다.

키 길이	가능한 키 조합 수	초당 10억 키 시도 시 소요 시간
40비트	2^40 (약 1조)	약 18분
56비트	2^56 (약 7경)	약 2.28년
128비트	2^128	약 10^21년
256비트	2^256	우주 나이보다 훨씬 긴 시간

통계적 특성이 드러내는 암호문의 흔적

통계적 분석 공격(Statistical Analysis)은 암호문과 평문 사이에 남는 통계적 특성을 활용한다. 문자나 단어의 출현 빈도를 이용하는 빈도 분석, 반복 패턴으로 키 특성을 추론하는 패턴 인식, 암호문에 나타나는 확률적 편향을 보는 확률적 모델링이 여기에 포함된다.

이 방식은 대체 암호(substitution cipher) 같은 고전 암호에서 특히 효과적이다. 현대 블록암호는 혼돈(confusion)과 확산(diffusion) 속성을 통해 이런 분석에 저항하도록 설계된다.

⤢✕

알고리즘 구조 자체를 겨냥하는 수학적 분석

수학적 분석 공격(Mathematical Analysis)은 암호 알고리즘의 수학적 구조와 특성을 분석해 취약점을 찾는다. 대수적 분석은 알고리즘 구조를 대수학적으로 다루며, 그룹 이론은 암호 연산의 그룹 특성을 활용한다. 대수적 공격에서는 암호 알고리즘을 다항식 방정식 시스템으로 모델링한다.

이 접근은 통계적 분석을 포함하는 더 포괄적인 분석 틀로서, 현대 암호 알고리즘의 취약점을 찾는 이론적 기반이 된다.

⤢✕

기본 분석을 확장한 현대 공격 기법

현대 블록암호 분석은 기본 방법론을 확장하거나 결합하는 방향으로 발전했다.

관련 키 공격(Related-key attack)은 여러 관련된 키로 암호화된 암호문 사이의 관계를 분석해 키 스케줄링 알고리즘의 취약점을 노린다. 부채널 공격(Side-channel attack)은 전력 소비, 전자기 방사, 시간 같은 암호 구현의 물리적 특성을 측정하고, 암호화 과정에서 누출되는 부가 정보를 활용한다.

중간 만남 공격(Meet-in-the-middle attack)은 서로 다른 두 키를 사용하는 이중 암호화에 효과적이다. 전방과 후방에서 동시에 공격해 계산 복잡도를 낮춘다. 양자 컴퓨팅 공격(Quantum computing attack)은 Grover의 알고리즘을 통해 전수공격 복잡도를 O(2^n)에서 O(2^(n/2))로 낮추며, 현재 블록암호의 키 길이 증가 필요성을 제기한다.

공격 모델을 견디는 블록암호 설계

블록암호는 충분한 라운드 수로 차분 및 선형 공격에 대한 저항성을 높인다. AES는 10, 12, 14 라운드를 사용한다.

S-박스는 비선형성을 최대화하고 차분 및 선형 특성을 최소화하도록 설계한다. 확산은 한 비트의 변화가 다른 많은 비트에 영향을 미치게 하며, 눈사태 효과(Avalanche effect)를 극대화한다. 키 스케줄링에서는 라운드 키 사이의 충분한 독립성을 보장해 관련 키 공격에 대한 저항성을 강화한다.

블록암호 분석은 알고리즘의 약점을 찾는 작업인 동시에 더 안전한 암호 시스템을 만드는 기반이다. 양자 컴퓨팅의 발전은 기존 암호 체계의 안전성을 위협할 수 있으며, 포스트 양자 암호학(Post-Quantum Cryptography) 같은 새로운 접근법도 연구되고 있다.