대칭키 암호, DES

블럭암호의 종류
블럭암호는 암호키와 복호키가 동일하냐 상이하냐에 따라 대칭키와 공개키로 구분된다. 블럭암호는 n비트 평문을 l비트 키로 n비트 암호화 시키는 방법이다. 평문이 n비트로 표현되니 최대 2n!개의 순열이 만들어진다. 따라서 이론적으로 키의 길이 l은 log22n! 비트가 되어야 하지만, 키의 길이가 너무 크면 실용성이 급격하게 떨어진다. 따라서?2n!개 순열 중 일부만 사용하여 키의 길이를 줄여 쓴다. 실용 블럭암호의 예로는 DES와 AES가 있다.

DES의 특징, 혼돈과 확산 혼돈이란, 평문 1비트의 변화가 암호문에 어떤 영향을 줄 지 모르는 성질이다. 즉 평문과 암호문 사이는 매우 복잡한 관계로 얽혀져 있어야 함을 말한다. 확산이란, ?평문을 구성하고 있는 비트들의 정보가 여러개의 암호문에 분산되어 정보 수집하기가 어려워야한다는 점이다. DES는 이 두 가지 특징을 모두 가지고 있는 암호화 기법이다.

DES의 동작 원리
IP(initial permutation)에 의해 64비트 평문은 재배열 된다. 평문은 각각 L과 R로 찢어져서 각 라운드(i) 마다 보조키 Ki와 XOR되어 다음 L과 R이 된다. 라운드 마다 생성되는 보조키는 키로 부터 56비트를 출력하는 PC-1(Permutation Choice 1) 과정에 의해 C와 D로 찢어진다. 64비트 중 8비트는 패리티 비트로 실질적인 키는 56비트이다. C와 D로 찢어진다음 왼쪽으로 비트들을 옮기게 된다. 시프팅 연산이 끝난 C와 D는 다음 C와 D가 되고 PC-2의 입력이 된다. PC-2는 56비트를 48비트로 전환하여 보조키 Ki를 생성한다. 이렇게 최종 라운드까지 반복 동작을 하고 난 다음 초기 순열의 역순열을 사용하여 최종 암호문을 만들게 된다. 복호화는 암호화 과정과 키의 적용만 다르고 과정은 동일하다. 단지 키를 역으로 적용시킨다. 여담으로 매우 신기하다.

쇄도 효과 쇄도 효과는 평문이나 키의 소량의 변화가 암호문에 대량의 변화를 가져오는 것을 말한다. 이는 곧 전수조사에 걸리는 키의 갯수가 많아짐을 의미한다. 따라서 안전한 암호설계를 위해선 쇄도 효과를 가져와야 하는데 DES에선 라운드의 수가 쇄도효과를 가져온다. 라운드를 많이 거칠 수록 쇄도 효과는 커진다. 1비트 차이나는 두 평문에 대해 서로 다른 비트들의 갯수를 의미하는 해밍거리를 라운드의 수에 따라 구했을 때 해밍거리는 16라운드 정도까지 했을 때 34가 나온다. 1비트의 차이가 평문의 절반 이상이 차이가 나게 되었음을 의미한다. 실효성으로 보았을 때 16라운드 정도까지만 해도 강력한 쇄도 효과를 볼 수 있음을 의미한다.

DES 암호 분석
실질적 키의 길이가 56비트이므로 256개의 키를 전수조사해야 DES를 깰 수 있다. 키 한번 시도에 1 나노초가 걸린다고 해도 이는 1000년이 걸린다고 저서에 적혀있다. 그런데 병렬 처리로 키를 나눠 계산하면 여전히 DES의 안전성은 의심받게 된다. 따라서 키를 이중 삼중으로 적용시키는, 이중 삼중으로 라운드를 돌아보자는 제안이 등장하는데 그것이 2중 DES와 3중 DES이다. 3중 DES의 출연은 2중 DES가 '중간 충돌 공격'에 의해 부서질 수 있기 때문에 제안이 되었다.

중간 충돌 공격
2중 DES는 c = Ek2?[ Ek1 (m) ] 로 암호화 한다. 이때?Ek1 (m) = x라면 결국??Dk2(c) = x =?Ek1 (m)이 된다. 따라서 가능한 키 k1들과?k2들을?각각 암호화 복호화에 사용하여 나온 x들을 가지고 있는다. 암호화에서 나온 값들와 복호화에서 나온 값들 중 일치하게 만드는 키?k1과 k2를 선별하여 2중 DES를 깰 수 있다. 2중 DES는 암호화 복호화에 2번씩 2*256번의 전수조사를 요함으로 이는 단일 DES에 비해 안정성이 대폭 향상된 것이 아님을 확인 할 수 있다.