Introduction

본 글에서는 DreamHack의 Abstruse DES 문제를 바탕으로 필요한 지식을 공부한 과정을 다룬다.

먼저 해당문제를 푼 후 읽기를 추천한다.

DES

Data Encryption Standard(DES)는 1970년대 IBM에서 개발된 대칭키 암호화 알고리즘이다. DES는 64비트의 블록 단위로 데이터를 암호화하며, 56비트의 키를 사용한다. DES는 16회의 라운드를 거쳐 데이터를 암호화한다.

총 64비트, 그중 8비트는 패리티 비트로 사용되며, 실제로는 56비트의 키를 사용한다. 여기에 수학적 트릭을 통해서 연산의 수를 $2^{47}$ 이하로 줄일 수 있기에 현재는 AES로 대체되었다.

DES의 구조

DES는 다음과 같은 구조를 가진다.

+-----------------+
| Initial Perm.   |
+-----------------+
| Round 1         |
+-----------------+
| Round 2         |
+-----------------+
| ...             |
+-----------------+
| Round 16        |
+-----------------+
| Final Perm.     |
+-----------------+

초기 순열(Initial Permutation, IP)로 시작하여 16회의 라운드를 거친 후 최종 순열(Final Permutation, FP)을 적용한다.

각 라운드는 다음과 같은 구조를 가진다.

+-----------------+
| Expansion       |
+-----------------+
| Key Mixing      |
+-----------------+
| Substitution    |
+-----------------+
| Permutation     |
+-----------------+
| Round Function  |
+-----------------+

각 라운드는 확장(Expansion), 키 혼합(Key Mixing), 대체(Substitution), 순열(Permutation), 라운드 함수(Round Function)로 구성된다.

현재 DES의 수학적 내용보다는 exploit에 더 관심이 있으므로 바로 DES의 특징을 알아보자.

Encryption and Decryption

암호화를 아래처럼 표기하자.

$C = DES(K, P)$

복호화는 아래처럼 나타낸다.

$P = DES^{-1}(K, C)$

여기서 $K$ 는 키, $P$ 는 평문(Plaintext), $C$ 는 암호문(Ciphertext)이다. 그리고 $DES^{-1}$ 는 DES의 역함수를 나타낸다.

복호화는 암호화와 동일한 과정을 거치지만, 키의 순서가 반대이다. 즉, DES의 암호화와 복호화는 동일한 구조를 가지지만, 키의 순서가 다르다.

예를 들어 64비트 키가 $K_1, K_2, ..., K_{16}$ 이라 할 때 복호화는 키가 $K_{16}, K_{15}, ..., K_1$ 의 순서로 사용된다. 따라서 거꾸로 키를 사용하여 암호화하면 그것이 곧 복호화가 된다.

Complementary

DES는 아래와 같은 성질을 가진다.

$C=DES(K, P) \Leftrightarrow \overline{C}= DES(\overline{K}, \overline{P})$

이 성질을 Complementary라고 한다. 이를 이용하면 특수한 경우의 - 예를 들어 CTF에서 주어진 상황 - 에서 키를 구할 수 있다.

Weak Keys

DES에는 약한 키(Weak Keys)가 존재한다. 약한 키는 DES의 암호화와 복호화가 동일한 결과를 생성하는 키이다. 즉, $K$ 가 약한 키일 때, $DES(K, DES(K, P)) = P$ 가 성립한다.

Abstruse DES Writeup

해당 글을 문제에 대한 직접적인 스포일러가 포함되어 있기에 문제를 푼 후 읽기를 추천합니다.

Analysis

주어진 것

$C=DES(F, K)$ for fixed $F=\text{flag}$ , $K=\text{key}$
$C'=DES(\text{input2}, K \oplus \text{input1})$ ( $\text{input1} \neq 0$ )
for an arbitrary input $\text{input1}$ and $\text{input2}$
$C=DES(\text{input}, K)$ for an arbitrary input $\text{input}$

Solution

$\begin{aligned} F &= DES^{-1}(C, K)\\ &= \overline{ DES^{-1}(\overline{C}, \overline{K})}\\ &= \overline{ DES^{-1}(\overline{DES(F,K)}, \overline{K})} \end{aligned}$

여기서 마지막 수식에 필요한 것은 모두 구할 수 있다. NOT 연산만 직접 구현해서 풀자.

def des_not(data):
    return bytes([b ^ 0xFF for b in data])

Additional Notes

이 문제를 풀면서 의도치 않게 삽질을 하면서 DES에 대해 깊게 공부하게 되었다. 공부한 결과, DES의 취약점을 아래와 같이 정리했다.

KEY-Related Attacks

Brute Force Attack: DES의 키 길이가 56비트이므로, 모든 키를 시도하는 브루트 포스 공격이 가능하다. 여전히 충분한 수학적 optimization과 hardware acceleration 없이는 어려운 방식이다.
Weak Keys: DES에는 약한 키가 존재한다. 약한 키는 DES의 암호화와 복호화가 동일한 결과를 생성하는 키이다. 즉, $K$ 가 약한 키일 때, $DES(K, DES(K, P)) = P$ 가 성립한다. 만약 key가 조작이 가능하다면, 이를 통해 plaintext를 쉽게 구할 수 있다.
Semi-Weak Keys: 약한 키와 유사하게, 세미-약한 키는 DES의 암호화와 복호화가 서로 다른 결과를 생성하지만, 특정한 패턴을 가진다. 이러한 키를 사용하면 공격자가 암호문을 쉽게 분석할 수 있다. 대충 pair을 이루는 약한 keyset 라고 생각하자.

Property-related

Complementary: DES는 Complementary 성질을 가진다. 즉, $C=DES(K, P) \Leftrightarrow \overline{C}= DES(\overline{K}, \overline{P})$ 가 성립한다. 이를 이용하면 특정한 상황에서 키를 구할 수 있다.
Differential Cryptanalysis: DES는 또한 Differential Cryptanalysis가 가능하다. 이는 암호문과 평문 사이의 차이를 이용하여 키를 추출하는 공격이다. 이글에서 DES에 대한 Differential Cryptanalysis를 다룬다.
linear Cryptanalysis: DES는 Linear Cryptanalysis에 취약하다. 간단하게 말해서, 여러번 대입을 해봤더니 key와 cipher 사이에 특정 선형 관계를 찾을 수 있고 이 통계적 확신을 기반으로 공격을 한다는 것이다. 이글에서 DES에 대한 Linear Cryptanalysis를 다룬다.

위와 같은 취약점으로 인해 3중 DES 같은 것도 존재한다. 지금은 AES로 대체되었지만, DES는 여전히 암호학의 기초를 이해하는 데 중요한 알고리즘이다.

[DH] Abstruse DES