해시 함수 정리: 암호화와의 차이, 비밀번호 저장, 해시 테이블
들어가며
서비스 데이터베이스가 유출됐다는 소식에 "비밀번호는 해시로 저장해 안전합니다"라는 설명이 따라오곤 합니다. 그런데 어떤 해시 함수를 어떻게 썼느냐에 따라 몇 시간 만에 뚫릴 수도, 사실상 포기하게 만들 수도 있습니다.
이번 글에서는 해시 함수의 성질과 암호화와의 차이를 정리합니다. 이어서 충돌, 비밀번호 저장 방법, 해시 테이블의 동작까지 용도별로 다룹니다.
1. 해시 함수의 성질
해시 함수는 길이에 상관없는 입력을 고정 길이 값으로 바꾸는 함수입니다. 같은 입력은 항상 같은 값이 되고, 입력이 조금만 바뀌어도 값은 크게 달라집니다.
from hashlib import sha256
sha256(b"hello").hexdigest()[:16] # 2cf24dba5fb0a30e
sha256(b"Hello").hexdigest()[:16] # 185f8db32271fe25SHA-256 같은 암호 해시는 여기에 조건이 더 붙습니다. 값에서 입력을 찾아내기 어렵고, 같은 값이 나오는 두 입력을 찾기도 어려워야 합니다. 되돌리는 키가 애초에 없다는 점이 암호화와 다릅니다.
해시는 사람에게서 찍은 지문이에요. 지문으로 사람을 만들 수는 없지만, 같은 사람인지는 알 수 있어요.
| 구분 | 키 | 되돌리기 | 주 용도 |
|---|---|---|---|
| 인코딩Base64 | 없음 | 누구나 | 전송 형식 |
| 암호화AES | 필요 | 키로 복원 | 기밀 유지 |
| 해시SHA-256 | 없음 | 불가 | 동일성 확인 |
2. 충돌과 무결성 확인
다른 입력이 같은 값이 되는 것을 충돌(collision) 이라고 합니다. 입력은 무한하고 값의 길이는 유한하므로 충돌은 반드시 존재합니다. 좋은 해시는 그것을 일부러 찾기가 사실상 불가능할 뿐입니다.
MD5와 SHA-1은 실제로 충돌을 만들 수 있어 보안 용도로는 쓰지 않습니다. 파일이 전송 중에 손상되지 않았는지 볼 때는 SHA-256 값을 대조합니다.
sha256sum release.tar.gz
# 공개된 값과 같으면 받은 내용이 같다다만 공격자가 파일과 해시를 함께 바꾸면 대조는 그대로 통과합니다. 위조까지 막으려면 비밀 키를 쓰는 HMAC이나 디지털 서명이 필요합니다.
3. 비밀번호 저장: 솔트와 느린 함수
SHA-256은 빠르게 계산하도록 설계됐습니다. 파일 확인에는 장점이지만 비밀번호 저장에는 약점입니다. GPU 한 장으로 초당 수십억 번을 대입할 수 있기 때문입니다. 값이 같으면 비밀번호도 같다는 사실이 드러나고, 미리 계산한 레인보우 테이블로 찾기도 쉽습니다.
그래서 두 가지를 더합니다. 솔트는 비밀번호마다 붙이는 임의 값으로, 같은 비밀번호도 다른 값이 되게 해서 미리 계산한 표를 쓸모없게 만듭니다. 느린 함수는 한 번 계산에 시간이 걸리도록 만들어 대입 속도를 깎습니다. bcrypt cost 12면 GPU 한 장으로 초당 천 번 안팎입니다(어림).
솔트는 지문을 찍기 전에 사람마다 다른 도장을 손에 찍는 일이에요.
같은 비밀번호도 솔트가 달라 값이 다르다.
값을 되돌리지 않고 다시 계산해 비교한다.
import bcrypt
stored = bcrypt.hashpw(password, bcrypt.gensalt(rounds=12))
# $2b$12$ 뒤에 솔트 22자와 해시 31자가 함께 들어 있다
bcrypt.checkpw(password, stored) # 저장값의 솔트로 다시 계산해 비교솔트는 비밀이 아니므로 해시 옆에 그대로 저장합니다. bcrypt의 cost는 1 올릴 때마다 계산 시간이 2배가 됩니다. 새로 만든다면 메모리까지 많이 쓰게 해 GPU 공격을 어렵게 하는 Argon2id가 많이 권장됩니다.
4. 해시 테이블
해시는 빠른 조회에도 쓰입니다. 해시 테이블은 키의 해시 값으로 저장할 칸을 바로 계산하는 자료구조입니다. 칸이 8개라면 해시 값을 8로 나눈 나머지가 칸 번호가 됩니다.
해시 테이블은 이름 첫 글자로 칸을 정하는 사물함이에요. 같은 칸이 나오면 함께 넣어요.
위 그림처럼 키가 달라도 같은 칸에 들어갈 수 있습니다. 같은 칸에 목록으로 잇는 방식을 체이닝, 다음 빈칸을 찾는 방식을 개방 주소법이라고 합니다. 파이썬 dict 는 개방 주소법을 쓰고, 자바 HashMap 은 체이닝을 쓰다가 한 칸이 길어지면 트리로 바꿉니다.
buckets = [list() for _ in range(8)]
def put(key, value):
bucket = buckets[hash(key) % len(buckets)]
for item in bucket:
if item[0] == key:
item[1] = value
return
bucket.append([key, value])평균 조회는 O(1)이지만, 한 칸에 몰리면 최악의 경우 O(n)이 됩니다. 그래서 칸이 어느 정도 차면 테이블을 키워 전부 다시 배치합니다. 값의 순서가 보존되지 않으므로 범위 조회에는 맞지 않습니다.
한눈에 비교
| 용도 | 고르는 것 | 필요한 성질 |
|---|---|---|
| 파일 손상 확인 | SHA-256 | 빠름, 충돌 저항 |
| 위조 방지 | HMAC, 디지털 서명 | 키 또는 서명 |
| 비밀번호 저장 | Argon2id, bcrypt | 솔트, 느린 계산 |
| 해시 테이블 | 언어 내장 해시 | 빠름, 고른 분포 |
헷갈리기 쉬운 점
- 해시를 암호화의 한 종류로 보는 오해. 암호화는 키로 되돌리지만 해시는 되돌리는 키가 없습니다.
- 솔트는 숨겨야 한다는 오해. 솔트의 목적은 숨기는 것이 아니라 계정마다 값을 다르게 만드는 것입니다. DB 밖에 따로 두는 비밀 값은 페퍼(pepper)라고 부릅니다.
- 해시 테이블 조회는 항상 O(1)이라는 오해. 평균이 O(1)입니다. 일부러 충돌을 일으키는 공격도 있어서, 파이썬은 문자열 해시를 프로세스마다 무작위로 바꿉니다.
면접에서 자주 받는 질문
솔트를 해시와 같은 DB에 두면 의미가 없지 않나요?
의미가 있습니다. 솔트는 미리 계산한 표를 쓰지 못하게 하고, 같은 비밀번호를 쓰는 계정이 드러나지 않게 합니다. 공격자는 계정을 하나씩 대입해야 합니다.
cost를 올리면 기존 사용자의 해시는 어떻게 바꾸나요?
평문을 모르므로 한 번에 변환할 수 없습니다. 로그인에 성공한 순간에는 평문이 있으므로, 그때 새 cost로 계산해 다시 저장합니다.
해시 테이블에서 충돌이 나면 어떻게 하나요?
같은 칸에 목록으로 잇거나 다음 빈칸을 찾습니다. 어느 방식이든 충돌이 많으면 느려지므로, 채워진 비율이 일정 수준을 넘으면 테이블을 키워 다시 배치합니다.
정리
- 해시는 입력을 고정 길이 값으로 바꾸는 단방향 함수이고, 암호화와 달리 되돌리는 키가 없습니다.
- 무결성 확인에는 빠른 SHA-256을, 비밀번호 저장에는 솔트가 들어간 느린 함수를 씁니다.
- 해시 테이블은 평균 O(1)로 찾지만 충돌 처리와 재배치 비용이 있고 범위 조회는 못 합니다.
같은 해시라도 빠른 것이 장점인 곳과 약점인 곳이 다르니, 용도부터 묻고 고릅니다.