레인보 테이블

단순화한 레인보 테이블.

레인보 테이블(영어: rainbow table)은 일반적으로 비밀번호 크래킹을 위해 암호화 해시 함수의 출력을 캐싱하는 미리 계산된 테이블이다. 비밀번호는 일반적으로 평문 형태로 저장되지 않고, 해시 값으로 저장된다. 해시된 비밀번호 데이터베이스가 공격자의 손에 들어가면, 공격자는 미리 계산된 레인보 테이블을 사용하여 평문 비밀번호를 복구할 수 있다. 이 공격에 대한 일반적인 방어는 해시하기 전에 각 비밀번호에 "솔트"를 추가하는 키 유도 함수를 사용하여 해시를 계산하는 것이다. 이때, 다른 비밀번호에는 다른 솔트가 적용되며, 솔트는 해시와 함께 평문으로 저장된다.

레인보 테이블은 공간-시간 트레이드오프의 실질적인 예시이다. 이는 모든 시도에서 해시를 계산하는 무차별 대입 공격보다 적은 컴퓨터 처리 시간과 더 많은 저장 공간을 사용하지만, 모든 가능한 비밀번호의 해시를 저장하는 간단한 테이블보다 더 많은 처리 시간과 적은 저장 공간을 사용한다.

레인보 테이블은 필리프 외슐린(Philippe Oechslin)이 마틴 헬먼의 이전의 더 간단한 알고리즘을 적용하여 발명했다.

배경

사용자 인증을 위해 비밀번호는 평문 또는 해시 형태로 저장된다. 평문으로 저장된 비밀번호는 데이터베이스 접근이 침해될 경우 쉽게 도난당할 수 있으므로, 데이터베이스는 일반적으로 대신 해시를 저장한다. 따라서 인증 시스템을 포함하여 누구도 데이터베이스에 저장된 값만으로는 비밀번호를 알 수 없다.

사용자가 인증을 위해 비밀번호를 입력하면, 해당 비밀번호의 해시가 계산된 다음 해당 사용자의 저장된 해시와 비교된다. 두 해시가 일치하지 않으면 인증이 실패하며, 해시된 값을 비밀번호로 입력하는 경우에도 인증 시스템이 이를 두 번 해시하므로 동일하게 실패한다.

해시에서 비밀번호를 알아내는 것은 해시 함수에 입력될 때 동일한 해시를 생성하는 문자열을 찾는 것이다. 이는 해시 함수를 역전시키는 것과 같다.

무차별 대입 공격 (예: 사전 공격)을 사용하여 해시 함수를 역전시키려 할 수 있지만, 가능한 비밀번호 집합이 충분히 클 때는 비현실적일 수 있다. 무차별 대입의 대안은 미리 계산된 해시 체인 테이블을 사용하는 것이다. 레인보 테이블은 특정 기술적 어려움을 극복하는 특별한 종류의 테이블이다.

어원

크립토 2003에서 발표된 레인보 테이블 그림

레인보 테이블이라는 용어는 외슐린의 초기 논문에서 처음 사용되었다. 이 용어는 공격의 성공률을 높이기 위해 서로 다른 환원 함수가 사용되는 방식에서 유래되었다. 헬먼의 원래 방법은 각각 다른 환원 함수를 가진 여러 개의 작은 테이블을 사용한다. 레인보 테이블은 훨씬 더 크며 각 열에서 다른 환원 함수를 사용한다. 환원 함수를 나타내는 데 색상이 사용될 때, 레인보 테이블에는 무지개가 나타난다. 외슐린의 논문 2번 그림에는 이 섹션들이 어떻게 관련되어 있는지를 보여주는 흑백 그래픽이 포함되어 있다. 크립토 2003 컨퍼런스 발표를 위해 외슐린은 무지개 연관성을 더 명확히 하기 위해 그래픽에 색상을 추가했다. 컨퍼런스에서 발표된 향상된 그래픽이 그림에 나와 있다.

미리 계산된 해시 체인

