Triple DES

http://blog.naver.com/hiko_seijuro/110003760133

1. Triple DES

   그러면 과연 DES는 안전한 알고리즘일까? 안타깝게도 그에 대한 대답은 '예'가 될 수 없다. DES에 대한 안전성이 증명되어 있는 것은 아니다. 다만 아직까지도 효율적인 해독 방법이 발표되어 있지 않다는 것이 안전성에 대한 대답이다. 일일이 키를 대입하는 exhaustive attack을 하면 어떻게 될까? 만약 DES의 키 하나를 조사하는데 1 마이크로초(100만분의 1초)가 걸리는 칩이 있다면 이 칩을 이용해서 모든 키를 조사하는데에 2^55초가 걸린다. 2^55초? 얼마인지 감이 잡히는가? 약 1000년이다. 훨씬더 빠른 칩이 개발된다하더라도 DES는 어느 정도 안전한 것으로 간주할 수 있다.

   그런데 병렬처리기술을 이용하면 말이 좀 달라질 수 있다. 위에서 말했던 칩을 1000개 나열해서 병렬처리를 한다면 약 1년이면 모든 키를 조사해낼 수 있다는 것이다. 단순히 숫자를 곱하는 것은 의미가 없겠지만 병렬처리의 강력함을 생각해볼 때 더욱 빨리 키를 알아낼 가능성을 배제할 수도 없는 것이다. 현실적으로 그렇게 많은 수의 병렬처리를 해낼 능력과 자금력을 가진 사람이 얼마나 될 지 알 수는 없지만 이런 식으로 해서 누군가가 암호 해독을 시도하고 있는지도 모른다.

   대안으로 제시된 것이 바로 Multiple Encryption이다. 여러번 암호화를 해서 그 해독을 더욱 어렵게 하는 것이다. 이럴 경우 암호화와 복호화에도 몇배의 시간이 더 걸리지만 해독에는 훨씬 더 많은 시간이 필요하게 된다. 56bit의 키가 112bit의 키로 늘어난다면 필요한 시간은 제곱으로 늘어난다.

Double Encryption

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 방식을 이용한 것이라고 보면 된다. 이 경우에는 앞에서 설명했던 중간 일치 공격을 할 수가 없다.

Triple Encryption

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)))

1. Triple DES

   그러면 과연 DES는 안전한 알고리즘일까? 안타깝게도 그에 대한 대답은 '예'가 될 수 없다. DES에 대한 안전성이 증명되어 있는 것은 아니다. 다만 아직까지도 효율적인 해독 방법이 발표되어 있지 않다는 것이 안전성에 대한 대답이다. 일일이 키를 대입하는 exhaustive attack을 하면 어떻게 될까? 만약 DES의 키 하나를 조사하는데 1 마이크로초(100만분의 1초)가 걸리는 칩이 있다면 이 칩을 이용해서 모든 키를 조사하는데에 2^55초가 걸린다. 2^55초? 얼마인지 감이 잡히는가? 약 1000년이다. 훨씬더 빠른 칩이 개발된다하더라도 DES는 어느 정도 안전한 것으로 간주할 수 있다.

   그런데 병렬처리기술을 이용하면 말이 좀 달라질 수 있다. 위에서 말했던 칩을 1000개 나열해서 병렬처리를 한다면 약 1년이면 모든 키를 조사해낼 수 있다는 것이다. 단순히 숫자를 곱하는 것은 의미가 없겠지만 병렬처리의 강력함을 생각해볼 때 더욱 빨리 키를 알아낼 가능성을 배제할 수도 없는 것이다. 현실적으로 그렇게 많은 수의 병렬처리를 해낼 능력과 자금력을 가진 사람이 얼마나 될 지 알 수는 없지만 이런 식으로 해서 누군가가 암호 해독을 시도하고 있는지도 모른다.

   대안으로 제시된 것이 바로 Multiple Encryption이다. 여러번 암호화를 해서 그 해독을 더욱 어렵게 하는 것이다. 이럴 경우 암호화와 복호화에도 몇배의 시간이 더 걸리지만 해독에는 훨씬 더 많은 시간이 필요하게 된다. 56bit의 키가 112bit의 키로 늘어난다면 필요한 시간은 제곱으로 늘어난다.

Double Encryption

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 방식을 이용한 것이라고 보면 된다. 이 경우에는 앞에서 설명했던 중간 일치 공격을 할 수가 없다.

Triple Encryption

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)))