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


이번 강좌는 Stream Ciphers 2: attacks and common mistakes 에 포함된 "Attacks on Stream Ciphers and The One Time Pad" 입니다.


이번 강의에서는 One Time Pad에 대한 공격기법을 설명하고, 이를 통해 스트림 암호 사용에 있어서 주의해야 할 사항들을 집어보고자 합니다.

지난 시간까지의 내용을 짧게 요약해보겠습니다. One time Pad는 원문 메시지와 비밀키(secret key)를 배타적 논리합(Exclusive-OR) 연산을 수행함으로써 암호화합니다. 이때 Secret key의 길이는 메시지의 길이와 동일해야만 합니다. 복호화 과정 역시 암호문에 동일한 비밀키를 다시 한번 XOR함으로써 진행됩니다. Key가 균등분포(Uniform)을 따르고 예측할 수 없는 난수라고 가정했을 때 One-Time Pad는 암호학적으로 완벽히 안전(Perfect secrecy)함이 Shannon에 의해 증명된바 있습니다.
하지만 문제는 키의 길이가 메시지의 길이만큼 길어야한다는 조건에 달려있습니다. 이러한 이유로 One-time Pad를 사용하기에는 현실적인 어려움이 따릅니다. 따라서 One-time Pad를 좀더 실용적으로 구현하기 위해 의사 난수 생성기(Pseudo Random Generator)라는 것을 사용합니다. PRG는 짧은 길이의 값을 seed로 사용하여, 일정한 알고리즘을 적용하여 메시지의 길이만큼 긴 비트수열을 생성해냅니다. 결국 작동방식 자체는 One-time Pad와 Stream 암호 사이에 큰 차이점은 없어 보입니다.

이번 시간에는 안타깝게도, Stream 암호가 Perfect Secrecy하다고 보장할 수는 없다는 사실을 보여드리고자 합니다. 왜냐하면 스트림 암호는 의사난수생성기(PRG)에 안전성을 의존하기 때문이며, 이는 진성 난수 생성기(Truly Random)에 비해 예측불가능성(Un-predictable) 측면에서 부족할 수 밖에 없습니다. *(역주 : 진성 난수 생성은 현실적으로 굉장히 어렵습니다.) 어쨌든, 그렇다면 이제부터 PRG와 관련하여 필연적으로 발생하는 스트림 암호에 대한 취약점과, 그 공격에 대해 살펴보도록 합시다.

먼저, One time Pad의 취약점은 무엇일까요? 이름에서 알 수 있듯이, 일회용(One-time)이라는 것입니다. 만약 이를 두번 이상(Two-time)사용하게 된다면 어떻게 될까요? 이를 “Two time pad Attack”공격이라고 합니다. 즉, 똑같은 키값을 사용해서 2개 이상의 메시지를 암호화한다면 그 방식의 안전성은 형편없이 깨지게 됩니다. 도청자(eavesdropper)는 해당 메시지를 모조리 해독해낼 수 있습니다. 예를들어볼까요? 두개의 메시지를 각각 M1과 M2라고 가정합니다. 이 둘을 동일한 키(pad)를 사용하여 암호화한 결과를 C1, C2라고 부르겠습니다. 이때 도청자가 C1과 C2를 입수하였습니다. 그가 C1과 C2를 XOR 하면 어떤 결과가 나올까요?

이해가 되시나요? C1과 C2에 XOR 연산을 수행한다면, 암호화 키(Pad)가 소거되어서 원래의 평문인 M1과 M2들의 XOR결과가 도출됩니다. 영어의 경우 몇가지 알려진 통계적 성질을 통해서 더욱 쉽게 추론이 가능합니다. 만약 평문끼리 XOR된 값들을 몇가지 더 확보할 수 있는 상황이라면 더욱 쉽게 키를 획득하여 원문을 복원할 수 있습니다. 영어가 아닌 ASCII의 경우에도 마찬가지로 인코딩 정보의 redundancy를 사용하여 원문 메시지를 파악할 수 있습니다. 원문 하나(M1)의 정보를 알았다면 이를 다시 XOR해서 다른 원문(M2)도 획득할 수 있습니다. 그러므로 One-time Pad를 사용할때에는 절대로 같은 비밀키(Pad)를 2번 이상 사용해서는 안됩니다. 누군가가 이를 가로챈다면 모든 내용을 해독당할 가능성이 큽니다. 따라서 Stream 암호나 One-time Pad나 동일하게 비밀키로 사용할 Pad는 글자그대로 일회용(One-time)으로 사용하셔야만 합니다.

