해쉬함수는 왜 '일방향 암호화'가 아닌가

https://damoang.net/new/44938

이 '새로운 소식'에 올라온 글을 보다 보니, 제가 매우 싫어하는 '일방향 암호화'라는 표현이 등장했더군요. 그래서, 해쉬함수를 왜 그렇게 부르는 것이 그다지 좋은 표현이 아닌지에 대한 개인적인 설명을 해볼까 합니다.  사실 이 이야기는 기초적인 암호학을 배운 분이면 다 아는 이야기라서 그다지 새로운 내용은 없습니다만, 그래도 한번 정리해 보면 좋을 것 같아서 써봤습니다.

물론, 돌을 떡이라고 한들, 뭐가 문제이겠습니까. 말은 말이고, 물건은 물건이니, 어떤 물건을 뭐라고 부르는가는 어디까지나 자유입니다. 하지만, 돌을 떡이라고 부르면, 자칫 잘못하면 누군가 돌을 씹어서 이가 부러질 가능성을 조금이나마 높이는 효과가 있습니다. 치아 건강에 신경을 쓰는 사람이라면, 그런 면에서 아무리 기호와 사물의 관계가 자의적이라 하더라도, 사물에 이름을 붙일 때에 좀 조심할 필요는 있습니다. 최소한, 다른 이름과 그 의미와의 관계를 고려해서 적절한 이름을 붙이는 것이 좋겠지요.

< 먼저, 단어에 대해 >

단어에 대한 문제와 개념에 대한 문제는 사실 좀 별개이기는 합니다만, 먼저 언급하겠습니다. 사실, cryptography, encryption, password가 모두 죄다 ‘암호‘로 번역되는 상황은 좀 문제가 있습니다. 이들은 모두 다른 개념이기 때문입니다. 특히, ‘cryptography’는 어원적으로는 물론 ‘숨겨진 글쓰기’에서 왔기 때문에 결국 encryption과 비슷하게 출발했다고 볼 수 있지만, 오늘날 encryption 말고도 다양한 개념들을 포함하고 있습니다.

encryption은, 기본적으로 데이터의 기밀성을 보호하기 위한 기법입니다. 즉, 내 데이터에 대한 정보를 제 삼자가 알지 못하게 하는 것을 목적으로 합니다. 그에 비해, cryptography는 물론 encryption을 포함하고 있고, 사실 어떤 의미에서는 가장 중요하다고도 볼 수 있지만, encryption 말고도 여러 가지 기법들이 있습니다. 아마 encryption을 빼고 가장 중요한 것은 데이터의 무결성(integrity, authenticity)을 보호하는 기법들일 것입니다. 즉, 내 데이터가 변조나 변형 없이 온전하게 남아 있는지 확인하는 것이고, 전자서명이나 MAC 등이 여기에 포함됩니다. 그밖에도 영지식 증명이라든가 identification이라든가 여러 가지 개념과 기법들이 있습니다.

password는, 그냥 password죠. 대강 넘어갑시다.

결국, 이 셋은 각각 상당히 다른 개념을 포함하는 단어들입니다. cryptography가 아마도 가장 포괄적이고 다양한 개념을 포함하고 있고, encryption이나 password는 그 하부에 자리잡고 있는 개념들입니다. 이걸 죄다 '암호'라고 번역하는 것은, 현실이 어찌 되었건 간에, 최소한 그다지 좋은 선택이 아니라고 느껴집니다. 그나마, password에 대해서는 '비밀번호'라는 표현이 꽤 많이 쓰이기 때문에, 큰 문제는 없습니다. (아마도, password에 대해서는 '암구호'가 생각보다 나은 대안이라고 진지하게 생각합니다만, 이게 이런 식으로 사용될 것 같지는 않습니다.) 하지만 어떤 의미에서는 password의 중요성이 나머지 둘 보다 상대적으로 낮기 때문에, 이 단어의 번역은 어찌 되었건 그나마 덜 중요한 편이 아닌가 싶어요.

그에 비해, cryptography와 encryption의 구분은 실질적인 의미가 있습니다. 여기에 대해서는 가장 적절한 표현은 아마도 cryptography를 '암호학'으로 옮기고, encryption을 '암호화'로 옮기는 것이 아닐까 싶습니다. 한국어 위키백과의 경우에는, 'cryptography'를 '암호학'으로 옮기고 있고, 'encryption'은 '암호화', 혹은 '암호'라고 옮기고 있습니다. 여기까지는 대강 괜찮은데, 문제는 cryptography의 형용사형인 cryptographic을 일관되게 '암호화'로 옮기고 있습니다. cryptography를 '암호학'이라고 옮기기로 했다면, 오해를 피하기 위해서는 그 형용사형을 '암호화'라고 옮길 것이 아니라 '암호학적'으로 옮기는 것이 더 나은 선택이었을 것이라고 생각합니다. 예를 들어서 'cryptographic hash function'의 경우에는 이것이 '암호화 해시 함수'라고 옮겨져 있는데, 일단 여기에서도 이 번역은 해쉬함수가 일종의 암호화 기능을 수행한다고 여겨지게 하는 면이 있습니다. 그냥 '암호학적인' 해쉬 함수인데 말입니다.

< Snuffle >

사실, 암호학을 조금만 공부한 분이라면, 해쉬함수의 주된 용도는 암호화가 아니라 주로 무결성 보호와 관련된 쪽이라는 것을 아실 겁니다. 물론, 그렇다고 해쉬함수로 기밀성 보호를 할 수 없느냐...라고 진지하게 묻는다면, 물론, 그렇지는 않다라고 답해야 할 것 같기는 해요. 예를 들어, 잘 디자인된 해쉬함수가 있다면 그것으로부터 암호화 알고리즘을 만드는 것은 비교적 자연스럽기도 합니다. 대표적인 사례는 Snuffle 알고리즘입니다.

https://en.wikipedia.org/wiki/Bernstein_v._United_States

