정의
레인보우 테이블(Rainbow Table)은 암호학에서 사용되는 사전 계산(precomputed) 테이블로, 특정 해시 함수에 대해 가능한 입력값(예: 비밀번호)과 그 해시값 사이의 매핑을 효율적으로 저장한다. 이를 통해 대상 해시값에 대응되는 원본 입력값을 빠르게 찾아낼 수 있다. 주로 암호 해시 함수(예: MD5, SHA‑1, SHA‑256 등)의 충돌 검색 및 비밀번호 복구에 활용된다.
구조와 원리
- 체인(chain): 입력값 → 해시 함수 → 해시값 → 감소 함수(reduction function) → 새로운 입력값 형태의 연속적인 변환을 반복한다.
- 다중 감소 함수: 각 단계마다 서로 다른 감소 함수를 적용함으로써 동일한 해시값이 여러 체인에 나타날 확률을 낮춘다.
- 색깔(Rainbow) 비유: 체인마다 서로 다른 감소 함수를 사용함을 색상의 차이에 비유하여 “레인보우”라는 명칭이 붙었다.
- 테이블 저장: 각 체인의 시작점(첫 입력값)과 끝점(최종 해시값)만을 저장한다. 검색 시 대상 해시값을 체인 끝점부터 역추적해 시작점에 도달하면 원본 입력값을 재구성한다.
장점
- 사전 계산을 통해 실시간 해시 역추적 속도가 크게 향상된다.
- 동일 해시 함수를 사용하는 여러 대상에 대해 재사용 가능하다.
제한점
- 저장 용량: 대상 입력 공간이 클 경우 테이블 크기가 기하급수적으로 증가한다.
- 솔트(salt) 적용된 해시: 각 계정마다 고유한 솔트가 포함되면 레인보우 테이블이 무용지물이 된다.
- 최신 강력한 해시 알고리즘(예: Argon2, bcrypt)에서는 연산 비용이 높아 테이블 구축 자체가 비효율적이다.
사용 사례
- 보안 감시·감사: 기업·기관에서 자체 비밀번호 정책을 검증하기 위해 기존 해시를 테스트한다.
- 포렌식·디지털 수사: 침해 사고 후 유출된 해시를 분석하여 원본 비밀번호를 확인한다(법적 절차에 따라).
- 교육·연구: 암호학 교육에서 해시 역공학 원리를 설명하기 위한 예시 자료로 활용된다.
관련 용어
- 해시 함수: 입력 데이터를 고정 길이의 해시값으로 변환하는 일방향 함수.
- 감소 함수(reduction function): 해시값을 다시 입력값 형태(예: 문자열)로 변환하는 함수.
- 솔트(salt): 해시 계산 시 입력값에 추가하는 무작위 데이터로, 레인보우 테이블의 효율을 저하시킨다.
참고
- 레인보우 테이블은 2003년 Philippe Oechslin이 발표한 논문 “Making a Faster Cryptanalytic Time‑Memory Trade‑Off”에서 체계적으로 소개되었다.
- 실제 구현 예시로는 오픈소스 프로젝트 “rtgen”, “rainbowcrack” 등이 있다.
요약
레인보우 테이블은 해시 역추적을 위한 사전 계산 방식으로, 동일 해시 함수에 대해 대량의 입력값-해시값 매핑을 저장하여 비밀번호 복구 및 보안 평가에 활용된다. 다만, 솔트와 현대적인 메모리‑시간 강화 해시 함수의 도입으로 실용성이 제한되는 경우가 많다.