실제로 사례를 살펴보겠습니다. 스트림 암호나 One-time Pad의 비밀키를 두번 이상 재사용하는 것은 종종 일어나는 실수이며, 생각보다 훨씬 위험한 결과를 초래합니다. 1940년대 초반 냉전(Cold War) 당시에 실제로 러시아에서 중요한 기밀 정보들을 One-time Pad를 사용하여 암호화하였습니다. 당시에는 암호화 키를 생성하기 위해서 사람이 수동으로 주사위를 여러번 던져서 나온 결과를 일련의 패턴으로 만들어서 나열하였습니다.(*역주 : wiki백과에 따르면 35,000 pages) 이것을 매번 새로 생성한다는 것은 불가능에 가까웠으며 매우 곤란한 작업이었습니다. 이것을 단지 한번 쓰기 위해서 그 많은 노력을 다해야한다는 것에 깊은 회의감을 느낀 것이죠. 그래서 그들은 One-time Pad를 재활용하기로 합니다. 그리고 그것은 미국측 정보국 요원들에겐 매우 중요한 공격 포인트가 되었죠. 그들은 이 암호문들을 수집하였고 그것들이 동일한(Two-time) Pad로 암호화되었다는 것에 착안하여 3000여개의 원문을 복호화 작업에 성공합니다. 이를 일명 베노나 프로젝트(Project Venona)라고 하며, 암호분석자들에게는 전설과도 같은 역사적 사건입니다. 결론적으로 Two-time Pad는 결코 안전하지 않음이 이미 오래전부터 밝혀졌습니다. 


뿐만 아니라, 현재 시점에서도 동일한 취약점이 존재합니다. 특히 네트워크 프로토콜에 포함되어있는 사례를 살펴보도록 하겠습니다. Windows NT운영체제에는 PPTP(Point to Point Transfer Protocol)이 존재합니다. 클라이언트와 서버 사이의 통신을 안전하게 암호화하기 위한 수단이죠. 이를 위해서는 서버와 클라이언트 사이에 비밀키를 공유하고, 이를 이용하여 메시지를 주고 받습니다. 이때, 해당 클라이언트와의 통신과정에서 Stream 암호키를 사용하게 됩니다. 보내고자하는 메시지들(M1, M2, M3 …)을 우선 모두 덧붙여서(concatenation), 이것을 하나의 긴 메시지로 간주하고 여기에 적절한 스트림 키수열과 XOR 연산을 수행하는 것입니다. 사실 여기까지는 아무런 문제가 없습니다. 데이터는 적절한 키를 사용하여 암호화되었고 안전하게 잘 전송됩니다. 하지만 문제가 되는 것은, 위와 동일한 과정이 서버측에서 다시한번 반복된다는 것입니다. 서버가 보려는 메시지들(S1, S2, S3 …) 역시 덧붙여져서 하나의 긴 메시지가 되는데, 이를 암호화 할 때에는 안타깝게도 위에서 생성했던 동일한 의사난수가 적용되고, 결국 동일한 스트림 암호 키가 사용됩니다. 결국 위에서 살펴본 것과 같은 Two-time pad 문제가 클라이언트 측과 서버측의 메시지 암호화시에 발생하는 것입니다.


이러한 사례들로부터 배울 수 있는 교훈은 양방향 통신에서 절대로 같은 키를 사용해서 암호화해서는 안된다는 것입니다. 즉, 클라이언트측에서 암호화할 때 사용하는 키와, 서버측에서 암호화할 때 사용하는 키는 서로 독립적으로 사용해야 합니다. 이를 하나의 키 쌍(pair)로 생성하여 하나는 서버용, 하나는 클라이언트용으로 사용하는 방식을 추천드립니다. 

