От Ильича до Ильича
by sonnet 2006 이글루스 TOP 100 2007 이글루스 TOP 100 2008 이글루스 TOP 100 2009 이글루스 TOP 100 2010 이글루스 TOP 100 2011 이글루스 TOP 100
rss

skin by 이글루스
MaskCrypt에 대한 생각
블록암호화 알고리즘 ECB 모드와 암호대회 (헐랭이)

위 글을 읽고 나니, 제 글도 ECB(Electronic CodeBook)을 함축한 것처럼 읽힐 수도 있다는 생각도 들고 해서 제 생각을 좀 덧붙여 보겠습니다. 가능한 쉽게 쓰려고 했지만 이해하려면 약간의 프로그래밍 경험은 필요할 것 같습니다.



가장 많이 쓰이는 암호인 블럭 암호는 64비트(8바이트) 혹은 128비트(16바이트) 단위(블럭)으로 암호화를 하고 그 결과 암호문이 블럭 단위로 나옵니다. 64비트 블럭을 사용하면 1~8바이트를 암호화하면 8바이트, 9~16바이트를 암호화하면 16바이트가 나오는 식입니다. 사실 (요즘) 컴퓨터에선 모든 데이터를 바이트 단위로 저장하니까 블럭이 8비트이면 아주 편리할 것 같지만 실제로는 블럭이 그것보다 큽니다. 그 이유는 여러가지가 있지만 안전성과 효율성 양 면에서 장점이 있어서라고만 말해도 충분할 것 같습니다.

이번에 문제가 된 암호 알고리즘인 MaskCrypt는 두 가지 유용한 특성을 갖고 있습니다.

1. 동일한 문자 길이 유지 (11바이트 평문을 암호화하면 11바이트 암호문이 나옴)
2. 암호문이 printable character로 구성됨.

이제 설계기준(design criteria)을 한 번 검토해 보지요.

개발자 입장에서 1번 특성은 분명히 유용합니다. 기존 시스템에 암호화 기능을 더하고자 할 때 확실히 손이 덜 가게 되지요. 문제는 2번 특성인데, 이 특성은 많은 사람들이 꼭 필요하다고 느낄 만한 것은 아니라고 봅니다. 암호문을 e-mail에 첨부한다든가 하는 용도를 제외하면 사용자는 암호문을 볼 일이 없습니다.[1] 이 제품이 상정하는 응용분야(주로 DB)라면 디버깅이나 테스트할 때 좀 편리할 수도 있지만, 사실 핵심적인 기능이라고 하긴 어렵죠.

개발자가 1번 특성만 있어도 된다고 판단하면, 이런 새로운(=신뢰성을 보장하기 힘든) 알고리즘을 쓸 이유가 없습니다. 모든 스트림암호들은 이런 특성을 보장합니다. 기존의 잘 알려진 스트림 암호 중 아무 거나 마음에 드는 걸 골라 쓰면 되지요. 그런데 사실 스트림암호는 블럭암호만큼 많이 쓰이지는 않기 때문에, 그만큼 설계기술이나 안전성 분석이 충분히 되었다고 보기는 힘듭니다. 보수적인 개발자라면 미덥게 느껴지는 게 없을 수도 있는 게 사실입니다.

이럴 때 정상적인 개발자라면 동작모드(mode of operation)[2]를 제일 먼저 떠올릴 것입니다. 블럭암호의 동작모드 중에는 CFB(Cipher Feedback)나 OFB(Output Feedback)라는 것이 있는데 이를 사용할 경우 블럭암호를 스트림암호처럼 바꾸어 사용할 수 있습니다. 그럼 잘 검증된 블럭암호의 안전성을 갖고 스트림암호와 같은 효과를 기대할 수 있습니다.

이 이야기가 앞의 글에서 언급했던 것입니다. 사실 엔지니어들에게 내려오는 유명한 경구 중에 '바퀴의 재발명'이란 말이 있습니다. 이미 잘 확립된 기술이 있는데, 고생해서 똑같은 것을 다시 만들어내는 어리석음을 비꼬는 말입니다. 2번 특성이 그렇게 중요하지 않다면 우리는 새로 할 일이 하나도 없는 셈입니다.



