느린 해쉬함수와 솔트의 사용

https://damoang.net/lecture/9146

위의 글에 덧붙여, 느린 해쉬함수의 사용 및 솔트의 사용에 대해 약간만 더 이야기해 보겠습니다.

우선, 해쉬함수로 (기밀성 보호 목적으로) 처리할 수 있는 데이터는 제한적이라는 말씀을 드렸었습니다. 즉, 저 엔트로피 데이터를 안전하게 처리하는 것은 힘들다. 하지만 고 엔트로피 데이터는 보호가 가능하다. 그래서, 패스워드의 처리는 원칙적으로 가능합니다. 특히, 패스워드 관리자 등을 사용해서 고 엔트로피 패스워드를 잘 사용한다고 하면, 충분히 안전할 수 있습니다. 그렇다고 'password', 'q1w2e3r' 같은 패스워드가 보호되지는 않겠습니다만...

대표적인 저 엔트로피 데이터가 어떤 것들이 있을까요? 음... 상당수의 개인정보는 낮은 엔트로피를 갖습니다. 성별, 생일, 전화번호, 주민등록번호, ... 이들 모두는, 웬만하면 해쉬함수로 소위 '일방향 암호화'하면 안되는 것들입니다. 사실, 충분히 랜덤한 패스워드를 제외하고 굳이 해쉬함수로 기밀성을 보호해야 할만한 데이터가 있는지 잘 모르겠습니다.

어쨌든, 굳이 해쉬함수를 데이터의 기밀성을 보호하는 데에 그나마 좀 도움이 될 수 있을 만한 기법으로, '느린 해쉬함수를 쓴다'와 '솔트(salt)를 뿌린다' 정도가 있습니다.

< 전수조사 공격과, 느린 해쉬함수의 사용 >

낮은 엔트로피를 갖는 데이터에 대한 공격은 간단합니다. 가능한 입력들에 대해 모두 해쉬값을 계산해 보는 겁니다. 그러다가 어쩌다 목표 해쉬값이 나오면, 이제 그 해쉬값을 주는 입력을 알게 됩니다. 이를 막기 위해서는 해쉬 계산 한 번에 시간이 많이 걸리게 하면 됩니다. 생일이라고 하면, 지난 100년간의 생일은 대강 36500개가 있으므로, 이런 종류의 공격을 위해서는 해쉬함수를 36500번 계산해 보면 됩니다. 해쉬 함수 한 번의 계산이 매우 오래 걸린다고 하면, 이러한 전수조사 공격은 쉽지 않게 되겠지요.

그리고, 해쉬함수를 느리게 만드는 방법 또한 어렵지 않습니다. 기본적인 아이디어는, 그냥 정상적인 해쉬 함수를 반복하면 됩니다. SHA-256같은 보통의 해쉬함수를 생각해 보죠. 이걸 계산한 후, 그 해쉬값의 해쉬값을 구하고, 그 해쉬값의 해쉬값을 구하는 식으로, 반복적으로 SHA-256 값을 만번 계산해본다고 합시다. 그렇게 해서 나오는 값을 우리의 새로운 해쉬함수의 값이라고 정의한다고 하죠. 이 새로운 해쉬함수는 SHA-256보다 만배 느려질 겁니다. 실제로는 이보다는 좀 더 잘 할 필요가 있을 것 같긴 한데, ... 어쨌든 대강의 아이디어는 이렇습니다. 그냥 반복하면, 느려집니다. 간단하지요. (실제로는, 이런 목적을 위해 이보다는 더 잘 설계된 느린 해쉬함수들이 있습니다.)

그래서 해쉬함수 한 번 계산하는데 1년이 걸리게 하면, 생일을 알아내는 전수조사 공격을 위해서는 36500년이 필요할 것입니다. 좋네요.