암호학자 Daniel Bernstein이 대학원 시절에 만든 이 알고리즘에는 흥미로운 배경이 있습니다. 20세기가 끝나기 직전까지도 미국은 안전한 암호 기술이 민간에서 쓰이는 것을 좋아하지 않았습니다. 악용될 여지도 있고, 또한 적국이 이를 미국의 감시를 피할 목적으로 사용할 수도 있기 때문입니다. 그래서, 암호화(encryption) 기술을 '무기'로 분류해 버렸습니다. 무기니까, 외국에 수출하기 위해서는 연방정부의 수출 통제를 받아야 합니다. 총의 수출입이 제한된다고 장난감 총의 수출입이 제한되는 것이 아니듯이, 충분히 안전하지 않은, 예를 들어 비밀키의 크기가 충분히 크지 않은 암호화 알고리즘들은 괜찮습니다. 하지만 충분히 안전한, 미국에서 개발된 암호화 알고리즘을 포함한 소프트웨어는 미국 밖으로 나갈 수가 없었습니다.

전 세계가 연결된 인터넷 시대에, 이러한 접근 방식은 이미 시대에 한참 뒤떨어진, 현실적이지 않은 방식이었고, 실제로 그러한 이유로 미 정부는 20세기가 끝날 무렵에 이러한 정책을 폐기하게 됩니다. 하지만 그런 이유로 미국에서 만든 웹 브라우저나 운영체계에는 한동안 키 크기가 상당히 제한적인 알고리즘들만 들어가 있었었고, 이는 실제적인 문제를 일으켰습니다. 우리나라를 비롯해서 다른 여러 나라들이 이에 대응하여 독자적인 안전한 알고리즘을 개발하게 되는 계기가 되기도 했죠. (이게 SEED 및 악명높은 공인인증서 체계의 시작이긴 한데, 저는 최소한 이게 좋은 의도에서 출발했다는 것에는 의심의 여지가 없다고 생각합니다. 다만 그 결과가 의도보다 안 좋았을 뿐...)

그런데 여기서 재미있는 것은, 무기로 분류되는 것은 '암호학적' 알고리즘이 아니라 '암호화' 알고리즘이었습니다. 대표적으로, 전자서명이나 해쉬함수는 수출 통제의 대상이 아니었습니다. 그런데, 현대 암호학의 시작 자체가 6-70년대 히피 운동과도 정서적으로 연결된 부분이 있었고, 초창기의 암호학계에는 분명히 암호학적 기술을 독점하는 정부나 국가 권력에 대한 비판적인 정서가 상당히 있었습니다. 번스틴도 대표적으로 이러한 정서를 공유하고 있었던 사람이었고, 그러한 입장에서 암호 기술의 수출 통제에 부정적이었습니다. 그래서, 그는 미국 정부를 엿먹일 방법을 생각해냅니다. 암호화는 수출 통제 대상이지만 해쉬 함수는 수출 통제 대상이 아니죠. 해쉬 함수는 암호화 알고리즘이 아니니까요. 그러면, 해쉬 함수로 쉽게 암호화 알고리즘을 만들 수 있게 하면 어떨까. 그 결과가 Snuffle입니다. 그리고, 그 결과로 당연히 미 정부로부터 형사 소송을 당하게 되었고, 위의 위키백과 글이 그에 대한 내용입니다.

하지만, 여기에서 제가 언급하고 싶은 것은, 미국 정부도 해쉬 알고리즘 자체를 암호화 알고리즘이라고 보지 않았다는 것입니다. 물론, 해쉬 알고리즘으로 암호화 알고리즘을만들 수있느냐는 다른 문제입니다. 하지만 그 자체가 암호화라는 기능을 수행하느냐? 답은, 아닙니다.

< 그래서 암호화가 뭔데? >

암호화 알고리즘이란, 데이터의 기밀성을 지켜줄 수 있는 알고리즘이라고 정의할 수 있을 겁니다. 물론 이는 매우 모호한 이야기입니다. 조금만 다시 풀어보자면, 아마도 이렇게 얘기할 수 있을 겁니다: 암호문이 평문에 대해서 어떤 것도 말해주지 않아야 한다. 즉, 설령 공격자가 암호문을 도청한다고 해도, 공격자의 평문에 대한 지식이 증가하지 않아야 합니다. 이미 공격자가 평문에 대해 예상하고 있는 것 이상의 새로운 것을 배우면 안됩니다.

(아, 평문의 길이는 일반적으로 보호되지 않습니다. 이게 예외인데, 왜 그런지는 생략하겠습니다.)

이 정의는, 엄밀하게 형식화될 수 있습니다. 그러한 결과 중 하나가 소위 IND-CPA 같은 안전성 정의입니다. 하지만 이 글에서는 굳이 엄밀한 정의를 하지는 않겠습니다.

하지만, 간단한 한 가지는 언급하고 넘어갈 가치가 있습니다. 즉, 안전한 암호화 알고리즘은 결정론적(deterministic)일 수 없다는 것입니다. 어떤 암호화 알고리즘이 안전하기 위해서는,최소한, 그것이 확률론적(probabilistic)이어야 합니다. 즉, 같은 평문을 여러번 암호화해도 그 결과로 나오는 암호문이 매번 달라야 합니다. 암호화 과정에 난수가 포함되어 있어야 합니다.

이유는 매우 간단합니다. 같은 평문을 암호화할 때 매번 같은 암호문이 나온다고 하면, 이는 매우 자명하게 평문에 대한 정보를 노출합니다: 즉, 최소한 두 평문이 같은지 다른지 여부를 암호문만 가지고 알 수 있게 됩니다. 이는 암호문이 없었고 평문이 비밀이면 알 수 없는 정보이므로, 실제로 평문에 대한 정보가 새게 되는 것이고, 안전성이 침해되는 것입니다. 따라서, 암호화 알고리즘이 안전하기 위해서는, 최소한, 그것이 확률론적 알고리즘이어야 합니다.

