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


이번 강좌는 Stream Ciphers 1: the one-time pad and stream ciphers 에 포함된 첫번째 강의인 "Information Theoretic Security and The One Time Pad" 입니다.


지금까지 살펴본 고전적인 암호들은 대부분 취약점이 발견되었다는 것을 살펴보았습니다. 그렇다면 이제는 고개들 돌려서, 비교적 더 잘 설계된 암호 방식들을 학습해보도록 합시다.

시작하기에 앞서, 먼저 ‘암호’가 정확히 무엇인지 면밀하게 정의하여 보겠습니다. 암호란 두가지의 알고리즘으로 이루어집니다. 각각 ‘암호화 알고리즘’과 ‘복호화 알고리즘’이라고 부릅니다. 또한, 암호의 세번째 요소인 키(key)가 포함되며 이를 일반적으로 K로 표기합니다. K값의 크기, 즉 K가 가질 수 있는 범위를 ‘키 스페이스’로 부를 것입니다. 암호화 알고리즘 E는 원문 메세지M과 K를 사용하여 암호문 C를 생성합니다. 반대로, 복호화 알고리즘 D는 암호문C와 K를 사용하여 원문 M을 복원해냅니다. 이 두 알고리즘은 양립하며, 정확해야 한다는 특성을 가지고 있습니다. 모든 메세지에 대해, 모든 키에 대해 성립해야하며 암호화 과정과 복호화 과정은 정확무오해야 합니다. 이를 공식으로 표현하자면 D(K, E(K,M)) = M이며, Consistency Equation 이라고 합니다. 복호화가 불가능한 알고리즘(해시)을 제외하고는, 모든 암호 알고리즘은 이 방정식을 따릅니다.


특별히 '효과적이다‘(efficient)라는 단어에 강조를 해두었습니다. 효과적이어야 한다는 뜻은 사람마다 다르게 이해될 수 있을 것입니다. 만약 암호학적 이론에 조금 더 관심을 두는 사람이라면 다항 시간(Polynomial time)안에 계산이 수행되어야 한다는 것으로 받아들일 것입니다. 때문에 해당 방면으로 연구하시는 분들은 E와 D 알고리즘은 각각의 input값에 따른 다항시간 안에 계산이 수행되어야 함을 증명하기 위해 논문을 쓰십니다. 하지만 암호학적 실무에 종사하시는 분들의 경우에는 알고리즘이 실제로 수행되는 시간이 얼마나 짧은지를 목적으로 하십니다. 때문에 기가바이트 단위의 데이터를 암호화하는데 1분을 초과해서는 안된다거나 하는 기준으로 벤치마킹을 하곤 합니다. 어쨌든, 저희가 지금 공부하려는 상황에서 효율성(efficient)는 양쪽 어느 분야에 적용하던 상관없을 것입니다. 여러분이 배워서 활용하시는 분야에 맞추어 적절히 적용하시면 됩니다.


또 한가지 말씀드리자면, 암호화 E는 확률적 알고리즘(Randomized)이라는 것과, 복호화 D는 결정론적(Deterministic) 알고리즘이라는 것입니다. 암호화시에는 원본 메세지를 사용해서 전혀 다른 무작위의 비트들을 새롭게 생성해냅니다. 그 결과물은 암호방법에 따라 달라질 수 있습니다. 하지만 복호화 알고리즘은 무작위한 성질을 갖지 않고, 항상 동일한 결과값을 도출하도록 설계되어 있습니다. 

그렇다면 이제 조금 더 나은 암호화 방법을 소개시켜드리려합니다. 오늘 처음으로 배울 것은 OTP(One-Time Pad) 입니다. OTP는 20세기초 Vernam이 개발하였습니다. OTP의 특징은 암호화하려는 메시지가 있다면, 그 메시지의 길이만큼의 동일한 space를 갖는 key가 필요하다는 것이며, 암호문 역시 동일한 space의 String이 된다는 것입니다. 때문에 OTP의 key는 무작위로 나열된 아주 긴 문자열을 사용하며, 메세지의 길이만큼의 암호문이 출력됩니다. 

이제 OTP가 작동하는 원리를 알아보겠습니다. 간단히 말해서 메세지 M과 키 K를 XOR연산을 수행함으로써 암호화를 수행할 수 있습니다. 여기에서 msg를 0110111로 가정하고, k를 1011010으로 설정되어있다고 해보겠습니다. XOR연산은 두 이진수 값을 더한 뒤에 2로 나눈 나머지(Modulo)를 구하는 것입니다. 이를 적용하여 K XOR M을 계산해봅시다. 답은 1101110 입니다. 이것이 바로 암호문입니다.


