[cryptography] Cryptography 3.(1) - Block cipher

 일과 올림픽 때문에 내 블로그가 죽어가고 있었다.. 그동안 정리하려고 자료들을 모아두기만 하였기에 이제 시간을 내서 몰아서 정리를 해야겠다.

 이번엔 Block cipher에 대해서 정리를 해본다.

 Block cipher에는 DES, 3DES, AES 등이 있다. 사실 무선 공유기를 설정할 때에, 어떤 암호화 기법을 사용할지 선택을 해야하기에, 이러한 예의 이름은 상당히 익숙하다. 물론 어떻게 암호화가 되었는지는 이제까지는 몰랐지만 말이다. cryptography 3번째 강의는 이 block cipher에 관한 내용이다. 양이 적지 않기 때문에, 2~3 부분으로 나누어 정리한다.

 이번 강의의 첫번째 부분의 내용을 요약하면 아래와 같다.

1. Block cipher 개요
2. Pseudo Random Function (PRF), Pseudo Random Permutation (PRP)의 정의
3. Secure PRF 정의
4. Example : DES

 그러면, 하나하나 정리를 시작한다.

1. Block cipher 개요

 Block cipher는 n bits의 Plain Text (PT, 평문)을 k bits의 key를 통해서 암호화를 시켜 역시 n bits의 Cipher Text (CT, 암호문)을 만들어 낸다. 여기까지는 Stream cipher와 크게 다를 바가 없어 보인다. 하지만 이제 곧 알게 되겠지만, Stream cipher와는 암호화 방법에서 차이점이 있다.

 이제, Block cipher에서 암호화하는 방법을 살펴보자.

 위의 그림은 Block cipher의 암호화 방법을 도식화한 것이다. 찬찬히 살펴보면, 먼저 key를 확장시켜서 총 n개의 key를 생성해 낸다. 그러면 텍스트와 key를 인풋으로 받는 R (round function)을 총 n번 거치면서 평문 m은 c로 암호화된다. 지금은 조금 받아들이기 힘들 수 있으나, 마지막에 DES에 대한 예를 살펴보면 확실히 와 닿을 것이다.

2. Pseudo Random Function (PRF), Pseudo Random Permutation (PRP)의 정의

 PRF와 PRP는 block cipher의 암호화 과정의 round function을 엄밀하게 정의한 개념들이다. PRF는 좀더 일반적인 개념이고, Block cipher에서 필요한 것은 PRF의 좀더 특별 케이스인 PRP이다.

 PRF의 정의는 상당히 단순하다. 위에 나타난 것처럼, K와 X를 Y로 대응시켜주는 함수 F가 PRF인데, 조건은 이 F(k, x)를 평가하는 효과적인 알고리즘만 있으면 된다. 한마디로 k와 x를 가지고 효과적으로 F(k, x)를 뽑아내면 된다는 것이다.

 이제 PRF를 정의했으니 PRP를 정의해보자.

 PRP는 PRF의 좀더 특별한 케이스이다. 공역이 줄어들고, 조건이 몇가지 더 붙었다. 먼저 PRF의 조건에서 결정적이라는 단어가 추가되었다. 이 말은 즉, k와 x를 주면 E(k, x)는 하나로 결정된다는 것이다. 그리고, 추가적으로 key k가 주어졌을 때는 1대1 대응함수가 된다. 감이 오는가? PRP는 말 그대로 X에서 X로 K에 따라서 순서를 뒤섞어 주는 함수이다. 물론 마지막 조건, 효과적인 역함수가 존재해야 하는 것은 암호의 특성상 당연히 필요하다.

