해시한 컬럼은 되돌릴 수 없다 — SHA-256에서 HMAC, 그리고 AES까지
ISMS 심사에서 개인정보 컬럼이 걸렸다. salt 없는 SHA-256은 안전한 저장으로 안 쳐준다는 것이었다. HMAC으로 바꾸려고 열어보니 컬럼에는 다이제스트만 있고 원문이 없었다.
암호화를 붙일 때 제일 먼저 정하는 게 알고리즘인데, 정작 문제가 된 건 알고리즘이 아니라 그 결정을 되돌릴 수 있느냐였다. SHA-256으로 저장해둔 컬럼은 검색도 중복 확인도 잘 됐다. 결정론적이라 같은 번호는 항상 같은 다이제스트가 나오고 WHERE phone_hash = ?가 그대로 동작한다. 그래서 그동안 아무 문제 없이 썼는데, 그 컬럼을 다른 방식으로 바꾸라는 요구가 오자 손댈 방법이 없었다.
▍salt 없는 SHA-256이 걸린 이유
심사에서 보는 건 해시를 썼느냐가 아니라 원문으로 되돌아갈 수 있느냐다. salt가 없으면 같은 입력이 항상 같은 다이제스트로 나오니까, 그 필드가 가질 수 있는 값을 전부 계산해서 표로 만들어두면 조회 한 번에 원문이 나온다. 형식이 정해진 필드는 경우의 수가 생각보다 작다.
노트북 코어 하나로 SHA-256을 재보니 초당 223만 건이 나왔다. 이 속도로 필드별 전체 공간을 훑는 데 걸리는 시간을 계산하면 이렇게 된다.
| 필드 | 경우의 수 | 전수 계산 |
|---|---|---|
| 생년월일 (100년치) | 3.7 × 10⁴ | 16 ms |
| 한글 이름 3자 | 1.1 × 10⁶ | 0.5 초 |
전화번호 010-XXXX-XXXX | 1.0 × 10⁸ | 45 초 |
| 이메일, 주소 | 사실상 무한 | 불가 |
이름은 성 100개에 이름 두 글자를 자주 쓰는 음절 105개씩으로 잡은 값이다. 전화번호가 45초인데, 이건 노트북 코어 하나 기준이라 하한에 가깝다. 실제 공격은 GPU를 쓰고 SHA-256 해시레이트가 초당 수십억 건이라 이 표보다 서너 자릿수 빠르다.
그러니까 salt 없이 해시해서 저장한 건 원문을 감춘 게 아니라 조회 단계를 하나 더한 것에 가까웠다. 심사에서 지적한 게 정확히 이 부분이다.
▍원문이 없다는 문제
HMAC으로 옮기려면 HMAC(key, 원문)을 계산해야 하고, 그러려면 원문이 있어야 한다. 컬럼에는 다이제스트만 있다. SHA256(원문)에서 HMAC(key, 원문)으로 가는 변환은 존재하지 않는다. 기존 다이제스트에 HMAC을 한 번 더 씌우면 값이 나오기는 하지만 그건 원문의 HMAC이 아니라서, 사용자가 다음에 전화번호를 입력해도 그 값과 안 맞는다.
결국 원문을 복구하는 수밖에 없었는데, 여기서 상황이 뒤집힌다. 심사에서 지적받은 그 취약점이 유일한 복구 수단이었다. salt가 없어서 전수 계산으로 표를 만들 수 있었고, 그래서 옮길 수 있었다. salt를 제대로 넣어뒀다면 복구율이 0이고 마이그레이션 자체가 불가능했다.
복구되는 범위는 앞 표 그대로다. 전화번호와 생년월일은 전부 나왔고 자유 입력 필드는 하나도 안 나왔다. 그래서 컬럼 하나가 옮겨진 행과 안 옮겨진 행으로 갈렸다.
▍단방향과 양방향의 진짜 차이
보통 둘을 복원 가능 여부로 나누는데, 운영에서 부딪히는 차이는 그게 아니라 나중에 바꿀 수 있느냐다.
양방향으로 저장해둔 컬럼은 키만 있으면 원문이 나오니까, 나중에 HMAC으로 가든 다른 키로 재암호화하든 배치 한 번이면 끝난다. 단방향으로 저장해둔 컬럼은 원문이 없어서 어디로도 못 간다. 알고리즘을 잘못 골랐다는 걸 나중에 알아도 고칠 방법이 없다.
그래서 단방향을 고르는 건 알고리즘 선택이 아니라 이 값의 원문을 영구히 버린다는 결정이다. 비밀번호는 그래도 되는 필드라서 맞는 선택이고, 전화번호는 그러면 안 되는 필드였다.
▍lazy migration
복구 못 한 행이 남았으니 배치로 한 번에 못 옮긴다. 그래서 조회 경로를 두 겹으로 만들고, 원문이 들어오는 순간에 갱신하는 방식으로 갔다. 배치 대신 접근할 때 옮긴다고 해서 lazy migration이라고 부른다.
async function findByPhone(input: string) {
// ① 이미 옮겨진 행
const row = await db.user.findFirst({
where: { phone_hash: hmacSha256(indexKey, input) },
});
if (row) return row;
// ② 아직 안 옮겨진 행은 옛 다이제스트로 한 번 더 찾는다
const legacy = await db.user.findFirst({
where: { phone_hash: sha256(input) },
});
if (!legacy) return null;
// 원문이 들어온 김에 갱신한다
await db.user.update({
where: { id: legacy.id },
data: { phone_hash: hmacSha256(indexKey, input) },
});
return legacy;
}조회가 두 번 나가는 건 아직 안 옮겨진 행에서만이라 부담이 크지 않다. 문제는 다른 데 있다. 끝나는 시점이 없다. 원문이 다시 들어오지 않는 행은 그대로 남는다. 탈퇴하지 않은 채 몇 년째 로그인하지 않는 계정이 그렇다.
그래서 이 방식에는 마감이 같이 붙어야 한다. 남은 행 수를 지표로 뽑아두고 옛 경로를 언제 닫을지 정해두지 않으면, 조회 코드에 분기가 영구히 남는다.
비밀번호 해시를 올릴 때 쓰는 silent rehash가 기전이 똑같다. 로그인에 성공하면 그 김에 새 알고리즘으로 다시 해시해서 덮어쓰는 방식인데, 원문이 들어오는 순간에만 옮길 수 있다는 제약까지 같다. Symfony의 password migration이나 PHP의 password_needs_rehash()가 이걸 프레임워크 차원에서 지원한다.
▍세 방식의 공존
나중에 이 필드는 암호화를 안 해도 될 수 있다는 얘기가 나왔다. 그러면 양방향으로 바꾸게 되는데, 지금 옮기는 중인 컬럼에 세 세대가 겹친다.
| 세대 | 값 | 상태 |
|---|---|---|
| 1세대 | SHA256(원문) | 아직 안 옮겨진 행 |
| 2세대 | HMAC(key, 원문) | 지금 옮기는 중 |
| 3세대 | AES(dek, 원문) | 갈 수도 있는 방향 |
컬럼 값만 봐서는 어느 세대인지 알 수 없다. 그래서 값에 세대 표시를 붙여둔다.
v1:9f86d081884c7d65...
v2:c1e3672da5da19b9...
v3:073036ee2e1f28cc...접두어 세 글자면 조회 코드가 분기를 정확히 태울 수 있고, 1세대를 걷어낼 때 남은 행을 세는 것도 WHERE phone_hash LIKE 'v1:%' 하나로 끝난다. 처음부터 붙여뒀으면 이 절이 필요 없었다.
여기서 중요한 건 v2가 헛수고가 아니라는 점이다. 양방향으로 가더라도 HMAC 컬럼은 버려지지 않는다. 아래 나오는 이유로, 양방향으로 저장하면서 검색까지 하려면 HMAC 컬럼이 반드시 다시 필요해진다.
▍양방향으로 바꿀 때의 검색 문제
양방향으로 옮기면 마이그레이션 문제는 영구히 사라진다. 대신 지금 잘 되던 게 하나 안 되기 시작한다.
AES-GCM은 암호화할 때마다 새 IV를 만들어 쓴다. 같은 평문을 세 번 넣어도 결과가 세 번 다 다르다.
AES-256-GCM (랜덤 IV) 3회
073036ee2e1f28ccacfa9571c016fd6c88f0b9b56bacf779...
b8c187d321d4468c605782066d8504f925d27cb04149740c...
72d03c86a044276a50ecf9064a7f8a727d5567cfd3d656a2...
HMAC-SHA256 3회
c1e3672da5da19b98e4b94364b07eb2804e77d8f660db573...
c1e3672da5da19b98e4b94364b07eb2804e77d8f660db573...
c1e3672da5da19b98e4b94364b07eb2804e77d8f660db573...이건 결함이 아니라 AES-GCM이 보장하려는 성질이다. 암호문이 매번 달라야 컬럼을 통째로 떠가도 어느 행과 어느 행이 같은 값인지 알 수 없다. 그리고 정확히 이 성질 때문에 WHERE phone = ?가 성립하지 않는다. SHA-256 컬럼에서 아무 문제 없이 되던 조회가 안 되는 것이다.
그러면 IV를 고정하면 되지 않을까 싶은데, 검색은 실제로 된다. 대신 평문도 같이 풀린다.
왜 그렇게 되는지는 AES가 실제로 하는 일을 보면 알 수 있다. AES-GCM은 평문을 직접 뒤섞지 않는다. 키와 IV로 평문 길이만큼의 난수열을 만들어서 평문과 XOR 하는 게 전부다. 이 난수열을 키스트림이라고 부른다.
XOR에는 성질이 하나 있는데, 이 절의 내용이 전부 여기서 나온다. 같은 값을 두 번 XOR 하면 지워진다.
9 XOR 5 XOR 5 = 9복호화가 되는 이유가 이것이다. 암호문에 같은 키스트림을 한 번 더 XOR 하면 키스트림이 지워지고 평문만 남는다.
암호화 c = p XOR KS
복호화 c XOR KS = p XOR KS XOR KS = p문제는 IV를 고정했을 때다. 키스트림은 키와 IV로 만드는데 키는 원래 고정이니까, IV까지 고정하면 모든 행이 같은 키스트림 하나를 쓰게 된다. 그러면 암호문 두 개를 XOR 하는 것만으로 같은 일이 일어난다. 아래에서 KS가 지워지는 지점을 볼 수 있다.
복호화할 때 키스트림을 걷어내는 것과 정확히 같은 일이, 암호문 두 개를 나란히 놓는 것만으로 일어나는 것이다. 키를 한 번도 쓰지 않았다는 게 중요하다. 실제로 돌려보면 두 값이 그대로 맞는다.
same plaintext -> same ciphertext : true
c1 XOR c2 = 000000080a04020002040a
p1 XOR p2 = 000000080a04020002040a첫 줄이 검색이 된다는 뜻이고, 아래 두 줄이 그 대가다.
그래서 실제 공격은 이렇게 된다. 자기 번호로 계정을 하나 만들면 p1을 알게 되고, DB에서 자기 행의 c1과 대상의 c2를 꺼내 마지막 단계의 계산을 돌리면 남의 번호가 나온다.
p2 recovered = 01098765432
p2 actual = 01098765432키가 전혀 필요 없고 DB 덤프와 자기 계정 하나만 있으면 된다. 이 상태로 심사를 받으면 salt 없는 SHA-256보다 나쁜 지적을 받는다.
전부 가져와서 앱에서 복호화해 거르는 방법도 있다. 10만 행 복호화가 131밀리초로 끝나서 될 것 같아 보이는데, 실제로는 인덱스, UNIQUE 제약, 네트워크 비용, 메모리에 올라오는 평문을 한꺼번에 포기하는 방법이다. O(log n) 조회가 O(n) 풀스캔이 되고, 중복 확인을 DB 제약으로 못 걸게 된다.
▍이중 컬럼 구성
그래서 복원용 컬럼과 검색용 컬럼을 따로 둔다. 두 컬럼의 요구 조건이 정반대라서 하나로 합칠 수가 없다. 저장 컬럼은 같은 평문이 매번 다른 값이어야 하고, 검색 컬럼은 같은 평문이 항상 같은 값이어야 한다.
CREATE TABLE "user" (
id uuid PRIMARY KEY,
phone bytea NOT NULL, -- AES-256-GCM. 양방향. 원문 복원용
phone_bidx bytea NOT NULL -- HMAC-SHA256. 단방향. 검색용
);
CREATE INDEX user_phone_bidx_idx ON "user" (phone_bidx);
ALTER TABLE "user" ADD CONSTRAINT user_phone_bidx_key UNIQUE (phone_bidx);지금 옮기고 있는 HMAC 컬럼이 그대로 phone_bidx 자리에 들어간다. 양방향으로 가더라도 새로 만드는 건 AES 컬럼 하나뿐이라, 2세대 마이그레이션은 3세대로 갈 때 버려지는 작업이 아니다.
조회할 때는 단방향 컬럼으로 행을 찾고, 양방향 컬럼에서 원문을 꺼낸다.
const row = await db.user.findFirst({
where: { phone_bidx: hmacSha256(indexKey, "01012345678") },
});
const plain = row ? aesGcmDecrypt(dek, row.phone) : null;WHERE, JOIN, UNIQUE는 전부 bidx 컬럼에 걸고, AES 컬럼은 이미 찾은 행에서 원문을 꺼낼 때만 쓴다.
결정론적 AES를 써서 컬럼 하나로 끝내면 되지 않을까 싶은데, 속도 때문은 아니다. 둘 다 마이크로초 단위라 차이가 없다.
| 알고리즘 | 건당 |
|---|---|
| HMAC-SHA256 | 0.963 µs |
| AES-256-GCM (랜덤 IV) | 2.066 µs |
인덱스 컬럼을 복원 불가능하게 두는 것이 목적이다. 결정론적 암호문도 암호문이라 키가 있으면 평문이 나오고, 그 컬럼에 인덱스를 걸면 백업, 리드 리플리카, 인덱스 덤프에 평문의 두 번째 사본이 그대로 들어간다. 게다가 암호문이 곧 인덱스면 DEK를 회전할 때마다 B-tree를 다시 만들어야 한다.
▍bidx에 남는 노출
단방향이라고 해서 동일성까지 가려지는 것은 아니다. 결정론적이니까 같은 번호는 항상 같은 다이제스트가 되고, 그것을 확인하는 데는 역산이 필요 없다.
SELECT phone_bidx, COUNT(*) FROM "user" GROUP BY phone_bidx HAVING COUNT(*) > 1;심사에서 다시 물어볼 수 있는 지점이라 미리 정리해뒀다. 동일성을 가리려면 다이제스트를 잘라서 충돌을 일부러 만들어야 하는데, 얼마나 잘라야 하는지가 직관과 어긋난다. 서로 다른 전화번호 10만 개를 넣고 세어봤다.
| 남긴 비트 | bucket 수 | 평균 후보 | 최대 후보 | 유일한 값 |
|---|---|---|---|---|
| 256 (자르지 않음) | 100,000 | 1.00 | 1 | 100.0% |
| 32 | 99,999 | 1.00 | 2 | 100.0% |
| 24 | 99,729 | 1.00 | 2 | 99.5% |
| 20 | 95,407 | 1.05 | 4 | 91.0% |
| 16 | 51,326 | 1.95 | 9 | 21.7% |
| 12 | 4,096 | 24.41 | 47 | 0.0% |
| 8 | 256 | 390.63 | 451 | 0.0% |
4바이트인 32비트까지 잘라도 10만 행이 전부 유일하게 남는다. 실제로 가려지기 시작하는 구간은 12비트에서 16비트 사이다. 그런데 자른 bidx에는 UNIQUE를 걸 수 없다. 충돌을 일부러 만든 컬럼이라 제약을 걸면 멀쩡히 다른 번호를 넣는 가입이 막힌다.
| 자르는 정도 | 동일성 은닉 | DB UNIQUE | 조회당 복호화 |
|---|---|---|---|
| 자르지 않음 (32B) | 안 됨 | 가능 | 1건 |
| 24~32비트 | 거의 안 됨 | 가능하나 충돌 시 오탐 | 1~2건 |
| 12~16비트 | 됨 | 불가 | 2~24건 |
셋을 다 가질 수는 없어서, 전화번호 중복 가입 검사가 목적이면 자르지 않고 UNIQUE를 택하는 편이 낫다. 이 번호가 이미 있다고 응답하는 순간 동일성은 애플리케이션이 알려주는 정보가 되니까, 인덱스에서 가려봐야 얻는 것이 적다.
▍세 번째 질문
여기까지 겪고 나서 필드를 볼 때 묻는 순서가 바뀌었다. 원래는 두 가지를 물었다.
- 원문을 다시 읽어야 하는가. 아니면 단방향으로 끝낼 수 있다.
- 그 값으로 검색해야 하는가. 그러면 결정론적인 컬럼이 하나 필요하다.
여기에 세 번째가 붙었다. 이 결정이 나중에 바뀔 수 있는가. 법이 바뀌거나 심사 기준이 바뀌거나 요구사항이 바뀌면 저장 방식을 바꿔야 하는데, 바뀔 여지가 조금이라도 있으면 단방향 단독은 위험하다. 원문을 버리는 순간 그 뒤의 선택지가 같이 사라진다.
비밀번호만 이 질문에서 자유롭다. 어떤 기준이 와도 비밀번호를 복원할 일은 생기지 않으니까 bcrypt나 Argon2로 끝내면 된다. 나머지 개인정보는 전부 세 번째 질문에 걸린다.
▍마무리
정리하면 이렇다.
- salt 없는 SHA-256은 원문을 감춘 게 아니다. 전화번호 전체 공간이 노트북 코어 하나로 45초고, GPU면 서너 자릿수 빠르다.
- 단방향으로 저장하면 나중에 방식을 바꿀 수 없다. 알고리즘 선택이 아니라 원문을 버리는 결정이다.
- 이번에 옮길 수 있었던 건 salt가 없었기 때문이다. 제대로 저장했다면 복구율이 0이었다.
- 한 번에 못 옮기면 lazy migration으로 가되, 남은 행 수를 지표로 잡고 옛 경로를 닫을 시점을 정해둔다.
- 값에 세대 접두어를 붙여두면 세 방식이 공존해도 조회 코드가 분기를 정확히 태울 수 있다.
- 양방향으로 바꾸면 마이그레이션 문제는 사라지지만 검색이 깨진다. IV를 고정해서 풀려고 하면 키 없이 평문이 복원된다.
- 검색이 필요하면 AES 컬럼과 HMAC 컬럼을 따로 둔다. 지금 만드는 HMAC 컬럼이 그때 bidx로 그대로 쓰인다.
- 필드를 볼 때 복원과 검색에 더해 이 결정이 나중에 바뀔 수 있는지를 같이 묻는다.
처음에 SHA-256을 고른 게 틀린 판단은 아니었다. 그때 기준으로는 해시로 저장하면 안전하다는 게 상식이었고, 검색도 중복 확인도 잘 됐다. 놓친 건 알고리즘이 아니라 그 컬럼이 나중에 바뀔 수 있다는 사실이었다.
그래서 지금 컬럼 하나를 설계할 때 마지막으로 확인하는 건 성능도 알고리즘도 아니고, 이 값을 나중에 다른 방식으로 옮겨야 할 때 옮길 수 있는가다. 답이 아니오라면 그 컬럼은 지금 결정으로 영원히 간다.
측정 환경: Node v22.23.0 / OpenSSL 3.5.7, Apple Silicon, 단일 코어. SHA-256 처리량은 워밍업 20만 회 후 200만 회씩 5세트 중간값, 건당 시간은 워밍업 2만 회 후 20만 회씩 7세트 중간값, 전수 복호화는 워밍업 3회 후 7회 중간값. bucket 실측은 서로 다른 전화번호 10만 개에 HMAC-SHA256을 적용한 뒤 상위 비트만 남겨 집계.
참고
- RFC 5297 — Synthetic Initialization Vector (SIV) Authenticated Encryption
- RFC 8452 — AES-GCM-SIV: Nonce Misuse-Resistant AEAD
- NIST SP 800-38D — Recommendation for Block Cipher Modes: GCM and GMAC
- Nonce-Disrespecting Adversaries — GCM nonce 재사용 실태 조사
- CipherSweet — blind index 구현체
- How to Migrate a Password Hash — Symfony Docs
- password_needs_rehash — PHP Manual
- Password hash migration: formats, salting, and silent rehashing — WorkOS
- OWASP Password Storage Cheat Sheet
- OWASP Cryptographic Storage Cheat Sheet