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


이번 강좌는 Stream Ciphers 3: real-world examples 에 포함된 "Real-World Stream Ciphers" 입니다.


이번 강좌에서는, 실무에서 널리 사용되고 있는 스트림 암호에 관련한 몇가지 예시를 보여드릴 것입니다.

아마 여러분도 들어보셨을듯한 아주 유명한 암호 알고리즘 두가지가 있습니다. 이들은 시스템에 더이상 도입하지 말아야할정도로 오래되었음에도 불구하고, 여전히 아주 널리 이용되고 있습니다. 오늘 이들을 살펴보도록 하겠습니다. 


먼저, 첫번째로 소개드리는 스트림암호는 1987년 설계된 RC4입니다. 구현원리를 대략적으로 설명드리고, RC4의 취약점에 대해 살펴보겠습니다. RC4는 가변크기의 seed를 사용합니다.(여기의 예제에서는 128bit로 가정해보겠습니다.) 해당 seed를 사용하여 2,048 bit 결과물을 생성합니다. 이를 확장(Expansion)이라고 하며, 생성기의 내부에서는 루프(loop)동작을 반복하여 결괏값을 하나하나 출력합니다.

앞서 말씀드렸듯이, RC4는 과거부터 굉장히 자주 사용되었습니다. 특히 HTTPS 통신에서 실제적으로 이용되곤 합니다. 그러나 RC4에서는 몇 년 동안 다양한 취약점이 발견되었으며, 따라서 향후의 프로젝트에서는 RC4를 사용해서는 안됩니다. 실제로 RC4의 문제로 인해 WEP 등의 프로토콜마저도 사용이 권장되지 않는 현시국입니다. 따라서 RC4를 사용하지 마시고, 보다 안전한 의사난수 생성기를 고려하시는 것이 좋다는 것을 추후 알려드리도록 하겠습니다. 

우선 여기에서 제시하는 RC4의 약점은 두가지입니다.


첫째, RC4 출력 결과물의 두번째 byte를 보면 굉장히 기이한 현상이 관측됩니다. 두번째 값이 항상 편향된(biased) 상태로 나타나는 것인데, 만약 RC4가 좋은 암호화 알고리즘이라면, 확률분포가 고르게 나타나야 하겠죠? 그렇다면 두번째 byte가 0이 될 확률은 전체 경우의 수(256)에 대하여 1/256이 될 것입니다. 그러나, 실제로 실험해보면 RC4의 경우에는 이 확률이 2/256입니다. 별로 큰 차이가 안 느껴지신다구요? 그렇지 않습니다. 이는 RC4를 사용하여 메시지를 암호화하면, 두번째 바이트는 제대로 암호화가 되지 않을 가능성이 있다는 의미입니다. 또한, 이를 토대로 앞 뒤의(1번째와 3번째) 바이트들을 분석하면 그 또한 biased되었는지 아닌지를 추정할 수 있습니다. 이러한 이유로 RC4는 안전하지 않습니다. 때로는, 이러한 취약점을 감안하여 앞부분의 256 바이트를 무시하고 257번째 바이트부터 사용하도록 하는 꼼수(?)도 존재하기는 합니다. 어쨌든, biased 된 결괏값은 암호학적으로 안전하지 않으므로 사용하지 않는 것이 좋습니다.

두번째 취약점은, RC4의 아웃풋의 길이가 길면 길수록 ’00’의 시퀀스가 더욱 자주 나타난다는 것입니다. 다시 말해서, 2byte(16bit)의 000000..0 을 얻기 쉽다는 것입니다. 만약 RC4가 완벽히 랜덤하게 작동한다면, 이러한 ’00’이 나타날 확률은 (1/256) ^2 일 것입니다. 그러나 RC4는 (1/256)^3 만큼 편향되어 있다는 것이 밝혀졌습니다. 실제로 몇 기가바이트 정도의 데이터를 처리하여 실험해보면 해당 시퀀스가 출현하는 것을 확인할 수 있으며, 이는 0과 0이 자주 나타난다는 사실을 구분자(Distinguisher)로 사용하여 제너레이터의 출력을 분석하는 등의 방법을 사용한다면 난수생성기 자체가 예측가능해진다는 것을 의미합니다.