3. Secure PRF 정의

 PRF가 무엇인지 알았다면, 이제 안전한 PRF가 무엇인지 정의를 해야 PRF를 사용하는 Block cipher가 안전한지 아닌지를 알 수 있을 것이다.

 Secure PRF의 정의를 위해 두가지 집합을 새로 정의했다. Funs[X, Y]와 S_F이다. S_F는 모든 Key에 대한 PRF (F)의 집합으로 정의했다. 여기서 포인트는 모든 함수의 집합에서 임의로 선택된 함수와, S_F에서 선택한 임의의 함수가 서로 구별할 수 없다는 부분이다. 이 명제가 성립해야만 이 PRF가 안전하다는 것이다. "구별할 수 없다"에 대해서는 앞서 포스팅한 2.(2)의 PRG Security 부분을 참고하시라.

 4. Example : DES

 이제 마지막으로, DES (Data Encryption Standard)에 대해서 살펴본다.

 DES는 1970년대 초반, IBM의 Horst Feistel이 고안한 Lucifer로 부터 시작된다. 1973년, IBM에서는  NBS (National Bureau of Standards, 미국 표준 규격국)의 block cipher 제안 요청에 따라 Lucifer를 조금 변경하여 제출하였다. 이 것이 DES이며, 1976년에는 연방 표준으로 자리 잡게 되었다. 하지만 1997년, 무차별 대입으로 인해 암호가 깨지면서 보안성에 문제가 제기되었고, 2000년에는 AES가 DES를 대신하게 된다.

 그럼 이제, 이 DES의 원리를 살펴보자. DES의 핵심은 바로 Feistel Network이다.

 위의 그림에서 f1, f2, ..., fd는 바로 다음에서 설명을 하겠다. 먼저 그림을 보면 대강 Feistel Network가 어떤 것인지 감이 올 것이다. 먼저 input은 n bits 짜리 text 2개이다. 첫번째 round function을 지날 때, L1은 R0가 그대로 들어오고, R1은 L0와 f1을 통과한 R0와의 XOR 연산된 값이 들어오게 된다. 이런식으로 반복하여 d번째 결과가 곧 output이 된다.

 항상 암호에서 중요한 것은 역연산이 가능한가이다. 위의 network를 보면 복잡하여 역연산이 불가능해 보일 수도 있지만, 역연산은 생각보다 간단하게 똑같은 회로에서 f1부터 fd까지의 순서만 바꾸면 된다. 결과적으로 추가적인 회로 없이도 역연산을 할 수 있기 때문에 효율적이라 할 수 있겠다.

 여기서, 중요한 정리를 하나 소개한다.

 앞에서 우리가 정의 했던 것은 secure PRF였다. 위의 정리는 key 3개를 사용한 Feistel이 secure PRP이다 라는 것이다 (자세한 증명은 위의 논문 참조). 이는 3DES가 안전하다는 것의 밑바탕이 된다.

 아무튼, 이제 위의 Feistel Network에서 설명을 넘어갔던 f1, f2 ... fd에 대해서 설명을 한다. 이 설명에서 R0, L0 등은 32 bits, 그리고 각 key들은 48 bits를 사용한다고 가정한다.

 수식으로 나타낸다면, f (x) = F (k, x) 정도 이겠다. 먼저 함수 E는 주어진 32 bits 데이터를 확장 및 뒤섞는 역할을 한다. 그 결과 key의 크기와 같은 48 bits 데이터가 나오며, 이는 key와 XOR 연산이 된다. 이는 각 6 bits 씩 나누어져서 S box 들을 통해 4 bits의 데이터로 축소되고, 이것이 다시 모여 32 bits 데이터를 이룬다. P는 단순히 뒤섞는 역할을 하여 결과적으로 32 bits 데이터를 내놓는다.

 한가지 주의할 점이 있다. S box는 6 bits를 4bits로 축소하는 역할을 하는 데, 이 것이 linear 해서는 절대로 안된다. 만약 linear일 경우, 전체 DES cipher 자체가 linear하게 된다.

( m이 64 bits, n이 16이라 하면 각 k가 48 bits 이므로 총 832 bits )

 이렇게 되면 몇개의 암호문만 알게 된다면, 손쉽게 key를 복구할 수 있기 때문에, 암호의 보안성은 사라지게 된다고 한다.

