🔐 [클래식] A Future-Adaptable Password Scheme — 비밀번호 해시는 하드웨어와 함께 늙는다

논문 정보

한 줄 요약 — '비밀번호의 길이와 무작위성은 고정인데, 공격자의 컴퓨터는 매년 빨라진다. 그렇다면 해시 함수의 비용도 함께 올라가야 한다'

사용자가 고르는 비밀번호의 엔트로피는 시간이 지나도 거의 늘지 않는다. 반면 하드웨어는 꾸준히 빨라진다. 1976년 UNIX의 crypt(3)는 비밀번호를 DES 한 번(DES 상수를 25회 반복)으로 해시했고, 당시엔 그것으로 충분했다 — 1977년 VAX-11/780에서 초당 3.6회밖에 계산하지 못했으니 사전 공격이 비현실적이었다. 그런데 20여 년 뒤, 같은 알고리즘이 초당 수십만 회 계산되면서 그 '충분함'은 사라졌다. 이 논문(1999)은 그 비대칭을 정면으로 다룬다 — 비밀번호 해시의 계산 비용은 하드웨어가 빨라지는 만큼 스스로 올라가야 한다. 그리고 그 첫 구현이 바로 bcrypt다. 요령은 단순하다: 해시의 반복 횟수를 조절 가능한 '비용(cost)' 파라미터로 노출하고, 검증할 때마다 그 비용을 지불하게 만든다. 하드웨어가 2배 빨라지면 비용을 1만큼 올리면 된다. 논문이 1999년에 남긴 문장은 지금 읽으면 소름 돋는다 — "이 알고리즘들은 비밀번호 기반 시스템이 하드웨어 개선에 적응해 앞으로 20년 동안 안전하게 남게 해줄 것이다." 그리고 27년이 지난 2026년에도 bcrypt는 현역이다.

"비밀번호 스킴의 보안은 사용자가 고르는 비밀번호만큼만 좋다(as good as the passwords users choose) … 따라서 어떤 안전한 비밀번호 스킴이든, 그 계산 비용은 하드웨어 성능이 향상됨에 따라 반드시 증가해야 한다." — 논문 3·7절

배경 — '전통 crypt'가 실패할 수밖에 없었던 이유

• 전통 crypt(3)(1976)는 당시 하드웨어에 묶여 있었다: 최대 8자 비밀번호를 DES 키(56비트, 각 문자의 하위 7비트)로 사용하고, 64비트 상수 "0"을 25회 DES 암호화했다. 입력 공간도 반복 횟수도 고정이다. 안전성이 "그 순간의 컴퓨터 속도"에 못 박혀 있다는 뜻이다.
• 솔트가 12비트뿐: 4,096가지. 같은 비밀번호라도 4,096가지 암호문이 되지만, 공간이 작아 서로 다른 사용자가 같은 솔트를 받는 충돌이 흔하다. 출력은 12비트 솔트 + 64비트 암호문 = 76비트 → 13글자 ASCII.
• 그때는 정말 안전했다: 1976년엔 crypt가 "초당 4개 미만"이었고, 1977년 VAX-11/780에서도 3.6회/초였다. 사전 전체를 훑는 것이 불가능했다.
• 20년 뒤 뒤집혔다: 1998년 EFF DES 크래커는 56비트 DES 키를 56시간에 찾았고(초당 약 88×10⁹ 키), 그와 비슷한 기계면 전통 crypt를 22일에 브루트포스할 수 있었다. "가장 빠른 Alpha 프로세서에서 875년" 걸리던 것을 말이다.
• MD5 crypt도 같은 병: FreeBSD의 Poul-Henning Kamp가 만든 MD5 crypt는 더 긴 비밀번호와 12~48비트 솔트를 허용했지만, 역시 고정 비용이라 하드웨어가 빨라지면 함께 약해진다. → "고정 비용 함수는 반드시 무너진다"가 이 논문의 출발점이다.

핵심 1 — 좋은 비밀번호 스킴의 세 가지 조건 (논문 3절)

