아무튼, 이번엔 2-(2) 강의 내용을 크게 두가지 부분으로 나누어 정리한다.
- Real World Stream Cipher
- PRG Security
첫번째 부분에서는 세가지 Stream Cipher를 소개하고, 설명하는 것이며, 다음 부분인 PRG Security 부분에서는 Secure PRG에 대해서 정의를 한다.
- Real World Stream Cipher
- RC4
- CSS
- 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가 일어나지 않는 장점이 생기게 된다. 이에 더해, 암호화 알고리즘은 아래와 같이 나타낼 수 있다.
다음으로, 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"하다는 것은 어렵지 않게 알 수 있다.
-----------------------------------------------------------------------------
--- 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"하다는 것은 어렵지 않게 알 수 있다.
-----------------------------------------------------------------------------