[webhacking.kr] old-4번 문제

webhacking.kr old-4번 문제 풀이법입니다.
이번 문제는 Rainbow Table을 이용하여 풀 수 있습니다.

4번 문제의 메인 페이지입니다.
위에 인코딩 된 것으로 보이는 초록 문자열과 패스워드 입력란, 그리고 소스코드를 볼 수 있는 하이퍼링크를가 있습니다.
[view-source]를 클릭해 먼저 소스코드를 보도록 하겠습니다.

전체 소스코드입니다.
중요한 아래쪽 php 부분만 해석해봅시다.

	<?php
  sleep(1); // anti brute force
  if((isset($_SESSION['chall4'])) && ($_POST['key'] == $_SESSION['chall4'])) solve(4);
  $hash = rand(10000000,99999999)."salt_for_you";
  $_SESSION['chall4'] = $hash;
  for($i=0;$i<500;$i++) $hash = sha1($hash);
?>

세션 chall4의 값과 POST로 전달된 key의 값이 같으면 문제가 풀립니다.
hash 변수의 값을 (10000000~99999999 중 랜덤 숫자)+salt_for_you로 설정합니다.
처음 hash 변수의 값은 세션 chall4에 저장해두고, hash 변수의 값은 자신의 값을 sha1로 500번 인코딩한 값으로 바꿉니다.

Password로 입력한 곳의 내용이 POST method의 key 값으로 전달되므로 이곳에 초록 문자열을 500번 인코딩 하기 전의 값을 넣어주면 됩니다.
하지만 sha1은 역함수를 구할 수 없는 해시 함수이므로 Rainbow Table을 만들어 두고, 해시 값으로 원본 데이터를 찾아야 합니다.
여기서 Rainbow Table이란 해시 함수를 사용하여 변환 가능한 모든 해시 값을 저장시켜 놓은 표입니다.
따라서 우리는 (10000000~99999999 중 랜덤 숫자)+salt_for_you라는 원본 값과, 이를 sha1로 500번 인코딩한 해시 값을 저장하고 있는 Rainbow Table을 만들어야 합니다.
Rainbow Table을 생성하기 위해 아래와 같은 python 스크립트를 코딩했습니다.

	from hashlib import sha1
from multiprocessing import Process

START, END = 10000000, 100000000
PARTS = 10 #프로세스 개수
SIZE = (END-START)//PARTS

#hash_i.csv 파일에 (원본 값), (해시 값)의 형태로 저장
#hash_0.csv ~ hash_(PARTS-1).csv 파일에 나누어 저장
def rainbow(i):
	start = START + SIZE * i
	end = start + SIZE

	fname = 'hash_'+str(i)+'.csv'
	f = open(fname, 'w')
	for x in range(start, end):
		chall4 = _hash = str(x)+'salt_for_you'
		for y in range(500):
			_hash = sha1(_hash.encode('utf-8')).hexdigest()
		data = chall4+','+_hash+'\n'
		f.write(data)
	f.close()

if __name__ == '__main__':
	procs = []

	for i in range(PARTS):
		proc = Process(target=rainbow, args=(i,))
		procs.append(proc)
		proc.start()

	for proc in procs:
		proc.join()

Rainbow Table을 만들기 위한 연산이 많아 하나의 프로세스로는 시간이 매우 오래 걸리기 때문에 저는 프로세스 10개로 멀티 프로세싱을 돌렸습니다.
하루가 꼬박 걸리는 작업이 약 3시간 가량으로 단축되는 나름 괜찮은 속도가 나왔습니다.
이제 남은 작업은 여기서 얻어낸 Rainbow Table로 원본 값을 얻어내는 것입니다.
이 작업도 마찬가지로 python 스크립트로 코딩했습니다.

	from multiprocessing import Process

_hash = '' #해시 값(초록 문자열)을 입력
PARTS = 10 #csv 파일 개수

#csv 파일에서 해시 값을 찾으면 원본 값을 출력
def find(i):
	fname = 'hash_'+str(i)+'.csv'
	f = open(fname, 'r')
	while True:
		line = f.readline().strip()
		if not line:
			break
			
		data = line.split(',')
		if data[1] == _hash:
			print(data[0])
			break
	f.close()

if __name__ == '__main__':
	procs = []

	for i in range(PARTS):
		proc = Process(target=find, args=(i,))
		procs.append(proc)
		proc.start()

	for proc in procs:
		proc.join()

_hash 변수에 해시 값을 입력하면 csv 파일로 저장된 Rainbow Table을 읽어 이에 해당하는 원본 값을 출력해줍니다.
이렇게 얻은 원본 값을 Password 입력란에 입력하면 문제가 풀립니다.

Tip: 시간을 단축하는 방법
변환 가능한 모든 값이 아니라 일부에 대해서만 테이블을 생성하면 문제를 푸는 시간을 단축할 수 있습니다.
일부만 테이블을 생성했을 때, 해시 탐색에 성공할 확률을 알아봅시다.
전체 값에서 테이블 생성에 사용된 값의 비율을 m, 해시 탐색 시도 횟수를 n이라고 하면 탐색에 성공할 확률 p(m,n)은 다음과 같습니다.
$p(m,n)=1-(1-m)^n$
이를 이용하여 두 가지 상황에 대한 탐색 성공 확률을 계산해 봤습니다.
m=0.1, n=30 일 때, 95.77%
m=0.2, n=15 일 때, 96.49%
본인의 PC 상황에 따라 이런 방법을 이용하는 것도 좋은 방법일 것 같습니다.