블록암호(Block Cipher) #DES

DES(Data Encryption Standard)

1970년대에 IBM에서 제안한 루시퍼(Lucifer)암호를 기반으로 수정하여 만들어진 대칭키 블록암호이다. 여담으로 NSA가 비밀리에 관련되어있었고, 설계과정이 비공개이었다 보니 DES에 백도어를 숨겼을거라는 의심도 받았다고 한다. 루시퍼 알고리즘을 교묘하게 변경하기도 하였고, 키의 길이가 128비트에서 64비트로 줄어서 DES개발은 논쟁이 있었다고 한다.

DES의 수비학(Numerology)

- 64bit 블록 길이

- 56bit 키 길이

NSA에서 키 길이를 64비트에서 48비트로 줄이려고 노력했으나 결국 최상위 8비트를 제거한 56비트가 되었다고 한다

- 16번의 라운드(회전)

- 각 회전에서 48비트의 보조키(Subkey) 사용

- 각 회전은 단순

- 안정성은 주로 S-box들에 의존

각 S-box들은 6비트를 4비트로 매핑

전반적인 DES 알고리즘의 구조

(사실 봐도 잘 모르겠다;;;) DES 수비학에서 보았듯이 총 16개의 Round가 있음을 확인할 수 있다. 또한, 각 회전(라운드)에서 48비트의 보조키(를 사용함을 알 수 있다. 좌측 상단에 키의 길이가 64비트로 나와있는 이유는 실제 키의 길이인 56비트에 패리티 비트 8bit가 추가되어 들어가기 때문이다.

구조를 어느정도 가볍게 설명하자면 좌측 열이 중심 과정이라고 할 수 있다(라운드 함수가 존재하기 때문이랄까..ㅎ) 중심 열에서는 평문을 분리하고, 라운드 함수를 거쳐 암호문을 만들어낸다. 각 라운드 함수에서는 중심 열을 기준으로 우측에서 키값을 가지고 만들어낸 보조키(K)를 제공받는다.

이정도만 확인하고 큰 구조에서부터 세부적인 기능까지 천천히 알아보자

DES 알고리즘의 단일 라운드(Round)

전반적인 DES 알고리즘 구조에서 볼 수 있었던 Round들이 어떻게 구성되어있는지 알아보자

평문을 두 개로 나눈것이 Li-1과 Ri-1이며, 키를 두 개로 나눈것이 Ci-1과 Di-1이다. 즉, 좌측 두 열이 평문, 우측 두 열이 키를 처리하는 과정이다. 자세히 보면 페이스텔 방식으로 평문을 처리하는 것을 알 수 있다. C와 D를 시프트 관련 처리를 하여 라운드 함수의 보조키로 전송된다.

처리 과정들(이름만 봐도 어지럽네..)에 대한 기능들을 알아야지 단일 라운드를 이해할 수 있을것 같다. Permutation E Table에 대해서부터 알아보자.

DES Expansion Permutation

위에서 언급한 Permutation E Table이 바로 Expansion Permutation이다. 사실 영알못이라 검색해보니 확장 순열이라고 한다. 해당 테이블을 참고하여 전치 작업을 하는 기능이라고 한다. 테이블은 아래와 같다.

표에 보이는 숫자가 인덱스를 의미한다. 원래의 데이터를 저 순서대로 넣어 전치하라는 의미라고 한다. 그러나 평문을 쪼갠 하나의 데이터 길이는 32bit인데 표의 총 칸수는 48(6x8)칸, 48bit이다. 즉, Expansion Permutation 과정을 거치면 확장 순열이라는 이름에 걸맞게 데이터의 길이가 48비트로 늘어나게 되는것이다.

DES S-box

단일 라운드 구조 사진에서 보면 Expansion Permutation 아래에 있는 Substitution Function이 바로 S-box이다. 이 또한 테이블을 이용하여 전치하는 함수이며 확장 순열 함수를 거쳐 48비트로 만들어진 데이터를 다시 32비트로 다시 바꿔주는 함수이다

총 8개의 S-box로 이루어져 있다. 즉, 48bit의 데이터를 6bit씩 8개로 나누어 각각의 S-box로 전치한다는 뜻이다. 이렇게 자리를 바꾸게되면 6bit 데이터는 4bit로 줄어들게 되고 8개의 데이터를 합치면 32(4x8)bit가 된다.

DES P-box

단일 라운드 구조 사진에서 S-box 밑에 있는 과정인 Permutation CP가 P-box과정이다. 이 또한 이름처럼 순서를 바꾸는 과정이다. 데이터의 크기변화는 없다. 테이블은 다음과 같다

DES Subkey

보조키(K)를 생성하는 과정에 대해서 알아보자. 단일 라운드 구조 사진에서 우측 두 개의 열에 해당하는 내용이다. 우선 전반적인 DES 알고리즘 구조 사진을 보면 처음 64비트 키를 받는다. 이때 키는 56bit의 실질적인 키와 8비트의 패리티 비트로 이루어져 있다. 이 키는 Permuted choice 1(PC1) 과정을 거치게 되는데 비트의 순서가 바뀜과 동시에 데이터의 길이도 64bit에서 56bit로 실제 키값만 남게 된다.

이렇게 만들어진 56bit의 데이터는 시프트 연산과 PC2 과정을 하나의 라운드로 16번 반복하게된다.

시프트 연산의 경우 라운드마다 시프트값이 다르다. 아래를 참고하자

1, 2, 9, 16번째에 해당하는 라운드에서는 1씩, 그 외에는 2씩 왼쪽 시프트 연산을 진행한다. 여기서 시프트 연산은 순환형이기 때문에 맨 앞 값은 맨 뒤로 나온다.

시프트 연산을 통해 만들어진 데이터는 단일 라운드 구조 사진처럼 PC2 과정을 거친다. PC2에서는 56bit를 48bit 로 줄인다. 아래를 참고하자

이러한 키 스케줄 과정은 보조키를 생산한다. 생성된 보조키는 XOR연산에 이용된다.

DES swap

전반적인 DES 알고리즘 구조 사진을 보면 16번의 라운드 작업이 끝난 후에 32bit swap을 진행한다. 암호화와 복호화 양쪽 모두에 대해 동일한 논리를 사용하기 위해 swap하는것이라고 한다.

DES의 안정성

- DES의 안정성은 다수의 S-box에 의존하며, 나머지는 모두 선형

- 30년간의 강도 높은 분석으로 '백도어'가 없음을 밝힘

- 현대 공격은 전수키 조사를 사용

- 마이크로칩을 이용한 DES 해독 칩도 존재