저는 여전히 회의적이지만, 이제 2번 특성이 의미가 있다고 전제하고 좀 더 이야길 해 보겠습니다. 제품을 만드는 회사 입장에선 다른 조건이 같다면 한 가지 개선점이 있는 정도로도 의미 있는 신제품이 될 수 있겠지요.

만약 1번뿐 아니라 2번 특성[3]도 가져야만 하는 암호를 만들라는 과제를 받는다면 어떻게 접근해야 할까요? 뭐 꼭 한가지 방법만 있는 건 아니겠지만 저라면 이런 식으로 하겠습니다.

1) 지원해야 할 문자집합을 n비트 길이 출력을 갖는 연속된 테이블을 참조해 변환한다.
2) 적절한 스트림암호로 암호화한다
3) 암호문을 n비트 길이의 블럭으로 잘라서, 각 블럭마다 대응하는 printable character로 변환한다.

예) "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"로 구성된 base64 charset이란 것이 있다고 하자. 이는 000000~111111까지 6비트(2^6=64)에 대응된다. 이 문자집합 4글자(4바이트)를 테이블변환하면 24비트(3바이트)가 된다. 이를 암호화해 같은 길이의 암호문을 얻는다. 24비트를 6비트씩 4블록으로 쪼개고 각각을 printable character에 대응시킨다."

위 예처럼 2^n개로 딱 떨어지지 않는 일반적인 문자집합이나 SBCS/DBCS가 혼용될 경우, 조금 더 tricky한 수법이 필요하지만 기본적으로 원하는 문자집합을 모두 표현할 수 있는 n비트에 대해 2^n개의 printable character를 구할 수 있는 한 위와 유사한 변환은 수행 가능합니다.

이런 식으로 접근하는 이유는 물론 블랙박스처럼 기성 암호의 얼개를 손대지 않고 쓰기 위함입니다. 이렇게 하면 2번 단계에서 사용한 암호와 같은 안전성이 보장되고, 만약 내가 사용하던 암호가 깨졌다는 소식이 들리면 수많은 다른 암호 알고리즘 중 적당한 것으로 교체만 하면 되니까 안전성에 대한 책임 문제에서 거의 해방될 수 있습니다. 사실 이런 방식은 HMAC에서 아주 성공적으로 사용되고 있습니다.

암호 알고리즘 전/후의 선형변환이 아무리 tricky하고 case by case로 구성된다 하더라도, 단언하건대 새 암호 알고리즘의 안전성을 검증하는 것보다는 훨씬 쉽습니다. 실제로 우리가 MaskCrypt 제품에서 본 결과는 '네모난 바퀴를 재발명(reinventing the square wheel)'한 거나 다름없습니다.

안전성을 줄여 속도를 빠르게 한다든가 하는 식의 trade-off를 생각할 수도 있지만, 사실 안전성을 정량적으로 측정하는 게 아주 어렵기 때문에 이런 접근은 지독하게 위험합니다. 예를 들어 피상적으로 속도를 2배로 만들겠다고 어떤 암호의 라운드 수를 반으로 줄이면 그게 50%만 약해지는 건 아니겠지요. 그건 한 백만 배쯤 약해질 수도 있습니다.[4] 사실 이정도 용도[5]로는 잘 알려진 대가들이 만들고 지금 널리 쓰이는 암호 중에서 충분한 속도를 내는 놈을 찾는 것은 어렵지 않다고 생각합니다.



이어서 다음은 제품소개서에서 이 제품의 특징으로 거론된 기능들인데, 제생각에 이 부분은 유용하다고 생각되질 않아서 앞서 언급한 특성에서는 제외했습니다.

a) 비밀키의 길이에 제한이 없다.
b) 원문의 처음 일부가 동일해도, 전혀 다른 암호문 출력
c) 문자열의 코드를 분석하여 일부 비트만 암호화