근데 이럴 수는 없습니다. 느린 해쉬함수 사용의 문제는, 정상적인 사용자들을 불편하게 하지 않는 범위 내에서만 느려질 수 있다는 것입니다. 공격자를 괴롭히다 보면, 자칫 잘못하면 사용자를 덩달아 괴롭힐 수 있습니다. 패스워드를 사용해서 사용자 인증을 하는 시스템을 개발하는데, 인증에 1년이 걸리면 곤란합니다. 1년이 아니라, 보통의 사용자들의 인내심에는 1분도 지나칩니다. 현실적으로, 해쉬함수를 느리게 만든다 해도, 한 번 계산하는데에 걸리는 시간을 아마도 몇초 이상 길게 늘리기는 쉽지 않을 겁니다. 그래서, 그냥 해쉬함수의 1회 계산에 1초 걸리게 만들 수 있다고 합시다. 아마도 이 정도가 현실적이고 합리적인 타협점일 것 같습니다.

그렇게 한다고 하면, 해쉬값이 하나 주어질 때 그에 대응되는 생일을 복구하는 데에는 최대 36,500초가 필요합니다. 10시간 8분 정도입니다.

나의 비밀 정보를 '암호화' 했는데, 공격자가 그 비밀을 알아내는데 10년도, 10개월도, 10일도 아니고, 고작 10시간이 걸린다?

이건 어떤 관점에서 보아도 좋은 암호화라고 보기 어렵습니다.

아마 주민등록번호 등은 최소한 생일보다는 더 나을 것 같긴 합니다. 가능성이 훨씬 더 많기 때문에, 이러한 전수조사가 생일보다는 훨씬 더 오래 걸릴 수 있습니다. 느린 해쉬함수의 사용으로 어쩌면 어느 정도 막아줄 수 있을 지도 모르겠습니다.

그래도, 이 생일의 예를 통해 제가 말씀드리고 싶은 것은, 개인정보는 기본적으로 저 엔트로피 데이터이고, 느린 해쉬함수의 사용에는 기본적인 한계가 있어서, 데이터 자체의 엔트로피가 낮으면 이걸 해쉬함수로 보호하기는 어렵다는 것입니다.

만일 정말로 나는 생일을 반드시 해쉬함수로만 사용해서 '암호화'해야 하겠어라고 한다면, 생일을 처리하기 위한 전용 해쉬함수를 만들어야 하겠지요. 반복 횟수를 충분히 늘려서, 예를 들어 해쉬함수 1회 계산에 하루가 걸리게 만들 수 있을 겁니다. 그러면 36,500일이 필요할 것이고, 이는 100년에 해당합니다. 100년 정도면 괜찮네요. 하지만, 대체 무슨 이유로 꼭 생일을 해쉬함수로 처리한 것인지는 모르겠지만, 정상적인 사용에 하루가 꼬박 필요하다면 뭔가 데이터 처리를 반드시 이렇게 해야만 하는 것인지 다시 생각해볼 필요가 있지 않을까요. 코인 채굴을 하는 것도 아니고...

< 사전 계산과, 솔트의 사용 >

예를 들다 보니, 생일이 예를 들기에 딱 좋은 것 같습니다. 성별은 가능성이 좀 적어서 너무 극단적이고, 패스워드는 패스워드 관리자를 사용하면 충분히 고 엔트로피 패스워드를 만들 수 있습니다. 하지만, 내 생일을 억지로 고 엔트로피 데이터로 만들 방법은 없지요.

한번 계산에 1초가 걸리는 느린 해쉬함수를 써서 생일을 처리했다고 하면, 이를 복구하는 데에는 10시간이 걸립니다. 즉, 어떤 사람의 생일에 대한 해쉬값이 h라고 한다면, 그 h에 대응되는 실제 생일을 10시간만에 알아낼 수 있습니다.

그리고, 그 사람 말고 또다른 사람의 생일에 대한 해쉬값이 h'라고 한다면, 그 h'에 대응되는 실제 생일을 10시간만에 알아낼 수 있습니다.

그런데, 조금 생각해보면 일을 이런 식으로 처리하는 것은 어리석은 일입니다. 어차피 처음에 h에 대한 생일을 복구하는 과정에서, 가능한 모든 생일에 대한 해쉬값을 계산할 필요가 있었습니다. 이 계산 결과를 그냥 버리지 말고 남겨두면, h 말고 h'에 대한 생일을 복구할 때에 같은 계산을 또 할 필요가 없어집니다.