Two-time Pad를 사용한 또 하나의 잘못된 사례로는 Wi-Fi 통신에서 사용되는 IEEE 802.11b 프로토콜이 있습니다. 여기에는 일명 WEP라 불리우는 암호화 계층이 포함되어 있으며, 이 WEP는 보안적 측면에서 좋지않게 설계되어 매우 취약한 프로토콜입니다. 저는 보통 WEP를 소개할 때 ‘결코 사용해서는 안될’ 예시로만 언급하지, 실생활에서는 절대 사용하지 않습니다. 여기에서도 내부적으로 Two-time pad에서와 동일한 문제점을 가지고 있습니다.


WEP가 어떤 원리로 작동하는지를 간단히 살펴보겠습니다. WEP는 무선 공유기를 사용하려는 클라이언트 사이의 구간을 암호화할 때 사용됩니다. 메시지(M)의 오류검사를 위해 CRC체크섬을 계산하여 덧붙이고, 여기에 사용할 비밀키(K)를 통해 메시지(Frame이라는 용어를 사용)를 암호화하여 전송합니다. WEP를 설계한 사람들은 스트림 암호화에서 매번 키를 다르게 적용해야 한다는 점은 숙지하고 있었습니다. 그리하여 단순히 동일한 Key를 반복사용하는 방법을 취하지 않고, 대신 Key에 초기화 벡터(IV)를 추가한 뒤 이를 PRG의 seed로 사용하는 기법을 사용했습니다. IV는 24bit길이의 스트링으로 이루어져있는데, 암호문에 추가하여 전송하면 수신자측에서 IV를 분리하여 복호화에 사용하도록 한 것입니다. 이 IV값에 일종의 카운터를 적용하여 매번 변화를 주면 각각 다른 스트림을 출력할 것으로 생각한 것입니다. 


그러나 이 방법은 현명하지 못한 선택이었습니다. IV의 길이가 24bit이고, 1프레임에 1씩 카운트한다고 했을 때 2^24, 즉 1600만 프레임정도면 IV값이 다시 초기화되어 최초의 상태로 돌아오고, 결국 동일한 패턴이 반복되는 사이클을 형성하게 됩니다. (원활히 네트워크를 사용하는 환경이라면 이정도 수치는 길지 않은 시간안에 수집됩니다.) K는 변하지않는 값으로 유지되고, 동일한 IV값으로 두개 이상의 다른 메시지가 암호화된다면, 결국 Two-time Pad 문제가 다시 발생하게 되는 것입니다. 공격자는 이를 도청하여 원문을 복호화낼 수 있습니다.


뿐만아니라 더욱 최악의 문제는 802.11 네트워크 자체의 취약점입니다. 해당 장비를 재부팅하면 IV 값은 0으로 초기화됩니다. 때문에 처음 통신에 사용되는 값은 (K + 0)으로 암호화되는 것이고, 이 상태로 지속적으로 통신을 유지한다면 K값마저 노출될 수 있습니다. 이러한 프로토콜 자체의 문제로 인해 더이상은 WEP를 사용하지 않아야 합니다.

WEP이 가지고 있는 또 하나의 심각한 취약점을 계속해서 살펴보겠습니다. 이것이 얼마나 중대한 위협이고, 어떻게 이를 개선시킬 수 있는지 설명하겠습니다. 위에서 언급한 사례로부터 얻은 교훈은, 패킷마다 모두 다른 키를 사용하도록 설계해야 한다는 것이었습니다. 그리하여 모든 프레임들을 각각 다른 키(IV + K)로 암호화하도록 다시 설계하였습니다. 안타깝게도, 그들은 이를 조금 더 정교하게 설계하진 못하였습니다. 단순히 숫자(24bit)로 카운터를 적용하였는데, 예를들면 프레임1을 암호화 할 때에는 1+K로, 프레임2을 암호화할 때에는 2+K로, 그 다음은 3+K .. 이런식으로 사용한 것이죠. 따라서 각 키들은 서로 다르기는 하지만 자세히 관찰해보면 서로 매우 깊은 연관성이 있다는 것을 발견할 수 있었습니다. 또한, K는 의사난수로 생성된 104bit길이의 값입니다. 이렇게 24+104 = 총 128bit가 됩니다. 그런데 104bit의 K가 동일한 패턴으로 삽입되기 때문에, 각 키들 사이에서 긴밀한 연관성을 유발하게 되고, 따라서 ‘Random’하지 않은 결과를 유발하게 됩니다. 결국 암호학적으로 안전하지 않게 설계된 난수생성기 때문에 상당수의 키가 유사한 형태로 생성되고, 각 키들의 패턴을 예측할 수 있게되는 상황을 초래합니다. 


