107. 레인보우 테이블 (Rainbow Table)

⚠️ 이 문서는 "해시 함수는 단방향이라 안전하다"는 믿음을 비웃듯, 수천억 개의 패스워드를 미리 해시로 갈아 만든 거대한 엑셀 사전을 이용해 암호화된 DB가 털렸을 때 10초 만에 평문 패스워드를 찾아내는 무시무시한 역산 공격 기법인 '레인보우 테이블'을 다룹니다.

핵심 인사이트 (3줄 요약)

본질: 레인보우 테이블(Rainbow Table)은 해커가 무차별 대입 공격(Brute Force)을 할 때 걸리는 엄청난 계산 시간을 줄이기 위해, 자주 쓰이는 수많은 비밀번호의 **[평문 ↔ 해시값] 쌍을 특수한 체인 구조로 미리 계산하여 하드디스크에 저장해 둔 거대한 오프라인 사전(Dictionary)**이다.

가치: MD5나 SHA-1 같은 고속 해시 함수로만 비밀번호를 구워놓은 구형 데이터베이스가 통째로 해킹당했을 때, 해커가 이 테이블에 Ctrl+F 로 해시값을 검색하기만 하면 수백만 명의 비밀번호가 단 몇 분 만에 평문으로 도륙 나는 파국을 초래한다.

융합: 이 가성비 극강의 공격을 무력화하기 위해, 현대 보안 아키텍처는 비밀번호를 구울 때 사용자마다 랜덤한 쓰레기 문자를 덧붙이는 **'솔트(Salt)'**와 해시를 수만 번 반복하는 **'키 스트레칭(Key Stretching)'**을 필연적으로 융합하여 방어한다.

Ⅰ. 개요 및 탄생 배경 (Context & Necessity)

해커가 어느 웹사이트를 해킹해 users 테이블을 통째로 다운받았다. 하지만 비밀번호 컬럼에는 e10adc39... 같은 알 수 없는 쓰레기 문자(해시값)만 가득했다. 해시 함수는 역산(복호화)이 불가능하다. 과거의 해커는 해시를 풀기 위해 "a", "b", "c" 부터 "zzzz" 까지 직접 암호학적 믹서기에 넣고 갈아보며 훔쳐온 해시값과 일치하는지 하나하나 대조(무차별 대입)해야 했고, 이는 수백 년이 걸리는 바보 같은 짓이었다.

하지만 2003년 필립 외클랭(Philippe Oechslin)이 기발한 타협안을 고안해 냈다. "미리 다 갈아서 엑셀 표로 만들어두면 어떨까?" 해커들은 슈퍼컴퓨터를 1년 내내 돌려서 인류가 자주 쓰는 비밀번호 1조 개(123456, password, qwerty 등)를 미리 MD5나 SHA-1으로 다 갈아버렸다. 그리고 이 거대한 매핑 사전을 인터넷 어둠의 경로(Dark Web)에 테라바이트 단위의 파일로 공유하기 시작했다. 이것이 레인보우 테이블의 시작이다.

📢 섹션 요약 비유: 두꺼운 수학 문제집의 정답을 풀려면 1년이 걸립니다(무차별 대입). 하지만 누가 전 세계의 모든 수학 문제와 정답을 미리 계산해서 적어둔 '비밀 해답지(레인보우 테이블)'를 만들어 놨다면? 문제의 번호(해시값)만 찾으면 1초 만에 정답(평문)을 베낄 수 있게 됩니다.

Ⅱ. 레인보우 테이블의 동작 원리와 체인 구조

"그냥 [평문, 해시] 쌍을 1조 개 저장하면 엑셀 파일 용량이 수천 테라바이트(TB)가 넘어서 하드디스크가 터지지 않나요?" 맞다. 단순한 사전(Dictionary Attack) 방식은 저장 공간의 한계 때문에 실용성이 없었다. 레인보우 테이블은 이 용량 문제를 **'체인(Chain)과 환원 함수(Reduction Function)'**라는 수학적 마법으로 압축해 냈다.

1. 환원 함수 (Reduction Function, $R$)

해시 함수($H$)가 평문을 넣으면 긴 해시값을 뱉어낸다면, **환원 함수($R$)**는 그 긴 해시값을 대충 뭉개고 잘라서 다시 '짧은 평문 문자열'처럼 보이게 강제로 축소시키는 함수다. (※ 역산이 아님. 그냥 맘대로 자르는 것)