그래서, 각각의 36500개의 생일 b 하나 하나마다, 해쉬값 h=H(b)를 계산합니다. 그 다음에, 이 해쉬값을 오름차순 정렬해서 그 결과를 표로 만듭니다. 해쉬 하나를 적는데, 예를 들어 512비트 출력 해쉬를 쓴다고 하면 64바이트. 생일을 적는데 보다 효율적으로 적을 수도 있겠지만 느슨하게 하면 8바이트. 즉, 생일 하나마다 72바이트가 필요합니다. 이런 일을 36500번 하므로, 데이터의 총량은 36500 곱하기 72 바이트. 2,628,000 바이트입니다. 2,628 킬로바이트. 1000이냐 1024이냐에 따라 다르겠지만, 어떻게 계산해도 3메가가 되지 않습니다. 그러고 나면, 이제 이 3메가짜리 테이블을 이용하면, 누군가의 해쉬 정보를 보자 마자 이진 탐색을 통해 거의 곧장 생일을 뽑아낼 수 있습니다. 10시간이 걸리는 것이 아니라, 1초도 채 걸리지 않을 겁니다. (너무 대충 말하는 것 같기는 한데, 1초도 채 걸리지 않는다고 했지만 아마 실제는 1초보다는 1/1000초라든가 그런 정말 작은 시간에 더 가까울 거에요.) 10시간짜리 공격도 문제가 많지만, 해쉬값에 대응되는 생일을 순식간에 뽑아내는 공격은 더 치명적입니다.

물론, 이 공격에 쓰이는 계산의 총량이 '1초도 안 걸리는' 것은 아닙니다. 처음 한 번은 10시간 정도 계산을 해야 하니까요. 이러한 계산을 '사전 계산(precomputation)'이라고 합니다. 이렇게 사전 계산을 한 결과를 정리해두면, 실제 본격적인 공격이 필요할 때, 즉, 어떤 해쉬값이 구체적으로 h라고 주어지고 h=H(m)을 만족하는 메시지 m을 알아내야 할 때, 매우 적은 양의 계산 만으로 m을 찾아낼 수 있게 됩니다.

'솔트(salt)'는 이러한 사전 계산을 막아줄 수 있습니다. 어떤 메시지 m에 대한 해쉬값을 계산할 때, 메시지 m만 사용해서 h=H(m)이라고 계산하는 것이 아니라, 어떤 랜덤한 값 s를 고른 뒤에, s와 m을 함께 사용해서 h=H(s, m)을 계산합니다. 그리고, (h, s)를 같이 저장해 둡니다. 나중에 m이 주어지면, 이 m이 맞는 값인지 확인하기 위해 저장된 s를 통해 H(s, m)을 계산하고, 그것이 저장된 h와 맞는지 봅니다.

먼저 확인할 것은, 솔트는 전수조사 공격을 막아주지 못한다는 것입니다. 어떤 해쉬값 h와 솔트 s가 주어졌다고 합시다. 그리고 거기에 대응되는 생일 m을 알아내고 싶습니다. 그러기 위해서는, 공격자는 가능한 모든 생일들 m마다 H(s, m)을 계산해서, 그 결과를 h와 맞춰보면 됩니다. 이 작업을 위해서는 최대 36500번의 해쉬 계산이 필요합니다. 솔트가 없을 때와 다르지 않습니다. 10시간을 돌리면 생일을 알아낼 수 있습니다.

하지만, 여기서 중요한 것은, 이 해쉬 h와 솔트 s를 공격하기 위해 공격자가 10시간동안 계산한 것들은, 다른 해쉬 h'과 솔트 s'을 공격하는 데에 도움이 되지 않는다는 것입니다: 다른 사람의 생일을 저장할 때에는 그 솔트 s가 아니라 랜덤하게 다른 솔트 s'이 쓰였을 것이고, 10시간동안 계산하면서 이 특정 솔트 s를 기준으로 가능한 모든 m에 대해 해쉬값 h들을 계산했다고 해도, 다른 솔트를 위해서는 이 계산이 쓸모가 없으므로 다시 해야죠. 그러니, 계산 결과를 남겨두는 것도 의미가 없습니다.