단순히 두 평문이 같은지 다른지를 아는게 그렇게 심각한 문제일까요? 그렇기도 하고, 아니기도 합니다. 기본적으로, 이것이 문제가 되는 것은 평문의 엔트로피가 적을 때입니다. 즉, 보내지는 평문의 후보가 그리 많지 않을 때. 왜 이런 경우를 따져야 할까요? 암호 알고리즘의 설계자는, 자신의 알고리즘을 '범용 알고리즘'으로 설계합니다. 즉, 그 알고리즘은 보내는 평문이 어떤 종류인가와 무관하게 잘 동작해야 합니다. 예를 들어, 어떤 두 사람이 의사소통을 하는데, 어떤 단순한 의사 결정의 결과만을 보내주면 된다고 합시다. 즉, yes/no의 두 메시지만 보내면 된다고 하죠. 아예 더 간단히 해서, yes는 1로, no는 0으로 보낸다고 합시다. 그러면, 이들의 메시지는 단 1비트입니다. 만일 이때 사용하는 암호화 알고리즘이 결정론적이라면, 단 두 종류의 암호문이 계속 보내질 것입니다. 그중 하나는 0의 암호문이고, 다른 하나는 1의 암호문일 것입니다. 이로부터 공격자는 처음에는 어느 것이 0인지, 어느 것이 1인지 모르겠지만, 어느 순간 뭔가 상황을 파악하게 될 것이고, 이윽고 모든 비밀을 알아낼 수 있을 것입니다. 예를 들어 이 메시지가 어떤 고객이 자신의 대리인에게 거래를 진행해라 말아라 하는 메시지라고 하죠. 실제로 거래가 진행되는지를 몇 번 보고 나면, 어느 암호문이 0인지, 어느 암호문이 1인지 알게 될 것입니다. 그러고 나면, 거래가 이루어지기 전에 암호문만 보고서도 대리인이 거래를 진행할 지의 여부를 미리 알게 될 것이고, 그에 맞게 전략을 수정할 수 있을 겁니다. 이 경우에는, 단순히 두 평문이 같은지 다른지의 여부를 아는 것이 엄청나게 많은 정보를 공격자에게 제공해 버렸습니다.

조금 다른 상황에서는 더 극적인 예도 있습니다. 보통 블록 암호의 운영 모드를 이야기할 때 많이 나오는 그림이죠. 다음은 리눅스 마스코트인 Tux의 그림입니다.

이걸 안전한 암호화 알고리즘으로 암호화를 하면, 그 결과는 (이를 그림으로 다시 표현하면) 다음과 같은 식으로 나옵니다.

원 그림이 무엇인지 전혀 알아볼 수 없습니다.

그런데, 이를 ECB라는 암호화 알고리즘을 (사실 블록암호 운영모드) 이용해서 암호화하면 다음과 같은 식으로 나옵니다.

놀랍게도, 원 그림이 무엇인지 대강 파악이 가능합니다.

왜 이런 일이 벌어질까요? 일단, ECB는 결정론적 알고리즘입니다. 그런데, 뿐만 아니라, 사실 ECB는 긴 메시지를 블록 단위로 (예를 들어 16바이트) 잘라서 각각을 결정론적으로 암호화합니다. 각각의 블록이 결정론적으로 암호화되기 때문에, 예를 들어 원 그림의 흰 배경은 16진수로 FFFFFF들이 연속된 블록값을 갖게 되는데, 그 평문 블록이 특정 암호문 블록으로 대응되게 됩니다. 흰 배경을 그러한 흰 점들이 가득 채우고 있으니, 그 부분은 이 특정 암호문 블록이 연달아 붙어서 이루어진 이상한 배경 무늬를 이루게 됩니다. 경계선에서는 그림이 희미해지지만, 어떤 특정 색깔로 칠해진 영역이 넓게 분포해있으면, 그 영역을 암호문에서도 관찰할 수 있습니다. 이런 경우는, 결정론적 암호화 알고리즘의 약점이 가장 극적으로 드러나는 예입니다. 일반적인 경우에는 이 정도까지는 아닐 수 있습니다. 하지만, 여전히 두 평문이 같은지 다른지에 대한 정보는, 분명히 자명하지 않은 정보임이 분명하고, 이것이 누출되는 것은 분명히 유의미한 공격이 맞습니다.

< 패스워드의 저장 >

그렇다고 역사적으로 해쉬함수가 데이터의 저장에 쓰이지 않았냐 하면, 물론 그렇지는 않습니다. 가장 대표적으로, 패스워드를 저장하는 데에 전통적으로 해쉬함수가 쓰여왔고, 현재도 그렇게 쓰이고 있습니다. 개인적으로는, 이것은 일종의 역사적 우연이라고 생각합니다. 가장 좋은 솔루션은 아니지만, 현실이 이런 해법을 말하자면 강요했다고 말이지요. 왜 그런지 살펴보겠습니다.

데이터의 기밀성을 보호한다고 할 때, 전송되는 데이터를 보호하는 것과 저장되는 데이터를 보호하는 것은 조금 다른 접근을 필요로 합니다. 보통 전송되는, 즉 통신 데이터를 보호한다고 할 때에는, 통신망을 통한 도청의 가능성을 걱정합니다. forward security 등의 모델이 예외이기는 합니다만, 대체로 공격자가 예를 들어 해킹을 통해 적법한 사용자의 시스템에 침입한다거나 하는 시나리오는 염두에 두지 않습니다. 그래서, 이러한 상황에서 암호화 알고리즘을 통해 데이터의 기밀성을 확보하는 것은 상대적으로 간단합니다.

그에 비해, 저장되는 데이터도 사실 보호의 필요성이 있습니다. 그러니 뭔가 암호화를 하기는 해야 할 것 같습니다. 그런데, 좀 생각해 보면, 만일 공격자가 앞에서와 같이 적법한 사용자의 시스템에 침입할 수 없다고 한다면, 사실 굳이 데이터를 저장할 때 암호화해서 저장할 이유가 없습니다. 하지만 민감한 데이터를 저장할 때에 암호화를 안 한다는 것은 물론 이상합니다. 즉, 저장되는 데이터를 암호화한다는 것은, 공격자가 시스템에 최소한 어느 정도는 접근 가능성이 있음을 인정한다는 것을 의미합니다. 혹은, 아예 공격자가 내부자이거나요. 예를 들어 다수의 사용자가 한 시스템을 공유하는, 서버 같은 시스템이라면, 접근 권한이 제대로 설정되어 있지 않다면 내부의 사용자가 다른 사용자의 데이터에 접근할 여지가 있을 것입니다.

