선형 암호 분석(Linear Cryptanalysis)
선형 암호 분석은 암호 알고리즘의 구성 요소에 대한 아핀 근사식을 찾는 데 기반한 대표적인 암호 분석 기법입니다. 블록 암호와 스트림 암호 모두에 대한 공격이 개발되어 왔으며, 블록 암호에 가장 널리 사용되는 두 가지 공격 기법 중 하나로 꼽힙니다. 나머지 하나는 차분 암호 분석입니다.
선형 암호 분석은 블록 암호 분석에 있어 매우 강력한 도구입니다. 이 기법에서 공격자는 비선형 함수를 확률 1/2가 아닌 값으로 근사하는 선형 표현식을 찾으려고 시도합니다.
평문과 암호문 사이의 관계를 담고 있는 최적의 근사식이 발견되면, 공격자는 비밀 키에 대한 유용한 정보를 얻게 됩니다. 근사식의 형태는 다음과 같습니다.
$$\mathrm{P_{i} \oplus ..\, \oplus P_{j}\oplus C_{k}\oplus C_{1}=k_{m}\oplus k_{n}}$$
여기서 Pi ~ Pj는 평문 비트, Ck ~ Cl은 암호문 비트, Km ~ Kn은 키 비트를 의미합니다. 이 근사식은 어떤 확률 p로 성립하며, 그 품질은 일반적으로 편향(bias)으로 평가합니다. 편향은 ε = |p − 1/2|로 정의됩니다.
차분 암호 분석(Differential Cryptanalysis)
차분 암호 분석은 주로 블록 암호에 적용되지만, 스트림 암호나 암호학적 해시 함수에도 활용할 수 있는 보편적인 암호 분석 기법입니다. 넓은 의미에서 이 기법은 입력 정보의 차이가 출력에서 나타나는 차이에 어떤 영향을 미치는지를 연구합니다.
블록 암호의 경우, 여러 변환 단계를 거치는 동안 차이가 어떻게 전파되는지 추적하여 암호가 비무작위적으로 동작하는 지점을 찾아내고, 이러한 특성을 이용해 비밀 키를 찾아내는 일련의 기법을 의미합니다.
공격이 효과적으로 작동하려면 입력 차이를 신중하게 선택해야 합니다. 알고리즘의 내부 구조를 분석한 뒤, 일반적으로는 여러 단계의 암호화 과정을 통과하며 높은 확률로 나타나는 차이의 경로를 추적하는데, 이를 차분 특성(differential characteristic)이라고 부릅니다.
그렇다면 선형 암호 분석과 차분 암호 분석은 어떤 차이가 있을까요? 아래 표에서 두 기법을 비교해 보겠습니다.
| 선형 암호 분석 | 차분 암호 분석 |
|---|---|
| 기지 평문 공격(known plaintext attack)의 일종으로, 공격자는 평문·암호문·숨겨진 키의 패리티 비트들 사이의 확률적 선형 관계인 '선형 근사식'을 연구합니다. | 주로 블록 암호와 암호학적 해시 함수에 적용되는 일반적인 암호 분석 기법입니다. 입력 정보의 차이가 출력의 특성에 어떤 영향을 주는지 정밀하게 분석합니다. |
| 암호 분석가의 목표는 평문의 여러 비트, 암호문의 일부 비트, 알 수 없는 키의 몇몇 비트 사이의 선형 관계를 찾아내는 것입니다. | 선택한 평문들의 변화를 서로 비교하고, 각 평문을 암호화했을 때 나타나는 출력의 차이를 분석함으로써 여러 키 후보를 좁혀갈 수 있습니다. |
| 암호 분석가는 적용 가능한 일부 하위 키로 한 라운드의 암호화를 복호화한 뒤, 그 결과로 얻은 중간 암호문을 연구하여 무작위 결과와 비교합니다. | 여러 라운드의 암호화 사이에서 중간 암호문의 변화를 추적합니다. 두 공격 기법은 결합이 가능하며, 이를 차분-선형 암호 분석(differential-linear cryptanalysis)이라고 합니다. |