그래서, 솔트가 없는 상황에서는 사전 계산이 가능하므로 공격자가 10시간동안 딱 한번만 열심히 계산하고, 그 결과를 3메가짜리 테이블로 남겨두기만 하면, 그 다음에는 해쉬가 보이자 마자 거의 즉각적으로 대응되는 생일을 뽑아낼 수 있게 됩니다. 그에 비해, 솔트가 도입되면, 공격자가 더 이상 이런 짓을 할 수는 없게 되지만, 그럼에도 불구하고 여전히 공격해야 할 해쉬가 나타나면 10시간동안 열심히 계산을 하기만 하면 생일을 찾아낼 수 있습니다. 압도적으로 치명적인 공격을 피할 수 있는 것은 맞는데, 그렇다고 딱히 안전하다고 할 수도 없는 상황이죠. 마치, 거열형은 피할 수 있게 되었으니 이제 기쁜 마음으로 교수형을 당하면 되겠다... 같은 느낌입니다.

이러한 사전 계산 공격의 유일한 문제는, 사전 계산에 걸리는 시간과, 사전 계산의 결과물의 크기입니다. 생일의 경우에는 36500가지밖에 되지 않는다고 할 수 있으므로, 사전 계산에 걸리는 시간이나 결과물의 크기가 다 충분히 작았습니다. 그런데, 보다 엔트로피가 높은 데이터의 경우에는 사전 계산도 많이 걸릴 수 있고, 사전 계산의 결과물의 크기도 3메가가 아니라 너무 클 수도 있습니다. 아마 전화번호 정도까지는 꽤 괜찮을 것 같은데, 패스워드는 원하는 만큼 엔트로피를 올릴 수 있으므로, 낮은 엔트로피의 패스워드만 공략하는 식의 공격을 시도할 수 있으나, 이 경우에도 그래도 어느 정도 복잡한 것도 공격하기 위해서는 사전 계산량도 크고, 무엇보다 그 결과물의 크기가 너무 클 수 있습니다. 3메가면 괜찮습니다만, 결과물이 3테라라면 상당히 난감하겠죠. 결과물이 3페타라면 문제이고요.

그런데, 여기에서 'time-memory tradeoff (TMTO)'라는 아이디어가 등장합니다. 우선, TMTO 역시 일종의 사전 계산 공격이고, 기본적으로 매우 큰 한번의 사전 계산이 필요하다는 것은 바뀌지 않습니다. 그리고 일반적으로 TMTO를 하기 위해서는 단순한 사전 계산에 필요한 계산보다 계산이 조금 더 걸리는 경향이 있습니다. 어쨌든, 기본 전제는, 데이터의 엔트로피가 너무 지나치게 높지는 않아서, 매우 큰 사전 계산량을 공격자가 (간신히) 감당할 수 있는 수준이라는 가정입니다. 그렇다면 공격자의 관점에서 남는 문제는, 사전 계산의 결과가 저장하기에 너무 클 수 있다는 것입니다.

