블록암호화 알고리즘 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팀이 상정한 것처럼 실제로 암호화되는 데이터의 양이 크지 않다면 실질적인 부담은 무시할 수 있을 수준일 것입니다.