위에서 언급한 2가지는 RC4자체의 취약점이며, 마지막으로 한가지 더 말씀드릴 사안은 의사난수생성기에서 발생하는 존재적 약점입니다. 지난 강의에서 이미 WEP가 취약하다는 것을 소개해드린 바 있습니다. 기본적으로 비밀 키(KEY)를 관리할 때 어떠한 관련성(related)이 발견된다면 그 자체만으로 상당한 위협이 될 수 있습니다. RC4역시 동일한 문제점을 가지고 있으며, 따라서 현대의 시스템을 설계할 때에는 RC4 대신 더욱 안전한 의사난수 생성기를 사용하도록 권고합니다.


두번째로 설명드릴 예제는 일명 CSS라고 불리는 스트림암호입니다. 여러분이 상점에서 DVD 영화를 구입하시면 원본 동영상을 암호화할 때 CSS(Content Scrambling System)이 사용되며, 이는 이미 심각하게 안전성이 훼손되었음이 밝혀졌습니다. 이번 슬라이드에서 그 부분을 집중 조명하여 공격 알고리즘이 어떻게 작동하는지 보여드리고자 합니다.

CSS를 공격하는 다양한 공격 방식이 있지만, 기본적으로 사용되는 공통적인 부분은 바로 CSS자체의 설계적 취약점을 타겟으로 하는 것입니다. 보통 CSS는 선형 되먹임 시프트 레지스터(Linear-feedback Shift register)라고 불리우는 메커니즘을 사용하여 전용 하드웨어의 형태로 구현합니다. 이 LFSR은 의사난수를 생성하는 역할을 합니다. seed가 주어지면, 그것을 이용해서 레지스터를 펼쳐놓고, 특정 위치의 값(tap이라고 부름)을 클럭 사이클마다 XOR 연산하여 왼쪽방향으로 내보내는 동작을 수행합니다. 마지막 비트까지 이동하였으면 다시 첫 비트와 XOR을 합니다. 이것의 구현은 매우 간단하며, 만약 하드웨어로 구현한다면 매우 용이합니다. 이 LFSR은 의사난수를 생성하는 역할을 합니다. seed가 주어지면, 그것을 이용해서 레지스터를 펼쳐놓고, 특정 위치의 값(tap이라고 부름)을 클럭 사이클마다 XOR 연산하여 왼쪽방향으로 내보내는 동작을 수행합니다. 마지막 비트까지 이동하였으면 다시 첫 비트와 XOR을 합니다. 이것의 구현은 매우 간단하며, 만약 하드웨어로 구현한다면 매우 용이합니다.  이처럼 LFSR을 이용한 스트림암호가 상당히 많은데, DVD암호화인 CSS의 경우에서는 LFSR 두개를 사용하는 것이 널리 알려져 있습니다. 또한, GSM(개인 휴대통신 시스템)에서 사용되는 A5/1 이나 A5/2 알고리즘은 3개의 LFSR을, 블루투스 암호화에 사용되는 E0 알고리즘은 4개의 LFSR을 사용합니다. 이들 모두 스트림 암호이며, 현재는 심각하게 취약성이 드러났으므로 신뢰해서는 안되지만 이들이 하드웨어로 구현되어 있어서 그 동작을 쉽사리 수정할 수 없다는 어려움에 직면해 있습니다.


어쨌든 여기에서는 이들 중 가장 단순한 CSS를 구체적으로 어떻게 공격할 수 있을지 살펴보겠습니다.