TMTO 기법은, 사전 계산의 결과물의 크기를 줄이고, 대신에 실제 해쉬 h가 주어졌을 때 이를 공격하는데 드는 시간을 조금 더 늘리는 것을 가능하게 합니다. 그리고, 공격 시간과 사전 계산 결과물의 크기 사이에는 타협이 가능합니다. 생일의 경우를 다시 생각해 보면, 타협의 양 극단에는 a) 사전 계산의 결과물로 아무 것도 남기지 않고, 대신 해쉬 하나를 깰 때마다 10시간씩 공격을 하는 공격, 그리고 b) 사전 계산의 결과물로 모든 생일에 대한 해쉬값들을 다 기록한 표를 남기고, 깨야 되는 해쉬가 있으면 곧장 이진 탐색으로 이 표에서 답을 읽어내는 공격, 이 둘이 있습니다. 그런데 TMTO는 그 중간에도 다양한 타협점을 제시할 수 있습니다. 예를 들어 3메가짜리 결과물을 다 남기는 것이 아니라, 계산을 통해 결과물을 1메가로 줄이고, 대신에 실제로 깨야 하는 해쉬값 h가 주어지면 그냥 단순한 테이블 룩업이 아니라 좀 더 복잡한 계산을 통해 생일을 알아내는 공격도 가능합니다. 실제로 계산한 게 아니라 그냥 대충 예를 들기 위해 숫자를 지어내 보자면, 사전 계산의 결과물은 3메가가 아니라 1메가인데, 해쉬 하나를 깨기 위해 10시간이나 아니라 1분이 걸리는 그런 타협점도 있을 수 있을 겁니다.

생일의 경우에는 너무 엔트로피가 작아서, 사전 계산 결과를 그냥 죄다 저장해도 아무런 문제가 없기 때문에 TMTO가 그다지 의미가 없습니다만, 엔트로피가 좀 더 큰 경우라면 그래도 의미가 있을 수 있습니다. 예를 들어, 어떤 데이터를 해쉬값으로부터 복구하기 위해 1년이 걸린다고 합시다. 이런 경우, 정말 대단히 중요한 데이터가 아니라면, 한 사람을 공격하기 위해 1년동안 이런 계산 자원을 투입하는 것이 합리적이지 않은 결정일 수 있을 겁니다. 그런데, 사전 계산을 1년쯤 해서, 한 사람을 공격하는 것이 아니라 모든 사람의 데이터를 즉각적으로 공격할 수 있다면? 그 정도면 훨씬 합리적인 해볼만한 일이 될 수도 있습니다. 근데 그러한 사전 계산의 결과물이 너무 커서 저장하기 버거운 수준이라면? 이 경우 TMTO는 공격자에게 적절한 해법을 제공할 수 있습니다.

보통 TMTO의 구체적인 기법으로 레인보우 테이블 등이 쓰입니다. 하지만 이건 말하자면 기술적인 디테일이고, 꼭 레인보우 테이블만이 TMTO의 방법인 것은 아닙니다.

솔트가 가장 힘을 발휘하는 것은, 바로 이 애매한 지점입니다. 기본적으로, TMTO를 쓰든 안 쓰든, 사전 계산 공격은 여럿에 대한 공격이고, 전수 조사 공격은 하나에 대한 공격입니다: 사전 계산을 하고 나면 아무 해쉬값이나 쉽게 깰 수 있습니다. 그에 비해 단순한 전수 조사 공격은 해쉬값이 하나 주어지면 그 해쉬값을 깹니다. 그리고, 사전 계산에 드는 계산량은 대강 전수조사 한번에 드는 계산량보다 좀 더 큰 수준이라고 간주할 수 있습니다. 편의상, 사전 계산에 드는 계산량과 전수조사에 드는 계산량이 동일하다고 하기로 하지요. 솔트가 없으면, 사전 계산을 통해 여럿을 동시에 깰 수 있습니다. 그에 비해 솔트가 있으면, 사전 계산은 어려우니 남는 것은 전수조사입니다. 즉, 여럿을 동시에 깰 수는 없지만 개별 해쉬를 깰 수는 있습니다.

생일의 경우, 전수조사에 드는 시간 자체가 워낙 작기 때문에, 솔트가 있어봤자 그 결과를 안전하다고 말하기 어렵습니다. 어쨌든 개별 해쉬값은 10시간만에 깨지니까요.

그에 비해, 예를 들어 전수조사에 드는 시간이 1년이라고 하면, 솔트가 없다면 대강 비슷한 시간을 사전 계산에 할애해서 모든 해쉬를 필요할 때마다 금방금방 깨는 것이 가능해집니다. 하지만, 이 경우 솔트가 도입되면, 사전 계산이 불가능해지니, 깨야 하는 구체적인 해쉬값이 주어질 때에 그때부터 1년동안 열심히 계산을 해서 해쉬값을 깰 수 있습니다. 그리고 그 계산은 재사용될 수 없고요. 공격자 쪽에서 의사결정을 한다고 할 때에, 이런 상황은 충분히 공격을 포기할 수 있는 상황입니다. 이런 경우에는 솔트의 유무가 공격자를 포기시킬 것인지 아닌지를 결정하는 중요한 요소가 됩니다.