그런데, 이러한 상황을 고려하기 시작하면 일이 복잡하게 꼬입니다. 데이터의 기밀성을 위해 데이터를 암호화한다고 합시다. 그건 좋습니다. 그런데, 이 데이터는 나중에는 언젠가 사용해야 하니까, 복호화를 위한 키가 어딘가에 있어야 합니다. 이 키를 어디에 두어야 할까요? 이를 그냥 시스템 내부에 저장한다면, 어쩌면 시스템의 내부에 접근 가능한 공격자가 키에도 접근할 수 있을 지도 모릅니다. 이 키를 그럼 암호화해야 할까요? 그럼 키를 암호화하기 위한 키는 어디에 두어야 할까요?

이런 문제가 해결이 불가능하다고까지는 하지 않겠습니다만, 최소한 이 상황을 통해 알 수 있는 것은, 키 관리가 생각보다 복잡한 일이 될 수 있다는 것입니다. 암복호화에 사용하는 키를 적법한 사용자만이 접근 가능하게 잘 관리하는 것은, 물론 전송 데이터의 보안에도 중요하겠지만, 저장 데이터의 보안에는 특별히 더 중요합니다.

패스워드를 해쉬함수로 ’저장’하는 것에는 이러한 배경이 있습니다. 사용자를 공격자와 구분하기 위해서는, 사용자를 공격자와 차별화할 수 있는 무엇인가가 있어야 합니다. 지문과 같은 고유의 생체 정보일 수도 있겠습니다. 혹은, 패스워드나 암호 키와 같은, 사용자만이 아는 비밀 정보일 수도 있습니다. 생체 정보에도 나름대로의 단점이 있습니다만, 생체 정보를 이용한 사용자 인증은 상당히 매력적이기는 합니다. 다만 여기에서 문제는, 생체 정보를 이용하려면 이를 읽어낼 수 있는 리더나 센서가 필요한데, 옛날에는 그런 것이 마땅치 않았죠. 그러니 패스워드가 만만합니다. 결과적으로, 패스워드는 사용자 인증을 위한 가장 저렴하고 보편적인 솔루션으로 자리잡았습니다.

문제는, 이걸 어떻게 저장할까입니다. 이때 시대적 배경은 예를 들어 UNIX 메인프레임 같은 것이 쓰이던 20세기 중후반입니다. 이러한 시스템들은, 처음에는 보안 같은 것을 그다지 걱정하지 않고 만들어졌습니다. 아무나 이용하는 시스템이 아니라, 정부 관계자들, 혹은 대학의 구성원들, 등 특정 계층의 사람들만이 쓸 수 있었고, 기본적으로 이를 이용하는 사람들은 말하자면 ‘친구’들이었습니다. 그러니 공격에 대한 대비 같은 개념이 그다지 세련되게 발달한 상황은 아니었습니다. 그럼에도 불구하고, 뭔가 패스워드를 안전하게 저장할 필요가 있고, 이를 외부자 뿐만 아니라 내부자로부터도 지켜야 한다는 것은 어느 정도 분명했습니다. 암호화하는 것이 가장 당연한 답입니다만, 패스워드를 확인하기 위해서는 암호문을 복호화해야 합니다. 복호화하기 위해서는 복호화 키가 필요하고, 이 키를 어떻게 저장해야 할 것인지 자체가 문제가 될 여지가 있습니다.

그로부터, 해쉬 함수를 패스워드의 ‘저장‘에 사용하겠다는 아이디어가 등장하게 됩니다. 해쉬 함수는 결정론적 함수이므로, 패스워드가 아니라 패스워드의 해쉬를 저장해 두면, 나중에 사용자가 패스워드를 입력할 때, 그 패스워드의 해쉬를 계산해서 저장된 해쉬와 비교해 보면, 사용자의 패스워드가 맞는지 여부를 판별할 수 있습니다. 해쉬 함수는 복호화 알고리즘이 존재하지 않고 (매우 긴 패스워드를 짧은 해쉬값으로 대응시키는, 다대일 함수이므로 표준적인 복호화 알고리즘이 있을 수는 없습니다), 잘 만든 해쉬함수라면 해쉬로부터 그 해쉬값을 갖는 원 메시지를 복구하기 어려워야 하므로 (일방향성), 내부자가 해쉬값을 알아낸다고 해서 그에 대응되는 패스워드를 알기는 어려울 것입니다. 해쉬함수에는 암복호화 키가 없으므로, 키 관리의 필요성 또한 사라집니다. 이보다 더 완벽할 수 없습니다. 그래서 뭐가 문제죠?

무엇이 문제인가를 이야기하기 전에 우선 한 가지만 언급하자면, 현재는 이런 식으로 유닉스 시스템의 사용자 인증을 위해 패스워드를 쓰던 시대와 비교할 때, 상황과 환경이 상당히 많이 바뀌었습니다. 이제는 인터넷을 통한 원격 사용자 인증의 중요성이 보다 높아졌습니다. 또한, 그때와는 달리 기술적인 진보가 상당히 있었습니다. 우선, 생체 정보 리더가 온 천지에 널리 보급되는 사태가 벌어졌습니다. 생체 정보 리더라고 쓰고, 스마트폰이라고 읽으면 되지요. 지문, 얼굴, 홍체 등, 다양한 생체 정보를 읽을 수 있는 리더가 사방에 널려있습니다. 생체 정보를 이용한 사용자 인증은 그 어느때보다도 쉬워졌습니다. 또한, 암호키 저장소가 발전했습니다. key storage, secure enclave, 등등 다양한 이름으로 불리우는 이것은, 특히 스마트폰에서부터 시작되었지만, 이제는 그보다 더 다양한 환경에 도입되었습니다. 일반적인 사용자 프로세스가 접근할 수 없는 영역에 암호키를 잘 저장하고, 암호키 자체가 그 저장 공간을 벗어나지 못하게 합니다. 때로는 아예 별도의 처리장치를 사용해서, 아예 주요 암호화 과정 자체를 그 내부에서만 수행합니다. 이러한 기술은 패스워드를 해쉬함수로 저장하던 시절의 기술적 배경에 비하면 상당한 진보가 맞습니다. 내부 공격자를 염두에 둔 키 관리가 가능해졌고, 꼭 패스워드가 아니더라도 생체 정보와 같은 다른 인증 수단의 대안들이 생겨났습니다. 그래서, 패스키와 같은 보다 진지한 암호학적 사용자 인증 솔루션들이 진지하게 제안되고 사용되기 시작했습니다. 아마도, 이런 방향이 사용자 인증의 미래가 아닐까 싶습니다. 패스워드는 오래되었고, 값싸고, 우리가 잘 이해하는 솔루션이지만, 다른 한편으로 낡았고, 꾸준히 자질구레한 문제를 일으키고 있으며, 관리가 귀찮고, 안전성이 떨어집니다. 우리는 패스워드를 써 왔고, 앞으로도 상당 기간 사용하겠지만, 이 기술이 어디까지나 과거의 기술임은 분명합니다.