a) 비밀키의 길이에 제한이 없다.
결과적으로도 증명되었지만 이렇게 안전하지 않은 암호에 키 길이는 아무 의미가 없습니다. 키 길이는 너무 짧으면 위험하지만, 사실 일반적인 것보다 길다고 더 안전해지는 것은 아닙니다. 잘 검증되지 않은 암호에는 수많은 약점이 있을 수 있기 때문에 키 길이는 잘 모르는 사람의 착시만 유도하는 경향이 있지요. 사실 이 바닥의 경험법칙에 따르면 키 길이가 길다는 것을 '강하게' 세일즈포인트로 하는 암호는 잘 모르는 사람을 후리기 위한 수상쩍은 물건(snake oil)일 가능성이 아주 높습니다. 제 생각에는 독자적으로 암호를 평가할 능력이 없다면 키 길이는 다른 일반적인 대안들(의 평균)과 비교해 더 짧지만 않으면 문제가 안 된다고 생각하는 것이 간단한 기준이 될 수 있을 듯 합니다.

b) 원문의 처음 일부가 동일해도, 전혀 다른 암호문 출력
이게 무슨 의미가 있는지 잘 모르겠지만 원한다면 이 제품이 한 것처럼 원문 길이를 세어서 IV(initial vector)에 반영하면 될 듯 합니다. IV의 선택은 일반적으로 암호 강도에 영향을 주지 않습니다.

c) 문자열의 코드를 분석하여 일부 비트만 암호화
… 내부를 들여다보지 않아도, 이런 특징이 이 암호가 잘 깨지도록 만든 데 일조했을 것 같은 생각이 드는군요. 이건 잘 해봐야 중립적인 특성이지 장점이 될 순 없을 겁니다.



끝으로 왜 이런 일이 일어났는지에 대한 제 의견을 좀 적어 보겠습니다. 이런 결과는 전형적으로 일반적인 프로그래머가 새로운 암호를 만들 수 있다고 생각했을 때 발생된다고 봅니다. 그렇게 생각한 사람은 프로그래머 본인일 수도 있고 그의 상사일 수도 있겠죠. 어쨌든 99.99+%의 프로그래머는 완전히 개발된 암호를 이용하는 사람이지, 새 암호를 만드는데 필요한 특수한 지식과 경험을 쌓은 사람이 아닙니다. Applied Cryptography의 저자 Bruce Schneier는 이를 "자신이 기존의 알고리즘을 깰 수 있는 사람임을 입증했을 때, 당신은 새 알고리즘을 설계하기 시작할 수 있다."라고 간명히 요약한 바 있습니다. 이런 의미에서 지금 우리가 보는 현상은 정비사가 설계-제조한 새 비행기가 첫 비행에서 추락한 것과 흡사하다고 말씀드릴 수 있겠습니다.




[1] 보면 뭐하겠습니까. 암호화되어 읽는 의미가 없는데.
[2] mode of operation에 대해서는 어느 책이나 다 잘 다루고 있겠지만, 예를 들면 A. Menezes, P. van Oorschot, and S. Vanstone의 Handbook of Applied Cryptography, CRC Press, 1996의 7.2.2절 참조.
[3] 이는 평문이 printable character로 구성되어 있다는 암묵적인 가정을 담고 있습니다. 평문이 바이너리였다면 이런 조건을 내걸 리가 없겠죠.
[4] 오래 전에 일본 NTT의 FEAL이 이와 비슷한 접근법을 취했다가 비참한 최후를 맞은 바 있습니다.
[5] DB에 주로 사용된다는 가정처럼 32bit 이상 환경에서 돌아가는 경우 충분한 속도를 내는 블럭 암호를 구하긴 어렵지 않습니다. MaskCrypt팀이 상정한 것처럼 실제로 암호화되는 데이터의 양이 크지 않다면 실질적인 부담은 무시할 수 있을 수준일 것입니다.
by sonnet | 2009/03/20 22:33 | 과학기술 | 트랙백(1) | 덧글(21)
트랙백 주소 : http://sonnet.egloos.com/tb/4094186
☞ 내 이글루에 이 글과 관련된 글 쓰기 (트랙백 보내기) [도움말]
Tracked from 한글이 꿈틀 at 2009/03/23 02:08

