[정보보안] 대칭키 암호 - DES

1. DES (Data Encryption Standard)

DES는 대칭키 블록 암호이다. 1977년 NIST에서 채택한 표준 암호이다. 

기본적으로 평문 64 bit를 입력받아 암호문 64 bit를 생성해낸다. 키 값은 56 bit이다.

키 값이 64bit에서 8bit 빠진 것은 1byte를 parity bit로 사용했기 때문이다.

 

여담으로 DES의 모태였던 IBM의 Lucifer 알고리즘에서는 키 길이가 처음에 128 bit로 제안되었지만 NSA에서 64 bit로 줄여버렸다. NSA는 미국 정보기관이다. NSA가 NIST의 암호 표준 선정에 개입한 것이다. 이것은 민간 수준에서는 충분히 안전하면서 국가 권력의 슈퍼컴퓨터를 보유한 NSA에서만 뚫을 수 있게 의도적으로 키 길이를 줄였다는 의혹이 있다. 의혹이지만 거의 정설로 받아드려진다. 이렇게 64bit 단위로 동작하게된 DES는 하드웨어가 비약적으로 발전한 현대에 이르러서는 민간 수준에서도 22시간만에 뚫려버리는 약한 암호체계가 되었다.

 

그래서 현재 DES는 안전한 암호체계가 아니다.

 

---

2. DES 전체 구조

 

DES는 크게 4단계로 이뤄진다.

1. 초기 전치 (Initial Permutation, IP): 입력된 64비트 평문의 비트 위치를 IP 테이블에 따라 단순 재배열한다.
2. 16 라운드 진행 (16 Rounds): IP를 통과한 64비트 데이터는 32비트씩 좌우 두 개($L_0$, $R_0$)의 블록으로 나뉜다. 이후 16번의 라운드를 거치며 Feistel 연산이 수행된다.
3. 32비트 스왑 (32-bit Swap): 16라운드가 모두 끝난 후, 최종적으로 생성된 $L_{16}$과 $R_{16}$의 위치를 서로 바꾼다.
4. 역 초기 전치 ($IP^{-1}$): 스왑된 64비트 데이터에 대해 초기 전치의 역과정($IP^{-1}$)을 수행해 최종 64비트 암호문을 도출한다.

앞서 키 값이 8 bit가 빠져서 56 bit라고 했다. 우리는 이 56 bit 키에 기반해서 16 라운드에 쓸 각각의 키 16개를 생성해야한다. 

매 라운드에 사용하는 키는 48 bit의 길이를 갖는다. 

결국, 56 bit의 key 한 개를 key scheduling을 통해 48 bit 길이의 subkey 16개를 생성해야하는 것이다.

 

---

3. 라운드 함수 세부 동작

라운드 함수	라운드 함수 내부의 비선형 함수 $f$ 구조

DES는 16번의 라운드 함수를 거친다. 라운드 함수 내부는 기본적으로 Feistel 구조이다.

• $L_i = R_{i-1}$
• $R_i = L_{i-1} \oplus f(R_{i-1}, K_i)$

좌우 블록을 위와 같이 계산한다. 

여기서 가장 중요한 것은 내부의 비선형함수 $f$이다. 비선형함수 $f$는 P-box와 S-box를 여러번 복잡하게 거치는 구조로 이뤄진다.

---

4. DES 암호분석 (Cryptanalysis)

DES의 키 길이는 56 bit로 키 공간은 $2^{56}$이다. 과거에는 이 길이를 전수 조사 공격(Exhaustive Search)로 뚫는 것이 불가능했지만 현대 하드웨어의 발전으로 1999년에 22시간만에 전수 조사 공격으로 뚫어버렸다. 

 

전수 조사 공격이 아닌 분석적 공격(Analytic Attack)도 있다. 분석적 공격이란 암호 알고리즘의 수학적 구조를 활용해서 효율적으로 해독하는 방법이다. 

• 차분 암호 분석(Diffrential Cryptanalysis): 두 개의 평문 - 암호문 쌍을 비교하여 분석하는 기법이다. 비트 패턴의 차이(입력 차분)가 암호화 과정(P-box, S-box)를 거치며 출력 데이터에 어떤 영향(출력 차분)을 미치는지 분석한다.
• 선형 암호 분석(Linear Cryptanalysis): 암호 알고리즘의 비선형 연산(S-box)들을 선형적인 관계식으로 근사하여 그 확률을 분석하는 공격기법이다. 선형 근사식을 찾아내서 암호화의 특정 부분을 예측해 궁극적으로는 키를 추정해낸다.

이러한 공격들 덕분에(?) 현재 DES는 안전하지 않다. 따라서 현재는 DES를 개선한 AES(Advanced Encrypt Standard) 알고리즘을 더 많이 사용한다.