이번에는 Triple DES란 어떤 것인지를 알아본다. 그리고 DES 외에 어떠한 블럭암호시스템들이 개발되어 있는지에 대해서 간략히 알아보고, AES에 대해서도 살펴본다.
1. Triple DES
그러면 과연 DES는 안전한 알고리즘일까? 안타깝게도 그에 대한 대답은 '예'가 될 수 없다. DES에 대한 안전성이 증명되어 있는 것은 아니다. 다만 아직까지도 효율적인 해독 방법이 발표되어 있지 않다는 것이 안전성에 대한 대답이다. 일일이 키를 대입하는 exhaustive attack을 하면 어떻게 될까? 만약 DES의 키 하나를 조사하는데 1 마이크로초(100만분의 1초)가 걸리는 칩이 있다면 이 칩을 이용해서 모든 키를 조사하는데에 2^55초가 걸린다. 2^55초? 얼마인지 감이 잡히는가? 약 1000년이다. 훨씬더 빠른 칩이 개발된다하더라도 DES는 어느 정도 안전한 것으로 간주할 수 있다.
그런데 병렬처리기술을 이용하면 말이 좀 달라질 수 있다. 위에서 말했던 칩을 1000개 나열해서 병렬처리를 한다면 약 1년이면 모든 키를 조사해낼 수 있다는 것이다. 단순히 숫자를 곱하는 것은 의미가 없겠지만 병렬처리의 강력함을 생각해볼 때 더욱 빨리 키를 알아낼 가능성을 배제할 수도 없는 것이다. 현실적으로 그렇게 많은 수의 병렬처리를 해낼 능력과 자금력을 가진 사람이 얼마나 될 지 알 수는 없지만 이런 식으로 해서 누군가가 암호 해독을 시도하고 있는지도 모른다.
대안으로 제시된 것이 바로 Multiple Encryption이다. 여러번 암호화를 해서 그 해독을 더욱 어렵게 하는 것이다. 이럴 경우 암호화와 복호화에도 몇배의 시간이 더 걸리지만 해독에는 훨씬 더 많은 시간이 필요하게 된다. 56bit의 키가 112bit의 키로 늘어난다면 필요한 시간은 제곱으로 늘어난다.
| one method of improving the security of a block cipher, i.e. | |
| let K1 and K2 denote two keys of block cipher, then | |
| Encryption | C = E(K2,E(K1,P)) |
먼저 생각해 볼 수 있는 것이 두 개의 키를 이용한 암호화이다. 이렇게 하면 해독은 더욱 어려워진다. 위의 계산에서 우리가 생각했던 것은 제곱으로 해독시간이 걸리는 것인데 안타깝게도 이 경우 그렇게 되지 않는다. 기껏해야 2배의 시간이 증가하는 linear한 증가를 보일 뿐이다. 어떻게 된 것일까?
평문 - 일차암호문 - 이차암호문
위의 상황에서 우리는 모든 키를 이용하여 exhaustive attack을 한다. 그것은 이차암호문에서 일차암호문으로 가는 과정이다. 그리고 평문에서 모든 키를 이용하여 암호화를 수행한다. 감이 잡히는가? 그러면 이것은 평문에서 일차암호문이 되는 과정이다. 눈치빠른 사람은 알아챘으리라. 먄약에 우리에게 2^56개 정도의 암호문을 기억할 수 있는 메모리가 있다면 결국 평문에서 암호화한 것과 최종암호문에서 복호화한 것이 같아야 하기 때문에 그 둘을 exhaustive attack으로 모두 조사하여 같은 것을 비교하면 된다. 이렇게 하면 결국 암호화할 때 사용했던 키를 찾아낼 수 있게 된다. 평문 하나만 알려지게 되면 결국 모든 암호가 해독되어 버리는 일이 생기게 되는 것이다. 이것을 바로 Diffie와 Hellman이 발표한 중간 일치 공격(meet-in-the-middle attack)이다. Double encryption이 결정적인 단점이다.
이러한 이유로 multiple encryption은 적어도 세번 이상의 암호화가 사용된다. Hoffman은 세 가지 서로 다른 키를 이용한 E-E-E 방식의 triple encryption을 제안했고 Tuchman에 의해서 E-D-E 방식의 triple encryption이 제안되었다. 결국 E-D-E 방식은 ANSI 표준으로 지정되고 우리가 쓰는 Triple-DES는 E-D-E 방식을 이용한 것이라고 보면 된다. 이 경우에는 앞에서 설명했던 중간 일치 공격을 할 수가 없다.
| Use of three stage of encryption with two or three different key | |
| Use two keys K1 and K2 | C = E(K1,D(K2,E(K1,P))) |
| Use three keys K1, K2, K3 | C = E(K3,D(K2,E(K1,P))) |
2. 다른 블럭 암호 시스템
FEAL
FEAL(Fast data Encipherment Algorithm)은 1987년 일본 NTT에서 기존의 DES를 대신하기 위해 만든 블럭 암호 시스템이다. 기본적인 구성은 Feistel 알고리즘에 바탕을 두고 있지만 DES와 같은 Table Look-up 방식을 사용하지 않는데 의의가 있다. 라운드 수에 따라 FEAL-N으로 나타내는데 여기서는 FEAL-8에 대해 알아보기로 한다.
FEAL은 DES와 마찬가지로 64bit 비밀키를 사용하여 64bit 평문을 64bit 암호문으로 바꾸는 블럭 암호 시스템이다. FEAL의 처리부는 키 생성부와 데이타 암호화부의 두 부분으로 구성되는데, 키 생성부는 64bit의 키를 256bit의 키로 확장시키는 일을 하고 데이타 암호화부는 이들 확장된 키를 이용하여 64bit 암호문을 만들어내는 일을 한다.
FEAL은 DES보다 암호화 시간이 더 빠르고, 더 값싸게 구현하기 위하여 만들어졌는데 안타깝게도 발표후 얼마되지 않아서 선택평문 공격에 약하다는 것이 발표되었고 그리고 차분공격에 의해 해독되어지는 모습을 보여주었다. 이후 개량된 FEAL은 이런 공격에 대해 강해졌지만 한번 깨어진 암호화 방법에 대한 불신은 그리 쉽게 회복되지 않았다.
RC5
가변 워드 크기 방식에 기반한 암호화 방식이다. 워드 크기는 16, 32, 64비트가 가능하다. 또한 라운드의 수도 가변적이고 키의 바이트 길이도 가변으로 지정가능하다. RC5-w/r/b로 표현 가능한데 이 경우 16비트 키가 사용된 12라운드 32워드이면 RC5-32/12/16으로 표현한다. RC5-32의 경우 12라운드가, RC5-64의 경우 16라운드가 권장된다. 아래 알고리즘에서 田는 addition mod 2^w를 나타내고, 꺾어진 화살표는 rotation을 나타낸다. 왼쪽으로 향하는 화살표는 left-rotation이다.
IDEA
스위스에서 만들어진 IDEA(International Data Encryption Algorithm)은 초당 177Mbit의 처리가 가능한 빠른 암호화 방법이다. IDEA은 128-bit key, 8-round, 64-bit block cipher이며 주된 연산은 XOR, add mod 216, multiply mod 216+1이다. RSA와 더불어 PGP에 사용되는 방식이기도 하다.
Blowfish
아직까지 유효한 공격법이 발표되지 않은 Blowfish도 있다. Blowfish의 특징은 variable length key (up to 448 bits), 16-round, 64-bit block cipher로 요약되며 주된 연산은 XOR, add, table lookup 4 8*32 S-boxes이다.
3. AES
DES 이후의 새로운 암호화 방법으로 여러 가지가 제안되었다. Advanced Encryption Standard가 새로운 표준을 제정하려는 노력인데 현재 5개의 후보작을 뽑고는 final round를 진행하고 있다.
1998년에 캘리포니아의 벤츄라에서 열린 첫번째 라운드에서는 15개의 후보작이 발표되었다. CAST-256, CRYPTON, DEAL, DFC, E2, FROG, HPC, LOKI97, MAGENTA, MARS, RC6, RIJNDAEL, SAFER+, SERPENT, TWOFISH이 그것인데 이 중에서 CRYPTON은 우리 나라에서 발표한 것이다.
1999년 8월 9일에 제2라운드가 발표되었는데 MARS, RC6, Rijndael, Serpent, Twofish가 새로운 후보작이다. 이 중에서 IBM의 MARS와 RSA의 RC6가 유력해 보인다.
AES에 대해서 더 알고 싶은 사람은 아래의 홈페이지를 참고하기 바란다.