PBKDF2

PBKDF2 는 사람이 외운 비밀번호를 기계가 쓸 키로 바꿔 줍니다. 바꾸는 계산을 몇 번 되풀이할지는 밖에서 정해 넣습니다. 그래서 값 하나를 만드는 비용을 원하는 만큼 키웁니다. 비밀번호를 저장할 값으로 바꿀 때도, 비밀번호로 파일을 잠글 키를 만들 때도 같은 함수를 씁니다.

상세

PBKDF2 는 Password-Based Key Derivation Function 2 를 줄인 이름입니다. 비밀번호에서 키를 뽑아내는 함수를 키 유도 함수라고 부릅니다. 이 함수가 그중 하나입니다. 이름 끝의 2 는 같은 목적으로 먼저 나왔던 함수의 뒤를 이었다는 뜻입니다.

이 절은 먼저 비밀번호를 키로 바로 쓰지 못하는 까닭을 봅니다. 그다음 이 함수가 무엇을 받아 무엇을 내놓는지를 봅니다. 이어서 값을 만들 때 안에서 도는 계산과 원하는 길이를 채우는 방법을 봅니다. 마지막은 반복 횟수를 정하는 기준, 이 함수가 요즘 장비에 약한 까닭, 그리고 어디에 쓰고 어디에 안 쓰는지입니다.

키의 조건과 비밀번호의 한계

파일을 잠그거나 통신을 암호화하는 데 쓰는 암호화 키는 길이가 정해진 바이트 덩이입니다. 그리고 그 안의 바이트는 무엇이 올지 짐작할 수 없어야 합니다.

사람이 외우는 비밀번호는 둘 다 못 맞춥니다. 길이가 제각각입니다. 쓰는 글자도 몇 종류 안 됩니다. 게다가 사람이 고르는 문자열은 몇몇 후보에 몰려 있습니다.

몰려 있다는 것이 특히 아픕니다. 후보를 하나씩 대입해 보며 맞을 때까지 훑는 것을 무차별 대입 공격이라고 합니다. 비밀번호 앞에서는 이 방법이 잘 먹힙니다.

가능한 문자열을 남김없이 훑을 필요도 없습니다. 사람들이 자주 고르는 문자열을 모은 목록만 대 봐도 적지 않게 맞습니다. 그렇게 목록을 놓고 훑는 것이 사전 공격입니다.

그래서 비밀번호를 키로 쓰려면 두 가지가 필요합니다. 길이와 모양을 키에 맞게 바꿔 주는 일, 그리고 후보 하나를 대 보는 비용을 키우는 일입니다. 뒤엣것처럼 일부러 계산을 무겁게 만드는 장치를 키 스트레칭이라고 부릅니다. PBKDF2 는 이 둘을 한 함수 안에서 합니다.

입력과 출력

PBKDF2 가 받는 것은 넷입니다.

넷 중에 솔트만 성격이 다릅니다. 숨기는 값이 아니라 사람마다 다르게 뽑는 값입니다. 만들어 낸 결과 옆에 저장해 둡니다. 다음에 같은 값을 다시 만들 때 꺼내 씁니다.

사람마다 다르니 같은 비밀번호를 쓰는 두 사람도 서로 다른 결과를 남깁니다. 흔한 비밀번호의 계산 결과를 미리 표로 만들어 두는 레인보우 테이블도 못 쓰게 됩니다. 표를 솔트마다 따로 만들어야 하기 때문입니다. 그러면 미리 만들어 두는 이득이 사라집니다.

내놓는 것은 하나입니다. 유도 키 길이만큼의 바이트 덩이입니다. 이 값을 유도 키라고 부릅니다.

같은 입력 넷을 넣으면 언제나 같은 값이 나옵니다. 되돌리는 계산은 마련되어 있지 않습니다.

아래는 같은 입력으로 두 번 불러 본 것입니다. 반복 횟수 10 만은 예시로 든 숫자입니다. 몇으로 둘지 정하는 법은 뒤의 「반복 횟수를 정하는 일」에서 봅니다.

dk  = pbkdf2(pw, salt, iters=100_000, dklen=32)
dk2 = pbkdf2(pw, salt, iters=100_000, dklen=32)
len(dk)     # 32 — 유도 키 길이
dk == dk2   # 맞다 — 같은 값이 다시 나온다

유도 키 길이가 곧 결과의 길이입니다. 안쪽에서 쓰는 함수가 내놓는 길이와 상관없이 원하는 만큼 받을 수 있습니다. 이것이 이 함수의 쓸모 하나입니다.

블록 하나를 만드는 반복