제목 : 암호의 강력함과 편리함에 대한 단상
MaskCrypt에 대한 생각 안 그래도 이야기해야지, 해야지 하던 사건입니다. 저도 잠깐은 암호 분야에 발을 담그었습니다. 충분히 짧고 읽을 수 있는 특정 한글이나 알파벳 문자들로 맞추는 부분은 저도 고려를 했던 부분입니다. 특히 전 세계로 나아가는 해군의 국방 분야를 생각하면 음성이나 문자를 통한 키 전달 부분은 거의 필수 불가결한 요건이라고 할 수 있습니다. 예를 들자면, 이라크에 USB 드라이브를 2분 안에 물리적으로 전달하거나, ......more

Commented by 계란소년 at 2009/03/20 22:41
으흠, 암호는 보통 프로그래머가 아니라 수학자가 만드는 것일텐데...
Commented by sonnet at 2009/03/21 08:51
꼭 수학 전공일 필요는 없지만, 정수론을 비롯해 상당한 수학적 기초가 필요하긴 하지요.
Commented by Merkyzedek at 2009/03/20 23:12
흠... 언젠가 도전해 보고 싶은 학문의 일은 이해가 어렵습니다만...

열쇠를 좀 새롭게 만들려고 초콜렛으로 만들었다가, 열쇠구멍에 넣고 잘못돌려서 부러졌다던가.. 하는 비유는 ... 좀 안맞겠지요? ^^
Commented by sonnet at 2009/03/21 08:56
하하. 뭐 대충 통할 것 같기도요.
Commented by 게드 at 2009/03/21 12:19
열쇠보다는 자물쇠..가 비유에 맞지 않을까요..
자물쇠를 새롭게 만들려고 초콜렛으로 만들었다가.. 대충 넣은 열쇠에 부셔져버렸다.. 라고;;
Commented by 곤충 at 2009/03/20 23:37
단어 하나하나는 '~다.'가 기억나는데, 글 자체는 마치 외계어 orz
문과는 역시 답이 없군요.
Commented by sonnet at 2009/03/21 08:53
사실 좀 어쩔 수 없는 부분이 있습니다. 저걸 더 길게 풀어썼다고 이해가 더 쉬워지는 게 아니라서요.
Commented by 하이얼레인 at 2009/03/21 02:10
동그란 바퀴를 못찾았던게지(먼산) 혹은 할당된 예산이 적었다는데 대한 마케터의 자폭-.-?

솔직히 이쯤가면 범 국가적으로 특정 계층들에 대한 떡밥 테스트가 연일 이어지고 있는게 하는 기분이 들기도 함' ㄱ' 특정 계층에 대해 화력이 확실했던 이벤트이긴 했으니까(ㄲㄲㄲ)
Commented by sonnet at 2009/03/21 08:56
기존 암호를 쓰면서 전처리/후처리에 간단한 테이블 변환만 붙이자고 했으면, "독창적인 제품"으로 인정받긴 힘들었겠지 아무래도. 대충 보니 기보에서 돈도 받은 것 같아. 저 프로젝트로.
Commented by 하이얼레인 at 2009/03/21 12:31
...또 그놈의 독창성이냐OTL
Commented by paro1923 at 2009/03/22 09:40
세간의 인식이란 게 원래 '유니크'란 단어를 훨씬 '유니크'하게 여기니... (...)
Commented by 게드 at 2009/03/21 12:24
암/복호화 속도를 높이기 위해서는..
간단합니다.. 하드웨어로 만들어버리면 됩니다 <-
스마트 카드의 경우 기존의 Des, 3Des같은 경우 하드웨어로 임베디드 되어있죠..
뭐 최근 나오는 카드는 소프트웨어로 구현해도 별로 느리진 않습니다.. Seed의 경우 소프트로 구현되어 있기도 하니까요..(회사에따라 하드웨어로도 구현)
거기다 어짜피.. 암호의 주 사용 계층은 금융권이고.. 그곳은 금감원™님이 지배하에 계시고.. 저런 삐리리한 암호는 승인해주실리 없습니다..
사실 Seed도 단독 사용에선 갈굼받는 세상인데;;
Commented by sonnet at 2009/03/22 22:08
DES는 그 설계를 살펴본 사람이면 누구나 인정하지만, 처음부터 하드웨어로 구현할 것을 전제로 설계된 흔적(소프트웨어로 구현할 경우 효율적으로 만들 수 없는 요소가 있음)이 역력하지요. 개발연도(1975)를 생각하면 당연한 것인지도 모르지만요. 반면 요즘 암호는 어떤 것이나 소프트웨어로 아주 빠르게 동작할 것을 당연한 요구사항으로 생각하고 있습니다. AES공모만 봐도 그렇구요.
스마트카드에 하드웨어 암호 모듈을 쓰는 이유는 주로 카드의 프로세싱 능력이 떨어지기 때문이지만, 이번 경우는 최소한 32비트 환경에서 동작될 것으로 보이므로 그런 걱정은 안 해도 될 것 같습니다. 어쨌든 소프트웨어 라이브러리를 파는 업자들 입장에서는 하드웨어 가속기를 추가로 붙일 수 있는 기능은 유용할 수 있지만. 하드웨어가 필수인 라이브러리라면 거의 팔 수 없을 것입니다.

