레인보 테이블

3. 용어의 유래

"레인보 테이블"이라는 용어는 외슐린(Oechslin)의 최초 논문에서 처음 사용되었다.^[1] 이 용어는 공격의 성공률을 높이기 위해 서로 다른 축약 함수(Reduction Function)가 사용되는 방식을 나타낸다. 헬만(Hellman)의 원래 방법은 각각 다른 축약 함수를 가진 여러 개의 작은 테이블을 사용하는 반면, 레인보 테이블은 훨씬 더 크며 각 열에 서로 다른 축약 함수를 사용한다. 색상을 사용하여 축약 함수를 나타낼 때 레인보 테이블에 무지개가 나타난다.

4. 사전 계산된 해시 체인

레인보우 테이블의 기본 원리는 사전 계산된 해시 체인(Precomputed Hash Chains)에 기반한다. 해시 체인은 해시 함수(H)와 감소 함수(R)를 번갈아 적용하여 비밀번호와 해시 값의 연결 고리를 만든다. 감소 함수는 해시 값을 다시 비밀번호 공간으로 매핑하는 역할을 한다.

예를 들어 P가 소문자 알파벳 6자로 구성된 비밀번호 집합이고 해시값이 32비트 길이인 경우, 다음과 같은 체인이 만들어질 수 있다.

:$\{\backslash color\{Red\}\backslash mathtt\{aaaaaa\}\}\backslash ,\backslash xrightarrow[\backslash ;H\backslash ;]\{\}\backslash ,\backslash mathtt\{281DAF40\}\backslash ,\backslash xrightarrow[\backslash ;R\backslash ;]\{\}\backslash ,\backslash mathtt\{sgfnyd\}\backslash ,\backslash xrightarrow[\backslash ;H\backslash ;]\{\}\backslash ,\backslash mathtt\{920ECF10\}\backslash ,\backslash xrightarrow[\backslash ;R\backslash ;]\{\}\backslash ,\{\backslash color\{Violet\}\backslash mathtt\{kiebgt\}\}$

감소 함수에 대한 유일한 요구 사항은 특정 크기의 "일반 텍스트" 값을 반환할 수 있어야 한다는 것이다.^[1]

해시 체인의 각 체인은 무작위로 선택된 초기 비밀번호에서 시작하여, 해시 함수와 감소 함수를 반복 적용하여 생성된다. 각 체인의 시작점과 종료점만 저장하여 테이블의 크기를 줄인다. 위의 예시에서 "aaaaaa"는 시작점, "kiebgt"는 종료점이 되며, 중간의 비밀번호나 해시 값은 저장되지 않는다.

주어진 해시 값에 대한 비밀번호를 찾기 위해, 해시 값에 감소 함수와 해시 함수를 번갈아 적용하며 체인을 생성하고, 테이블에 저장된 종료점과 비교한다. 일치하는 종료점이 발견되면 해당 체인의 시작점부터 다시 체인을 생성하여 비밀번호를 찾는다.

예를 들어, 해시 값 920ECF10이 주어지면, 먼저 R을 적용하여 체인을 계산한다.

:$\backslash mathtt\{920ECF10\}\backslash ,\backslash xrightarrow[\backslash ;R\backslash ;]\{\}\backslash ,\{\backslash color\{Violet\}\backslash mathtt\{kiebgt\}\}$

"kiebgt"가 테이블의 종료점 중 하나이므로, 해당 시작점 "aaaaaa"를 사용하여 920ECF10에 도달할 때까지 체인을 따라간다.

:$\{\backslash color\{Red\}\backslash mathtt\{aaaaaa\}\}\backslash ,\backslash xrightarrow[\backslash ;H\backslash ;]\{\}\backslash ,\backslash mathtt\{281DAF40\}\backslash ,\backslash xrightarrow[\backslash ;R\backslash ;]\{\}\backslash ,\backslash mathtt\{sgfnyd\}\backslash ,\backslash xrightarrow[\backslash ;H\backslash ;]\{\}\backslash ,\backslash mathtt\{920ECF10\}$

따라서 비밀번호는 "sgfnyd"이다(또는 동일한 해시 값을 가진 다른 비밀번호).

하지만 이 체인이 ''항상'' 해시 값을 포함하는 것은 아니다. h에서 시작하는 체인이 다른 시작점을 가진 체인과 병합될 수도 있다. 예를 들어, 해시 값 FB107E70의 체인도 "kiebgt"로 이어질 수 있다.

:$\backslash mathtt\{FB107E70\}\backslash ,\backslash xrightarrow[\backslash ;R\backslash ;]\{\}\backslash ,\backslash mathtt\{bvtdll\}\backslash ,\backslash xrightarrow[\backslash ;H\backslash ;]\{\}\backslash ,\backslash mathtt\{0EE80890\}\backslash ,\backslash xrightarrow[\backslash ;R\backslash ;]\{\}\backslash ,\{\backslash color\{Violet\}\backslash mathtt\{kiebgt\}\}$