해시 함수 H와 유한한 비밀번호 집합 P가 주어졌을 때, 목표는 해시 함수의 출력 h가 주어지면, H(p) = h인 P의 원소 p를 찾거나, P에 그러한 p가 없음을 결정할 수 있는 자료 구조를 미리 계산하는 것이다. 이를 수행하는 가장 간단한 방법은 P의 모든 p에 대해 H(p)를 계산하는 것이지만, 테이블을 저장하는 데에는 Θ(|P|n) 비트의 공간이 필요하다. 여기서 |P|는 P 집합의 크기이고 n은 H 출력의 크기인데, 이는 |P|가 클 경우 엄청난 비용이다. 해시 체인은 이러한 공간 요구 사항을 줄이기 위한 기술이다. 이 아이디어는 해시 값을 P의 값으로 다시 매핑하는 환원 함수 R을 정의하는 것이다. 그러나 환원 함수는 실제로 해시 함수의 역함수가 아니라, 해시 함수의 정의역과 공역이 교환된 다른 함수임을 주목해야 한다. 해시 함수와 환원 함수를 번갈아 적용함으로써, 비밀번호와 해시 값이 번갈아 나타나는 체인이 형성된다. 예를 들어, P가 소문자 알파벳 6자리 비밀번호 집합이고 해시 값이 32비트 길이인 경우, 체인은 다음과 같을 수 있다.

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

환원 함수의 유일한 요구 사항은 특정 크기의 "평문" 값을 반환할 수 있어야 한다는 것이다.

테이블을 생성하기 위해 P에서 무작위 초기 비밀번호 세트를 선택하고, 각 비밀번호에 대해 고정된 길이 k의 체인을 계산한 다음, 각 체인의 첫 번째 비밀번호와 마지막 비밀번호만 저장한다. 첫 번째 비밀번호는 시작점이라고 불리고 마지막 비밀번호는 끝점이라고 불린다. 위 예시 체인에서 "aaaaaa"는 시작점이고 "kiebgt"는 끝점이며, 다른 비밀번호(또는 해시 값)는 저장되지 않는다.

이제 역전할 해시 값 h가 주어졌을 때 (해당하는 비밀번호를 찾기 위해), R을 적용한 다음 H를 적용하고, 다시 R을 적용하는 식으로 h에서 시작하는 체인을 계산한다. 어느 지점에서든 값이 테이블의 끝점 중 하나와 일치하면, 해당 시작점을 통해 전체 체인을 재구성할 수 있다. 이 체인이 값 h를 포함할 가능성이 높으며, 만약 그렇다면 체인에서 바로 이전 값이 우리가 찾는 비밀번호 p이다.

예를 들어, 해시 920ECF10가 주어졌을 때, 먼저 R을 적용하여 체인을 계산할 수 있다.

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

"kiebgt"가 우리 테이블의 끝점 중 하나이므로, 해당 시작 비밀번호 "aaaaaa"를 통해 920ECF10에 도달할 때까지 체인을 따라갈 수 있다.

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

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

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

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

해당 시작 비밀번호 "aaaaaa"에 의해 생성된 체인은 FB107E70에 도달할 때까지 따라간다. 이 값이 체인에 포함되어 있지 않으므로 FB107E70에 도달하지 않고 검색이 종료될 것이다. 이를 오탐(false alarm)이라고 한다. 이 경우 일치는 무시되고 h의 체인은 다른 일치를 찾기 위해 확장된다. h의 체인이 좋은 일치 없이 길이 k로 확장되면, 비밀번호는 어떤 체인에서도 생성되지 않은 것이다.

테이블 내용은 역전할 해시 값에 의존하지 않는다. 한 번 생성된 후 수정되지 않고 반복적으로 조회에 사용된다. 체인의 길이를 늘리면 테이블의 크기가 줄어든다. 그러나 조회 수행에 필요한 시간도 늘어나는데, 이것이 레인보 테이블의 시간-메모리 트레이드오프이다. 단일 항목 체인의 간단한 경우, 조회는 매우 빠르지만 테이블은 매우 크다. 체인이 길어지면 조회 속도는 느려지지만 테이블 크기는 줄어든다.

단순 해시 체인에는 몇 가지 결함이 있다. 가장 심각한 것은 어느 지점에서든 두 체인이 충돌(동일한 값 생성)하면 병합되어, 생성에 동일한 계산 비용을 지불했음에도 불구하고 테이블이 더 적은 비밀번호를 커버하게 된다는 것이다. 이전 체인들은 전체적으로 저장되지 않기 때문에 이를 효율적으로 감지하는 것은 불가능하다. 예를 들어, 체인 3의 세 번째 값이 체인 7의 두 번째 값과 일치하면 두 체인은 거의 동일한 값 시퀀스를 커버하지만, 그들의 최종 값은 같지 않을 것이다. 해시 함수 H는 일반적으로 중요한 보안 기능으로 간주되므로 충돌을 일으킬 가능성이 낮지만, 환원 함수 R은 예상되는 평문을 올바르게 커버해야 할 필요성 때문에 충돌 저항성이 없을 수 있다.