그럼 이번에는 복호화를 수행해볼까요? 복호화방법은 암호화와 비슷합니다. 이번에는 k와 C를 XOR하는 것이죠. 정의를 자세히 증명해보겠습니다. D(k, E(k,m))이었습니다. 이를 XOR를 대입하여 풀어보면 D(k, k XOR m)  이 되고, 다시 XOR를 대입하면 k XOR ( k XOR m) 입니다. 이 때 결합법칙(associative law)가 적용되므로 (k XOR k) XOR m 이 됩니다. 같은 값을 XOR 하면 무조건 0이 됩니다. 0과 m을 XOR 하면 m이 출력됩니다. 그러므로 복호화 결과가 원문 메세지와 같아진다는 것을 알 수 있습니다. 이를 통해 OTP가 암호화임을 확인해보았습니다. 그렇다면 OTP의 암호화 강도는 얼마가 될까요? 계속 학습을 진행하기전에, 여러분이 잘 따라오고 계시는지 퀴즈를 하나 드리겠습니다.


만약 여러분에게 원문 메세지 M과, 그것을 OTP로 암호화한 결과문인 C가 주어졌다고 가정해봅시다. 이 때 해당 M이 어떤 K값을 사용해서 C로 암호화가 되었는지 찾아낼 수 있을까요? 즉, M과 C만을 가지고서 K값을 추론해낼 수 있을까요? 

모두 정답을 맞추셨으리라 기대합니다. 정답은 “Yes” 입니다. XOR값의 성질에 의해 M과 C를 XOR하면 K값이 쉽게 도출됩니다. 혹시 잘 이해가 되지 않으셨더라도 "그대여, 아무 걱정하지 말아요!" 강의를 계속 진행하며 알 수 있을 것입니다.

어쨌든 다시 본론으로 돌아와서, OTP는 성능 측면에서 꽤 우수합니다. 보셨던 것과 같이 단순히 key와 메시지를 XOR하는 연산만을 수행함으로써 암호화를 하기 때문에, 아주 긴 메세지라도 굉장히 빠른 속도로 처리할 수 있습니다. 그렇지만 안타깝게도, 현실 세계에서 OTP는 활용하기 어렵습니다. 왜일까요? 그것은 key의 길이가 길어지면 그만큼 사용이 불편하기 때문입니다. OTP는 메세지의 길이만큼 똑같이 긴 key를 사용해야만 합니다. 앨리스와 밥이 암호화된 안전한 통신을 원할 때, 메세지를 보내면서 동시에 key도 메세지와 동일한 수준으로 관리하며 송수신해야 한다는 점은 배보다 배꼽이 거의 비슷하게 커진 상황이라고 할 수 있습니다. 비효율적이라는 문제 때문에 실생활에 적용하기 애매한 부분이 있는 것이죠. 그럼에도 불구하고 이번 강의에서는 이론적으로 OTP의 작동방식을 잘 이해하고 넘어가시는 것이 다음 강의를 위해 좋습니다.


그렇다면, 과연 OTP는 얼마나 안전한 것일까요? 얼마나 견고한 암호를 생성할 수 있을까요? 이 질문에 답을 하기 위해서는 먼저 ‘안전하다는 것은 정확히 어떻게 증명할 것인가? 그 기준이 무엇인가?’에 대해 정의해야 할 것 같습니다.

암호의 안정성에 대해 학문적으로 논하기 위해서는 먼저 정보이론(Information theory)를 조금 살펴보는 것이 좋습니다. 흔히들 정보이론의 창시자이자 아버지라고 부르는, 클로드 섀넌(Claude Shannon)을 빼놓고 이야기하면 서러워하시겠지요. 그는 이미 1949년에 OTP의 안정성에 대한 분석 논문을 투고하였습니다. 섀넌의 기본적인 아이디어는 이러합니다. “암호문을 아무리 들여다보더라도, 그것으로부터 원문에 대한 정보를 전혀 알아낼 수 없다.” 다시 말해서, “암호문은 그 자체만으로 아무런 힌트도 주지 않는다.”라는 것입니다. 정보이론을 창시하신 분은 어떤 의도로 이렇게 말씀하셨을까요?

섀넌이 내린 정의를 분석해봅시다. 암호화 / 복호화 함수 E와 D가 있고, 이에 따른 3가지 필수요소(Key, 메세지, 암호문)이 각각의 Space에 따라 존재한다고 가정했을 때, 만약 다음의 조건이 성립한다면 


임의의 메세지 M0와 M1에 대하여,
M0과 M1의 길이가 len(M0) == len(M1)로 서로 같고, 
그 각각을 암호화한 E(K, M0)와 E(K, M1)의 결과가 C가 될 확률이 서로 동일하고, 
K가 Uniform Distribution일 때

그 암호문은 완벽하게 안전(perfect secrecy)합니다.


이해를 돕기위해, 만약 공격자가 특정한 암호문 C를 얻어냈다고 가정해봅시다. 이 C의 원본인 M을 찾기위해 애를 써보려해도, C로부터 M을 찾아낼 확률이 모든 경우의 수에 대해 동일한 값으로 일정하다는 것입니다. 만약 OTP의 암호문에 대해 전수조사 공격을 시도한다면, 모든 가능한 경우의 수가 전부다 출력될 것입니다. 그중에는 암호화에 사용했던 것과 똑같은 키도 포함이 되어있겠지만 공격자는 그 중 어떤것이 올바른 평문인지 판단을 할 수 없게됩니다. 각각의 결과물이 정답일 확률이 모두 동일하기 때문입니다. 따라서 공격자는 키나 평문을 추측할 수 있는 어떠한 방법도 없으며, 암호문의 통계적인 특성 또한 존재하지 않게 됩니다. 평문과 암호문 사이에도 아무런 관계가 없습니다. 이것이 섀넌이 주장한 핵심 내용입니다.

