[Webhacking.kr] old-04 (레인보우테이블 문제)

1. 서론

본 포스팅 시리즈는 webhacking.kr의 문제 풀이를 하면서 정리한 자료이다.
필자가 풀이한 방법들이기 때문에 완벽하지 않을 수도 있다는 점을 참고 바란다. (지적과 조언은 언제나 환영이다)

이번 문제는 old-4, 레인보우테이블에 대한 이해와 활용이 필요한 문제이다.

2. 본론

이번 문제를 접속해보면 위와 같은 화면이 나타난다. 뭔가 알 수 없는 방식으로 인코딩 된 듯한 초록색 문자열과 패스워드를 입력하고 제출하라는 Form이 눈에 띈다.

이건 이번 문제의 소스코드이다.
여기서 요점을 보자면 우선 "sleep(1)"을 통해 브루트포스를 방지하는 모습을 볼 수 있다.
이부분에서 알 수 있는 점은 이번 문제에선 반복작업이 매우 많이 필요할 수 있다는 점이다.

그 아랫 부분을 보면 세션변수 "chall4"의 존재 여부를 확인하면서 POST로 전달된 "key" 값과 세션변수 "chall4"의 값이 동일한지 검사하고, 참이라면 이번 문제를 해결하게 된다. 여기서 POST로 전달된 key는 우리가 맨 처음 이번 문제에 접속했을 때 나온 페이지의 Form에 있던 입력창이다.

문제 해결 여부를 검사 시 "key"와 "chall4"가 동일하지 않은 경우, 10000000 ~ 99999999 사이의 랜덤 숫자와 "salt_for_you"라는 문자열이 결합된 문자열을 "chall4"에 저장해두고 이 문자열을 SHA1로 500번 해쉬하여 이걸 초록색 문자열로 표시해준다.

결론적으로 이 문제에서 해결해야하는 것은 초록색 문자열(SHA1으로 500번 해쉬된 세션변수 "chall4"의 값)을 가지고 해쉬되기 이전의 원본 문자열을 찾아서 입력창에 넣어야 하는 것이다.
하지만 문제는, 이론상 SHA1는 단방향 암호화 알고리즘이기 때문에 해쉬된 문자열만으로는 일반적으로 복호화할 수 없다.

그래서 우리는 레인보우테이블을 이용하여 해쉬된 문자열의 원본 값을 찾아내야한다.

- 레인보우테이블이란?

레인보우테이블은 쉽게 말해서 나올 수 있는 모든 경우의 수의 해쉬 원본값을 모아놓은 컨닝페이퍼 같은거다. 그런데 이걸 어디서 구하냐? 사실 이건 구한다기 보단 만들어내야하는거다(가끔씩 특별한 경우엔 인터넷에 돌아다니는 레인보우테이블이 있긴하다). 이번 문제같은 경우엔 원본 문자열이 10000000 ~ 99999999 사이의 랜덤 숫자와 "salt_for_you"라는 문자열이 결합된 형태인데, 그렇다면 원본값이 나올 수 있는 경우의 수는 총 90000000(9천만) 가지이다. 이건 도저히 사람이 운으로 때려 맞출 수 있는 수준의 양이 아니다(9천만 분의 1의 확률에 도달할 수 있다면 사실 아무 숫자나 넣고 맞을 때까지 돌리면 문제를 풀 수도 있긴하다).

그래서 우리는 약간의 툴을 만들어서 사용할 것이다.
이번엔 오랜 시간동안 수 억번의 반복 작업(기본 9천만번에 SHA1 500번 해싱이 곱해지기 때문에 최대 반복 횟수는 450억번이다)을 돌려야하기 때문에 사용중인 컴퓨터의 컴퓨팅 파워가 어느정도 필요하니 참고바란다. 물론 2천만 ~ 3천만 가지의 경우의 수들만 구해도 문제를 풀 수는 있는니 모든 경우의 수를 전부 구하진 않아도 된다 (필자의 경우 맥북에어 m1 8gb 모델로 36327562개의 경우의 수를 구하기 까지 2시간 정도 걸렸다)

- 문제 해결을 위한 툴 제작

빠른 해쉬값 검색을 위해서 DB를 사용하는 경우도 있지만 필자는 귀찮기 때문에 텍스트 파일에 경우의 수를 덤프해서 grep 명령어를 이용해 해쉬값을 검색하여 찾을 계획이다.

필자의 경우, 연산시간을 조금이라도 줄이기 위해 10000000 ~ 99999999의 범위를 8개의 구간으로 자른뒤, 서브 프로세스를 8개를 생성하여 구간 별로 병렬 계산이 가능하도록 했다. 자신의 PC 성능에 맞춰서 서브 프로세스의 개수를 조절할 필요가 있다.

위 코드를 실행하면 생성된 서브 프로세스의 개수만큼 텍스트 파일들이 생성될 것이다. 어느정도 문제의 답을 구하려면 2천만 ~ 3천만 정도의 경우의 수는 구해야하기 때문에 (3천만개의 경우의 수를 구하면 3분의 1의 확률로 정답을 맞출 수 있다) 연산과정이 어느정도 진행될 때까지 기다림이 필요하다.

$ cat ./sha1_*.txt | wc -l

현재까지 구한 경우의 수의 개수는 위 명령어로 확인이 가능하다. 파일이 여러개로 분할되어있기 때문에 파일 이름에 와일드카드 넣어야한다.

grep {찾고자 하는 해쉬값 (초록색 문자열)} ./sha1*.txt

예시:
$ grep 55393e831308935b856fe41d74f18f3f6ed04718 ./sha1*.txt

해쉬된 값의 원본값을 찾은 화면

그리고 어느정도 연산이 진행되었다면 grep 명령어로 찾고자 하는 해쉬값(초록색 문자열)을 검색하면 된다. 만약에 검색결과가 없을 경우, 문제 페이지를 새로고침해서 새로운 문자열을 받아온 뒤 재검색을 수행하면 된다. 그러다보면 분명 하나쯤 검색이 되는 경우가 생길 것이다.
만약에 검색결과가 뜬다면 원본 문자열 부분을 복사해서 입력창에 붙여넣은뒤 submit하면 된다