선형 공격

선형 공격(linear cryptanalysis)은 암호 공격의 한 방법으로, 암호화 과정에서의 근사적 선형 관계식을 찾는 것을 목적으로 한다.

선형 공격은 마쓰이 미쓰루(松井 充)의 논문에서 처음 공개되었으며, 해당 논문에서는 선형 공격으로 FEAL 암호를 공격하는 방법을 제시했다.

선형 공격은 차분 공격과 함께 블록 암호를 공격하는 방법으로 널리 응용된다.

공격 방법

선형 공격은 먼저 암호화 과정에서의 근사적인 선형 관계성을 찾는다. 어떤 암호화 함수가 입력값 $P=(P_{1},\cdots ,P_{n})$와 암호화 키 $K=(K_{1},\cdots ,K_{k})$를 받아 암호화된 출력값 $C=(C_{1},\cdots ,C_{n})$을 반환한다고 할 때,

$P_{i_{1}}\oplus P_{i_{2}}\oplus \cdots \oplus C_{j_{1}}\oplus C_{j_{2}}\oplus \cdots =K_{k_{1}}\oplus K_{k_{2}}\oplus \cdots$

과 같은 형태의 관계식들이 어떤 확률로 성립하는지를 관측한다. 이상적인 암호화 함수는 이 확률이 1/2이어야 하지만, 암호화 방법에 따라서 이 확률이 1/2과 크게 다를 수 있다.

이러한 선형 관계식을 찾는 방법은 암호화 과정에 따라 다르다. 대입-혼합 네트워크(substitution-permutation network)의 경우 혼합 과정은 선형적이며, S-박스에서의 대입 과정에서만 비선형적인 변환이 일어난다. 따라서 S-박스의 연산을 선형 과정으로 근사화할 방법을 찾는 것이 목표가 된다.

근사 선형 관계성을 찾았다면, 이를 통해 chosen-plaintext 공격을 수행할 수 있다. 암호화 모듈에 임의의 입력값을 입력할 수 있을 때, 관계식에서 입력값 부분과 출력값 부분이 얼마나 일치하는지 횟수를 측정한다. 이 횟수를 기반으로 암호화 키 비트들에 대한 관계식을 확률적으로 추정할 수 있다.