2. 체인(Chain)을 통한 극한의 압축

해커는 평문 하나를 시작점으로 잡고, [해시($H$) $\rightarrow$ 환원($R$) $\rightarrow$ 해시($H$) $\rightarrow$ 환원($R$)] 이 짓을 수만 번 반복하여 하나의 긴 쇠사슬(Chain)을 만든다.

password $\xrightarrow{H}$ 5E88 $\xrightarrow{R}$ qwerty $\xrightarrow{H}$ D41D $\xrightarrow{R}$ admin $\xrightarrow{H}$ 8C69
이 체인을 1만 번 돌리고 나서, 해커는 하드디스크에 [시작 평문: password, 최종 해시: 8C69] 이 두 개만 딱 저장한다. 중간에 지나간 1만 개의 평문-해시 데이터는 다 버려버린다(용량 압축).

3. 해킹의 순간 (검색과 복원)

DB에서 해시값 D41D를 훔쳐왔다. 해커는 이 값을 레인보우 테이블의 '최종 해시' 리스트에서 찾는다.
없으면? 훔쳐온 해시에 환원 함수($R$)와 해시($H$)를 번갈아 돌려본다. 몇 번 돌리다 보니 표에 있는 최종 해시 8C69가 나왔다!
해커의 환호: "아! 이 D41D라는 값은 저 password로 시작하는 1만 번짜리 체인 어딘가에 숨어있었구나!"
해커는 password부터 다시 체인을 돌려가며 D41D가 나오기 바로 직전의 평문을 낚아챈다. 정답은 qwerty 다.

┌───────────────────────────────────────────────────────────────────────────────────────┐
│           레인보우 테이블의 용량 압축 (Chain) 메커니즘 시각화                         │
├───────────────────────────────────────────────────────────────────────────────────────┤
│                                                                                       │
│ [ 1. 테이블 생성 단계 (오프라인에서 미리 계산) ]                                      │
│  시작점 (평문)               (1만 번 반복)               도착점 (해시)                │
│  "admin" ──▶(H)──▶(R)──▶(H)──▶ ... ──▶(H)──▶ "F9X3"                                   │
│  "12345" ──▶(H)──▶(R)──▶(H)──▶ ... ──▶(H)──▶ "Q2@8"                                   │
│                                                                                       │
│  ★ 하드디스크에는 1만 개의 징검다리를 버리고 [시작-끝] 쌍 2개만 저장! (용량 1/10000)  │
│                                                                                       │
│ [ 2. 해킹 단계 (실시간 역산) ]                                                        │
│  훔쳐온 해시 "K#1P" 를 R과 H로 계속 굴려보니 "F9X3"에 도착했다!                       │
│  -> "오호라! 이 해시는 'admin'으로 시작하는 체인 안에 숨어있구나!"                    │
│  -> 'admin'부터 다시 돌려서 진짜 평문을 뽑아냄.                                       │
└───────────────────────────────────────────────────────────────────────────────────────┘

[다이어그램 해설] 체인 방식은 컴퓨터의 '계산 시간(Time)'과 하드디스크의 '저장 공간(Space)'을 교환하는 위대한 트레이드오프(Time-Memory Trade-off)다. 해커는 수만 개의 징검다리 데이터를 버렸기 때문에 1TB짜리 하드디스크에도 수조 개의 패스워드 조합을 거뜬히 우겨넣고 다닐 수 있게 되었다.

📢 섹션 요약 비유: 해커가 지하철 노선도(체인)를 통째로 외우는 대신, 출발역과 종착역만 수첩에 1만 개 적어둡니다(용량 압축). 나중에 해킹한 역을 찾을 때, 그 역에서 몇 정거장만 더 가보니 내가 아는 '강남역(종착역)'이 나오면, 수첩을 보고 "아, 이 역은 '신도림(출발역)'에서 시작하는 2호선 라인에 있구나!" 하고 노선을 다시 타보며 정확한 원래 역(평문)을 알아내는 무서운 꼼수입니다.

Ⅲ. 파멸적 위력과 실무의 대재앙

