선형 공격 (Linear Cryptanalysis)
한 줄 정의: 평문·암호문·키 비트 사이에 성립하는 근사적 선형 관계의 통계적 편향을 대량 표본으로 축적해 키 비트를 추정하는 대칭키 암호분석 기법입니다.
쉽게 풀면
암호는 원래 입력과 출력의 관계를 아주 복잡하게 뒤섞어야 하는데, 완벽하지 않으면 '평문 몇 비트와 암호문 몇 비트를 XOR하면 절반보다 조금 더 자주 0이 된다' 같은 미약한 규칙이 남습니다. 선형 공격은 이 근사적 규칙을 엄청나게 많은 데이터로 관찰해 키를 알아냅니다.
왜 중요한가
선형 공격은 알려진 평문만 있으면 되어 차분 공격보다 현실적인 경우가 많고, DES에 대한 최초의 이론적 실전 공격으로 알려졌습니다. 오늘날 모든 블록 암호는 선형 공격 저항성을 설계 단계에서 정량적으로 검증합니다.
논문에서는 이렇게 쓰입니다
"S-박스의 선형 근사 확률이 이상적인 1/2에서 얼마나 벗어나는지를 계산해, 전체 암호의 선형 편향과 필요한 평문 수를 추정하였다."
조금 더 깊게 보면
선형 공격의 위력은 선형 근사가 이상적인 확률 1/2에서 얼마나 벗어나는지를 나타내는 '편향'에 달려 있으며, 필요한 알려진 평문의 수는 이 편향의 제곱에 반비례합니다. 여러 라운드를 지나면 편향이 급감하므로 라운드 수가 방어의 핵심입니다. 차분 공격이 선택 평문을 요구하는 것과 달리 선형 공격은 알려진 평문 공격 모형에서 동작한다는 차이가 있습니다.
주의할 점
선형 공격은 차분 공격과 짝을 이루는 개념이지만, 이용하는 성질(선형 근사 대 차분 전파)과 공격 모형이 다릅니다. 실제 실행에는 방대한 평문 표본이 필요하다는 점도 유의해야 합니다.