이 포스팅은 CourseraStanford University Cryptography I - Dan Boneh 강의를 바탕으로 제작되었습니다. Cryptography를 공부하시고자 하는 분들을 위해 조금이나마 기여할 수 있을까하여 포스팅을 지속하기로 결정하였습니다. 


이번 강좌는 Stream Ciphers 1: the one-time pad and stream ciphers 에 포함된 두번째 강의인 "Stream Ciphers and Pseudo Random Generators" 입니다.



지난 시간에는 One Time Pad를 학습하였습니다. 그렇다면 이번에는 OTP를 조금 더 실용성있게 개선한 “스트림 암호(Stream cipher)”에 대해 살펴보도록 하겠습니다.

시작하기에 앞서, 간단히 지금까지의 내용을 빠르게 요약하겠습니다. 

암호화라함은, 어떤 메세지 M을 암호화하는 E함수와, 이를 복호화하는 D함수로 구성되며, 암호문을 다시 복호화하면 원래의 메세지를 얻을 수 있어야합니다. 이때 K라는 암호화 키가 사용됩니다.
지금까지 배운 암호로는  Substitution 암호, Vigenere 암호 등이 있었는데, 이것들은 이미 취약함이 만천하에 공개되었으므로 여러분은 절대 실무에서 사용하셔서는 안됩니다. 단순히 역사적으로 이런 암호들이 있었다는 것 정도만을 확인하는 차원에서 기억하시기 바랍니다.
지난 시간에는 OTP라는 암호를 배웠습니다. 이 방식은 상당히 간단합니다. 암호화 키인 K와 메세지 M을 XOR연산을 수행하는 것으로 빠르게 암호화를 수행할 수 있습니다. 또한 암호문 C에 다시 K를 XOR하면 복호화까지 수행되는 방식입니다. (이 때 M, C, K 의 길이는 모두 같아야합니다.)신기하게도 OTP는 이전의 다른 암호방식에 비해 암호문 단독 공격으로부터 ‘완벽히 안전(perfet secrecy)’함이 입증되었습니다. 공격자는 암호문 C로부터 원문M에 대한 그 어떠한 정보도 얻을 수 없습니다.
OTP의 이러한 장점에도 불구하고, 한가지 치명적인 단점이 있습니다. 이것은 Shannon이 증명한 좋지 않은 소식(bad news lama)이라 할 수 있는데요, OTP를 수행하기 위해서는 키의 길이가 메세지의 길이 이상으로 길어야만 한다는 점입니다. 이것이 최악의 단점인 이유는 메세지 송신자와 수신자가 안전하게 통신을 하고 싶어서 암호화를 수행하고, 암호화에 필요한 키를 서로 공유해야하는데 이 과정에서 키의 길이가 메세지처럼 길다면 배보다 배꼽이 더 커지는 상황이 발생하는 것입니다.
그렇다면, OTP의 장점을 살리되, 단점을 최소화할 수 있는 방책은 없을까요?

즉, OTP의 실용적인(practical) 버전을 만들자는 것입니다. 그러한 방법을 일명 “스트림 암호(Stream Cipher)”라고 합니다. 원래대로라면 완전히 무작위적인 난수로 이루어진 암호화 키(Totally random key)를 사용해야하지만, 이것을 조금 단순화 시켜서 의사 난수(Pseudo-random key)로 대체하는 것입니다. 의사 난수가 무엇인지 조금 자세히 살펴보도록 하겠습니다.
의사 난수를 생성하는 Function을 의사난수 생성기라고 하며, 영어로는 PRG(Pseudo Random Generator)라고 부릅니다. 이 함수는 전체 스페이스인 N보다 차원을 축소시킨 S만큼의 스페이스를 seed로 설정합니다. 즉 {0,1}^S 로 표기하면 S-bit의 값이 seed가 되며, 해당 함수를 통해 {0,1}^N인 N-bit의 문자열로 매핑시키는 것입니다. 이때 N은 S보다 훨씬 더 큰 값으로 가정합니다.(N >> S) 예를들어 S가 128bit정도 길이라면, 결과값은 기가바이트 단위의 데이터가 될 수도 있습니다. 이것이 의사난수생성기(PRG)의 역할이며, 이 기능을 수행할 때 효과적(efficiently)으로 그 값을 계산해 낼 수 있다고 가정합니다. 이 알고리즘은 빠르게 계산이 가능하여야하며, 결정론적(deterministic)입니다.
실제로 여기에서 무작위적인 값은 seed이며, 이 seed의 작용으로 인한 결과물은 마치 '무작위인 것 처럼 보이는(look random)’ 값이 도출됩니다. 무작위가 아니라 무작위처럼 보인다는 말은 무슨뜻일까요? 잠시 후 설명드리겠습니다.