CSS가 실제로 어떻게 작동하는지 설명해 보겠습니다. 따라서 CSS의 seed는 5 byte(40bit), 즉 5 * 8 bit = 40 bit입니다. 40 비트로 제한해야했던 이유는 미국 수출 규정이 키가 40bit인 암호화 알고리즘만 수출할 수 있는 시점에 DVD 암호화가 설계 되었기 때문입니다. 따라서 CSS는 이미 매우 제한적인 짧은 키로 구현되었습니다. CSS는 두개의 LFSR을 사용한다고 하였는데, 처리될 때 하나는 17bit이고 하나는 25bit로 나뉘어 집니다. 그리고 시드를 생성할 때, 기존의 5byte 시드를 2byte 와 3byte로 나누어서 1을 덧붙인 1 + (8 *2), 1 + (8*3) 으로 처리합니다. 때문에 17bit와 25bit가 되는 것입니다. 이러한 방식으로 seed를 사용하고, 결과적으로 LFSR이 8사이클 실행되면서 8bit의 출력을 생성합니다. 이 값을 가산하여 256으로 modular하는 과정을 거칩니다.(Carry 발생에 대한 구체적인 처리과정은 논외로 하겠습니다.)

어쨌든 이렇게 계산된 값을 한번에 하나씩 영화의 원본 데이터에 배타적 논리합(XOR)연산을 수행합니다. 이는 아주 기본적이면서도 간단한 스트림 암호입니다. 구현이 매우 간단하기 때문에 저렴한 하드웨어 비용으로 빠르게 영화 콘텐츠를 암호화할 수 있습니다. 그러나 밝혀진바에 따르면, 이는 대략 2^17 의 시간복잡도로 무력화시킬 수 있습니다.

이제 어떻게 공격하는지 살펴봅시다. 만약 여러분이 재생중인 영화의 데이터를 가로챘다고 가정해봅시다. 영화는 암호화되어있기 때문에 이를 적절히 해독해야만 원하는 내용을 얻을 수 있습니다. 암호화된 DVD 파일이 MPEG 포맷이라면, 해당하는 매직 넘버(또는 파일 시그니처)의 원본이 무엇인지 알 수 있습니다. 이것이 대략 20byte정도 된다고 가정해 봅시다. 그렇다면 그 원본 값을 암호문에 XOR하면, 일종의 기지 평문공격을 수행하여 PRG의 첫 20bytes를 얻을 수 있습니다. 이를 통해 다시 CSS의 복호화된 원문 20 바이트를 추론할 수 있습니다. 자, 그럼 이번에는 다시 조금 더 거꾸로 올라가봅니다. 우선 두개의 LFSR중 첫번째를 보면 17bit니까 17가지의 경우의 수가 존재합니다. 때문에 2^17의 시간복잡도입니다. 그리고 위에서 얻었던 20bytes의 값을 대입하여 역산한 값과 일치하는 조건을 찾아내면 됩니다. 이미 CSS 암호문 전체를 가지고 있다고 가정하므로, 나머지 부분에 대해서도 동일하게 적용이 가능합니다. 또한, CSS 시스템의 설계원리상 20bytes가 25bit LFSR과도 상관관계가 있음을 알고 있기 때문에, 먼저 17bits LFSR값을 얻어낼 수 있다면 이후 나머지 25bits에 대해서도 쉽게 계산이 가능합니다. 이를 이용하여 영화의 나머지 부분 모두를 해독할 수 있습니다. (즉, 암호문을 평문으로 복구할 수 있습니다.)

이는 지금까지 일관되게 설명드렸던 사항입니다. 스트림 암호는 일정부분만 조금 드러나도 곧 전체가 무너지는 것과 같습니다. 사소한 힌트라도 주어져서는 안됩니다. 이러한 기본 원리를 응용하여 CSS 암호화 데이터를 해독하려는 다양한 오픈소스 소프트웨어가 널리 퍼져있다는 사실을 꼭 기억하십시오.


지금까지 취약한 암호 알고리즘에 대해 예시를 들었었는데요, 그렇다면 이번에는 현시점에 가장 개선된 의사난수 생성기를 소개해 드리려고 합니다. 이것은 2008년에 개최된 eStream Project에서 기인한 것인데요, 최종적으로 5개의 Stream 암호가 공표되었지만 여기에서는 그 중 하나를 대해서 소개하고자 합니다.


