Webhacking.kr 04번 - Rainbow Table

4번 문제의 소스는 다음과 같음

POST메서드로 넘기는 "key" 값과 "chall4"값이 동일해야 함

"chall4"의 값은 10000000~99999999의 숫자중 랜덤하게 뽑은 값과 문자열 "salt_for_you"의 합.

(ex. 24120593salt_for_you, 59534952salt_for_you, ...등)

화면에 표시되어 있는 해쉬값은 "chall4"에 할당한 값을 500번 해쉬한 결과값

따라서, 화면에 표시되어 있는 해쉬값이 "chall4"의 어떤값으로 부터 계산되었는지 알면 문제해결

 

해쉬는 일방향 함수이므로, sha1 Dictionary(레인보우 테이블)를 만들어야 함.

파이썬으로 구현

#-*- coding:utf-8 -*-
#!/usr/bin/env python3

from hashlib import sha1

with open("c:\\users\\hackcatml\\desktop\\sha1_dict.txt", "w") as f:
    for i in range(10000000,99999999):
        k = 0
        res = (str(i)+"salt_for_you")
        while k < 500:
            res = sha1(res.encode('utf-8')).hexdigest()
            k = k+1

        f.write(res + ':' + str(i) + '\n')

print("it's over")

 

실행하는데, CPU 사용량이 고작 18%

(5천만개 테이블 만드는데 8시간 정도 걸렸음)

 

어떻게 하면 CPU를 최대한으로 사용 가능한가?

파이썬으로 멀티프로세싱 구현(concurrent.futures 모듈 사용)

#-*- coding:utf-8 -*-
#!/usr/bin/env python3

from hashlib import *
from concurrent.futures import ThreadPoolExecutor, ProcessPoolExecutor, as_completed

def worker(arg):
    with open(f"C:\\Users\\hackcatml\\Desktop\\sha1dict_{arg}.txt", "w") as f:
        for i in range(arg * 10000000, (arg + 1) * 10000000):
            k = 0
            res = (str(i) + "salt_for_you")
            while k < 500:
                res = sha1(res.encode('utf-8')).hexdigest()
                k = k + 1

            f.write(res + ': ' + str(i) + '\n')
       
def main():
    with ProcessPoolExecutor(max_workers=10) as executor:
        for arg in range(1, 10):
            executor.submit(worker, arg)

if __name__ == '__main__':
    main()

 

실행시 CPU 사용량 100% 찍음.

적당히 두시간 정도 돌리면 2천만개 테이블이 만들어짐(컴퓨터 성능에 따라 다름)

 

위 코드 실행시 .txt 파일이 9개 생기는데, cygwin을 이용하여 합치기를 수행

cygwin은 윈도우에서 리눅스 명령어를 사용하게끔 해주는 유용한 도구(https://www.cygwin.com/)

 

합치기 명령어:

cat sha1dict*.txt > sha1table.txt

 

문제 화면에 표시되어 있는 해쉬값을 테이블에서 검색하여 숫자와 salt_for_you를 합쳐서 제출하면 해결

(ex. 20401204salt_for_you)