< 해쉬 함수의 사용 >

해쉬 함수는, 앞에서 잠시 말씀드렸던 대로, 기본적으로는 데이터의 기밀성 보다는 데이터의 무결성을 지키는 용도로 주로 사용됩니다. 하지만, 패스워드의 경우를 보면 알 수 있듯이, 실제 응용 사례를 볼 때에 이것이 데이터의 기밀성을 지키는 목적으로 전혀 사용되지 않는 것은 아닙니다. 또한, 해쉬 함수가 결정론적 함수라는 것도 나름 이 용도에의 사용에 나름 이유가 있습니다. 사용자가 입력한 패스워드가 맞는지 확인하기 위해서는, 해쉬 함수가 확률론적이라면 문제가 있겠지요. 계산할 때마다 해쉬값이 달라져서야 두 해쉬값을 비교할 수 없으니까요.

하지만, 그럼에도 불구하고, 저는 이러한 해쉬 함수의 사용은 어디까지나 가능한 기술적 수단이 별로 없었던 과거의 역사적 상황의 유산에 불과하다고 생각하는 편입니다.

사실, 여기까지 설명했으면 사실상 해쉬함수의 문제에 대해 이미 다 설명한 셈입니다. 그럼에도 불구하고, 문제점들을 구체적으로 이야기해보도록 하겠습니다.

말씀드렸듯이, 저는 해쉬함수를 일종의 암호화 알고리즘으로 보는 것이 그다지 좋은 관점이 아니라고 생각합니다. 진지한 암호학적 문서들에서는 보통 그런 표현이 잘 나오지는 않는데, 그럼에도 불구하고 보안 업계에서 해쉬함수를 ‘일방향 암호화‘라고 부르는 경우가 있음을 알고 있습니다. 이 일방향이라는 표현은 아마도 두 가지 중의적인 뜻이 있을 겁니다. 첫째, 해쉬함수는 더 큰 공간에서 더 작은 공간으로의 함수, 즉 다대일 함수이므로, 자연스럽게 수학적 의미의 역함수가 존재하지 않습니다. 그러므로, 통상적인 암호화 알고리즘과는 좀 달리, 표준적이고 효율적인 복호화 알고리즘이 없는 것이 당연합니다. 그런 의미에서 ’일방향’ 암호화라고 할 수 있을 것입니다. 또 하나, 해쉬함수의 안전성 요구조건으로 흔히 등장하는 것 중 하나가, 역상 저항성(preimage resistance) 입니다. 메시지에 대해 해쉬값을 계산하는 것은 쉽지만, 해쉬값에 대해 그 해쉬값을 갖는 메시지를 거꾸로 계산하는 것은 어려워야 합니다. 즉, 해쉬함수는 일종의 일방향 함수(one-way function) 이어야 합니다. 제가 이 ‘일방향 암호화’의 엄밀한 정의를 들어본 적은 없습니다만 ( ‘해쉬함수는 일방향 암호화이다’ 라는 선언 말고는 들어본 적이 없어요. 그냥 두 대상은 개념적으로 동일한 대상인 것인가요?), 제 맘대로 해석하자면, 여기서 ‘일방향’의 의미는 이 둘 다일 것입니다.

그래서, 해쉬함수를 암호화 알고리즘으로 사용하면 무슨 문제가 발생하나요? 말씀드렸듯이, 해쉬함수는 결정론적 알고리즘입니다. 그리고, 만일 암호화 알고리즘이 결정론적이면, 평문에 대한 정보가 새어나갑니다. 그게 문제의 본질이고, 전부입니다.

이게 문제가 되나요? 네 됩니다. 기본적인 문제는 메시지의 엔트로피가 적을 때, 즉 처리될 수 있는 메시지의 후보가 적을 때 발생합니다. 예를 들어, 어떤 사람의 생일을 ‘저장’한다고 합시다. 생일의 해쉬값을 저장합니다. ‘일방향 암호화’가 되어 있으니, 이 사람의 생일 정보는 이제 안전합니다. 그렇죠?

물론 그렇지 않습니다. 생일은 생각보다 그리 많지 않습니다. 1년은 365일밖에 되지 않습니다. 보통 지금 살아있는 사람들의 대부분의 나이는 100세 미만일 것이고, 그렇다면 고려해야 할 생일은 고작 36500일… 윤년을 포함…귀찮으니 하지 말기로 합시다. 36500가지의 후보만이 존재합니다. 각각의 해쉬값을 계산해서, 저장된 해쉬값과 비교하는 작업을 계속하면, 36500번만 시도하면 그 사람의 생일을 ‘복호화’할 수 있습니다. 어, 일방향 암호화라더니 역방향 계산이 되네요?

평문의 엔트로피가 더 적어지면, 즉, 선택지가 더 적은 경우에는 이는 더 치명적이 됩니다.
예를 들어 개인정보 데이터베이스에 성별이 기록되어 있고, 성별이 남/여의 두 종류밖에 없다고 합시다. (성별이 보다 다양하다고 말하는 사람들도 많이 있습니다만, 여기서는 이 데이터베이스가 이렇게 이분법적인 성 구분을 하고 있는 경우를 편의상 생각하겠습니다.) 이 경우에는, 시도해야 하는 횟수가 36500회가 아니라 2회가 됩니다. 거의 곧장 ‘복호화’를 할 수 있습니다.

