선형 암호 분석이란?
선형 암호 분석(Linear Cryptanalysis)은 기지 평문 공격(known-plaintext attack)의 일종으로, 공격자가 평문·암호문·숨겨진 키의 패리티 비트들 사이에 성립하는 확률적 선형 관계, 이른바 '선형 근사(linear approximation)'를 분석하는 기법입니다.
공격자는 알려진 평문과 암호문의 패리티 비트를 계산함으로써 숨겨진 키의 패리티 비트에 대한 높은 확률의 근사식을 얻습니다. 여기에 보조 기법 등 다양한 방법을 결합하면 공격 범위를 넓혀 비밀 키의 추가 비트까지 알아낼 수 있습니다.
차분 암호 분석과의 관계
선형 암호 분석은 차분 암호 분석(differential cryptanalysis)과 함께 블록 암호에 가장 널리 사용되는 공격 기법으로 꼽힙니다. 이 기법은 미쓰루 마쓰이(Mitsuru Matsui)가 처음 고안했으며, FEAL 암호에 처음으로 적용되었습니다.
선형 암호 분석의 두 단계
선형 암호 분석은 일반적으로 다음 두 부분으로 구성됩니다.
- 선형 방정식 작성: 평문, 암호문, 키 비트를 연결하는 선형 방정식 중 편향(bias)이 큰 것, 즉 성립 확률이 0 또는 1에 최대한 가까운 식을 찾아냅니다.
- 키 비트 도출: 찾아낸 선형 방정식을 알려진 평문-암호문 쌍과 함께 활용해 키 비트를 역산합니다.
동작 원리
선형 암호 분석은 암호화 과정 내부의 비선형 연산을 선형 근사로 모델링합니다. 대량의 알려진 평문에 근사식을 적용하면 특정 확률로 정확한 키 비트를 하나씩 찾아낼 수 있으며, 암호 알고리즘의 특성에 맞게 기법을 세분화하면 여러 키 비트를 동시에 복원할 수도 있습니다.
DES에 대한 적용
선형 암호 분석 공격은 데이터 암호화 표준(DES) 내부 변환을 기술하는 선형 근사를 발견하는 데 기반합니다. 이 방법은 2⁴³개의 알려진 평문만 있으면 DES 키를 복원할 수 있는 반면, 차분 암호 분석은 2⁴⁷개의 선택 평문(chosen plaintext)을 필요로 합니다.
선택 평문보다 알려진 평문을 확보하기가 상대적으로 쉽다는 점에서 의미 있는 진전이지만, 그럼에도 불구하고 선형 암호 분석이 현실적으로 DES를 공격하기에는 여전히 큰 어려움이 따릅니다.
목표 방정식과 판별 과정
선형 암호 분석의 목표는 다음과 같은 형태의 유효한 선형 방정식을 찾는 것입니다.
P[α₁, α₂, …, αₐ] ⊕ C[β₁, β₂, …, β_b] = K[γ₁, γ₂, …, γ_c]
(여기서 x = 0 또는 1, 1 ≤ a, b ≤ n, 1 ≤ c ≤ m이며, α, β, γ는 고정된 특정 비트 위치를 나타냅니다.) 이 식은 확률 p ≠ 0.5로 성립하며, p가 0.5에서 멀어질수록 방정식의 효과가 커집니다.
유력한 관계식이 결정되면, 다음 단계는 다수의 평문-암호문 쌍에 대해 위 식의 좌변 값을 계산하는 것입니다. 결과가 절반 이상 0이면 K[γ₁, γ₂, …, γ_c] = 0으로 가정하고, 대부분 1이면 K[γ₁, γ₂, …, γ_c] = 1로 가정합니다. 이렇게 얻은 키 비트에 대한 선형 방정식을 여러 개 확보하면 이를 연립하여 키 비트를 구할 수 있습니다. 선형 방정식을 다루는 만큼, 문제를 한 라운드씩 나누어 접근한 뒤 결과를 연결하는 방식으로 효율적으로 해결할 수 있습니다.