WEP에서 사용된 취약한 의사난수생성기(PRG)의 이름은 일명 RC4라고 합니다.(RC4는 다음 시간에 자세히 다루도록 하겠습니다.) 이 RC4에대한 효과적인 공격을 발견한 사람들의 이름을 따서 “FMS(Fluhrer, Mantin and Shamir attack), 2001”라고 합니다. 10^6(백만) 프레임 정도를 획득할 수 있으면, 그것을 분석하여 비밀키(secret key)를 찾아낼 수 있습니다. 단순히 도청하는 것만으로도 키를 복원할 수 있다는 것은 정말 막대한 파멸을 초래하는(disastrous) 심각하면서도 효율적인 공격입니다. FSM 2001 공격이 현재는 더 대중화되어서 AirSnort, Weplab, aircrack 등의 툴을 사용하면 4만 프레임정도만으로도 비밀키를 더 쉽게 찾아낼 수 있는 기법들이 널리 알려져 있습니다. 


그렇다면, WEP를 조금 더 안전하게 설계하려면 어떻게해야 할까요? 제 생각에는 메시지를 전부 덧붙여서 하나의 매우 긴 스트링으로 만든 후에 PRG(K)를 사용하여 암호화하는 것이 낫습니다. 

또 다른 설계방법으로는, 각각의 프레임들이 서로 독립적인 PRG(K)를 사용하여 암호화하도록 하는 것입니다. 이렇게 할 경우 각각의 K값들은 연관성이 없으므로 거의 Random하다고 보아도 합당합니다. 만약 PRG 함수 자체가 암호학적으로 안전하게 설계되어 seed를 random하게 생성한다는 것만 보장된다면, 그 결과값도 안전하다고 볼 수 있습니다. 

Two-time pad 문제로 인해 발생하는 현실적인 또다른 예시는 바로 Disk Encryption 입니다. 만약 “Bob에게” 라고 작성한 파일이 있고, 그것을 암호화하여 디스크에 저장했다고 칩시다. 추후에 당신은 그 파일을 이번에는 “Eve에게”로 수정하여 다시한번 저장했다고 칩시다. 이번에도 동일한 암호화 방식을 사용했습니다.이제 공격자의 입장에서 해당 파일을 살펴보면, 파일의 상당부분이 동일한데, 딱 한 부분(Bob에게 -> Eve에게)만 바뀌었다는 사실을 깨달을 수 있습니다. 비록 암호화되어 있으므로 그 글자가 Bob인지 Eve인지를 바로 구분할 수는 없을 것입니다. 그럼에도 불구하고 위에서 살펴보았듯이 이러한 정보가 공격자에게 노출되는 것은 상당히 위험합니다.그러므로 디스크 암호화와 같은 분야에서는 Two Time Pad 문제 때문이 아니더라도, 근본적으로 Stream 암호나 One Time Pad를 적용하기에 적절하지 않습니다. 어떤 내용이 변경되었고 어떤 것이 유지되었는지를 비교하고 통계를 분석함으로써 작업내역을 유추할 수 있기 때문입니다. 이런 경우에서는 파일 내용중 일부분만 바뀌었더라도 되도록 변화의 폭을 크게 확산시켜서 나머지 데이터들의 암호화에도 영향을 미치도록 설계하는 것이 좋습니다. 이를 블록암호(Block Cipher)라고하며, 다음 주제로 다루도록 하겠습니다.

