Rainbow Table Attack 알아보기

 

---

Rainbow Table Attack 알아보기

---

 

 

1. 개요

 

오늘은 Rainbow Table Attack에 대해서 알아보도록 하겠습니다.

Rainbow Table Attack은 주로 암호 알고리즘을 알고 있고 자유롭게 평문-암호문 쌍을 생성할 수 있는 환경의 선택평문공격(Chosen-Plaintext Attack)으로 분류됩니다.

 

예를 들어서 대부분의 서비스들은 유저의 비밀번호를 암호화/해싱이 된 형태로 저장합니다.

그래야 전송 과정에서 탈취를 당하더라도 credential이 유출되지 않기 때문입니다.

 

그러면 이때 암호문을 탈취한 뒤, 평문을 다시 얻어낼 수 있을까요?

선택평문공격을 할 수 있는 환경이라면 Rainbow Table Attack을 수행할 수 있습니다.

 

 

 

2. Rainbow Table 생성

 

우선 Rainbow Table의 정의는 다음과 같습니다.

 

A precomputed table to help with reversal of hashes/encryption.

 

간단히 말해서 정상적인 해시함수나 암호화 함수의 역함수를 구하는건 어렵기 때문에,

미리 평문-암호문 쌍을 엄청 많이 구해놓은 테이블을 Rainbow Table이라고 합니다.

이걸 가지고 공격을 수행하면 Rainbow Table Attack이구요. (하나라도 얻어걸리라는 마인드)

 

Rainbow Table을 생성하는 과정은 다음과 같습니다.

 

1. 크기 N의 Password Space 설정

- 이때 N은 임의의 숫자입니다.

 

2. k개의 Reduction Function 선언. (단, R_k(Ciphertext)→x∈N)

- k는 임의의 숫자입니다.

- 주의해야 할 건, Reduction Function은 암호화/해시함수의 역함수가 아닙니다. 함수의 정의역/치역이 있다고 하면, 단순히 임의의 치역에 대해 아무런 정의역 값을 리턴하는 역할을 합니다.

- Reduction Function은 더 효율적인 공격을 하기 위함입니다. 자세한 내용은 아래에도 작성하였습니다.

- 혹시나 Reduction Function이 이해가 안된다면 참고할만한 글 : https://security.stackexchange.com/questions/46510/rainbow-tables-what-is-the-reduction-used-for

Rainbow Tables: What is the Reduction Used for?

 

3. 길이 k만큼의 chain L을 연산합니다. 연산 후 Rainbow Table에는 처음과 마지막 값만 저장합니다.

- 아래 사진의 경우에는 k의 값은 2입니다.

 

 

 

3. Rainbow Table의 탐색 과정

 

Rainbow Table을 생성했다면 이에 대해서 평문을 다시 찾아내는 과정을 진행하도록 하겠습니다.

위의 Rainbow Table을 통해 공격을 수행한다고 가정합시다.

암호문 0F42B7을 찾아내는 과정은 다음과 같습니다.

참고로 해당 예시에서는 암호 과정을 해시 함수라고 가정합니다.

 

1. 먼저 마지막 reduction function을 이용해 해당 값이 테이블에 있는지 확인합니다.

R_k(h) = R₂(OF42B7) = 3kbv

3kbv는 테이블에 존재하지 않으므로 pass

 

2. 그 다음 reduction function을 사용하여 해당 값이 테이블에 있는지 확인합니다.

R_k(H(R_k-1(h))) = R₂(H(R₁(OF42B7))) = s63e

s63e는 테이블에 있기때문에 match found!

 

3. 찾은 체인(예시의 경우 첫 번째 체인)에서 연산을 다시 수행하여 해당 암호문에 대한 평문을 찾아냅니다.

이 경우에는 aoej가 0F42B7의 평문임을 알 수 있습니다.

 

4. 만약 찾지 못했다면 찾을때까지 reduction function을 포함한 연산을 진행합니다(최대 k번)

 

 

 

4. 기타

 

Rainbow Table을 공부하면서 한 가지 궁금했던 건 Reduction Function의 의도에 관한 것이었습니다.

굳이 왜 reduction function을 사용하는 것이지? 그냥 해시 한번 돌리고 rainbow table attack을 돌리면 되는거 아닌가? 라는 생각이 먼저 들었었거든요.

 

찾아보고 질문하여 받은 답변을 요약하면 이렇습니다.

 

1. Reduction Function은 추가적인 연산(additional computation)을 통해 사용 용량을 줄일 수 있다.

1.1. 특히나 공격을 수행하고자 하는 대상의 Domain이 커질수록 최소한의 용량으로 공격을 수행하는 것이 더 효율적이다.

2. 해시 함수를 단 한번 사용한 Rainbow table은 엄밀히 말하면 lookup database에 불과하다.

2.1. 물론 굳이 분류를 하자면 Rainbow Table에 포함시킬 수는 있겠지만, 본 강의에서는 reduction function을 사용한 table들만 rainbow table로 간주할 것이다.

 

 

그렇다고 하네요~.~ 내가 예전에 해본 rainbow table attack은 lookup database attack이었던 걸로...

 

 

5. 결론

 

이론적인 부분만 다뤄서 그런지 실제로 reduction function이 어떻게 사용이 되는지는 해봐야 알 것 같네요.

확실히 제가 기존에 rainbow table attack이라고 알고 있던 것보다는(해시를 한번만 진행하는) 훨씬 더 효율적으로 진행할 수 있을 것 같습니다.

 

끝!