다른 어려움은 R에 대한 올바른 함수를 선택하는 것의 중요성에서 비롯된다. R을 항등 함수로 선택하는 것은 무차별 대입 접근 방식보다 거의 나을 바가 없다. 공격자가 예상되는 평문에 대해 잘 알고 있을 때만 시간과 공간이 가능한 비밀번호 전체 공간이 아니라 예상되는 평문에만 사용되도록 하는 함수 R을 선택할 수 있다. 실제로 R은 이전 해시 계산 결과를 예상되는 평문으로 다시 되돌리지만, 이 이점은 R이 공격자가 확인하려는 클래스의 모든 가능한 평문을 생성하지 못할 가능성이 있다는 단점을 수반하여 공격자가 선택한 클래스에서 어떤 비밀번호도 나오지 않았다는 확신을 부정하게 만든다. 또한 함수 R을 평문의 예상 분포와 일치하도록 설계하는 것이 어려울 수 있다.

레인보 테이블

레인보 테이블은 단일 환원 함수 R을 R₁부터 R_k까지의 관련 환원 함수 시퀀스로 대체함으로써 일반적인 해시 체인의 해시 충돌 문제를 효과적으로 해결한다. 이러한 방식으로 두 체인이 충돌하고 병합되려면 동일한 반복에서 동일한 값에 도달해야 한다. 결과적으로 이 체인들의 최종 값은 동일할 것이다. 최종 후처리 단계를 통해 테이블의 체인을 정렬하고 다른 체인과 동일한 최종 값을 가진 "중복" 체인을 제거할 수 있다. 그런 다음 테이블을 채우기 위해 새로운 체인이 생성된다. 이 체인들은 충돌이 없지는 않지만 (잠시 겹칠 수 있음), 병합되지는 않아 전체 충돌 수를 대폭 줄인다.

환원 함수 시퀀스를 사용하면 조회 방식이 달라진다. 관심 있는 해시 값이 체인의 어느 위치에서든 발견될 수 있으므로 k개의 서로 다른 체인을 생성해야 한다. 첫 번째 체인은 해시 값이 마지막 해시 위치에 있다고 가정하고 R_k만 적용한다. 다음 체인은 해시 값이 끝에서 두 번째 해시 위치에 있다고 가정하고 R_k−1을 적용한 다음 H를 적용하고, 다시 R_k를 적용한다. 마지막 체인까지 이 과정을 반복하며 모든 환원 함수를 H와 번갈아 적용한다. 이는 오탐을 생성하는 새로운 방법을 만든다. 해시 값의 위치에 대한 잘못된 "추측"은 불필요하게 체인을 평가할 수 있다.

레인보 테이블은 더 많은 체인을 따라야 하지만, 더 적은 테이블을 가짐으로써 이를 보완한다. 단순 해시 체인 테이블은 병합 체인으로 인해 빠르게 비효율적이 되므로 특정 크기를 넘어설 수 없다. 이를 처리하기 위해 여러 테이블을 유지하고 각 조회는 각 테이블을 검색해야 한다. 레인보 테이블은 k배 더 큰 테이블로 유사한 성능을 달성할 수 있어 k배 더 적은 조회를 수행할 수 있다.

예시

1. 아래 이미지의 해시("re3xes")에서 시작하여, 테이블에서 사용된 마지막 환원 함수를 계산하고 테이블의 마지막 열에 비밀번호가 나타나는지 확인한다 (1단계).
2. 테스트가 실패하면 (rambo가 테이블에 나타나지 않음), 마지막 두 환원 함수를 사용하여 체인을 계산한다 (이 두 환원은 2단계에 표시됨).

   참고: 이 새로운 테스트가 다시 실패하면, 비밀번호가 발견될 때까지 3개, 4개 등의 환원 함수를 계속 사용한다. 어떤 체인에도 비밀번호가 포함되어 있지 않으면 공격은 실패한 것이다.

3. 이 테스트가 성공하면 (3단계, linux23이 체인 끝과 테이블에 나타남), 비밀번호는 linux23을 생성하는 체인의 시작 부분에서 검색된다. 여기서 우리는 테이블에 저장된 해당 체인의 시작 부분에서 passwd를 찾는다.
4. 이 시점에서 (4단계), 체인을 생성하고 각 반복에서 해시를 대상 해시와 비교한다. 체인에서 해시 re3xes를 찾고, 그것을 생성한 비밀번호(culture)를 체인에서 한 단계 앞에서 찾는다. 공격이 성공한 것이다.