2010년대 초반까지만 해도 네이버나 넥슨 같은 대기업조차 데이터베이스에 비밀번호를 단순 MD5(password) 로만 구워서 저장했다.

해커가 SQL 인젝션 같은 취약점으로 회원 100만 명의 ID와 비밀번호 해시 컬럼을 통째로 탈취한다.
해커는 어둠의 경로에서 500GB짜리 **'한국인 전용 MD5 레인보우 테이블'**을 다운받아 해킹 프로그램(Ophcrack 등)에 밀어 넣는다.
프로그램은 밤새도록 돌아가며, 100만 명 중 123456, qwer!@#$, 이름+생년월일 같이 흔한 패턴으로 만든 70만 명의 비밀번호 평문을 엑셀 파일로 완벽하게 뱉어낸다.
해커는 이 평문 비밀번호를 이용해 피해자들의 이메일, 은행, 게임 계정을 연쇄적으로 도용(Credential Stuffing)하며 2차 파멸을 일으킨다.

Ⅳ. 완벽한 방패: 솔트(Salt)와 키 스트레칭

레인보우 테이블을 쓰레기통에 처박는 방법은 해커가 "우리 서버만을 위한 맞춤형 테이블"을 만들기 위해 1만 년이 걸리게 만드는 것이다.

솔트 (Salt) 추가
- 사용자마다 가입할 때 16자리 랜덤 쓰레기 문자열(Salt)을 하나 뽑아서 DB에 저장해 둔다.
- 비번을 구울 때 Hash(비밀번호 + Salt) 형태로 굽는다.
- 해커가 갖고 있는 레인보우 테이블은 그냥 비밀번호만 갈아서 만든 표다. 솔트가 섞인 끔찍한 조합은 해커의 사전(Table)에 아예 존재하지 않는다! 해커는 회원 1명마다 테이블을 아예 처음부터 새로 만들어야 하므로 해킹을 포기하게 된다.
키 스트레칭 (Key Stretching)
- 해커가 화가 나서 솔트까지 섞은 테이블을 억지로 만들려 한다 쳐도, 해시를 1번만 도는 게 아니라 반복문(for)으로 10만 번씩 돌려버리게(Bcrypt, PBKDF2) 만든다.
- 해커가 테이블 1개를 만드는 데 1초가 아니라 1,000년이 걸리게 만들어 무차별 대입 공격 의지를 완전히 박살 낸다.

Ⅴ. 결론

"편리한 해시 함수는 해커에게도 편리하다." 레인보우 테이블은 '단방향 함수는 안전하다'는 개발자들의 순진한 안일함을 산산조각 낸 암호 해독학의 걸작이다. 이 무서운 오프라인 사전 공격 덕분에, 전 세계 모든 백엔드 아키텍처는 비밀번호를 저장할 때 무조건 랜덤한 짠맛(Salt)을 치고 수만 번 꼬아버리는 철칙을 강제로 몸에 새기게 되었다. 오늘날 솔트 없이 단순 해시로 비밀번호를 굽는 개발자가 있다면, 그는 회사의 명운을 해커의 엑셀 파일 하나에 내던지는 범죄자와 다름없다.

📌 관련 개념 맵

공격 대상: 솔트(Salt)가 없는 단방향 해시 함수 (MD5, SHA-1, SHA-256 등)
공격 모델 분류: 오프라인 사전 공격 (Offline Dictionary Attack), Time-Memory Trade-off
대표적인 방어 기술: Salt (소금 치기), Key Stretching (키 늘리기), Bcrypt, PBKDF2
관련 해킹 도구: Ophcrack, Hashcat

👶 어린이를 위한 3줄 비유 설명

비밀번호를 숨기는 '해시 믹서기'는 거꾸로 돌릴 수 없어서 안전한 줄 알았어요.
그런데 해커들이 전 세계 사람들이 쓸만한 비밀번호 1조 개를 미리 다 믹서기에 갈아보고, "어떤 쥬스가 어떤 과일에서 나왔는지" 전부 다 적어놓은 어마어마하게 큰 '커닝 페이퍼'를 만들어 냈죠.
이 커닝 페이퍼(레인보우 테이블)에 우리가 만든 쥬스(해시)를 대조해 보면 원래 과일(비번)이 뭔지 1초 만에 들통나버리는 엄청난 반칙 기술이랍니다!