마지막으로, 충분한 고엔트로피 데이터의 경우라면, 예를 들어 전수조사에 드는 시간이 30년이라고 하면, 역시 솔트가 큰 의미가 없게 됩니다. 솔트가 없으면 사전 계산을 할 수 있겠습니다만, 전수조사가 30년이면 사전 계산도 최소 30년인데, 굳이 그러고 싶지 않을 테니까요. 여전히, 솔트가 없는 것보다는 그래도 있는 것이 낫기는 할 것 같습니다.

여기까지 이야기를 보면, 개인정보와 패스워드가 좀 성격이 다른 면이 있는 것 같습니다. 패스워드는 선택이 가능한 정보입니다. 전통적으로 암기해야 하는 데이터이고, 그렇기 때문에 낮은 엔트로피의 패스워드가 사용되는 경향이 있습니다만, 이는 패스워드 관리자 등을 통해 얼마든지 보완이 가능합니다. 좋은 품질의 패스워드를 골라서 잘 관리하는 것은 이제 충분히 가능한 일이 되었습니다. 하지만, 다른 한편으로 여전히 좋은 패스워드와 나쁜 패스워드가 현실에서는 함께 쓰이는 것도 사실이고요. 좋은 패스워드는 해쉬함수로 잘 보호가 됩니다. 한편, 나쁜 패스워드도 여전히 쓰이고, 공격자는 어차피 고엔트로피 패스워드에 대한 공격을 포기하고, 자신이 도달할 수 있는 범위 내에서 최대한 많은 패스워드들을 공략하려고 시도할 것이므로, 솔트를 사용하면 이에 대한 어느 정도의 보완이 됩니다.

그에 비해, 개인 정보는, 많은 경우 선택이 불가능합니다. 내 생일은 바뀌지 않습니다. 그리고 보통은 그냥 엔트로피가 많이 낮고요. 그러니 전수조사에 필요한 시간 자체가 적게 걸리는 편입니다. 그런 경우라면, 여전히 솔트는 없는 것보다는 낫겠지만, 솔트가 있다고 해서 대단히 많이 안전해지는 것은 또 아닙니다.

< TL; DR >

- 개인정보 중 상당수는 선택과 변경이 불가능한 낮은 엔트로피의 데이터로, 솔트를 사용하든 사용하지 않든 해쉬함수로 그 기밀성을 보호하기 어렵습니다. 느린 해쉬함수를 이용하면 공격을 완화시킬 수 있으나, 본질적인 해결책은 아닙니다.

- 패스워드는 기밀성이 보호되어야 하고 매칭이 되어야 하므로, 해쉬함수의 사용을 고려해볼 수 있습니다. 개인정보와는 달리, 패스워드는 (특히 패스워드 관리자를 사용하면) 얼마든지 높은 엔트로피를 갖도록 선택될 수 있으므로, 해쉬함수를 사용해서 어느 정도 안전하게 보호될 수 있습니다. 다만, 여전히 패스워드의 처리를 위해서는 느린 해쉬함수의 사용이 바람직하고, 또한 현실에서는 고품질의 패스워드 뿐만 아니라 나쁜 패스워드들도 함께 사용되므로, 이에 대한 최대한의 보호를 위해서는 솔트를 같이 쓰는 것이 바람직합니다.

- 솔트는 언제나 없는 것보다는 있는 것이 낫지만, 사전 계산 공격을 막아줄 뿐이지 전수 조사 공격을 막아주지는 못합니다. SHA-256으로 전화번호를 해쉬 처리했다면, 솔트를 사용했다고해서 이 방식이 갑자기 안전해지는 것은 아닙니다.