• 두 번째 역상 저항(second preimage-resistance): 해시값이 주어졌을 때 다른 비밀번호를 찾는 일이, 비밀번호 자체를 추측하는 일만큼 어려워야 한다. 논문은 이를 형식화해 "비밀번호 스킴은 사용자가 고른 비밀번호만큼만 좋다"는 명제로 못 박는다.
• 충분히 큰 솔트 공간: 미리 계산한 룩업 테이블(레인보우 테이블의 원형)을 무력화한다. 솔트는 해시 출력에 영향을 주는 두 번째 입력으로, 같은 비밀번호가 매번 다른 해시를 갖게 만든다.
• 적응 비용(adaptable cost): 고정 비용 함수를 '더 비싼 함수'로 갈아치우는 것은 시스템을 매번 깨뜨린다. 대신 하나의 함수 안에 비용 파라미터를 두어, 호환성을 깨지 않고 비용만 올릴 수 있어야 한다.
• 논문의 핵심 공식: 비용(=반복 횟수)의 최적값은 하드웨어 성능에 반비례한다 → 하드웨어가 빨라질 때마다 올려야 한다. "무어의 법칙에 맞춘 보안"이라는 발상이 여기서 처음 구체화됐다.

핵심 2 — eksblowfish: '일부러 비싼' 키 스케줄

• 기반은 Bruce Schneier의 Blowfish: 64비트 블록, 16라운드 Feistel 네트워크. F 함수는 F(a,b,c,d) = ((S1[a] ⊞ S2[b]) ⊕ S3[c]) ⊞ S4[d] — 4개의 256×32비트 S박스를 쓴다.
• eksblowfish = "expensive key schedule blowfish": 암호화 과정은 Blowfish와 완전히 동일하다. 다른 것은 오직 키 스케줄(비밀번호+솔트를 서브키·S박스로 확장하는 단계)을 일부러 비싸게 만든 것뿐이다.
• EksBlowfishSetup(cost, salt, key): InitState(π 상수로 상태 채움) → ExpandKey(state, salt, key) → 이후 2^cost번 반복 { ExpandKey(state, 0, salt); ExpandKey(state, 0, key) }. 즉 비용 파라미터가 반복 횟수를 지수적으로(2^cost) 조절한다 — cost 6이면 64회, cost 8이면 256회.
• 솔트 128비트, 키(비밀번호) 최대 56바이트(Blowfish 최대 키 448비트).
• 설계 의도 — 'HW 파이프라인' 봉쇄: 4KB에 달하는 S박스를 매 반복마다 다시 쓰기 때문에, 전용 하드웨어의 파이프라이닝과 비트슬라이싱(bit-slicing)이 사실상 불가능하다. 논문 표현대로 "아직 알려지지 않은 최적화"의 여지를 줄이려는 것이다.

핵심 3 — bcrypt: 192비트 '마법값'을 64번 암호화한다

• bcrypt는 eksblowfish를 해시로 감싼 것이다. 128비트 솔트와 192비트 마법값(magic value)을 사용한다.
• 그 마법값의 문자열: "OrpheanBeholderScryDoubt" — 24바이트 = 정확히 192비트다. bcrypt는 이 고정 문자열을 암호화한다.
• 1단계(비싼 부분): EksBlowfishSetup(cost, salt, pwd)로 키 스케줄 상태를 초기화. 계산 시간의 대부분이 여기서 소비된다.
• 2단계(반복): 그 상태로 192비트 마법값을 ECB 모드로 64번 반복 암호화. 출력은 cost + 128비트 솔트 + 암호문을 이어붙인 값이다 — cost와 솔트가 함께 인코딩되므로 검증 시 그대로 재현된다.
• 버전 접두: 한 비밀번호 파일에 여러 스킴이 공존하도록, bcrypt 출력은 $2a$(후대 $2b$, $2y$)로, MD5 crypt는 $1$로 시작한다. 전통 crypt 출력은 $로 시작하지 않아 충돌이 없다.
• 기본 비용: 논문 게재 당시 일반 사용자 cost 6, 관리자(root) cost 8. bcrypt는 OpenBSD 2.1부터 기본 비밀번호 스킴이다. 비밀번호 최대 55바이트.

핵심 4 — 공격자 관점: 전통 crypt·MD5 crypt를 뚫는 다섯 갈래 (논문 6절)