레인보 테이블은 체인의 각 "링크"에 대해 다른 환원 함수를 사용하는 정교한 알고리즘을 사용한다. 따라서 두 개 이상의 체인에서 해시 충돌이 발생하더라도, 충돌이 각 체인의 동일한 위치에서 발생하지 않는 한 체인이 병합되지 않는다. 이는 주어진 테이블 크기에 대해 올바른 크랙 확률을 높여주지만, 조회당 필요한 단계 수가 제곱으로 증가하는 대가가 따른다. 조회 루틴은 이제 체인에서 사용된 첫 번째 환원 함수의 인덱스를 통해 반복해야 하기 때문이다.

레인보 테이블은 생성된 해시 함수에 특화되어 있다. 예를 들어, MD5 테이블은 MD5 해시만 크랙할 수 있다. 이 기술의 이론은 필리프 외슐린(Philippe Oechslin)이 시간/메모리 트레이드오프의 빠른 형태로 발명했으며, 그는 이를 Windows 비밀번호 크래커 Ophcrack에 구현했다. 나중에 더 강력한 RainbowCrack 프로그램이 개발되어 LM 해시, MD5, SHA-1을 포함한 다양한 문자 집합 및 해싱 알고리즘에 대한 레인보 테이블을 생성하고 사용할 수 있게 되었다.

환원 함수와 해시 함수에 충돌이 없는 간단한 경우, 완전한 레인보 테이블(어떤 해시가 주어져도 해당 비밀번호를 찾을 수 있는 테이블)이 주어지면, 비밀번호 집합의 크기 |P|, 테이블 계산에 필요한 시간 T, 테이블 길이 L, 그리고 주어진 해시에 일치하는 비밀번호를 찾는 데 필요한 평균 시간 t는 직접적으로 관련된다.

$T=|P|$

$t={\frac {|P|}{2L}}$

따라서 8자 소문자 영숫자 비밀번호의 경우 (|P| ≃ 3×10¹²)는 개인용 컴퓨터로 쉽게 처리할 수 있지만, 16자 소문자 영숫자 비밀번호의 경우 (|P| ≃ 10²⁵)는 완전히 처리 불가능하다.

레인보 테이블 방어

레인보 테이블은 대규모 솔트를 포함하는 단방향 해시에는 효과적이지 않다. 예를 들어, 다음 함수를 사용하여 생성된 비밀번호 해시를 고려해보자 ("+"는 문자열 연결 연산자이다):

saltedhash(password) = hash(password + salt)

또는

saltedhash(password) = hash(hash(password) + salt)

솔트 값은 비밀이 아니며 무작위로 생성되어 비밀번호 해시와 함께 저장될 수 있다. 큰 솔트 값은 각 사용자의 비밀번호가 고유하게 해시되도록 보장함으로써 레인보 테이블을 포함한 미리 계산된 공격을 방지한다. 이는 동일한 비밀번호를 가진 두 사용자가 다른 비밀번호 해시를 갖게 됨을 의미한다 (다른 솔트가 사용된다고 가정). 공격자가 성공하려면 각 가능한 솔트 값에 대한 테이블을 미리 계산해야 한다. 솔트는 충분히 커야 하며, 그렇지 않으면 공격자가 각 솔트 값에 대한 테이블을 만들 수 있다. 12비트 솔트를 사용했던 오래된 유닉스 비밀번호의 경우 4096개의 테이블이 필요했는데, 이는 공격자에게 상당한 비용 증가이지만 테라바이트 하드 드라이브로는 비현실적이지 않다. 리눅스, BSD 유닉스, 솔라리스에서 사용되는 SHA2-crypt 및 bcrypt 방법은 128비트 솔트를 사용한다. 이러한 더 큰 솔트 값은 거의 모든 길이의 비밀번호에 대한 사전 계산 공격을 비현실적으로 만든다. 공격자가 초당 백만 개의 테이블을 생성할 수 있다고 해도, 모든 가능한 솔트에 대한 테이블을 생성하는 데 수십억 년이 걸릴 것이다.