그리하여, PRG라는 함수를 활용하여 OTP를 다시 생각해봅시다. OTP에서는 암호화키가 메세지 만큼 길어야했지만, 이번에는 상당히 짧은 K를 사용하려합니다. 이를 위해 PRG(K)를 계산하면 그 결과값은 K를 활용한 (랜덤인 것 처럼 보이는) 적절한 길이의 키가 생성됩니다. 이 값을 메세지 M과 XOR연산을 하여 기존의 OTP방식처럼 암호화를 수행할 수 있습니다.
공식으로 나타낸다면, C = E(K, M) = M XOR PRG(K) 이고, D(K,C) = C XOR PRG(K) 가 되겠습니다.
그렇다면, 이렇게 만들어낸 스트림 암호는 얼만큼 안전한걸까요? 지난시간에 OTP는 섀넌의 정의에 따라 "Perfect secrecy"하다고 배웠습니다. 스트림 암호도 동일하게 Perfect secrecy할까요? (힌트 : OTP는 키의 길이가 메세지만큼 길어야했지만, 스트림 암호의 키는 비교적 굉장히 짦음)

문제 )  스트림 암호는 Perfect Secrecy한 특성을 갖는다?

1) 그렇다. PRG는 굉장히 안전하다고 볼 수 있다.

2) 아니다. Perfect secrecy한 암호문은 결코 존재할 수 없다.

3) 그렇다. 스트림 암호의 모든 암호문은 전부 perfect secrecy하다.

4) 아니다. 왜냐하면 메세지의 길이보다 키의 길이가 짧기 때문이다.


OTP가 perfect secrecy할 수 있었던 이유는 키의 길이가 길다는 전제조건이 있었기 때문이며, 그에비해 Stream 암호는 키의 길이를 짧게했기 때문에 이것을 Perfect하다고 볼 수 없습니다. 그러므로 답은 4번입니다. 어렵지 않으셨으리라 믿습니다.

자, 그럼 당혹스러운 생각이 듭니다. “아니 도대체 그러면 perfect하지 않은걸 왜 쓰는거야?” “그런데도 이게 안전하다고? 왜??” 라는 질문일 것입니다. 이를 설명하기 위해서는 먼저 스트림 암호의 ‘안전성’에 대한 기준을 재정립할 필요가 있습니다. 스트림 암호의 안전성은, 사용했던 PRG함수의 예측불가능성 여부(Unpredictable)에 의해 좌우된다는 것입니다. 이를 설명하기 위해서는 예측가능성(Predictability)을 먼저 이해해야겠지요?

