[cryptography] Cryptography 2.(1) - One Time Pad

 요즈음 GPGPU를 이용한 계산 최적화 일을 하느라 너무 바빠서 암호학 강의를 듣고 정리할 시간이 부족하다.... 특히 설명을 보조할 그림들을 파워포인트에서 다 직접 만드느라 시간이 많이 걸린다.

 그래도 작심삼일을 할 수는 없으니 정리 시작~!

 Cryptography 두번째 강의는 Stream Cipher에 대한 것이다. 강의가 너무 길어서 두개로 나누어 듣고 정리하려고 한다.

먼저 전체적으로 개요를 살펴보자면,

1. Symmetry cipher의 정의
2. The One Time Pad (OTP)
3. Stream Cipher
4. Attack on Stream Cipher

로 크게 나눌 수 있겠다. 

• 먼저 Symmetry cipher의 정의부터 정리하자.

 K는 모든 가능한 key의 집합, M은 모든 메시지의 집합, 그리고 C는 암호화된 메시지의 집합을 의미한다. 이를 바탕으로 Symmetry cipher의 정의를 천천히 풀어 설명하자면, Symmetry cipher는 효율적인 두 알고리즘, 즉 암호화 알고리즘 E와 복호화 알고리즘 D의 쌍을 의미한다. 중요한 것은 마지막 줄인데, 모든 메시지와 키에 대해서 암호화된 메시지, E(k,m)을 복호화 하면 다시 원래의 메시지(m)를 얻을 수 있어야 한다는 점이다.

•  One Time Pad는 Symmetry Cipher이면서 강의에서 처음으로 등장하는 안전한 암호화 방식이다.

 One time pad (이하 OTP)는 주어진 메시지와 키를 XOR 연산을 통해 암호화 한다. 물론 이때 메시지와 키는 {0,1}로 이루어진 string이다.

 이제 OTP가 Symmetry Cipher이면서 안전한 암호화 방식이란 것을 증명한다. 너무 자세한 증명과 정의가 난무하는 관계로 지루해 질지도 모르지만, 중요하기 때문에 천천히 읽어보기 바란다.

 OTP가 Symmetry Cipher임을 증명.

XOR 계산의 결합법칙의 증명과 항등원 0은 한번 생각해 보길 바란다.

 위에서 k와 m의 길이가 같아야하므로 (그래야만 XOR 연산이 가능하다) key가 메시지의 길이에 따라 상당히 길어질 수밖에 없다.

 그리고 두번째로, 안전한 암호라는 것은 모호하므로 새로운 개념을 도입한다. 바로 Perfect Secrecy이다.

 부연 설명을 하자면, key k가 전체 집합 K에 대해서 uniform하고, 이에 대해 같은 길이의 어떠한 두 메시지 m1, m2와 key k가 있다고 하자. 암호화 알고리즘을 통해 m1이 c로 암호화될 확률과 m2가 c로 암호화될 확률이 서로 같을 때, 이 암호화 방법(E,D)이 Perfect secrecy를 가진다고 한다.

 Perfect secrecy를 가지는 암호화 방법은 암호화된 메시지만 가지고는 공격이 불가능하다. 하지만 다른 공격방법이 존재하며, 이는 뒤에 설명한다. 이제 OTP가 Perfect secrecy를 가지는 지 증명한다.

 증명을 하기 전에, 한가지 덧붙일 것이 있다. 어떠한 key k, 메시지 m 그리고 암호화된 메시지 c에 대해서 E(k, m) = c일 확률은 그러한 k의 개수 / |K| 일 것이다 (|K|는 K의 원소의 개수, 즉 모든 가능한 key의 개수). 그렇다면 메시지 m을 c로 암호화하는 key k의 개수가 상수로 항상 일정하다면 Perfect secrecy의 조건을 만족하게 된다.

 위의 증명을 통해 OTP가 perfect secrecy를 가진다는 것을 보였으며, 이것은 즉 OTP는 암호화된 메시지만 가지고서는 원래의 메시지의 정보를 알 수 없다는 것을 의미하게 된다. 하지만 perfect secrecy는 현실적으로 사용하는 데에 한계점이 있다.
 이는 Perfect Secrecy를 가지려면 키 k의 길이가 메세지의 길이보다 크거나 같아야 하기 때문이다. (1TB의 데이터를 복호화 또는 암호화 하는데 1TB이상의 key가 필요하다면 정말 낭비일 것이다.)

