빠르고 안전한 통신 프로토콜을 만들어 보자 - XOR 가지고는 문제가 해결되지 않는다.

출처 : http://www.gamedevforever.com/165

 

 

 

Posted by 죠쉬

지난 두번에 걸쳐 다루었던 PGP 방식의 프로토콜은 거의 모든 상황에서 사용이 가능한 완전체에 한없이 수렴하는 프로토콜 이다. 그렇기 때문에 대부분의 환경에서 안전하게 데이터를 주고받는 용도로 사용할 수 있는 좋은 방식이기도 하다. 왜 좋은지에 대해서는 아래의 링크에서 확인해 보시라.

 

http://www.gamedevforever.com/141

http://www.gamedevforever.com/156

위의 포스팅에서 i5 2.5GHz 급의 CPU라면 하나의 코어로 대략 초당 282,489,299 바이트, 17,655,581번의 128비트 AES 암호화 연산이 가능하다는 것에 대해 이야기 했었다. 계산해 보면 개발중인 게임에서 PGP, GPG 혹은 SSL을 사용할 수 있을지 여부에 대해 확인 해 볼 수 있을 것이다. 틀림없이 어떤 환경에서는 그정도의 연산 조차 아끼고 싶은 경우가 있을 수 있다. 특히 휴대용 게임기나 스마트 폰 등의 제한적인 환경이라면 더더욱 암/복호화 연산이 부담스러울 가능성이 있다.

이번 글을 통해 전달하고자 하는 내용은 두 가지 이다. 첫번째는 XOR이 암호화 하는데 사용되는 특징이 있기는 하지만, 그 자체는 암호화하는 효과가 전혀 없으므로 XOR 만 가지고는 해결되지 않는다는 것을 보이는 것 이고, 두번째는 암호화를 할 때 사용하는 몇가지 기법을 이야기 하고자 한다.

1. XOR를 이용한 데이터 숨기기

XOR은 CPU에서 제공하는 연산이므로 128비트를 암 복호화 하는데 만여 사이클이 소요되는 AES 암/복호화와 달리 많아야 100 사이클 정도면 128비트를 암호화 할 수 있다. 물론, 구현하는 방법에 따라, CPU의 종류에 따라 달라질 수 는 있겠지만, 근본적인 차이는 발생할 수 없다. XOR를 이용하여 암호화 한다면, 대충 다음과 같은 방법으로 암호화가 진행 될 수 있을 것 이다.

오! 그럴듯 해 보인다. 뭔가 알 수 없는 형태로 데이터가 변환되어서 전송되었다. 훔쳐보고 싶어 하거나, 조작하고 싶어하는 공격자는 원래 데이터가 뭔지 상상할 수 도 없을 것이다. 그러니 이걸로 대 만족이다! 그럼 이걸로 글을 마치겠다... 일리가 없잖습니까?

 

위에 언급한 XOR 방식의 가장 치명적인 단점은 쉽게 키의 크기를 알아낼 수 있고, 키 자체도 알아내기 어렵지 않다는 것 이다. 물론 어떤 방식으로 XOR를 했는지 알아내기 위해서 시간을 투자해야 하겠지만 결국 알아내는 건 많이 어렵지 않다. 그럼 위의 방식을 한번 공격해 보겠다. 먼저 공격을 위해서 한가지 전제를 해야 한다. 위의 방식을 이용해서 모든 데이터를 암호화 한다 - 채팅 내용까지 위의 방식을 사용한다는 전제를 해두겠다. 물론, 채팅을 암호화 하지 않는다고 해서 공격하는게 불가능 하지는 않지만, 가장 간단한 방법으로 공격하기 위해서 채팅의 내용까지 암호화 한다고 전제 하는 것 이다.

 

공격 방법은 아주 단순하다. 채팅창에 "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA^[각주:1]"를 입력하는 것 이다. 그리고 전송되는 패킷을 관찰하면 다음과 같은 내용을 포함한 패킷이 날아가는걸 볼 수 있을 것 이다.

 

 

6E2AE83 6E2AE83 6E2AE83 6E2AE83 .... 6E2AE83 6E2AE83 6E2AE83 6E2AE83

 

보기 좋으라고 네 바이트 단위로 잘라 놓기는 했지만, 어찌 되었든 XOR를 이용해서 숨겼다는 사실만 알면, 반복되는 주기만 관찰을 하면 쉽게 키의 크기를 알 수 있다. 위의 경우에는 숨길 때 사용한 키의 크기가 네 바이트 라는 것을 알 수 있다. 그리고, 운영체제에서 기본적으로 제공하는 계산기를 실행시킨 후 다음을 계산해 보면 된다.

 

6E2AE83 XOR 41414141 (AAAA의 아스키 코드 값)

 

그러면, 짜잔! 계산기에 다음과 같은 값이 나올 것 이다.

 

47A3EFC2

 

뭐... 뭐냐?

 

