레인보우 테이블

레인보우 테이블은 해시값을 보고 원래 값을 되찾아 줍니다. 되찾을 때마다 후보를 하나씩 넣어 보는 계산을 미리 한 번만 해 두고 그 결과를 재사용합니다. 계산 결과를 전부 적어 두면 저장 공간이 감당이 안 되므로 계산 과정의 양 끝만 남기고 가운데는 버립니다. 그래서 공간은 크게 줄고 찾을 때 계산이 조금 듭니다.

상세

이 절은 레인보우 테이블이 무엇을 줄이려고 나온 물건인지부터 봅니다. 그다음 값을 줄로 잇는 방법, 그 줄에서 원래 값을 되찾는 방법, 줄끼리 겹칠 때 생기는 문제를 차례로 봅니다.

예는 영소문자와 숫자로 된 짧은 비밀번호로 듭니다. 마지막에는 이 표가 언제 듣고 언제 안 듣는지를 정리합니다.

해시는 되돌릴 수 없다

해시 함수는 어떤 데이터든 받아 정해진 길이의 값 하나로 바꿉니다. 그 결과값을 해시값이라고 부릅니다. 같은 입력을 넣으면 언제나 같은 해시값이 나옵니다.

거꾸로는 안 됩니다. 해시값만 보고 원래 입력을 계산해 내는 방법이 없도록 만든 것이 해시 함수이고, 이 성질을 역상 저항성이라고 부릅니다. 그래서 서비스는 비밀번호를 그대로 저장하지 않고 해시값으로 바꿔 저장합니다. 이 관행을 비밀번호 해싱이라고 부릅니다.

계산으로 못 되돌린다고 해서 못 알아내는 것은 아닙니다. 후보 비밀번호를 하나씩 해시해 보고 값이 맞는지 견주면 됩니다. 이렇게 후보를 전부 넣어 보는 것을 무차별 대입 공격, 흔한 비밀번호 목록만 넣어 보는 것을 사전 공격이라고 부릅니다.

이 견주기는 털린 데이터를 손에 쥐고 자기 컴퓨터에서 합니다. 서비스가 로그인 시도 횟수를 막아도 소용이 없습니다. 이런 상황을 오프라인 공격이라고 부릅니다.

미리 다 적어 두면 되지 않나

후보를 넣어 보는 계산은 해시값마다 처음부터 되풀이됩니다. 해시값이 백만 개면 같은 계산을 백만 번 합니다. 그러면 계산을 한 번만 해 두고 결과를 적어 두자는 생각이 자연스럽게 나옵니다.

후보마다 해시값을 구해 두고 해시값 순으로 정렬해 두면 찾기는 조회 한 번으로 끝납니다. 문제는 적어 둘 양입니다.

영소문자와 숫자로 여덟 글자를 만드는 방법은 36의 8제곱, 대략 2조 8천억 가지입니다. 한 줄에 40바이트만 잡아도 100테라바이트가 넘습니다. 개인이 들고 다닐 수 있는 크기가 아닙니다.

그래서 공간을 줄이는 쪽으로 방향이 바뀝니다. 미리 계산한 것을 다 들고 있지 않고 일부만 들고 있다가 필요할 때 나머지를 다시 만드는 것입니다. 공간을 줄인 만큼 찾을 때 계산이 늘어나는 이 맞바꿈을 시간-기억 맞바꿈이라고 부릅니다.

값을 줄로 잇는다

줄이는 열쇠는 해시값을 다시 비밀번호 후보로 되돌리는 규칙입니다. 이 규칙을 축약 함수라고 부르고, 영어로는 reduction function 입니다.

축약 함수는 해시 함수의 역함수가 아닙니다. 원래 입력을 찾아 주지 않고, 그저 해시값 하나를 받아 비밀번호 후보 하나를 뱉을 뿐입니다. 아무 규칙이나 되지만 결과가 후보 범위 안에 떨어져야 합니다.

아래는 해시값을 수로 읽고 여섯 글자 후보로 옮기는 축약 함수의 뼈대입니다. to_chars 는 수 하나를 여섯 글자 문자열로 바꾸는 함수라고 치겠습니다.

def reduce(h, step):
    n = int(h, 16) + step       # 열마다 다르게
    return to_chars(n % 36**6)  # 여섯 글자 후보