•  OTP가 현실적으로 한계점이 있기 때문에 이를 좀더 현실적인 측면에서 개선한 것이 Stream Cipher라고 할 수 있다.

 Stream Cipher의 기본적인 아이디어는 임의의 Key대신 임의인 것처럼 보이는 (Pseudorandom) key를 사용하는 것이다.

 여기서는 메세지보다 적은 어떠한 seed를 key로 사용한다. 이 key를 확장시키는 함수를 Pseudorandom generator (PRG)라고 하자. 이 함수는

로 정의 된다.

 이 PRG를 통해 어떻게 암호화되는 지 그림으로 나타내 보면 더 쉽게 이해가 갈 듯하다.

 주어진 key (seed)를 가지고 PRG를 통해 메세지의 길이와 같은 Pseudorandom key를 만든다. 그리고 그 pseudorandom key를 메시지와 XOR 연산을 함으로써 암호화를 시킨다.

 쉽게 알 수 있듯이, PRG를 통해 key를 늘이는 것으로는 Perfect secrecy를 가질 수 없다. 그렇기에 이 암호 방식의 안정성을 나타낼 수 있는 새로운 방법이 필요하며, 이는 "예측 불가능"이라는 성질을 통해 안전한지 판단한다. 예측 가능한 것이 어떻게 정의되는 지 살펴보자.

 "non-negligible" 값은 현실적으로 정의하자면 1/2^30 보다 크거나 같은 값을 의미하며, "negligible" 값은 1/2^80 보다 작거나 같은 값을 의미한다. 이론적인 정의는 생략한다.

 풀어서 설명하자면 i번 까지의 PRG(key)을 가지고 i+1번째 PRG(key) 값을 어떠한 확률 (1/2 + non-negligible value) 이상으로 찾아내는 효율적인 알고리즘이 존재한다면 이 PRG를 예측 가능하다라고 하는 것이다 위의 조건을 만족한다면 이 PRG는 예측 가능하다고 하며, PRG가 예측 가능하다면 암호화된 메시지를 복호화하는 것이 어렵지 않게 되기 때문에 안전하지 못하다고 할 수 있다.

 왜 PRG가 예측 가능하면 안전하지 못한지 살펴보자.

 암호화된 메시지 c가 있다. (1) 공격자가 만약 원래 메시지 중 앞의 부분을 알 수 있다면, (2) 이 메시지와 암호화된 메시지의 XOR 연산을 통해 일부 PRG(k)의 값을 알 수 있게 된다. (3) 이 PRG는 예측 가능하기 때문에 얻은 일부 key를 가지고 전체 key를 알 수 있게 되며, (4) 알게된 전체 key를 가지고 암호화된 메시지와 XOR 연산을 하기만 하면 전체 메시지를 복호화 할 수 있다.

• 이제 마지막으로 OTP에 가능한 공격들을 살펴보자

   1. Two Time Pad is insecure

  만약 똑같은 키 k를 가지고 서로 다른 두 메시지를 암호화 한다면 안전하지 않다.

 Two Time Pad로 인해 m1 XOR m2를 알게된다. 그러면, 영어, 특히 ASCII 코드로 인코딩된 메시지라면, m1과 m2를 어렵지 않게 분리해 낼 수 있다.

 정리하자면, 안전을 위해서, Stream Cipher의 key는 한번만 사용해야한다. (그래서 이름도 One Time Pad이다.)


   2. No integrity

  OTP는 쉽게 내용이 바뀔 수 있는 (malleable) 약점이 있다. 예를 들어보자.

 만약 공격자가 어느 부분에 email의 보낸 사람 이름이 암호화 되는 지 안다면, 키를 알 필요 없이, 암호화된 메시지를 가로채, 그 부분에 특정한 값을 XOR 연산을 통해 집어 넣은 후 전달 받을 사람에게 보낸다. 그러면 암호화된 메시지를 키를 가지고 복호화 하면 대상은 보내는 사람이 변경된 email을 받게 된다.

 보다 안전한 암호를 위해서는 integrity를 가져서 내용을 쉽게 바꿀 수 없어야 하겠다. 이에 대해서는 나중에 강의에서 integrity를 가지게 하는 방법도 소개를 해준다고 하신다. 이제 시간이 된다면 뒷 부분 강의를 듣고 프로그래밍 숙제에 도전해야겠다.