안쪽에서 도는 것은 유사난수 함수 하나입니다. 키와 데이터를 받아 짐작할 수 없는 값을 내놓는 함수를 그렇게 부릅니다. PBKDF2 는 이 함수를 갈아 끼울 수 있게 두었습니다.

여기에는 흔히 HMAC(Hash-based Message Authentication Code, 해시 기반 메시지 인증 코드)을 넣어 씁니다. HMAC 은 해시 함수에 키를 끼워 쓰는 방식입니다. 키와 데이터를 받는 이 함수 모양에 그대로 들어맞습니다.

첫 번째 되풀이는 비밀번호를 키로, 솔트를 데이터로 삼아 값을 하나 만듭니다. 두 번째부터는 앞에서 나온 값을 데이터로 넣어 같은 계산을 다시 합니다. 이렇게 반복 횟수만큼 값이 줄줄이 나옵니다.

마지막 값만 쓰지는 않습니다. 되풀이하며 나온 값을 전부 XOR(exclusive or, 배타적 논리합)로 겹쳐 하나로 만듭니다. 비트마다 두 값이 다르면 1, 같으면 0 을 남기는 연산입니다.

전부 겹치는 까닭은 되풀이가 도중에 제자리를 돌더라도 결과가 무너지지 않게 하려는 것입니다. 앞에서 나온 값이 어쩌다 뒤에서 다시 나오면 그 뒤로는 같은 값만 되풀이됩니다. 마지막 값만 쓰면 그 구간이 남김없이 헛일이 됩니다. 전부 겹쳐 두면 앞의 값들이 결과에 남습니다.

이 과정을 한 번 끝내면 값이 하나 나옵니다. 이것을 블록이라고 부릅니다. 블록의 길이는 안쪽에서 쓰는 함수가 내놓는 길이와 같습니다.

flowchart TD
    A["1회 · 비밀번호와 솔트를 유사난수 함수로 계산"] --> B["2회 · 앞의 결과를 유사난수 함수로 계산"]
    B --> C["3회 · 앞의 결과를 유사난수 함수로 계산"]
    C --> D["… 반복 횟수까지"]
    A --> X["나온 값을 전부 XOR 로 겹친다"]
    B --> X
    C --> X
    D --> X
    X --> T["블록 하나"]

그림에서 볼 것은 값 하나에서 화살표가 둘씩 나간다는 점입니다. 한쪽은 다음 되풀이로 넘어갑니다. 다른 한쪽은 겹치는 데로 갑니다. 넘어가는 갈래가 비용을 만듭니다. 겹치는 갈래가 결과를 만듭니다.

블록을 이어 붙이는 규칙

블록 하나의 길이는 정해져 있습니다. 유도 키 길이가 그보다 길면 블록을 여러 개 만들어 이어 붙입니다.

블록마다 첫 되풀이에 넣는 데이터가 달라야 합니다. 그래서 솔트 뒤에 몇 번째 블록인지를 나타내는 번호를 붙여 넣습니다. 번호가 다르니 블록마다 다른 값이 나옵니다.

아래 그림은 블록 두 개를 만들어 이어 붙이는 경우입니다.

flowchart TD
    subgraph S1["블록 1"]
        A1["솔트 + 번호 1"] --> B1["1회 → 2회 → … → 반복 횟수까지"]
        B1 --> X1["나온 값을 전부 XOR 로 겹친다"]
    end
    subgraph S2["블록 2"]
        A2["솔트 + 번호 2"] --> B2["1회 → 2회 → … → 반복 횟수까지"]
        B2 --> X2["나온 값을 전부 XOR 로 겹친다"]
    end
    X1 --> E["이어 붙여 앞에서 유도 키 길이만큼 자른다"]
    X2 --> E

여기서 볼 것은 둘입니다. 블록마다 머리에 들어가는 번호가 다르다는 것, 그리고 블록 하나하나가 앞 그림의 되풀이 사슬을 처음부터 다시 돈다는 것입니다.

마지막 블록은 대개 남습니다. 필요한 만큼만 앞에서 잘라 씁니다. 나머지는 버립니다.

블록을 늘리는 데는 비용이 붙습니다. 블록 하나마다 반복 횟수만큼의 되풀이를 처음부터 다시 돌아야 하기 때문입니다. 유도 키 길이를 두 배로 늘리면 계산량도 대략 두 배가 됩니다.

정리하면 계산량은 반복 횟수와 블록 수를 곱한 만큼입니다. 반면 쓰는 메모리는 그 둘과 무관하게 일정합니다. 어느 순간에도 값 몇 개만 들고 있으면 되기 때문입니다.

반복 횟수를 정하는 일

반복 횟수는 이 함수에서 사람이 손으로 정하는 유일한 비용 손잡이입니다. 올리면 공격자가 후보 하나를 대 보는 데 드는 시간이 그만큼 늘어납니다.