기본적으로, 해쉬함수로 ‘저장’할 때 안전하다고 할 만한 데이터는, 매우 엔트로피가 높은 데이터 뿐입니다. 즉, 가능한 후보가 너무나도 많은 것들은 그나마 안전하다고 할 수 있습니다. 해쉬함수는 기본적으로 엔트로피가 낮은 데이터의 기밀성을 보호하지 않습니다. 패스워드를 추측하기 어려운 것으로 고르고, 긴 패스워드를 고르라고 하는 이유이기도 합니다. 패스워드의 엔트로피가 올라가면, 해쉬함수는 이를 보호할 수도 있습니다. 하지만, 예측 가능한, 낮은 엔트로피의 패스워드를 해쉬함수는 보호해주지 않습니다. (해쉬함수가 암호화 알고리즘이 아닌 또다른 이유이기도 합니다. 왜 암호화했는데 보호가 안 되죠? 예를 들어 어떤 메시지를 AES-CTR로 암호화했다고 합시다. 그러면 그 메시지의 특성과 무관하게 그 메시지의 기밀성은 보호됩니다. 엔트로피가 크든 작든 상관없습니다.)

그리고 위에 나온 기사와는 달리, 이는 해쉬함수의 해쉬 길이와 그다지 상관이 없습니다. 이 이슈는 해쉬함수의 출력이 256비트이든, 512 비트이든 기본적으로 다를 바 없이 적용됩니다.

해쉬함수의 사용을 유지한 채로 이러한 공격의 위협에 그나마 어느 정도 대응할 수 있는 방법은 따로 있습니다. 해쉬함수를 매우 느리게 만들거나, 아니면 솔트(salt)를 사용하는 것입니다.

해쉬함수를 매우 느리게 만드는 것은 이해하기 쉽습니다. 앞에서 언급된 생일의 경우, 36500번 해쉬함수를 계산해 보면 생일을 ‘복호화’할 수 있습니다. 만일 해쉬함수의 속도를 만배 느리게 만들 수 있다면, 36500번 해쉬함수를 계산하려고 시도할 때 실제로는 365000000번 해쉬함수를 계산해야 하는 효과를 낼 수 있습니다. 단순 반복 시도에 의한 공격을 차단할 수 있는 나름 괜찮은 방법입니다. 느려지면 불편하지만, 예를 들어 정상적 사용자를 위한 인증은 해쉬함수 계산 한 번이면 되니까, 이 방식은 적법한 사용자를 많이 괴롭히지 않지만 공격자를 많이 괴롭히는 방식입니다.

하지만, 그럼에도 불구하고 해쉬 함수가 평문에 대한 정보를 누출한다는 사실은 바뀌지 않습니다. 그렇게 만배 느린 해쉬함수를 사용했다고 하더라도, 그러한 해쉬함수로 성별 정보를 ‘암호화’할 수는 없습니다: 두 번 계산해서 비교하면 끝나니, 아무리 느리게 해도 방법이 없습니다.

또다른 방법은 salt를 사용하는 것인데, 사실, 이는 굳이 말하자면 약간 보완적인 개념에 불과하고, 공격을 정말 직접적으로 잘 막아주는 방식은 아닙니다. 하지만, 솔트가 있으면 보다 치명적인 공격이 될 수 있는 상황을 덜 치명적인 공격만 있는 상황으로 바꾸어줄 수 있습니다.

솔트란, 어떤 메시지의 해쉬 값을 계산할 때, 해당 메시지만 입력으로 넣지 말고, 별도로 고른 다른 추가적인 메시지를 같이 계산하는 기법이고, 이때에 사용하는 추가적인 메시지가 바로 솔트입니다. 즉, 어떤 메시지 m의 해쉬값 H(m)을 계산할 때, 이렇게 그냥 계산하지 말고, 어떤 솔트 s를 골라서, H(s, m)과 같이 계산하는 방식입니다. 이 해쉬값은 s와 m 둘 다에 대해 결정론적으로 정해지게 됩니다.

패스워드를 저장한다고 합시다. m이 패스워드이고, 어떤 솔트 s를 시스템이 랜덤하게 골라서, 이렇게 나온 해쉬값 h=H(s, m)을 저장해 둡니다. 자, 이제 문제가 하나 있습니다. 나중에 이 사용자가 다시 와서 인증을 시도하는데, 그 과정에서 패스워드 m을 입력하면, 시스템은 이 m이 맞는 값인지 판별해야 합니다. 그러기 위해서 h를 계산해 봐야 하는데, 문제는 h의 계산에는 m 뿐만 아니라 솔트 s가 함께 쓰였습니다. 그래서, 패스워드의 검증을 위해서는 이러한 경우 해쉬 h만 저장하는 것이 아니라, 이를 계산하는 데에 쓰인 솔트 s를 같이 저장할 필요가 있습니다. 그러고 나면, 사용자가 패스워드 m을 입력할 때 h=H(s, m)을 계산할 수 있고, 이 계산된 해쉬값이 저장된 해쉬값과 같은지 여부를 판정할 수 있습니다.

그런데, 어차피 솔트가 저장될 거라면, 이는 잠재적으로 내부 공격자의 입장에서 볼 때에, 해쉬값에 접근할 수 있다면 솔트에도 접근할 수 있을 겁니다. 데이터의 ‘복호화’도 그냥 앞에서와 마찬가지로 그냥 진행할 수 있습니다. m이 성별이라면, 해쉬값 h와 솔트 s가 있을 때, H(s, ‘남자’)를 계산해보고, H(s, ‘여자’)를 계산해보면 그 사람의 성별을 ‘복호화’할 수 있습니다. 보시다시피, 이 경우 솔트가 전혀 장애가 되지 않습니다.

그래서, 솔트가 막아주는 것은 이러한 무차별 대입 공격이 아닙니다. 솔트는 조금 다른 종류의 공격을 막아주는 효과가 있습니다. 바로, 사전 계산(precomputation) 공격입니다.

이러한 사전 계산 공격의 목표물은, 무차별 전수 조사 대입 공격이 가능하기는 한데 좀 버거운 상황입니다. 이러한 경우, 사전에 전수 조사보다 더 많은 양의 계산을 해서, 그 결과를 말하자면 압축해서 저장해 두면, 그 사전 계산 결과를 이용해서, 실제로 '복호화'해야 하는 해쉬값이 있을 때 이를 매우 빨리 복호화할 수 있습니다. 솔트는 이러한 상황에 대한 효과적인 방어책이 됩니다. 왜냐하면, 솔트를 사용한다는 것은 말하자면 각각의 솔트마다 서로 다른 해쉬함수를 사용하는 것과 같은 효과를 주기 때문입니다. 각각의 솔트는 엄청나게 많으니, 각각의 솔트마다 사전 계산을 할 수는 없습니다. 그래서, 구체적인 공격 타겟이 나타나야 (해쉬값과 솔트) 그제서야 전수조사를 할 수 있게 됩니다. 그럼에도 불구하고 굳이 사전 계산을 하고 싶다면, 이제는 솔트 자체를 메시지의 일부로 간주하고 사전 계산을 해야 합니다. 하지만 이렇게 되면, 솔트가 메시지의 일부이므로, 이 메시지는 매우 높은 엔트로피를 갖게 됩니다. 패스워드와는 달리, 솔트는 시스템이 선택하고, 사람이 기억할 필요가 없으므로, 얼마든지 길고 복잡해질 수 있으니까요. 그러니, 결과적으로 솔트를 포함한 사전 계산은 불가능하게 됩니다.