---------------------------------------------------------------------------------------

[cryptography] RC4 - programming in python

 요즘 차근차근 python을 배우고 있다. 처음에는 C/C++이면 금방 작성할 것 같은 코드도 힘겹게 구글링 해가면서 작성해야 해서 힘들었지만, 조금 익숙해지고 나니 슬슬 python의 장점이 보이는 것 같다. 특히 깔끔하고 가독성 좋은 점이 마음에 든다 :)

 얼마전 Stream Cipher도 배웠고 해서, RC4 를 python으로 한번 구현해 보았다. 코드는 크게 2가지 함수와, 이를 묶어주는 함수 1개로 총 3가지로 이루어져 매우 간단하다. 첫번째 부분은 KSA (Key-scheduling algorithm)이다.

def KSA (key, S):
    for i in range(256):
        S[i] = i
    j = 0
    for i in range(256):
        j = (j + S[i] + ord(key[(i%16)])) % 256
        S[i], S[j] = S[j], S[i]

 key는 16 bytes로 만들어 놓았지만, key[(i%16)] 에서 숫자만 바꾸면 어떤 크기든 가능하다.

 다음은 PRGA (Pseudorandom generation algorithm)이다.

def PRGA (S, message, ciphertext, path, control):
    i = 0
    j = 0
    count = 0
    while count < len(message):
        i = (i+1) % 256
        j = (j+S[i]) % 256
        S[i], S[j] = S[j], S[i]
        K = S[(S[i]+S[j])%256]
        ciphertext += chr( K ^ ord(message[count]))
        count += 1
    
    if control == 'd':
        ofp = open("r_"+path[4:], "wb")
    elif control == 'e':
        ofp = open ("c_"+path[2:], "wb")
    else:
        print "ERROR: Unknown control"
        return 0
    
    ofp.write(ciphertext)
    ofp.close()

 PRGA는 key를 생성해서 암호화 또는 복호화를 진행하는 핵심부분이다. message와 ciphertext라고 변수 이름을 짓기는 했지만, 사실 message가 암호화된 문장이면 결과는 복호화된 문장이 출력된다.

 다음은 원래 메시지와 키의 경로 및 control을 인자로 받는 Enc_Dec 함수다.

def Enc_Dec (otext,keytxt,control = 'e'):
    kfp =  open (keytxt, "rb")
    fp  =  open (otext, "rb")
    S = [0] * 256

    ciphertext = ""
    KSA(kfp.read(), S)
    PRGA (S, fp.read(), ciphertext, otext, control)

    fp.close()
    kfp.close()

 control은 암호화면 'e', 복호화면 'd'를 예상하고 만들었다. Default는 'e'이다.
 -------------------------------------------------------------------

 만약 이 코드를 C/C++로 작성했으면 이보다 훨씬 길고 복잡해 졌을 것은 확실하다. python의 깔끔함이 마음에 들어서 암호 관련된 코드는 C 대신, python으로 작성을 해야겠다는 마음이다.

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

[cryptography] Cryptography 1 - introduction

암호는 나에게 마치 퍼즐 게임을 푸는 것처럼 흥미로운 소재이다.

내가 좋아하는 퍼즐게임 중 하나인 스도쿠를 예로 들어보자.

 스도쿠에서 처음 주어지는 판을 암호화된 정보라 하고, 이를 일련의 과정을 통해 풀어냈을 때, 얻어지는 완성된 판을 원래의 정보라고 생각해보면 암호와 퍼즐이 상당히 비슷하다는 생각이 들지 않는가.

 물론, 퍼즐은 목적 자체가 풀어보는 것이고 암호는 풀지 못하는 것 (최소한 풀지 못할 것을 예상하는 것)으로 근본적인 차이가 있지만 많은 공통점이 있는 것도 사실이다.

 남이 감추고 싶어하는 정보를 캐내어 보는 것에는 관심이 없지만, 암호 해독 자체로도 흥미로운 소재임이 틀림없다.