서버의 시간도 같은 만큼 늘어납니다. 로그인할 때마다 서버가 같은 계산을 합니다. 이 숫자는 곧 로그인 응답 시간이자 서버 용량입니다.

그래서 고르는 기준은 서버가 감당할 응답 시간입니다. 감당할 시간을 먼저 정합니다. 그 시간을 채우는 횟수가 몇인지는 서비스가 실제로 도는 장비에서 재어 정합니다. 장비가 좋아지면 이 숫자를 올려 따라갑니다.

반복 횟수도 솔트와 함께 결과 옆에 적어 둡니다. 숫자를 나중에 올리더라도 예전 값을 만들 때 쓴 조건을 알아야 그 값을 검증할 수 있습니다.

비밀번호를 저장하는 쓰임에서는 결과 옆에 셋이 나란히 남습니다.

block-beta
columns 3
  a["솔트"] b["반복 횟수"] c["유도 키"]

병렬 장비에 약한 까닭

PBKDF2 가 쓰는 메모리는 아주 작습니다. 계산 한 번(계산 단위 하나)이 차지하는 공간이 거의 없다는 뜻입니다.

공격자에게는 이것이 이득입니다. 그래픽 카드나 전용 칩은 같은 계산을 수천 개씩 동시에 돌립니다. 거기서는 그 공간이 몇 개를 밀어 넣을 수 있는지를 정합니다. 공간을 안 쓰면 그만큼 많이 들어갑니다.

방어하는 쪽은 일반 장비에서 한 번씩 계산합니다. 양쪽이 같은 반복 횟수를 돌아도 공격자가 같은 시간에 처리하는 후보 수가 훨씬 많습니다. 반복 횟수를 올려 양쪽 비용을 같이 키워도 이 격차는 남습니다.

뒤에 나온 bcrypt · scrypt · Argon2 는 이 격차를 메우려고 일부러 메모리를 쓰게 만들었습니다. 계산 단위마다 메모리를 요구하면 병렬 장비에 밀어 넣을 수 있는 수가 줄어듭니다. 이런 성질을 가진 함수를 메모리 하드 함수라고 부릅니다.

같은 장비에 무엇이 몇 개 들어가는지를 견주면 이렇습니다.

flowchart TD
    subgraph G1["같은 장비 · PBKDF2"]
        p1["계산 단위"]
        p2["계산 단위"]
        p3["계산 단위"]
        p4["계산 단위"]
        p5["계산 단위"]
        p6["계산 단위"]
    end
    subgraph G2["같은 장비 · 메모리를 쓰는 함수"]
        m1["계산 단위 + 메모리"]
        m2["계산 단위 + 메모리"]
    end

여기서 볼 것은 칸 하나의 크기가 들어가는 개수를 정한다는 점입니다. 칸 수는 견줌을 보이려고 대표만 그린 것입니다.

쓰는 곳과 안 쓰는 곳

가르는 기준은 하나입니다. 사람이 고른 비밀번호가 입력에 들어 있느냐입니다. 안 들어 있으면 되풀이로 비용을 키울 까닭이 없습니다. 아래는 그 기준을 쓰임마다 대 본 것입니다.

기준에 안 걸리는 쓰임에 이 함수를 넣으면 늘어난 비용을 서버 혼자 치릅니다. 막아 주는 것은 없습니다.

관련 항목

PBKDF2 가 속하는 상위 분류

키 유도 함수 · 비밀번호 해싱 · 키 스트레칭 · 해시 함수 · 암호학적 해시 함수

PBKDF2 를 대신할 수 있는 다른 함수

bcrypt · scrypt · Argon2 · Argon2id · yescrypt · Balloon · 메모리 하드 함수

PBKDF2 가 입력으로 받는 값

솔트 · 페퍼 · 반복 횟수 · 유도 키 길이 · 비밀번호

PBKDF2 안에서 도는 계산

HMAC · 유사난수 함수 · XOR · 해시 · 메시지 인증 코드

PBKDF2 가 비용을 키워 막으려는 공격

무차별 대입 공격 · 사전 공격 · 레인보우 테이블 · 크리덴셜 스터핑 · 타이밍 공격

PBKDF2 의 계산 비용을 좌우하는 장비

GPU · ASIC · FPGA · CPU · 병렬 처리

PBKDF2 로 만든 키를 쓰는 제품과 규격

디스크 암호화 · 비밀번호 관리자 · WPA2 · 암호화 키 · 키 래핑

PBKDF2 값으로 사람을 들여보내는 절차

인증 · 인증과 인가 · 세션 · 비밀번호 재설정 · 다중 인증