step 이 왜 섞여 있는지는 아래 「줄이 겹치면 생기는 일」에서 풉니다. 지금은 후보 하나가 나온다는 것만 보면 됩니다.

해시 함수와 축약 함수를 번갈아 걸면 값이 줄줄이 이어집니다. 후보에서 해시값이 나오고, 그 해시값에서 다음 후보가 나오고, 다시 해시값이 나옵니다. 이렇게 이어진 값 줄을 해시 체인이라고 부릅니다.

flowchart TD
    P0["시작 값"] --> H0["해시 함수"]
    H0 --> D0["해시값"]
    D0 --> R1["축약 함수 · 1열"]
    R1 --> P1["둘째 값"]
    P1 --> H1["해시 함수"]
    H1 --> D1["해시값"]
    D1 --> R2["축약 함수 · 2열"]
    R2 --> P2["끝 값"]

체인에서 값이 놓이는 순서 번호를 열이라고 부르겠습니다. 위 그림의 시작 값이 1열, 둘째 값이 2열, 끝 값이 3열입니다.

표에 남기는 것은 시작 값과 끝 값 두 개뿐입니다. 가운데 값들은 버립니다. 체인 길이를 1,000 으로 잡으면 남길 줄이 1,000분의 1 로 줄어듭니다.

버린 값들은 없어진 것이 아닙니다. 시작 값과 두 함수만 있으면 언제든 같은 순서로 다시 만들어 낼 수 있습니다. 표는 그 다시 만드는 재료만 들고 있는 셈입니다.

버린 가운데를 되살려 찾는다

찾으려는 해시값이 있다고 해 봅니다. 그 값이 어느 체인의 몇 번째에 있었는지는 모릅니다. 마지막 열에 있었다고 가정하고 시작해 한 열씩 앞으로 가정을 옮기는 것이 찾는 방법입니다.

먼저 찾으려는 해시값에 축약 함수를 걸어 후보 하나를 얻습니다. 그 후보가 표의 끝 값 목록에 있으면 그 체인이 답을 품고 있을 수 있습니다. 없으면 해시 함수와 축약 함수를 한 번 더 걸고 다시 견줍니다.

끝 값이 맞으면 그 줄의 시작 값을 표에서 꺼내 처음부터 다시 돌립니다. 돌리는 중에 찾던 해시값이 나오면, 그 해시값을 만든 바로 앞의 값이 원래 비밀번호입니다.

flowchart TD
    A["찾으려는 해시값"] --> B["축약 함수를 걸어 후보를 얻는다"]
    B --> C{"그 후보가 끝 값 목록에 있나"}
    C -->|없다| E["해시와 축약을 한 번 더 건다"]
    E --> C
    C -->|있다| D["그 줄을 시작 값부터 다시 돌린다"]
    D --> F{"돌리는 중에 찾던 해시값이 나오나"}
    F -->|나온다| G["바로 앞의 값이 답이다"]
    F -->|안 나온다| E

끝 값이 맞았는데 그 체인 안에 찾던 해시값이 없는 경우가 있습니다. 다른 값이 흘러들어 같은 끝 값에 도착했기 때문입니다. 이것을 거짓 경보라고 부르고, 영어로는 false alarm 입니다. 거짓 경보는 체인을 한 번 다시 돌린 만큼의 계산을 버리게 만듭니다.

줄이 겹치면 생기는 일

서로 다른 두 체인이 도중에 같은 값을 만나는 일이 있습니다. 축약 함수가 후보 범위 안으로 값을 눌러 담으니 다른 해시값이 같은 후보로 떨어질 수 있고, 해시 충돌로 같은 해시값이 나올 수도 있습니다.

축약 함수를 체인 내내 하나만 쓰면 이 만남이 병합으로 이어집니다. 같은 값을 만난 다음부터 두 체인은 완전히 같은 값을 밟습니다. 표에는 두 줄이 있는데 덮는 후보는 한 줄치입니다.

레인보우 테이블은 열마다 다른 축약 함수를 씁니다. 첫 열에서 둘째 열로 갈 때 쓰는 함수와 둘째 열에서 셋째 열로 갈 때 쓰는 함수가 다릅니다. 앞서 본 reduce 의 step 이 그 열 번호입니다.