미리 계산된 공격을 방지하는 데 도움이 되는 또 다른 기술은 키 스트레칭이다. 스트레칭을 사용하면 솔트, 비밀번호, 그리고 일부 중간 해시 값이 여러 번 기본 해시 함수를 통해 실행되어 각 비밀번호를 해시하는 데 필요한 계산 시간을 늘린다. 예를 들어, MD5-Crypt는 1000회 반복 루프를 사용하여 솔트, 비밀번호, 현재 중간 해시 값을 기본 MD5 해시 함수에 반복적으로 공급한다. 사용자의 비밀번호 해시는 솔트 값(비밀이 아님)과 최종 해시의 문자열 연결이다. 추가 시간은 사용자가 로그인할 때마다 1초 미만만 기다리면 되므로 눈에 띄지 않는다. 반면에 스트레칭은 공격자가 주어진 시간 내에 수행할 수 있는 시도 횟수를 줄이기 때문에 반복 횟수에 비례하여 무차별 대입 공격의 효과를 감소시킨다. 이 원리는 MD5-Crypt와 bcrypt에 적용된다. 또한 미리 계산된 테이블을 구축하는 데 필요한 시간을 크게 늘리지만, 솔트가 없는 경우에는 한 번만 수행하면 된다.

키 강화라고 불리는 대안적인 접근 방식은 공개 솔트와 비밀 솔트 두 가지를 사용하지만 (키 스트레칭과 달리) 비밀 솔트를 안전하게 삭제한다. 이는 공격자와 합법적인 사용자 모두 비밀 솔트 값을 무차별 대입 검색하도록 강제한다. 비밀 솔트 크기는 무차별 대입 검색이 합법적인 사용자에게 감지되지 않도록 선택된다. 그러나 이는 공격자에게 필요한 레인보 사전을 훨씬 더 크게 만든다. 키 스트레칭을 소개한 논문이 이 이전 기술을 언급하고 의도적으로 다른 이름을 선택했음에도 불구하고, "키 강화"라는 용어는 이제 종종 (논쟁의 여지가 있지만 잘못되게) 키 스트레칭을 지칭하는 데 사용된다.

레인보 테이블 및 기타 미리 계산된 공격은 가정된 범위 밖의 기호를 포함하거나 공격자가 미리 계산한 것보다 긴 비밀번호에는 작동하지 않는다. 그러나 사용자가 숫자나 특수 문자를 추가하는 등 더 안전한 비밀번호를 선택하려는 일반적인 방법을 고려하여 테이블을 생성할 수 있다. 계산 처리의 상당한 투자 때문에 14자리 이상 길이의 레인보 테이블은 아직 흔하지 않다. 따라서 14자보다 긴 비밀번호를 선택하면 공격자가 무차별 대입 방법을 사용하도록 강제할 수 있다.

마이크로소프트에서 사용되는 오래된 해시 알고리즘인 LM 해시에 중점을 둔 특정 집중적인 노력은 공개적으로 이용 가능하다. LM 해시는 7자보다 긴 비밀번호가 두 부분으로 나뉘어 각 부분이 개별적으로 해시되기 때문에 특히 취약하다. 15자 이상의 비밀번호를 선택하면 LM 해시가 생성되지 않도록 보장한다.

일반적인 사용

거의 모든 유닉스, 리눅스, BSD 배포판 및 변형은 솔트와 함께 해시를 사용하지만, 많은 응용 프로그램은 솔트 없이 해시(일반적으로 MD5)만 사용한다. 마이크로소프트 윈도우 NT/2000 계열은 LAN Manager 및 NT LAN Manager 해싱 방법(MD4 기반)을 사용하며 솔트가 없으므로 가장 일반적으로 생성되는 테이블 중 하나이다. 솔트 사용이 더 일반화되고 GPU 기반 무차별 대입 공격이 더 실용화되면서 2020년 현재 레인보 테이블의 사용은 줄어들었다. 그러나 8자 및 9자 NTLM 비밀번호에 대한 레인보 테이블은 여전히 사용 가능하다.

같이 보기

• A5/1
• 무차별 대입 공격

출처

• Oechslin, Philippe (2003년 8월 17일). 〈Making a Faster Cryptanalytic Time-Memory Trade-Off〉. 《Advances in Cryptology - CRYPTO 2003》 (PDF). Lecture Notes in Computer Science 2729. Santa Barbara, California, USA: Springer. 617–630쪽. doi:10.1007/978-3-540-45146-4_36. ISBN 978-3-540-40674-7. S2CID 16086595. 2020년 9월 26일에 원본 문서 (PDF)에서 보존된 문서. 2019년 3월 13일에 확인함.