프로그램 코드를 분석해 볼 필요도 없다. 그냥 시도해 보면 된다. 해봐서 아니면 그냥 다른 방법을 사용했을 가능 성이 높으니 사용된 다른 방법이 무엇이 있을지 고민하면 된다. 위의 암호문을 포함한 패킷이 날아가고, XOR을 이용한 게 아니라면 답은 하나 뿐이다. 128 비트 블럭 암호를 ECB 모드로 암호화 한 것 이다. 원하는 평문에 대한 암호문을 알아낼 수 있으니 이전에 이야기 했던 차분 공격법을 이용하면 오래 걸리지 않아 키를 알아 낼 수 있을 것이다. 또 다른 문제는, 궂이 키를 알아내지 않더라도 전달되는 데이터의 일부를 변경할 수 있다는 문제점도 있다. 단순히 특정 비트-바이트의 값을 수정하는 것 만으로도 원하는 데이터를 변형 할 수 있다. 그렇기 때문에 XOR로 데이터를 숨기는건 그다지 효용성이 높지 못하다.

2. 기존의 암호화 방식을 끌어다 써보자 - CBC의 Chaining 을 가져다 써보자

 

그러면 어떻게 해결을 해야 할 것 인가? 위에서 잠시 말했듯 이 암호화된 문자열이 6E2AE83 6E2AE83 6E2AE83 ... 와 같이 주기를 가지고 반복된다면 해당길이의 키를 사용한 XOR 이거나 ECB 모드를 사용한 블록암호중 하나로 볼 수 있는 것 이다. 이전 게시물 에서 ECB 모드의 문제점에 대해 이야기 하면서 다른 모드를 사용하면 문제가 해결 된다는 것에 대해 언급한 것을 혹시 기억할지 모르겠다. 다시 말해서 위의 경우에도 CBC, PCBC, CFB, OFB 등등의 방식을 흉내내서 문제를 해결 할 가능성이 있다는 걸 생각해 볼 수 있을 것 이다. 

1에서 언급된 문제를 해결하기 위해, 다음과 같이 CBC를 변형해서 XOR를 이용해서 전송방식 - 프로토콜을 변형해 보도록 하겠다.

XOR를 이용하여 원래 데이터를 숨길때 Chaining을 해보았습니다!

오! 이전 보다 조금 더 그럴듯 해 보인다. 이전 암호화 단위의 암호문을 그 다음 단위의 평문을 암호화하는 키로 사용했다. 복호화 할 때에는 첫 번째 값을 그 다음 번 값을 복호화하는 키로 사용해 주면 된다. 게다가 이 방법을 사용하면 공격자가 임의의 위치에 있는 데이터를 바꾸게 되면 그 이후의 데이터들도 영향을 받게 되기 때문에 전달되는 데이터는 복호화 하기 전엔 변경할 수 없다. 이렇게 하면 같은 키를 사용하더라도 처음부터 끝까지 완전히 같은 데이터가 아닌 다음에는 만들어진 암호문이 다르게 보일 것 이다. 이렇게 해주면 공격자는 키를 예측하기 위해 더 많은 고민을 할 수 밖에 없다. 똑같이 단순하게 XOR를 사용한 것 이지만 앞서 사용했던 방법 보다는 조금더 공격자를 고민하게 만들 수 있다. 그러나, 같은 평문은 같은 암호문을 만들기 때문에, 공격자는 어떤 규칙이 있다는 것을 쉽게 발견해 낼 수 있고, 공격 방법을 찾아내기 위해 그 규칙을 이용 하려고 시도 할 것 이다. 그러면, 어떻게 문제를 해결 할 수 있을까?

3. 그럼, 암호화 할 때 마다 다른 결과를 얻도록 해보자

문제를 해결하기 위해서 암호화 하는 것의 가장 기본적인 정의를 끌어들여 보겠다. 가장 안전한 암호화 방식은 공격자가 암호문과 랜덤 값 간에 구별을 하지 못하는 방식이다. 즉, 평문을 암호화 해서 만든 데이터 100 바이트와, 랜덤 함수를 이용해서 만든 데이터 100 바이트를 구별하지 못하면 - 암호화 해서 만들어진 암호문이 랜덤 값 100 바이트로 보인다면 공격자는 공격할 방법을 찾지 못하게 된다. 이 내용을 단순하게 문자 그대로 받아들여 보자. 다시 말해서 평문의 첫 네 바이트를 랜덤값으로 채워 넣는 것이다. 이 방식은 블록암호의 모드에서 사용되는 IV와 유사한 역할을 하는 것이다. 오히려 블록 암호의 모드에서는 IV 값을 알아야 하지만, 이 경우에는 최초의 랜덤 값을 몰라도 복호화가 되기 때문에 IV를 전달하지 않아도 된다. 이 아이디어를 적용한 방식을 그림으로 그리면 다음과 같이 될 것 이다. 

랜덤 값을 초기 값으로 하여 Chaining을 해보았습니다. 매우 그럴듯해 보입니다.