그러면 두 체인이 같은 값을 만나도 열이 다르면 다음 열에서 다시 갈라집니다. 병합은 같은 값을 같은 열에서 만날 때만 일어나고, 그 확률은 훨씬 낮습니다.

flowchart TD
    subgraph one["축약 함수가 하나일 때"]
        A1["체인 가"] --> X1["같은 값을 만난다"]
        B1["체인 나"] --> X1
        X1 --> Y1["뒤가 완전히 같아진다"]
    end
    subgraph many["열마다 축약 함수가 다를 때"]
        A2["체인 가 · 3열"] --> X2["같은 값을 만난다"]
        B2["체인 나 · 5열"] --> X2
        X2 --> Y2["다음 열이 달라 갈라진다"]
    end

열마다 다른 축약 함수를 그림으로 그릴 때 열마다 다른 색을 칠한 데서 레인보우라는 이름이 나왔습니다. 축약 함수를 하나만 쓰는 이전 방식은 헬만 테이블이라고 부릅니다.

무엇을 얼마나 맞바꾸나

후보 수를 N, 체인 길이를 t 라고 두고 세 방법을 나란히 놓아 봅니다.

찾는 계산이 t의 제곱인 까닭은 두 겹으로 돌기 때문입니다. 가정을 한 칸씩 옮기는 데 최대 t번이 들고, 끝 값이 맞을 때마다 그 체인을 최대 t열까지 되돌립니다.

미리 드는 계산은 전수 계산 한 번치와 같습니다. 그래서 해시값 하나만 되돌릴 생각이라면 표를 만들 이유가 없습니다. 같은 조건의 해시값을 여러 번 되돌릴 때부터 미리 든 계산이 회수됩니다.

표가 후보 전부를 덮지는 못합니다. 병합과 겹침 때문에 어떤 후보는 어느 체인에도 안 들어갑니다. 체인을 더 많이 만들면 비율은 올라가지만 저장하는 줄 수도 같이 올라갑니다.

언제 듣고 언제 안 듣나

표 하나는 세 가지에 묶여 있습니다. 어떤 해시 함수로 만들었는지, 어떤 글자 종류를 후보로 삼았는지, 몇 글자까지 덮는지입니다. 셋 중 하나만 달라도 그 표는 안 듣습니다.

가장 널리 쓰이는 대비책이 솔트입니다. 사용자마다 다른 무작위 값을 비밀번호에 붙여 함께 해시하고, 그 값을 해시값 옆에 같이 저장합니다.

솔트를 붙이면 같은 비밀번호라도 사용자마다 해시값이 달라집니다. 공격자는 솔트 값마다 표를 따로 만들어야 하고, 솔트가 충분히 길면 그 경우의 수가 감당할 수 없게 많아집니다. 미리 만들어 둔다는 전제 자체가 무너집니다.

다른 대비책은 해시 한 번에 드는 시간을 일부러 늘리는 것입니다. 같은 해시를 수만 번 되풀이하거나 메모리를 많이 쓰게 해서 한 번 계산에 드는 비용을 올립니다. 이 방법을 키 스트레칭이라고 부릅니다.

관련 항목

레인보우 테이블을 이루는 구성 요소

해시 함수 · 해시값 · 축약 함수 · 해시 체인 · 시작 값 · 끝 값

이 표가 되돌리려는 대상

해시 · 비밀번호 해싱 · 역상 저항성 · 일방향 함수 · 다이제스트

같은 목적을 두고 겨루는 다른 공격 수단

무차별 대입 공격 · 사전 공격 · 오프라인 공격 · 크리덴셜 스터핑 · 해시 크래킹

이 표를 무력하게 만드는 방어 수단

솔트 · 페퍼 · 키 스트레칭 · bcrypt · Argon2 · PBKDF2 · scrypt

이 표가 주로 노리는 해시 함수

MD5 · SHA-1 · SHA-256 · NTLM · LM 해시

이 표에 앞선 방식과 이웃한 기법

헬만 테이블 · 시간-기억 맞바꿈 · 룩업 테이블 · 메모이제이션 · 전처리

표를 만들고 찾을 때 걸리는 현상

해시 충돌 · 거짓 경보 · 체인 병합 · 생일 문제 · 비둘기집 원리

레인보우 테이블이 속하는 상위 분류

자료구조 · 암호학 · 암호 분석 · 보안 엔지니어링 · 비밀번호 크래킹