만약 PRG가 예측 가능한 함수라고 가정해보겠습니다. 이 말은 곧 G(K)를 계산한 결과에서, 만약 i번째 값을 알고있고 그 지식을 이용해서 i+1 번째의 값이라던지, 임의의 n번째 값을 획득할 수 있다는 뜻입니다. 이런 경우라면 해당 PRG함수는 굉장히 취약한 것이며 결코 안전하지 않은 함수입니다. 왜냐하면 공격자가 우연히 메세지의 일부분을 획득했을 때 그 정보의 내용을 토대로 나머지 부분을 추측할 수 있기 때문입니다. 예를들어서 인터넷에서 메일을 보내는 경우를 상상해봅시다. 표준 인터넷 메일 프로토콜인 SMTP는 전세계적인 공통 규약이기 때문에 모두가 동일한 약속을 따릅니다. 따라서 본문의 내용은 반드시 콜론(:)으로 시작한다거나, 어떤 특별한 예약어(keyword)가 사용되는지를 모두가 다 알고 있습니다. 따라서 공격자는 해당 메세지의 원문이 메일 형식일 것으로 가정한다면, 첫 글자는 당연히 콜론(:)일 것으로 예상할 수 있고, 이를 통해 :과 어떤 값이 XOR 연산되어 C라는 결과가 나왔는지를 거꾸로 계산하면 암호화 키로 사용된 G(K)값의 일부분을 알 수 있게됩니다. 그리하여 G(K)의 i번째 값을 알아내었으므로, 이번에는 G함수의 예측가능성을 이용하여 i+1, i+2,. .. .n번째 값까지 모두 추론할 수 있는 것입니다.
그러므로 예측가능한 PRG함수를 사용한다면 공격자는 한 글자만 알아도 나머지 모든 글자를 추론함으로써 암호화키를 획득할 수 있게되는 치명적인 문제가 발생합니다. 단 한 비트가 결국에는 아킬레스의 건이 되는 것이죠. 그렇기 때문에 스트림 암호에서 사용하는 PRG는 반드시 예측 불가능(Unpredictable)해야 안전한 것입니다.

예측불가능하다(unpredictable)는 용어의 의미를 조금 더 구체적으로 정의하겠습니다. G: K ->{0,1}^n이라는 function에 대해,만약, 효율적인 알고리즘 A와, 0 <= i <= n-1 의 범위인 i번째 bit의 값이 있고 아래의 식을 만족한다면, 이러한 경우의 의사난수생성기는 예측가능하다(predictable)고 합니다. 

(단, ε=1/2^30 이며 무시할 수 없는(non-negligible) 값이다.)
(단, ε=1/2^30 이며 무시할 수 없는(non-negligible) 값이다.)

(역주 : 1/2 즉 찍어서 맞출 50% 확률보다 아주아주아주 조금이라도 높으면.. 그건 엄밀하게 암호학적 기준으로 이야기하자면 예측가능한 것임)


위의 설명과 반대로, 모든 i번째 비트에 대해 i+1번째 bit를 높은 확률로 예측할 수 있는 효율적인 알고리즘 A가 결코 존재하지 않을 때, 이를 예측불가능(unpredictable)하다고 정의할 수 있겠습니다. 잘 이해하셨나요? 확인하기 위해 간단한 퀴즈를 내겠습니다. 


만약 아래와 같은 의사난수 생성 규칙이 있습니다. 이 함수는 모든 bit들에 대해 한꺼번에 XOR연산을 수행한 결과값 한개를 반환합니다. 그렇다면 이는 예측가능한 함수일까요? 

아주 쉽지요? 1부터 (n-1)가지의 xor한 값을 알고 있다면, 최종 결과값으로부터 역으로 계산해서 n번째 bit를 추론해낼 수 있기 때문입니다. 다시말해서, 딱 한비트 빼고 나머지 모든 비트에 대해 공개한다면 그 한 비트를 풀어낼 수 있으므로 해당 PRG는 예측가능하다고 할 수 있겠습니다.

G가 예측가능하면 취약하다는 점을 배웠습니다. 때문에 해당 PRG는 암호를 구현하는 상황에서 절대 사용해서는 안됩니다. 이런 초보적인 실수가 개발자들 사이에서 자주 일어나곤하는데 반드시 명심하셔야 합니다. 예를들어 선형 합동 생성기(Linear congruential generator, LCG)가 있습니다. LCG에서는 (a,b,p)라는 3가지 파라미터를 사용합니다. a와 b는 정수이고, p는 소수입니다. 이때 PRG는 다음과 같의 정의됩니다. r[0] 를 PRG의 seed로 설정하고, r[i] 는 a * r[i-i] + b mod 로 설정하여 r[i]의 일부분을 취하는 방식으로 i를 증가시키면서 반복문을 수행합니다. 이렇게 하여 얻은 r값은, 통계적으로 봤을 때 꽤 그럴듯하게 분포되어있기 때문에 사람의 눈으로 봤을 때 마치 무작위적인 난수로 보이겠지만, 사실상 매우 간단하게 그 숨겨진 규칙을 찾아낼 수 있습니다. 특히 그 인자들과 마지막으로 생성된 난수를 알면 그 뒤에 만들어질 모든 난수를 예측할 수 있기 때문에 결코 암호학적으로 안전한 난수생성기가 아닙니다. 결코 사용되어서는 안됩니다.


