레인보우 테이블
IT위키
더 많은 작업
레인보우 테이블(Rainbow Table)은 비밀번호 후보의 해시 값을 미리 계산해 두되, 해시 함수와 축소 함수를 번갈아 적용한 체인의 시작값과 끝값만 저장해 저장 공간을 크게 줄인 역해시용 표이다.
해시로 저장된 비밀번호를 알아내는 가장 단순한 방법은 가능한 모든 비밀번호의 해시를 계산해 비교하는 무차별 대입 공격이다. 시간이 너무 오래 걸리면 모든 후보의 해시를 미리 계산해 표로 저장해 둘 수 있지만, 이번에는 표가 너무 커진다. 레인보우 테이블은 그 중간이다. 미리 계산해 두는 시간과 저장 공간, 찾을 때 다시 계산하는 시간을 적당히 맞바꾼 시간-메모리 절충(time-memory trade-off) 기법이다. 2003년 필리프 외슬린(Philippe Oechslin)이 제안했다.
- 비밀번호 후보 하나에서 시작해 해시 함수 H 로 해시를 구한다
- 축소 함수 R 로 그 해시를 다시 다른 비밀번호 후보 로 바꾼다(역함수가 아니라 후보 공간으로 옮기는 함수일 뿐이다)
- H 와 R 을 정해진 횟수만큼 번갈아 적용해 체인을 만들고, 시작 후보와 마지막 해시만 표에 적는다
- 찾을 때는 목표 해시에 R·H 를 반복 적용하며 표의 끝값과 맞는지 보고, 맞으면 그 체인을 시작값부터 다시 계산해 원래 비밀번호를 찾는다
체인의 단계마다 서로 다른 축소 함수를 써서 체인끼리 합쳐지는 것을 줄였고, 이 여러 축소 함수를 색에 빗대 '레인보우' 라 부른다.