정리하면, 솔트가 있으면 사전 계산을 막아줄 수 있습니다. 하지만 사전 계산이 아니라 무차별 대입을 막지는 못합니다. 해쉬함수가 느리면 무차별 대입에 대한 어느 정도의 방어가 됩니다. 하지만 메시지 자체의 엔트로피가 너무 낮으면, 역시 별 방법이 없습니다.

< 카카오페이에서 일어난 일? >

사실, 신문기사나 금융감독원의 보도자료만 보고 무슨 일이 일어났는지 정확히 모든 것을 알기는 어렵습니다. 해쉬함수가 이야기의 핵심이니까, 해쉬함수에 대한 이야기만 주의깊게 보기로 하지요. 보도자료에 의하면, 카카오페이에서 넘긴 데이터 중에 해쉬값을 넘긴 것은 다음과 같은 모양입니다.

그리고, 다른 보도자료를 좀 더 보면,

라고 합니다. 그리고,

이라는 이야기가 있습니다.

여기까지의 이야기만으로도 아주 자세한 세부 사항은 애매한 면이 있긴 한데, 그래도 대강 무슨 일이 일어났는지는 짐작할 수 있습니다. 물론, 금융감독원의 말이 맞다는 전제 하에. 그리고, 금융감독원이 한 이야기의 상당 부분은 의견이나 주장이 아니라 팩트에 대한 부분이므로, 물론 거기에서 제시한 팩트가 사실인지의 여부가 남아 있기는 합니다만, 일단 그게 모두 사실이라는 전제 하에 살펴도록 하죠.

정리해 보면,

즉, 사용된 해쉬함수는 무조건 SHA-256이었고, 아마도 정확히 개인정보가 어떻게 전달되었고 어떻게 매칭에 사용되었는지는 모르겠으나, 최소한 계산된 해쉬값이 전달된 것은 맞는 것 같습니다. 아마도 솔트는 사용되지 않았을 것 같으나, 설령 사용되었다 하더라도, 매칭을 위해 함께 전달되었어야 했을 것입니다.

저는 금융감독원의 지적대로, 이러한 방식이 결과적으로 알리페이에 카카오페이 고객들의 개인정보가 전달되는 결과를 가져왔고, 분명 문제가 있다고 생각합니다. 다만, 금융감독원은 아마도 사용된 해쉬함수가 SHA-2 계열 중 가장 약하...한 편이라고 할 수 있는 SHA-256에 불과하고, 또한 솔트를 사용하지 않은 것을 문제삼은 것 같습니다만, 그 세부적인 지적은 제대로 된 지적이 아니라고 생각합니다.

여태까지의 설명을 대체 끝까지 읽은 분이 얼마나 될지 모르겠습니다만, 여태까지의 설명을 따라오셨다면, SHA-256이 아니라 SHA-512가 되었다 하더라도 근본적으로 상황이 바뀌는 것은 없다는 것을 알 수 있을 것입니다. 그냥 해쉬값의 크기만 커질 뿐인데, 여기서 문제는 해쉬값의 길이가 아니라 데이터의 성격이기 때문에, SHA-256이냐 SHA-512냐는 별로 대세에 영향을 주지 않습니다.

또한, 솔트를 쓰느냐 마느냐 또한 핵심적인 문제는 아닙니다. 솔트를 쓰면 사전 계산 공격을 막을 수 있기 때문에, 뭔가가 어차피 깨지는 상황에서 더욱 극적으로 왕창 깨지는 상황을 막아줄 수는 있지만, 처음부터 깨지는 사태가 발생하지 않게 막아주지는 않습니다. 솔트가 있든 없든, 전화번호를 전수조사 대입으로 공격하는 것을 막을 수는 없습니다.

이런 상황을 그나마 어느 정도 막아줄 수 있는 것은, 아주 느린 해쉬함수를 쓰는 것입니다. 그냥 보통의 해쉬 함수를 반복 적용하는 식으로 해서 이러한 해쉬함수를 쉽게 만들 수 있습니다. 그런데, SHA-256은효율적인해쉬함수입니다. 공격을 전혀 막아주지 못합니다.

SHA-256이 NSA가 만들었고 NIST가 표준화했고 각종 암호학적 목적으로 널리 쓰이는 것과 이 상황은 무관합니다. SHA-256은 이런 데 쓰라고 만든 것이 아닙니다. 그리고, 이 방식은 안전하지 않습니다. 전화번호는 이렇게 해쉬 처리하면 그냥 드러날 수밖에 없습니다.

< 해쉬함수를 암호화에 그래서 절대로 못 쓰나? >

그런 게 어딨겠습니까. 죽어도 써야 한다면, 써야지요.

어떤 특정 응용이 반드시 그러한 방식을 필요로 한다면, 어쩔 수 없이 써야 합니다. 하지만, 최소한 그 때에 어떤 위협이 있는지는 알아야 하고, 또한 그 위협을 그나마 감소시킬 방법이 있는지 확인해야 합니다.

일단, 백번 양보해도 해쉬함수는 최소한 저엔트로피 데이터를 보호하기 위한 수단이 아닙니다. 즉, 해쉬함수로 처리할 수 있는 데이터 자체에 제약이 있습니다. 해쉬함수로는 고엔트로피 데이터만을 다뤄야 합니다. 그리고 해쉬함수를 꼭 써야만 하는 이유가 있어야겠죠. 매칭을 해야만 하기 때문에 결정론적 알고리즘이 꼭 필요하다거나. 그러한 고엔트로피 데이터의 예로는, 패스워드 등이...