방금의 내용을 요약하여 정리하겠습니다. 이번 강의의 핵심은 스트림 암호에서 Key를 두번이상 재사용해서는 절대로 절대로 안된다는 것을 거듭 강조하였습니다. 만약 기본 설정이 그렇게 되어있는 경우라하더라도, 여러분은 그 설정을 바꾸셔서 반드시 매번 다른 키를 사용할 수 있도록 하셔야 합니다. 예시로 들었던 것 중에는 네트워크 트래픽과 관련된 내용이 있었습니다. 매 세션마다 매번 다른 키를 사용하도록해야 합니다. 디스크 암호화의 경우에서는 Stream 암호가 적합하지 않다고 말씀드렸습니다. 왜냐하면 파일의 변화를 관찰하다보면 파일의 내용에 대한 단서가 노출될 수 있기 때문입니다. 이로써 Two-time pad에 대한 설명을 마무리 짓도록 하겠습니다.

스트림 암호는 기밀성(confidentiality)을 보장할 수 있지만 키를 잘 관리하지 못한다면 기밀성에 타격을 받을 수 있다는 것을 지금까지 설명드렸습니다. 두번째로 말씀드릴 스트림 암호의 위험성은, 바로 무결성(integrity)를 보장해주지 못한다는 점입니다. 사실 스트림으로 암호화된 결과값은 누구나 쉽게 위변조가 가능합니다. 이러한 속성을 malleability라고 부릅니다. 예를들어, m이라는 메시지를 k로 암호화하여 전달했다면 그 결과값은 m xor k가 됩니다.그런데 악의적인 공격자가 p 라는 값을 끼워넣는다면 어떻게 될까요?이때의 결과값은 (m xor k) xor p 로 변조되었을 것입니다.아무것도 모르는 수신자가 이것을 받고, 약속했던 k 값으로 복호화를 시도한다면, 그가 얻게되는 값은 무엇일까요?

k값이 소거되었으므로 m xor p 값이 주어질 것입니다. 이는 원래 의도했던 m 값이 아니라, 공격자가 p를 사용해 훼손시켰으므로 오염된 정보입니다. 안타깝게도 이러한 종류의 변조가 일어났다는 사실을 검증할 수 있는 방법이 없습니다. 뿐만 아니라, 이러한 공격은 실제로도 매우 유효한 위협이 됩니다. 기밀성에 대한 공격만 위험한 것이 아니라, 무결성에 대한 것도 공격이기 때문입니다.


위의 화면은 Bob이 메시지를 전송한 상황을 도식화하고 있습니다. 이 메시지는 k값으로 암호화되기 때문에 공격자는 그것을 도청한다하더라도 내용이 무엇인지 알 수 없습니다. 그러나 그는 From Bob이라는 글자가 반드시 포함되어있을 것이라고 예측하고 이를 조작하려는 나쁜 마음을 품습니다. Bob의 ASCII 값은 42 6F 62 로 표현할 수 있습니다. 이것을 Eve(45 76 65)로 조작하기 위해서 두 메시지를 XOR 한 값을 계산해냅니다. (07 19 07) 그리고 이를 암호화된 메시지에 XOR 합니다. 이렇게 되면 기존의 Bob과 Bob xor Eve 에서 Bob이 소거되고, 메시지를 복호화했을 때 그 결과는 마치 Eve인 것으로 보이게 됩니다. 즉, 공격자는 메시지의 내용을 도청하지는 못했지만 그 메시지가 마치 전혀 다른 사용자의 것인것처럼 속임으로써 메시지의 본래의 기능을 방해하였습니다. 이 역시 암호학적인 관점에서 매우 중대한 위협입니다.


암호에서 무결성을 보장하려면 어떤 방법이 있을까요? 이 부분에 대해서도 추후에 논의해보도록 하겠습니다.어쨌거나 오늘의 마지막 교훈은, One time pad는 무결성을 보장해주지 못하며 따라서 메시지 위변조 공격에는 매우 취약하다는 점을 다시한번 강조하며 이번 강좌를 마무리하도록 하겠습니다.

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