별 필요없다고 생각되지만 속도(response time)를 정말 빠르게 하고 싶다면 OFB로 하고 precalculation을 좀 해두는 방법도 있습니다. 이러면 XOR한 방으로 끝나니까 더 할 게 없겠죠. 선계산 결과가 노출되면 취약할 수도 있지만 메모리에 키를 올려 둔 것보다 더 취약하진 않을 것입니다.
Commented by dhunter at 2009/03/21 15:20
대칭키 방식이 원래 좀... 난감하긴 하죠.

Printable 만 가진다면 UUENCODE 같은 방법도 있지만... '원래와 동일한 길이수를 가진다'라는 목표가 하나 더 있는덕에 보안성이 많이 떨어진것 같네요.
Commented by sonnet at 2009/03/23 09:17
말씀하신 대로 printable하면서도 길이가 그대로라는 조건을 맞추려고 이상한 방법을 도입한 게 쥐약이었던 것 같습니다. 그리고 사실 저는 대칭키라서 특별히 문제가 된 것은 없다고 생각합니다. 아, 개나 소나 만들수 있다는 게 문제일지도 모르겠네요.
Commented by 이네스 at 2009/03/21 23:02
역시나 골때리는 암호화.

효율보다 성능이 더 중요하지요. 뚫렸다간 안드로메다이니.
Commented by sonnet at 2009/03/22 22:09
네, 안전성은 필수요건이고, 다른 것들은 추가기능인 거죠.
Commented by 일화 at 2009/03/22 00:38
마지막 문장이 매우 와닿는군요. 뭐 떡밥이라기라고 보기에는 이벤트의 성격이나 마무리 방식이 설명이 잘 안돼서 말이죠. 힘들여서 네모난 바퀴를 재발명했다는 느낌이 듭니다. 그리고 문과인 (문과치고는 다소 과학에 대한 이해를 한다고 자부하기는 합니다만) 제가 봐도 핵심은 이해할 수 있을 정도로 설명을 잘 해주셔서 새삼 소넷님의 내공이 느껴지네요.
Commented by sonnet at 2009/03/22 22:09
읽어주셔서 감사합니다.
Commented by 하얀까마귀 at 2009/03/22 03:09
암호건 코딩이건 순수 아마추어지만 저같아도 저런 특성 가진 제품을 만들라치면 제일 먼저 생각날 방법은 소넷님이 제안하신 대로일 듯 하네요.

뭐, 그런 식으로 하지 못할 정치적인 이유가 있었거나, 개발자가 암호를 논하기 전에 아예 똥오줌을 못가리거나 둘중에 하나였겠지요.
Commented by sonnet at 2009/03/22 22:11
아마 그랬겠지요. 소프트웨어 개발은 워낙 비효율적인 과정이기 때문에 꼭 해야 하는 일만 하는 습관이 중요한데, 네모난 바퀴를 새로 만들고 있어서야 이건 원...

:         :

:

비공개 덧글

<< 이전 다음 >>