굉장히 그럴 듯 해 보이는 결과물을 얻었다. 랜덤 값을 특정 값과 XOR을 하면, XOR의 특성상 그 결과 값은 랜덤 값 일 수 밖에 없다. 그러므로, 랜덤 값과 키를 XOR를 하면 랜덤 값이 되고, 암호화 하고자 하는 평문 값과 앞서 얻은 키가 포함된 랜덤 값을 XOR를 해주면 랜덤 값이된다. 출력 결과물인 암호문은 말 그대로 랜덤 값 열이기 때문에 공격자는 전송되는 데이터가 암호문인지 아니면 그냥 랜덤값을 보내는 것 인지 구별이 불가능하다. 암호학에서 말하는 가장 이상적인 암호문 인 것이다! ... 이게 사실 이라면, 그동안 암호학을 연구하던 수학자와 암호 연구자들은 전 부 다 Bing신이 되는 거다. 그러나, 필자같은 반푼이도 아는 것을 두번째로 똑똑하다고 하면 암살이라도 할 똑똑한 분들께서 발견하지 못하고 복잡한 수학적 계산을 필요로 하는 블록암호를 만들었을리는 없는 것 이다.

위의 그럴듯해 보이는 방법의 문제점은, 키가 없어도 암호문을 복호화 할 수 있다는 것 이다. 일단 다음 그림을 보자.

슬프게도, 키나 첫 번재 랜덤값은 몰라도 암호는 깨진다.

위 그림을 보면 알겠지만, 전송되는 암호열의 첫번째 암호문을 그 다음 암호블록과 XOR 해주면 평문을 얻을 수 있다. 그러므로 애시당초 키는 필요도 없었다. 공격자가 암호화 방식을 모른다면 혹시 속아넘어가 줄 수... 조차 없다. XOR의 특성상 Chaining 방식은 사용이 불가능 하기 때문이다. 2에서 언급된 방법을 이용해서 암호화를 하는 경우 그 앞에서 사용했던 "A" 잔뜩 입력하기 기법을 사용하면 다음과 같은 결과물을 얻게 된다.

6E2AE83 47A3EFC2 6E2AE83 47A3EFC2 6E2AE83 47A3EFC2 6E2AE83 47A3EFC2

그리고, 여기에서 언급된 방법 이라면 다음과 같은 결과를 얻게 될 것 이다.

RANDOM RANDOM 47A3EFC2 RANDOM 47A3EFC2 RANDOM 47A3EFC2 RANDOM 47A3EFC2

 

...

(다시 한 번 수고해 주신 L 군에게 감사한다.)

패턴이 반복 될 뿐 아니라, 전송되는 데이터열에 비밀 키 까지 예쁘게 포함되어 있다. 이... 이건 아니잖아...

4. 결론

기본적으로 XOR 연산은 두 값을 섞어서 제 삼의 값을 만들어 내기 때문에 암호화에 사용할 수 있을 것 처럼 보인다. 그러나 XOR 연산은 '복원'의 특성을 가지고 있기 때문에 XOR 만을 이용하여 암호를 만든다면 알려져 있는 그 어떤 방식을 사용한다 할 지라도 약간의 노동 만으로도 원문을 얻어낼 수 있다. 게다가 XOR 은 사칙연산과 마찬가지로 아주 단순하기 때문에 그 자체만 가지고는 응용할 수 있는 영역에 한계가 있다. 그러므로 아무리 연산시간이 부족하다 할 지라도 XOR 만 가지고 전송하는 데이터를 암호화 하려는 시도는 원하는 목적을 달성 할 수 없을 것 이다.

겨우 그딴 소리를 하려고 이 글을 읽게 만들었단 말이냐! 죽고 시프냐!

자... 잠시만, 돌은 내려 놓으시고! !!! !!!! !!!! 아악!

그러나 XOR은 제일 처음에 말씀 드렸던 것과 같이 암호하는데 사용됩니다... 되... 되옵니다. 그렇기 때문에 XOR를 사용하는데 있어 한계를 알고 계시옵는 것은 이 후에 다른 방법을 사용하시어 전송하는 데이터를 암호화 하시옵는데 도움이 되실 것 이옵니다. 다음 번에는 XOR과 의사난수 발생장치(PRNG)와 해시 함수(HASH FUNCTIONS)를 이용하여 빠르고 깨지기 힘든 암호문을 만들어 전달하는 방법에 대하여 설명해 올리도록 하겠사옵나이다. 그리고, 그 다음에는 실제 사용할 수 있을 법 한 프로토콜을 만들어 올리겠나이다... 그... 그러니... 쇠구슬은...

아악!!!!!

*     *     *

'발행' 버튼을 누르면 예약일과 상관없이 바로 포스트가 열린다는 걸 몰랐습니다. 그래서 어제 밤에 쓰다만, 아니 타이핑 하다 만 글이 올라가 버리고 말았네요. 오늘 내일 여유있게 쓰려고 했는데... 일단 트윗에 포스트가 날아갔기에 부랴부랴 타이핑 작업을 마쳤습니다. 혹시 미리 보시고 '이쉐키 뭐얏'이라고 생각하신 분이 계시다면 용서하시길 부탁드립니다. (__)

우좌지 당간에, 그런 이유로  원래 스케쥴 보다 이틀 일찍 포스트 했습니다.

1. A의 갯수를 세지는 말아 주세요. 그냥 충분히 많은 갯수의 A인 겁니다. 한 백개정도? [본문으로]