먼저 이런 알고리즘은 그동안 학습해왔던 것들과는 사뭇 다른 구조를 가지고 있습니다. 특히, Seed와 Nonce라는 두가지 요소가 입력값으로 요구되고, 이를 통해 의사난수 결괏값이 생성됩니다. Nonce는 유일한 값이며 반복되지 않습니다. 암호화 시에는 이 nonce값이 사용되며, 의사난수 생성을 위해 k와 r이 적용되어 임의의 긴 메시지가 표출되면, 그것을 원본메시지와 XOR하게 됩니다. 이때 k와 r은 결코 재사용되지 않으며 이를 통해 키 쌍을 고유하게 만들 수 있기 때문에 매우 참신한 아이디어라고 볼 수 있습니다.

eStream 중 여러분께 소개시켜드릴 Salsa20은, 소프트웨어나 하드웨어적 구현 모두를 고려하여 설계되었습니다. 사실 그동안은 소프트웨어적 구현에 최적화하거나(RC4) 또는 하드웨어 구현만을 목적으로하는 (LFSR을 사용한 CSS) 것들이 대부분이었습니다. 그러니 하드웨어와 소프트웨어 구현 모두에서 저렴하고 빠른 성능을 얻을 수 있다는 것은 굉장한 메리트로 작용합니다. 


Salsa20은 128 또는 256bit key로 작동하지만, 여기에서는 128bit 기준으로 설명드리도록 하겠습니다. 앞에서 설명드렸듯이, {0,1}^128이 Seed이고 {0,1}^64가 Nonce로 사용됩니다. 이 때 {0,1}^n 인 출력값을 얻을 수 있으며 n의 최댓값은 2^73 (거의 무한대로 봄)입니다.

그렇게 얻은 값을 아래 그림과 같이 H함수(investable function)를 사용하여 10번의 Round를 거칩니다. 이후 최종결괏값을 글자대 글자로 연산함으로써 원본 메시지를 암호화 할 수 있습니다. 의사난수 생성을 위한 H 함수의 역할이 가장 핵심적이며, 내부에는 Counter를 사용하여 매번 다른 결괏값을 도출하도록 설계되어 있습니다. 현재까지 이러한 방식에 대한 효과적인 공격방법은 알려져있지 않으며, 2^128 수준의 보안강도로 여겨집니다.


마지막으로 성능 평가 지표를 살펴보겠습니다. 대략 아래와 같이 5개의 스트림 암호가 있다고 했을 때, 그 성능(단위시간당 처리 데이터)는 아래와 같습니다. Salsa20을 선택한 이유는 가장 뛰어나다고 보이기 때문입니다. 동일한 X86머신에서 2.2 GHz의 AMD CPU 으로 테스트 했을 때, RC4가 가장 느립니다. RC4는 소프트웨어적 구현에 초점이 맞추어져 있기 때문에 하드웨어가 더 좋아져도 동일하게 바이트 단위 조작을 함으로써 사이클을 낭비하기 때문입니다. 그러나 eStream 후보군이었던 Salsa나 Sosemanuk은 월등한 성능을 보이고 있습니다. 결국 최종적으로 eStream Finalist에 당선되었던 이들의 속도는 영화 재생속도와 비교해도 꽤 인상적인 속도입니다. 

지금까지 스트림 암호에 대한 공격을 포함하여, 더이상 사용해서는 안되는 두개의 구식 스트림 암호(CSS, RC4)를 살펴보았습니다. 또한, 현대의 스트림 암호가 작동하는 원리(Key, Nonce)를 살펴보았습니다. 그리고 이러한 최신 스트림 암호의 성능 수치를 비교분석하였으며, 어떤 것이 우등한지 알 수 있었습니다. 만약 여러분이 스트림 암호 사용이 필요한 경우라면, eStream Finalist 중 하나(ex: Salse20)를 사용하시길 권장드립니다. 


이상으로 본 강의를 마무리합니다.

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