이러한 경우를 ''가짜 경보''라고 하며, 일치를 무시하고 체인을 계속 확장하여 다른 일치를 찾아야 한다.

테이블 내용은 한 번 생성되면 수정 없이 반복적으로 사용된다. 체인의 길이를 늘리면 테이블 크기는 줄어들지만, 조회를 수행하는 시간은 증가한다. 이는 레인보우 테이블의 시간-메모리 트레이드오프를 보여준다.

단순한 해시 체인은 몇 가지 결함이 있다. 가장 심각한 문제는 두 개의 체인이 어느 시점에서든 ''충돌''하면(동일한 값을 생성), 병합되어 테이블이 많은 비밀번호를 다루지 못하게 된다는 것이다. 감소 함수 R은 충돌 저항성을 가질 수 없기 때문에 이러한 문제가 발생한다.^[1]

5. 레인보우 테이블의 원리

레인보우 테이블은 일반적인 해시 체인에서 발생하는 충돌 문제를 해결하기 위해 고안된 방법이다. 해시 체인은 해시 함수(H)와 축약 함수(R)를 번갈아 사용해 비밀번호와 해시 값의 연결고리(체인)를 만드는데, 서로 다른 체인에서 동일한 값이 생성(충돌)되면 체인이 합쳐져 테이블의 효율성이 떨어진다.^[1]

레인보우 테이블은 이러한 충돌 문제를 줄이기 위해 여러 개의 서로 다른 축약 함수(R₁, R₂, ..., R_k)를 사용한다. 각 체인은 서로 다른 축약 함수를 순차적으로 적용하여 생성되므로, 충돌 확률이 감소한다.^[1]

"레인보우 테이블"이라는 용어는 이처럼 서로 다른 축약 함수를 사용하는 방식에서 유래했다. 레인보우 테이블은 각 열에 서로 다른 축약 함수를 사용하는 하나의 큰 테이블을 사용하며, 축약 함수를 색상으로 표현하면 무지개와 같은 형태가 나타난다.

레인보우 테이블을 사용하면 해시 값 ''h''를 찾기 위해 여러 개의 서로 다른 체인을 생성해야 한다. 각 체인은 ''h''의 위치에 따라 다른 축약 함수 조합을 적용한다. 예를 들어, 첫 번째 체인은 R_k를 적용하고, 두 번째 체인은 R_k-1, H, R_k를 적용하는 식이다. 이 과정에서 찾고자 하는 해시 값이 체인에 없음에도 불구하고 테이블의 종료점과 일치하는 "거짓 경보"(False Alarm)가 발생할 수 있다. 그러나 전체적인 충돌 횟수를 줄여주기 때문에 레인보우 테이블은 여전히 효율적인 방법이다.

5. 1. 레인보우 테이블의 작동 예시

6. 레인보우 테이블의 약점 및 한계

레인보우 테이블은 특정 해시 함수에 특화되어 있다. 즉, MD5 해시를 위해 생성된 테이블은 MD5 해시만 크래킹할 수 있다. 평문의 문자 종류나 길이, 해시 값의 길이, 해시 함수 중 하나라도 다른 해시 값에 대해서는 다른 레인보우 테이블이 필요하다.^[1]

솔트가 사용된 해시 함수에 대해서는 레인보우 테이블의 효과가 크게 감소한다. 솔트는 비밀번호와 함께 해시되어, 각 사용자의 비밀번호 해시를 고유하게 만들기 때문이다. 예를 들어, 다음과 같은 해시 함수 MD5()를 생각할 수 있다(여기서 "."는 문자열 결합 연산자이다).^[1]

::hash = MD5 (password . salt)

이러한 해시로부터 비밀번호를 얻기 위해서는, 가능한 솔트 값의 개수만큼 테이블을 생성해야 한다. 솔트를 사용하면 비밀번호를 길게 한 것과 같은 효과를 얻을 수 있다. 솔트가 추가된 평문의 길이와 테이블이 대상으로 하는 평문의 길이가 다르면, 테이블에서 평문을 얻을 수 없다. 만약 평문을 찾더라도, 얻어진 평문에서 솔트 부분을 판단하여 제거해야 한다.^[1]

또한, 테이블 생성 시 지정하지 않은 문자 종류가 평문에 포함된 경우에도 테이블에서 평문을 얻을 수 없다. 따라서, 비밀번호에 충분한 길이와 문자 종류를 사용하는 것이 레인보우 테이블에 대한 효과적인 대책이 된다.^[1]

현재, 생성에 필요한 영역의 문제로 인해 8자 이상 길이의 평문에 대한 레인보우 테이블은 일반적으로 사용하기 어렵다.^[1]

7. 레인보우 테이블 방어 기법

레인보우 테이블 공격을 막기 위한 여러 기법이 존재한다. 주요 방어 기법은 다음과 같다:

• 솔팅(Salting): 비밀번호에 무작위 문자열(솔트)을 추가하여 해시 값을 계산하는 방법이다.^[4] 각 사용자마다 다른 솔트를 생성하므로, 같은 비밀번호를 사용하더라도 서로 다른 해시 값을 갖게 된다. 솔트는 비밀이 아니며 무작위로 생성되어 비밀번호 해시와 함께 저장된다. 큰 솔트 값을 사용하면 각 사용자의 비밀번호가 고유하게 해시되어 레인보우 테이블을 포함한 사전 계산 공격을 방지할 수 있다. 즉, 동일한 비밀번호를 가진 두 사용자는 서로 다른 솔트가 사용된다면 다른 비밀번호 해시를 갖는다. 공격에 성공하려면 각 솔트 값에 대해 미리 테이블을 계산해야 하므로, 솔트는 충분히 커야 한다. 예를 들어, 128비트 솔트를 사용하는 SHA2-crypt 및 bcrypt 방식은 리눅스, BSD Unix 및 솔라리스에서 사용되며, 이러한 큰 솔트 값은 거의 모든 길이의 비밀번호에 대한 사전 계산 공격을 불가능하게 만든다.^[4]

• 키 스트레칭(Key Stretching): 솔트, 비밀번호, 그리고 일부 중간 해시 값을 기본 해시 함수를 통해 여러 번 반복하여 실행함으로써 각 비밀번호를 해시하는 데 필요한 계산 시간을 늘리는 기술이다.^[5] 예를 들어, MD5-Crypt는 솔트, 비밀번호 및 현재 중간 해시 값을 기본 MD5 해시 함수에 반복적으로 공급하는 1000번의 반복 루프를 사용한다.^[4] 사용자는 로그인할 때마다 0.1초 미만의 시간만 기다리면 되므로 추가 시간은 사용자에게 눈에 띄지 않는다. 반면, 스트레칭은 공격자가 주어진 시간 내에 수행할 수 있는 시도 횟수를 줄여 무차별 대입 공격의 효과를 반복 횟수에 비례하여 줄인다. 이 원칙은 MD5-Crypt 및 bcrypt에 적용된다.^[6]

• 키 강화: 두 개의 솔트, 즉 공용 솔트와 비밀 솔트를 배포하지만, (키 스트레칭과 달리) 비밀 솔트를 안전하게 삭제하는 방법이다. 이렇게 하면 공격자와 합법적인 사용자 모두 비밀 솔트 값에 대한 무차별 대입 검색을 수행해야 한다. 비밀 솔트 크기는 무차별 대입 검색이 합법적인 사용자에게 감지할 수 없도록 선택된다. 그러나 이는 공격자에게 필요한 무지개 사전의 크기를 훨씬 더 크게 만든다.^[7]

8. 활용

레인보 테이블은 원래 비밀번호 해독을 위해 개발되었지만, 데이터 중복 제거, 해시 함수 분석, 암호학 연구 등 다른 분야에서도 활용될 수 있다.^[10]

유닉스, 리눅스, BSD 계열 운영체제는 대부분 솔트를 사용한 해시를 사용하지만, 마이크로소프트 윈도우의 LAN Manager 및 NT LAN Manager 해싱 방식(MD4 기반)과 같이 솔트가 없는 해시 함수를 사용하는 시스템에서는 레인보 테이블이 여전히 유용하게 사용될 수 있다. 솔트가 없는 MD5 해시 함수를 사용하는 애플리케이션도 많이 존재한다.^[10]

참조

_[1] 논문 A cryptanalytic time-memory trade-off http://www-ee.stanfo[...]
_[2] 서적 Advances in Cryptology - CRYPTO 2003
_[3] 웹사이트 LASEC - Security and Cryptography Laboratory: Dr Philippe Oechslin - Research https://lasec.epfl.c[...] 2004-03-01
_[4] 논문 Password Protection for Modern Operating Systems https://www.usenix.o[...] USENIX Association 2004-06-01
_[5] 서적 Practical Cryptography John Wiley & Sons
_[6] 논문 A Future-Adaptable Password Scheme http://www.usenix.or[...] USENIX Association 1999-06-06
_[7] 논문 A simple scheme to make passwords based on one-way functions much harder to crack http://webglimpse.ne[...] 2015-08-28
_[8] 서적 Information Security
_[9] 웹사이트 How to prevent Windows from storing a LAN manager hash of your password in Active Directory and local SAM databases http://support.micro[...] Microsoft 2021-09-24
_[10] 웹사이트 A Case for Modern Rainbow Table Usage https://www.rainbowc[...] Positron Security. 2021-02-26
_[11] 문서 以下の説明ではレインボーテーブルの末尾の要素としてハッシュ値ではなく平文を使用しているが、末尾がハッシュ値であるテーブルであっても生成および探索処理にほぼ変わりはない。