잠깐, 근데 패스워드가 고엔트로피 데이터라는 말은 조심스럽게 할 필요가 있습니다. 전통적으로 패스워드는 암기해야 하는 대상입니다. 왜냐하면, 함부로 적어 두면 누가 그걸 볼 수가 있잖아요? 그런데 암기를 위해서는, 너무 복잡하면 안되죠. 그리고 너무 복잡하지 않으면, ..., 엔트로피가 낮아집니다.

이 상황을 해결하기 위해서는, 패스워드를 사람이 선택하고 암기하면 안됩니다. 이제 패스워드라는 것은 사람이 외우는 물건이 더 이상 아닙니다. 기계가 고르고, 기계가 저장해야 합니다. 그러한 것을 '패스워드 매니저'라고 하죠. 패스워드 매니저는 더 이상 특별히 보안에 과민한 사람이나 쓰는 물건이 아닙니다. 웬만한 브라우저와 웬만한 운영체계에 보통 기본으로 딸려오고 있습니다. 아직도 패스워드 매니저를 안 쓰고 있다면, 뭔가 문제가 있는 겁니다. 대체 이걸 안 쓸 이유가 어디에 있단 말입니까.

패스워드 매니저가 패스워드를 고르고 저장하면, 얼마든지 원하는 만큼의 고 엔트로피 패스워드를 만들 수 있습니다. 그런 패스워드는 얼마든지 해쉬함수로 보호할 수 있습니다.

그럼에도 불구하고 나는 죽어도 저엔트로피 데이터를 해쉬함수로 처리해야만 하겠다?

정말로 그것밖에 답이 없는 상황이라면, 최소한 해쉬함수를 보통 많이 쓰는 표준 해쉬함수가 아니라, 매우 느린 것으로 사용할 필요가 있습니다. 또한, 추가적으로, 솔트를 덧붙일 필요가 있고요. 솔트는 정말로 엔트로피가 매우 적을 때에는 별 도움이 되지 않습니다만, 좀 애매한 상황에서는 그나마 어느 정도 공격을 완화시키는 효과가 있습니다.

< 굳이 그래야 하겠어요? >

하지만, 정말로 굳이 그래야 할까요? 그나마 잘 만들어진 패스워드 같은 것을 관리하기 위한 수단으로서 해쉬함수를 쓰는 것은 어느 정도 이해할 만도 합니다. 하지만 그렇다고 해서 아무 데이터나 해쉬함수를 써서 '일방향 암호화'하는 것은, 정말로 이해하기 어렵습니다. 왜 굳이?

무엇보다, 오늘날에는 패스워드든, 해쉬함수를 사용하는 '암호화'든, 기술적 대안들이 있습니다. 말씀드렸던 대로, 생체 정보를 이용한 인증의 길이 활짝 열려있습니다. 또한, 키 스토리지 기술을 통해 저장 데이터의 암호화를 위한 키 관리 또한 어느 정도 잘 할 수 있습니다. 인증의 경우에도, 패스워드가 아니라 패스키 같은 대안도 있습니다.

물론, 정말로 특정 상황에서 기술적인 답이 그것밖에 없다...라고 한다면, 해쉬함수를 기밀성 보호를 위해 사용해야 하겠지요. 하지만, 최소한 그런 경우에도 내가 어떤 위험을 감수하고 있는지는 알아야 합니다. 기본적으로, 해쉬함수는 임의의 데이터의 기밀성을 안전하게 보호할 수 있는 수단이 아닙니다.

그래서 이 상황을 간단히 요약하자면, 이렇게 말할 수 있습니다.

"해쉬함수는, 암호화 알고리즘이 아닙니다."

저는 어떤 때에는 단어나 용어의 선택이 실제로 뭔가를 오용하는 데에 기여하는 면이 있다고 생각합니다. 해쉬 함수에 대해 '일방향 암호화'라는 표현을 쓰면, 결국 해쉬 함수가 일차적으로 일종의 암호화 알고리즘이라는 인상을 심어주게 됩니다. 해쉬 함수는 '암호학적 알고리즘'이고, 암호학의 여러 분야에, 심지어 경우에 따라서는 암호화 알고리즘을 만들기 위한 목적으로도 사용됩니다만, 그 자체가 암호화 알고리즘이라고 보기는 어렵습니다. 그것을 굳이 암호화 알고리즘이라고 불러야 한다면 그걸 막을 방법은 없습니다. 형사법적으로 죄가 되지는 않을 테니까요. 하지만, 저는 그 표현이 정보보호 관점에서 실제적인 해를 끼친다고 생각합니다. 그리고, 해쉬함수는 일방향이든, 역방향이든, 옆방향이든, 그 자체로는 암호화 알고리즘이 아니라고 생각하는 것이 가장 건전한 접근 방식이라고 생각합니다.

그럼 해쉬 함수는 뭐냐?

뭐, 해쉬 함수죠. 다양한 암호학적인 목적으로 사용할 수 있는, 좋은 부품입니다. 블록 암호도 마찬가지입니다. 여태까지 제가 말씀드렸던 것을 이해하셨다면, 블록 암호 또한 그 자체로 '암호화 알고리즘'이라고 부르지 않는 것이 좋다고 제가 주장할 것임을 짐작하실 수 있을 것입니다. 블록 암호 또한, 매우 좋은 암호학적 부품입니다. 그걸로 암호화 알고리즘을 만들 수도 있고, 또한 무결성 보호 알고리즘을 만들 수도 있습니다. 하지만, 그 자체로는 블록 암호는 그냥 pseudorandom permutation, 즉 의사 랜덤 치환에 불과합니다. RSA 또한 마찬가지입니다. RSA는 트랩도어 일방향 치환(trapdoor one-way permutation)입니다. 소위 vanilla RSA encryption, vanilla RSA signature가 있지만, 이들은 오늘날의 현대적인 관점에서 볼 때에 안전한 암호화 알고리즘이 아니고, 안전한 전자서명 알고리즘이 아닙니다. RSA 함수 또한, 암호화라고 보는 것 보다는, 그냥 좋은 암호학적 알고리즘들을 만드는 데에 도움이 되는 좋은 트랩도어 함수, 좋은 암호학적 부품이라고 보는 것이 건전한 접근 방식이라고 믿습니다.