[cryptography] Cryptography 2.(2) - Real World Stream Cipher & Two time pad attack

 강의는 진작에 들었지만, 프로그래밍 숙제에 도전하느라 조금 늦게 정리하게 됬다. 프로그래밍 숙제는 OTP에서 같은 key로 암호화된 10개의 메시지들을 주고, 이를 해독하여 마지막 11번째 암호를 해독하는 것이었다. 주어진 암호 메시지 두개를 XOR 시켜서 나온 Text를 가지고 가능한 문자쌍을 모두 나열하는 프로그램을 만들어서 수작업으로 일일히 암호를 해독해 냈다. ㅋ 그 때의 뿌듯함이란! 해독 과정이 쉽지는 않았지만 재미있었다.

 아무튼, 이번엔 2-(2) 강의 내용을 크게 두가지 부분으로 나누어 정리한다.

1. Real World Stream Cipher
2. PRG Security

 첫번째 부분에서는 세가지 Stream Cipher를 소개하고, 설명하는 것이며, 다음 부분인 PRG Security 부분에서는 Secure PRG에 대해서 정의를 한다.

• Real World Stream Cipher

1. RC4
2. CSS
3. eStream (Salsa20)

  강의에서 현실에서 사용되는 Stream cipher의 예시로 세가지를 소개한다. 먼저 RC4다.

 RC4는 software 계층에서 최적화된 암호화 기법이라 한다. 1987년에 소개되었으며, 기억해야 할 점은 RC4는 조금 편향되어(biased), 키 공격과 연관된 약점이 있다는 것이다. 물론 살짝만 암호화를 해 놓아도 푸는 것은 정말 일이긴 하다.

 이제 RC4의 원리를 살펴보자.

 RC4에서는 key로 40~128 bits의 seed를 사용한다. 이 key를 Key-Scheduling algorithm을 통해 256 bytes, 즉 2048 bits로 확장시킨다. 그리고나서, 이 확장된 256 bytes를 가지고 PRG (pseudorandom Generator)를 통해 루프를 돌며 1 byte씩 내놓는다. 이를 가지고 원 메시지를 암호화 하는 것이다. 다음에 소개할 CSS에서 사용하는 LFSR 같은 구조는 software에서 구현하는 것이 어렵고, RC4의 방법에 비해서 느리다.

 다음으로, CSS (Contents scramble system)에 대해서 설명한다. CSS는 hardware로 구현하기가 매우 쉽고 효율적이기 때문에 DVD 등의 암호화에 많이 사용된다. 하지만 쉽게 깨질 수 있기 때문에 이 또한 안전한 암호화 방법은 아니라고 한다.
 CSS는 Linear Feedback Shift Register (LFSR)를 사용한다.

 위의 그림은 LFSR의 원리를 나타낸다. 먼저 몇개의 비트를 선택하여, 이를 XOR 연산을 통해 값을 구한다. 그러고나서, 이 레지스터의 마지막 비트가 Output이 되며, 레지스터의 모든 비트가 한칸씩 오른편으로 움직인다. 마지막으로 XOR 연산을 통해 구한 비트가 이 LFSR의 첫번째 비트가 된다. 이러한 식으로 사이클마다 1 bit씩 key를 계속해서 뱉어내게 된다.


 CSS는 이러한 LFSR을 두개 이용하여 내용을 암호화 한다. CSS에서 Key는 일반적으로 40 bits를 사용하는 데, 앞의 두 byte는 맨 앞에 bit 1을 붙여 17-bit LFSR에, 뒤의 세 byte는 역시 맨 앞에 bit 1을 붙여 25-bit LFSR의 seed가 된다.

 LFSR에서 매 사이클당 1 bit씩 튀어나오기 때문에, 8 사이클을 돌면 각 LFSR에서 1 byte 길이의 데이터가 나오게 된다. 이를 합하여 mod 256을 취하는 형식으로 1 byte의 key를 계속해서 생성한다. 내용상 중요하지는 않지만 더할 때, 전 블록에서의 캐리 값을 더해준다. 캐리(carry)를 모른다면, 이에 대해서는 몰라도 상관 없다.

 마지막으로, 현대의 Stream Cipher인 eStream(2008)을 소개한다. eStream에서는 PRG를 정의할 때, Nonce라는 새로운 개념이 등장한다.

