스트림 암호 one-time-pad 공격

스트림 암호의 일종인 One Time Pad는 강력한 복잡성을 가지고 있는 암호이지만, 구조적 한계로 인해 공격 방법이 존재한다.

One time Pad는 원문 메시지와 비밀키(secret key)를 배타적 논리합(Exclusive-OR) 연산을 수행하여 암호화합니다. 이때 Secret key의 길이는 메시지의 길이와 동일해야만 한다.

즉 E(k,m) = m ^ secret_key = c(ciphertext)

복호화 과정 역시 암호문에 암호화에 사용한 비밀키를 다시 한번 XOR함으로써 진행됩니다.

D(k,c) = c ^ secret_key = m(plaintext)

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란 무엇일까? 이름 그대로 일회용 암호키의 모음이라 생각하면 된다. 만약 이를 두번 이상(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)으로 사용해야한다.

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

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를 사용하지 않아야 한다.

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

요약하자면, 핵심은 스트림 암호에서 Key를 두번이상 재사용해서는 절대로 절대로 안된다는 것 이다. 

스트림 암호는 기밀성(confidentiality)을 보장할 수 있지만 키를 잘 관리하지 못한다면 기밀성에 타격을 받을 수 있다두번째로는 스트림 암호는 무결성(integrity)를 보장해주지 못한다는 점이다. 사실 스트림으로 암호화된 결과값은 누구나 쉽게 위변조가 가능하다. 이러한 속성을 malleability라고 부른다.

예를 들어, m이라는 메시지를 k로 암호화하여 전달했다면 그 결과값은 m xor k가 된다.그런데 악의적인 공격자가 p 라는 값을 끼워넣는다면 어떻게 될까?이때의 결과값은 (m xor k) xor p 로 변조되었을 것입니다.아무것도 모르는 수신자가 이것을 받고, 약속했던 k 값으로 복호화를 시도한다면, 그가 얻게 되는 값은 무엇 일까?

k값이 소거되었으므로 m xor p 값이 주어진다. 즉 공격자는 본래의 메시지르 훼손할 수 있다. 암호키에 대한 걸 모르고도 말이다. 공격자가 는 추가적인 p를 사용해 정보를 사용할 수 없도록 할 수 있다. 또한 이러한 변조가 일어났다는 사실을 검증할 수 있는 방법이 없다.