또한, 보안이 이슈인 요즈음, 프로그래머로서 암호에 관심을 가지는 것도 좋은 자세라고 생각한다.

 암호학에 입문하는 방법은 여러가지가 있겠지만, 나는 coursera.org에서 제공하는 Cryptography 강의를 들으려 한다. 위의 사이트에서는 해외 유명대학들에서 무료로 제공하는 양질의 강의를 들을 수 있어 정말 좋다.

 앞으로 블로그에 Cryptography 강의를 듣고 배운 것과 몇가지 드는 생각들을 정리할 생각이다. 이에 추가적으로 관련된 정보를 찾아 정리할 수도 있고, 시간이 남는다면 Course에서 제공하는 숙제를 제외한 (이에 관련된 정보를 공유하지 말라는 Honor Code에 동의를 했답니다 ㅋ) 직접 작성한 코드도 포스팅할 예정이다.


 맨 처음 1강은 여느 강의와 마찬가지로 Introduction으로 시작을 한다.
원래 Introduction은 흥미를 돋우기 위해 재미있는 것 위주로만 (^^) 정리를 했는데, 부분부분 조금 나누어 보자면,

1. 암호학에서의 세 단계 (Three steps in Cryptography)
2. 기억해야 할 몇가지    (Things to remember)
3. 공유키 프로토콜
4. 그리고 암호학의 간략한 역사

로 나눌 수 있겠다.


- 암호학은 매우 과학적으로 철저한(rigorous) 학문이라고 소개한다. 이 철저함을 위한 암호학의 세가지 단계가 있는데,

• 먼저 위협 모델을 자세하고 구체적으로 세워야 한다.
• 다음으로는 암호화된 모델을 내놓는다.
• 마지막으로, 위협 모델에서 암호화된 모델을 부수는 것이 암호화된 모델에 내재된 어려운 문제 (아주 큰 소수의 곱의 인수분해 등)을 푸는 것이라는 것을 증명한다.

 예를 들어, 국가의 안보에 관련된 파일이 있다고 하자. 이 파일의 암호를 부수는 위협 모델로, 적국의 스파이가 슈퍼컴퓨터를 이용하는 상황을 생각해 볼 수 있다. (아직 초기라 어느정도 더 자세하고 구체적이여야 하는 지는 잘 모르겠다.) 그래서 그 국가에서는 이를 암호화 하기 위한 모델을 내놓는다. 이 모델을 검증하는 것은, 스파이가 이 파일의 암호를 푸는데, 이 모델에 내재된 어려운 문제를 풀어야만 한다는 것을 증명해야한다. 만약 암호 모델이 의도한 것과는 다르게 파일 내부에 암호값이 존재한다든지 하는 경우는 어려운 문제를 풀어낼 필요없이 암호가 해독된다. 즉, 이 모델은 암호 자체가 되지 않을 수 있다는 것이다.

 - 또한 몇가지 기억해야할 것들이 있다.

• 암호는 굉장한 도구이다.
• 많은 보안 메카니즘의 기초가 된다.
• 암호는 모든 보안문제에 대한 해결책은 아니다.
• 적절하게 수행되고, 사용되지 않는다면 믿을 수 없다.
• 마지막으로 암호는 너 스스로 발명하려고 노력해야할 것이 아니다.

 몇가지는 한눈에 이해가 가지만 다른 몇가지는 언듯 이상해 보일 수도 있다.

하지만 생각해 보면 고개가 끄덕여질 것이다. 보안 문제에서 가장 취약한 부분은 사람이다. 사회공학(Social Engineering)에 능통한 사람들은 이 가장 취약한 부분을 노린다. 아무리 강한 암호로 보호되고 있다고 한들, 접근 권한을 가진 '사람'을 통해 접근한다면 어떻게 막을 수 있겠나... 

 또한 마지막 말은 나도 잘 이해가 가지 않았는데, 설명하기로는 이 강의에서 소개하는 암호들과 여러 암호들은 많은 연구가 이루어져서 쉽게 파괴가 가능하다는 의미에서 이런 말을 집어 넣은 것 같다.