• ① 사전 공격(dictionary attack): 사용자는 예측 가능한 비밀번호("Susan1", "neme$i$"처럼 이름+숫자)를 고른다. 해시가 빠르면 사전 한 부가 곧 열쇠가 된다. → bcrypt는 비용을 '정당한 사용자가 견딜 수 있는 한계까지' 높여 사전 공격을 비현실적으로 만든다.
• ② 솔트 충돌(salt collision): 전통 crypt는 솔트가 4,096개뿐이라 충돌이 다발한다. 공격자는 같은 솔트끼리 묶어 후보를 솔트당 한 번만 해시하는 최적화를 얻는다. 15,000개 엔트리 파일에서 솔트가 유일하려면 2⁴¹ 공간이 필요한데, 2¹²면 약 3,991개만, 2²⁴면 14,994개만 유일하다. bcrypt의 128비트 솔트는 이 문제를 원천 제거한다.
• ③ 미리 계산(precompute): 전통 crypt는 "사전 단어 전부 × 가능한 12비트 솔트"가 9GB 하드디스크 한 대에 들어간다. QCrack은 출력을 1바이트로 줄여 Webster 사전(1934판, 8자 절단·중복 제거 후 171,395개)을 670MB에 담았다. bcrypt는 솔트 공간이 커서 '솔트당 1비트'조차 저장이 불가능하다.
• ④ 알고리즘 최적화(비트슬라이싱): Biham의 비트슬라이스 DES는 300MHz Alpha 8400에서 137Mb/s로, libdes(28Mb/s)보다 약 5배 빨랐다. John the Ripper는 MD5 crypt의 핵심 루프를 단순화해 대폭 가속했다. 하지만 bcrypt는 S박스가 매번 바뀌어 비트슬라이싱이 통하지 않는다.
• ⑤ 하드웨어 발전: 1977년 3.6회/초 → 1998년 EFF DES 크래커까지. 고정 라운드 함수는 하드웨어가 빨라지는 만큼 자동으로 약해진다. bcrypt는 사용자가 비용을 올려 이 추세에 맞서는 유일한 방향을 제공한다.

핵심 5 — 1999년의 예언은 왜 2026년에도 유효한가

• 비용 파라미터 하나로 '안전 수준'을 시간에 대해 고정한다: cost를 1 올리면 계산량이 2배가 되므로, 하드웨어가 빨라진 만큼 따라잡을 수 있다. 이는 '고정 비용' 함수가 가진 구조적 결함을 없앤다.
• bcrypt가 현역으로 남았다는 증거: OpenBSD 기본, PHP password_hash()의 기본(PASSWORD_BCRYPT), 수많은 웹 프레임워크와 DB. $2b$ 접두는 오늘날 거의 모든 비밀번호 덤프에서 보인다.
• 현대 부채널과의 연결: 4KB S박스를 무작위로 접근하는 구조는 캐시 타이밍 부채널의 원인이기도 하다 — 그래서 지금은 메모리-하드 함수(Argon2·scrypt)로 이어졌다. bcrypt는 그 계보의 출발점이다.
• 진짜 유산은 '사고틀'이다: "큰 솔트 + 조절 가능한 반복 비용"이라는 틀 자체. 오늘날 OWASP의 work-factor 권고(예: cost ≥ 10)는 모두 이 틀 위에 서 있다.

한계 · 유의점 · 의의

• bcrypt 자체의 한계: 55바이트 비밀번호 제한(후대 구현은 72바이트에서 절단), 4KB S박스의 캐시 부채널, 병렬 공격에 대한 별도 비용이 없는 점(메모리-하드가 아님). → Argon2·scrypt·PBKDF2 같은 현대 대안의 등장 배경이다.
• '적응형'은 알고리즘이 아니라 운영의 문제다: 비용을 올리는 것은 정책이다. 한 번 정하고 방치하면 다시 늙는다. 논문도 "비용은 때때로 재평가해야 한다"고 명시한다.
• 패러다임 전환: 이 논문은 '해시 하나 더'가 아니다. 비밀번호 보안의 변수를 '알고리즘의 비밀'에서 '시간 축에서 조절 가능한 비용'으로 재정의했다. Morris & Thompson 1979가 '솔트'를 도입했고, 이 논문이 '적응 비용'을 도입했으며, 둘이 합쳐져 오늘날의 표준이 됐다.
• 오늘의 교훈: 비밀번호 DB를 설계할 때 "무엇으로 해시할까"만 묻지 말고, "이 선택이 5년 뒤에도 충분히 비쌀까"를 함께 물어야 한다.

출처

• 논문 원문: Niels Provos & David Mazières, A Future-Adaptable Password Scheme, FREENIX Track, 1999 USENIX Annual Technical Conference — usenix.org (PDF) · static 미러
• 계보의 뿌리(참고문헌 [9]): Robert Morris & Ken Thompson, Password Security: A Case History, Communications of the ACM 22(11), 1979 — 솔트와 느린 해싱의 원형
• 함께 읽기: 2026-09-16 How to Break MD5(해시 충돌의 실제 — 이 논문이 MD5 crypt를 비판한 이후의 이야기) · 2026-10-07 Differential Power Analysis(Kocher, 부채널) · 2026-10-05 RSA 원논문 · 2026-09-30 New Directions in Cryptography(Diffie–Hellman)