암호학에서 “해시(hash)”는, 입력 데이터가 조금만 달라져도 출력이 완전히 달라지는, 일방향 함수다. 이렇게 민감한 변화 덕분에 해시는 무결성 검증이나 데이터 위변조 감지 등의 용도로 널리 사용된다. 하지만 만약 입력값의 경우의 수가 유한하고 미리 알 수 있다면, 해시를 단순 비교만으로는 안전하지 않을 수 있다. 이럴 때 사용되는 것이 바로 Rainbow table 기법이다.
해시 함수의 기본 성질
해시는 보통 다음과 같은 성질을 가진다:
- 입력이 단 한 비트만 달라져도 출력 전체가 크게 바뀐다 (눈사태 효과, avalanche effect)
- 같은 입력은 같은 해시를 내보낸다 (결정적)
- 그러나 해시만 보고 원래 입력을 되찾는 것은 계산상 어렵다 (단방향 함수)
이 특성 덕분에, 해시는 파일 무결성 검증, 비밀번호 저장 및 검증, 디지털 포렌식 등 여러 곳에 사용된다.
Rainbow table 이란?
하지만 “입력의 경우의 수가 유한”하고 “가능한 모든 입력을 사전에 해시값과 함께 계산해 두는 것”이 가능하다면,
나중에 해시값만 보고도 원래 입력을 되찾을 수 있다. 바로 이 아이디어가 Rainbow table 이다.
- Rainbow table은 사전에 가능한 입력 전체 또는 상당수를 해시 → 대응하는 원문(plaintext)을 계산해 저장한 것
- 그래서 나중에 “해시값 → 원문” 역추적이 매우 빠르게 진행됩니다 (해시 계산 대신 단순 조회)
즉, Rainbow table은 시간(time) vs 저장공간(memory)의 절충(time–memory trade-off) 형태의 공격 방법이다.
순수 브루트포스(bruteforce, 모든 입력을 바로 해싱)는 시간이 오래 걸리는 반면, Rainbow table은 미리 계산해 둔 덕분에 해시 → 원문 변환이 매우 빠르다.
Rainbow table의 동작 원리 (단순 hash table 과의 차이)
일반 해시 테이블 방식이라면 “모든 가능한 입력 → 해시값”을 저장하면 되지만, 가능한 입력의 수가 크면 테이블의 크기가 엄청 커질 수 있다.
Rainbow table은 이 문제를 완화하기 위해 해시 체인(hash chain) + 축약 함수(reduction function) 방식을 사용한다.
- 무작위 또는 체계적인 시작 문자열(plaintext)에서 해시 함수를 적용
- 나온 해시값을 “축약 함수(R)”로 변환하여 다시 plaintext-형태로 변환
- 이 과정을 여러 번 반복하여 하나의 “체인(chain)”을 만든 후,
- 체인의 첫번째 plaintext와 마지막 hash만 저장
- 다양한 시작 지점을 여러 체인으로 만들어 놓고,
- 나중에 해시값이 주어지면 이 체인들을 역추적하여 원문을 찾음
이 방식 덕분에 “모든 (plaintext, hash) 쌍 저장” 방식보다 저장 공간을 훨씬 줄이면서, 브루트포스보다는 훨씬 빠르게 해시 역추적이 가능해진다.
Rainbow table이 갖는 한계 / 방어 방법
하지만 Rainbow table 방식에도 여러 한계와, 방어 수단이 존재한다:
- Rainbow table은 특정 해시 함수로 생성된 테이블이므로, 테이블이 MD5용이면 MD5로 해시된 것만 노릴 수 있다. 다른 해시 알고리즘이면 준비된 rainbow table은 무용지물이 되고 만다.
- 또, 만약 비밀번호 저장 시 salt를 도입한다면 (즉, 동일한 비밀번호도 각 사용자마다 다른 salt로 해싱), Rainbow table은 통하지 않는다 — salt가 다르면 해시도 다르기 때문.
- 그리고 가능한 입력의 길이/복잡성이 커지면, Rainbow table을 만들기 위한 계산량과 저장공간이 비현실적으로 커지는 한계가 존재한다.
이러한 이유로, 오늘날 많은 시스템은 salt + 느린 해시 함수 또는 키 스트레칭(key-stretching) 방식(예: bcrypt, Argon2)을 사용해 Rainbow table 공격을 방어한다.
Rainbow table을 이용한 카카오톡 패턴락 bruteforce 예제
안드로이드의 패턴락 및 카카오톡의 패런락은 사용자의 입력을 내부적으로 해시를 통해 저장하는데, 패턴락을 입력할 수 있는 경우의 수가 유한하기 때문에, 모든 경우의 수에 대한 패턴락을 미리 계산해 놓으면 추후 증거물에서 저장된 해시값을 데이터베이스의 키로 사용하여 원래의 패턴을 찾아낼 수 있다.
아래 화면은 카카오톡의 패턴락 입력 화면인데 좌측 상단부터 9개의 흰 점이 각각1, 2, 3, …, 7, 8, 9의 값을 가진다고 가정하자.
1에서 다음으로 이동할 수 있는 경우는 { 2, 4, 5 }. 2에서는 { 1, 3, 4, 5, 6 } 이런 식으로 나누어 볼 수 있는데 이것을 정리해 보면 다음과 같은 자료구조로 표현이 가능하다. (이후 코드는 ruby)
위의 코드에서 키 ‘0’은 사용자가 패턴을 시작하는 첫 지점, 즉 아홉 개의 점에서 어떤 점에서도 선택을 할 수 있다는 것을 표시하고 나머지 1 ~ 9의 경우는 각 점에서 이동할 수 있는 인접한 점(8-neighbor)을 표시한다.
이 데이터를 기반으로 ‘backtracking’을 해서 사용자가 입력가능한 모든 패턴의 경우를 나열하고 이 데이터를 기반으로 레인보우 테이블을 구성하여, 실제 증거물에서 발견된 해시를 기반으로 원래 패턴을 찾아낸다. 레인보우 테이블 구성을 위한 ‘backtracking’ 코드는 다음과 같다.