섀넌의 정의(Information-theoretic security)가 구체적으로 어떤 의미를 내포하고 있는지 조금 더 심층적으로 살펴봅시다. ‘두 확률이 같다’는 것이 과연 무슨 뜻일까요? 공격자가 어떤 암호문 C를 우연히 엿볼 기회가 생겼다고 생각해봅시다. 그리고 이것의 원문이 무엇일지를 골똘히 생각해봅니다. 그런데 M0가 암호화가 된 결과물인지, M1의 결과물인지 도대체 알 수 없습니다. 각각의 확률이 모두 동일하기 때문입니다. 이 세상의 모든 메세지를 다 대입하더라도, 적절한 key를 이용하면 전부 C로 만들 수 있습니다. 그렇다면 반대로 특정한 C가 어떤 것의 암호화된 형태인지 파악이 불가능하게 됩니다.

굉장히 중요한 내용이므로 한번 더 정리하겠습니다. 이번에는 엄밀하게 수학적 표현을 사용하였습니다. 만약 특정한 암호문이 주어졌을 때, 그것의 원문을 추론해낼 수 없습니다. 그것이 M0였는지, M1이었는지를 알 수 없습니다. 뿐만 아니라, M2이거나 M3, 심지어 M5 일 수도 있습니다. 이 모든 메세지들은 정확히 똑같은 확률로 암호문 C를 만들어낼 수 있는 가능성을 가지고 있습니다. 그러므로 OTP로 암호화를 사용하는 사람은 해커의 입장에서 굉장히 강력한 적수가 될 것입니다. ‘암호문으로부터 평문과 관련한 아무런 정보도 얻어낼 수 없다.’ 그러므로 암호문 단독 공격(Cipher text Only Attack)은  OTP방식에서는 아무런 소용이 없습니다. 


이제 'OTP가 완벽히 안전하다’는 말을 이해하셨겠지요? 그렇다면 질문을 하나 드려보겠습니다. 만약 OTP를 사용하여 암호화를 수행할 때, 특정한 메세지M을 알맞은 암호문C로 매핑시키는 OTP key는 몇개가 존재할까요? 다시말해서 M XOR K를 수행해서 그 결과값이 C를 성립하게 만드는 K값은 몇개나 존재할까요? 질문에 답해보세요.

답은 1이라는 것 아시겠지요? 오직 한개의 해밖에 존재하지 않는다는 것을 기억하세요. 

왜냐하면 E(K, M) 이 C이라면, K XOR M = C라는 뜻이고, 이것은 다시 K = M XOR C를 성립하게 합니다. 이 계산의 결과는 당연히 1개의 답밖에 주지 않으므로, E(K,M) =C 의 결과 역시 오직 1개밖에 존재하지 않습니다. 


그동안 배웠던 substitution 암호, vigenere 암호, ROT 등등은 암호문 단독 공격(Cipher text only attack)에 무너지고 말았지만, OTP 만은 해당 공격에 대해 완벽히 안전하다는 것을 수학적으로 증명하였습니다. (그렇다면 암호문 단독 공격이 아닌, OTP를 깰 수 있는 다른 공격도 있을까요? - 나중에 살펴보죠)

하지만 좋지 못한 소식이 있습니다. OTP가 안전하다고 그렇게 강조했지만, 그럼에도 불구하고 단점이 존재하기 마련입니다. OTP의 암호화 키의 길이는 상당히 길수밖에 없습니다. 자신의 메세지의 길이만큼이나 똑같이 긴 키를 사용해야 하기 때문이지요. 그러므로 OTP의 효율을 높이기 위해서는 키의 길이를 줄일 수 있는 방법이 없을지를 고민해야 합니다. 그런 방법은 없을까요?


안타깝게도 없습니다. 위에서 멋진 공식을 정의했던 섀넌은, OTP의 안전성을 증명함과 동시에 한가지 제약조건을 언급했습니다. 키의 길이는 메세지의 길이보다 크거나 같을 수밖에 없다는 것입니다. 이것은 매우 치명적인 단점입니다. 이러한 이유 때문에 OTP는 현실 세계에서 사용될 일이 거의 없습니다. 우리가 이번 course에서 살펴본바, One Time Pad는 매우 흥미로운 아이디어이긴 하지만, 그 한계가 있음을 확인하였습니다.


다음번 강의에서는 OTP 등의 Stream 암호를 실생활에서 활용하는 사례에 대해 계속해서 연구해보도록 하겠습니다. 수고하셨습니다.


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