여기서 R이 바로 Nonce인데, 의미는 "주어진 Key에 대해, 반복되지 않는 값"이다. Nonce덕분에 (k, r) 짝이 항상 유니크 하기 때문에 Key를 재활용 하여도 Two Time Pad가 일어나지 않는 장점이 생기게 된다. 이에 더해, 암호화 알고리즘은 아래와 같이 나타낼 수 있다.

 Salsa20는 이러한 eStream cipher의 한 종류이다. Salsa20는 128 혹은 256 bits의 seed와 64 bits의 Nonce를 이용하여 키를 생성한다.

 여기서 H는 역연산이 가능한 함수이다. 이해를 돕기 위해 도식화 해보자.

  k는 key이고, r은 Nonce, i는 위의 공식에서 r과 짝을 이루어, (k, r)의 짝이 항상 유니크 하도록 만들어 주는 인덱스를 의미한다. 나머지는 각각 4bytes 짜리 상수들이다. 4개의 상수 (16 bytes), k가 두번 (32 bytes) 중복해서 들어가고 r과 i는 각각 8bytes으므로 총 64 bytes가 된다. 이를 역연산이 가능한 h로 열번정도 섞어준 뒤, 마지막으로 원래 데이터와 XOR 연산을 통해 random 처럼 보이게 만든다. 위의 식에서 H는 열번정도의 h와, XOR 연산을 수행하는 함수라고 생각하면 되겠다. 이런 방식으로 인덱스를 증가시키면서 만들어진 64 bytes key를 계속 연결하여 메시지를 암호화할 key를 만들게 된다.

 특히, 이 방법은 아직까지 특별히 공격할 만한 방법이 없다고 한다.

• PRG Security

이제 PRG의 보안에 대해 정의를 해보자. Secure PRG를 정의하기 위해 두가지 개념을 도입한다. Statistical Test와 Advantage다.

 --- Statistical Test is, an algorithm A s.t. A(x) outputs 0 or 1.

 어떠한 암호문 x를 입력으로 받고, 만약 이 암호문이 random이면 1을 출력하고, 아니면 0을 출력하는 알고리즘 A를 생각해보자. 이 알고리즘은 어느 것이든 될 수 있다. 예를 들어 x의 0의 개수와 1의 개수의 차이가 10*sqrt(n) 보다 작거나 같을 때에 1을 출력하는 알고리즘 A도 일종의 Statistical Test라고 할 수 있다.

 그리고 중요한 것은 Advantage이다. 정의는 아래 박스에 나타나 있다.

 만약 Adv가 1에 가깝다면, algorithm A가 G와 random을 구별할 수 있다는 것을 의미한다.
반대로 Adv가 0에 가깝다면, A가 G와 random을 구별할 수 없다는 것이며, 이러한 G가 우리가 원하는 PRG가 된다.

 자, 이제 Secure PRG를 정의해보자.

 "Negligible"의 의미는 저번에 이야기 했었다 (<= 2^80). 위의 정의를 좀 더 풀어서 설명을 하자면, 모든 효율적인 (예를들어, polynomial time안에 수행되는) Statistical test A에 대해서 Advantage가 무시할 수 있어야만 G를 secure PRG라고 한다는 것이다.

 이렇게 정의를 했지만, 과연 이 정의를 만족시키는 PRG가 존재할까? 이는 P:NP 문제이며, 알 수 없다고 한다. 하지만 경험적인 대안(heuristic candidate)을 통해 Secure PRG가 무엇인지 알 수 있다고 한다. 그리고 덧붙여, Secure PRG는 "unpredictable"하다는 것은 어렵지 않게 알 수 있다.
-----------------------------------------------------------------------------

[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를 가지게 하는 방법도 소개를 해준다고 하신다. 이제 시간이 된다면 뒷 부분 강의를 듣고 프로그래밍 숙제에 도전해야겠다.