[패스워드 크래킹] Rainbow table

▶ 레인보우 테이블?

레인보우 테이블은 해시함수 (MD5, SHA-1, SHA-2 등)을 사용하여 만들어낼 수 있는 값들을 대량으로 저장한 표이다. 1980년 마틴 헬만에 의해 소개되었고 MD5 암호화가 쉽게 복호화될 수 있다는 것을 보여준 해킹 기법 중 하나이다. 하나의 패스워드에서 시작해 변이된 형태의 여러 패스워드를 생성하여 그 패스워드의 해시를 고리처럼 연결해 일정 수의 패스워드와 해시로 이루어진 테이블이다. 조합 가능한 모든 문자열을 하나씩 대입해 보는 방식으로 문제를 푸는 브루트 포스 공격을 뒷받침 해주는 역할을 하기도 하고 해시에서 평문을 추출해내기 위함의 역할도 있다.

 

▶ 원리

레인보우 테이블은 한 개가 아니라 몇 천개로 이뤄져있다. 이 몇 천개가 생성된 후 진짜 최종 테이블이 생성된다. 최종 테이블은 해당 테이블의 최초 패스워드랑 최종 해시값을 저장한다. 최초 패스워드에서 해시 함수를 이용해 해시값을 생성하고, 생성된 해시 값을 사용하여 R함수로 두번째 확인하고자 하는 패스워드를 생성한다. R함수는 해시테이블을 작은 크기로 줄이기 위하여 해시테이블의 해시 값으로 패스워드 문자열을 만들어 내는 함수이다. 규칙은 만들기 나름. 

 

▶ 과정

[1] 현재 해시값이 최종 테이블에 있는지 확인한다.

[2] 없으면 해시값을 R함수로 추출한다. -> ex. 31945

[3] 추출해낸 패스워드 기준으로 해시값을 생성한다. -> ex. F55078E976DF9B3214D3F222

[4] 생성한 해시값이 최종 테이블에 있으면 최종 테이블에서 생성한 해시값에 해당하는 패스워드가 최초 패스워드인 테이블로 이동한다.

[5] 이동한 테이블에 찾고자 하는 해시값에 대한 패스워드가 있는 것을 확인한다. -> ex. 38059

 

▶ 해시 알고리즘을 복잡하게 만든다면 안전할까?

Brute force attack을 생각해봤을 때, 미리 가능한 패스워드 조합을 다 계산한 테이블을 가지고 비교만 수행할 수 도 있다. 이 dictionary를 해시값 검색에 최적화시킨 것을 레인보우테이블이라고 한다. MD5의 경우, 인터넷에 이미 수백억개의 해시값에 대한 레인보우테이블이 있다. 이미 계산된 값을 이요하므로 알고리즘의 복잡도와는 관계가 없다. 해시값이 해당 테이블 안에 있다면, 패스워드는 거의 크랙될 수 있다. 물론 레인보우테이블을 만드는데도 시간이 많이 들기 때문에 알고리즘의 복잡도가 전혀 상관이없는 것은 아니지만, 쉬운 패스워드의 경우는 쉽게 뚫릴 수 있으므로 보안성을 크게 높일 수 있다고 말하기는 어렵다. 

 

▶ 방어법

[1] 길이가 짧거나 단순 조합에 의한 패스워드, 반복적인 단어나 특정 단어에 의한 패스워드, 유추가 가능하거나 많은 사람이 사용할만한 패스워드는 패스워드 크래킹 공격에 취약하므로 사용을 자제해야한다. 

[2] 솔티드 해시 : 가입 시간이나 난수를 비밀번호와 같이 해시값에 포함시킨다. 이 때, 추가적으로 포함된 가입 시간이나 난수를 솔트(salt)라고 한다. 이는 서로 다른 계정이 같은 비밀번호를 사용하더라도 솔트가 다르면 완전 다른 해시값이 생성되어, 평문을 유추하기가 힘들어진다. 일방향성이 아닌 암호화/역암호화시 둘다 사용되는(쌍으로 이루어지는) 솔트는, 같은 솔트가 사용되어야 하고 레인보우 테이블에 의한 암호 크랙 공격(사전 공격)을 어느정도 무력화시킬 수 있다.

[3] 블룸 필터 : 블룸 필터는 원소가 집합에 속하는지 여부를 검사하는데 사용되는 확률적 자료구조이다. 즉, 개발자들은 사용자가 회원가입을 할 때 레인보우 테이블에 있는 비밀번호에 대하여 사용을 금지하는 방법을 선택하는데 이러한 과정속에서 금지된 비밀번호를 걸러내는 역할을 한다. 이 방법을 사용하면 사용자는 취약한 비밀번호의 사용이 금지되어 공격자가 가지고 있는 패스워드 사전도 취약하게 된다. 설령 공격자가 갱신을 한 패스워드 사전을 가지고 있다 치더라도 개발자가 해당 사전을 수집할 수 있으므로 금지 비밀번호를 갱신하면 된다. 

 

▶ 실습

사실, 사전적인 정의를 보면 레인보우테이블이라기 보단 사전공격에 좀 더 가까운거 같지만.. webhacking.kr 에서 비슷하게 해시함수를 푸는 문제가 있다. 해당 문제에서는 R함수는 돌리지 않는데, SHA-1 해싱을 500번 돌린다. 자세한 풀이법은 해당 문제를 풀이할 때 올리고.. 공부도 할 겸 실제로 테이블을 만들어봤다. 근데 범위가 어마어마하게 많아서 만드는 시간과 용량이 엄청 소모된다. 소장하려고 엑셀 파일로 만들었는데, 엑셀 행 수가 제한이 있는걸 처음알았다(엑셀에서도 100만 행 정도가 넘어가면 더이상 데이터를 입력할 수 없다.).

사전공격 테이블을 만들어서 해결한 문제