- 공유키 프로토콜

 공유키 프로토콜의 핵심은 말 그대로 서로 Key 를 공유하는 것이다. 위의 그림에서 m은 원본 메시지, k는 공유키, c는 암호화된 메시지, E는 암호화 알고리즘, D는 복호화 알고리즘이다.

 이 프로토콜에서는 암호화된 메시지를 제 3의 존재가 가로챈다 하더라도 키가 없다면 쉽게 원본 메시지를 알 수 없다. 하지만 중요한 점은 키를 가지고 있다면 메시지의 암호화나 복호화는 매우 효율적으로 빠른 알고리즘이어야 한다는 점이다.

- 암호학의 간략한 역사

 암호학의 발전 과정을 간략하게 소개하면서 몇가지 암호화 방법을 소개한다.

• Substitution Cipher (대치 암호)

          대치 암호는 알파벳의 순서를 뒤죽박죽으로 섞어 암호화 하는 방식이다. 즉 암호문을 주고 받는 두 사람이 공유하는 키는 예를 들어 아래처럼 되어있다.

 이러한 키를 가지고 acyzb를 암호화 한다면 cloeq가 되겠다.

대치암호 방식은 알파벳의 빈도를 이용한 방법으로 쉽게 풀릴 수 있다는 한계점이 있다.

 예를 들어, 단일 알파벳중 가장 많은 빈도로 나타나는 것은 'e'이므로 암호문을 분석하여 가장 많이 나타나는 알파벳을 'e'로 치환하는 등의 방법으로 쉽게 풀린다는 것이다. 

• Vigener Cipher

                   Vigener 암호는 16세기에 Vigener가 고안한 암호이다.

먼저 Key 값을 설정해야한다. 만약 k = HELLO 라고 하고, 암호화 해야할 문장이 ICANDOTHAT이라고 해보자. 이 때, 키를 문장의 길이에 맞게 먼저 늘린다.

그리고 각 알파벳의 값에 A:=0부터 시작해서 Z:=25까지 부여를 한다. 그러면 키와 메시지의 첫번째 알파벳에 대응 되는 값은 H := 7이고 I := 8이다. 이제 이 두 숫자를 더한 후, mod 26을 취하면 15이고, 이 값은 P에 해당된다. 즉,

이런 식으로 암호화가 된다는 것!

이를 키 없이 해독하는 것은 대치 암호법 보다는 조금 복잡하지만 현대의 컴퓨터로 계산하면 역시, 빠르게 풀 수 있다는 한계점이 있다.

 해독 방법은 먼저 키의 길이를 가정한 후, 대치 암호를 해독하는 것처럼, 각 자리에 맞추어 암호를 해독한다. 맞지 않으면 키의 길이를 다시 바꾸어가면서 해독하면 된다.

• Rotor Machine

            Rotor Machine은 1920~1970년 사이에 사용된 암호화 기계다. 먼저 대치 암호화를 통해 알파벳을 뒤섞은 후, 한 글자를 칠 때마다 이 순서가 한칸씩 돌아가면서 재 암호화되기 때문에 빈도를 이용한 방법으로 해독을 하는 것이 불가능하다.

 하지만 이 방법도 역시 현대의 컴퓨터로 Brute force algorithm을 통해 쉽게 해결할 수 있다.

• Data Encryption Standard

            현대에는 Data Encryption Standard (DES)라는 발달된 형태의 암호화 기법이 나타났다. 이는 64bit 키를 이용한 암호화 방식인데, 이 것 역시도 너무나 발달된 컴퓨터의 능력 때문에 안전하지 못하다. 이를 더 보강한 Advanced Encryption Standard (AES)가 있는데, 이는 128bit 키를 이용한다. 자세한 내용은 이제 앞으로의 강의에서 설명해 주신단다.