또 다른 예시로,glibc라는 유명한 라이브러리가 있습니다. 이 라이브러리가 구현된 내부를 살펴보면, 위와같이 매우 간단한 수식에 몇번의 shift연산을 가해서 난수 문자열을 생성하는 것을 확인하실 수 있습니다. 이 방법 역시도 굉장히 쉽게 예측이 가능하므로, 절대로 glibc의 random function()을 암호학적인 용도에 사용해서는 안됩니다. 실제로 커버로스 버젼4에서 random()함수를 사용하였기 때문에 안전성이 무력화되어버린 사례도 있습니다. 그렇다면 난수를 안전하게 생성할 수 있는 방법은 없을까요? 다음 강의에서 그 부분을 자세히 다루도록 하겠습니다.

강의를 마무리하기 전에, 아까 언급했던 개념을 소개해드리고자 합니다. Negligible(사소해서 무시해도 좋은)과 Non-negligible(무시할 수 없는)에 대한 개념입니다. 이 개념은 암호학 연구자 그룹과 실무자 그룹 사이에서 바라보는 시각에 약간의 온도차가 있습니다. 어쨌든, 연구자들은 ε가 1/2^30 (십억분의 1) 보다 큰 값이라면 이는 무시할 수 없는 값(Non-negligible)이라고 합니다. 이 값이 매우 커보이지만, 1GB의 데이터가 2^30 ~ 2^32 정도이기 때문에 실제 우리의 실생활에서 상당히 현실적인 기준입니다.  

반대로, 1/ 2^80 보다 작은 값인 경우에는 현실적인 시간안에 발생할 가능성이 매우 드물다고 보기 때문에, Negligible(무시해도 좋은) 이벤트라고 정의합니다. 이러한 정의는 약간의 오차가 발생한다는 점을 감안해야 합니다. 조금 더 엄격하게 암호학 이론을 연구하는 사람들은 ε을 단순히 scalar 값으로 보는 것이 아니라, 하나의 function 으로 정의합니다. 아래와 같이 일종의 다항식 시간에 대입하여 λ값을 계산한다고 했을 때의ε을 비교하는 방식입니다.


두 개념을 잘 이해하셨나요? 간단한 퀴즈를 드리겠습니다.

만약 Negligible한 값인 1 / 2^λ와, Non-negligible한 값인 1 /λ^1000이 주어졌다고 합시다. 그리고λ값이 홀수인지 짝수인지에 따라 ε(λ)값이 결정된다고 합시다. 즉, 홀수항은 지수적으로 작아지고, 짝수항은 다항적으로 작아집니다. 그렇다면 이 둘의 성질을 모두 가진 함수는 Negligible 일까요? Non-negligible 일까요?


정답은 Non-negligible한 함수라고 볼 수 있습니다. 간단히 생각해서 Non-negligible한 값은 이미 매우 큰 값이기 때문에 이것이 포함되어있으면 그 결과도 Non-negligible 하게 되는 것이죠. 통상적으로 흔히 polynomial보다 큰지, 작은지를 구분합니다. 하지만 본 강의에서는 편의상 exponential보다 작으면 negligible이라고 할 것이며, polynomial보다 크면 non-negligible이라고 규정하도록 하겠습니다.


지금까지 One time Pad를 실용적인 암호 알고리즘으로 활용할 수 있는 핵심 아이디어, 즉 스트림 암호(Stream Cipher)를 학습하였습니다. 다음 강좌에서는 스트림암호가 과연 어떻게 안전한지에 대해 논해보도록 하겠습니다. 이를 위해서는 보안성(security)라는 용어에 대한 정확한 기준이 제시되어야 할 것이며, '완벽히 안전(perfet secrecy)'한 것이 충분히 좋은것만은 아니라는 점을 연구해보도록 하겠습니다. 수고하셨습니다.

CPUU님의 창작활동을 응원하고 싶으세요?