[Rubiya] webhacking.kr old-4번 문제 풀이

문제 페이지로 들어가보면, 해쉬값 같은 것과 입력 필드, 그리고 view-source라는 링크가 보인다.

 

일단 소스를 보자.

 

소스가 간단한데, 세션값에 저장된 값을 맞추면 된다.

 

만약 못맞춘 경우 랜덤값을 8자리 정수에 뒤에 "salt_for_you"라는 문자열을 붙인 뒤 sha1해쉬를 500번 한 뒤 세션값에 저장한다.

 

그리고 그 저장된 값을 보여준다.

 

그 저장된 값을 보고 그 값이 500번 sha1 해쉬가 되기 전 값을 알아내서 password에 입력하면 solve(4) 함수가 실행되면서 문제를 풀 수 있게 된다.

 

 

이 문제는 기존 webhacking.kr 문제에 조금 변형되어 난이도가 높아진 문제 중 하나인데, 랜덤값 8자리 정수이면 대충90,000,000 = 9천만이다.

 

보통 알고리즘 문제같은 것을 풀 때, 즉 Problem solving을 할 때 실행시간 측정을 1억번 루프를 도는데 1초 정도로 생각을 한다. 그에 비하면 9천만이면 0.9초 정도에 해당하는데

 

sha1함수를 500번 하기 때문에 0.9초 * 500 로 대충 계산하면 450초 정도가 된다.

 

물론 sha1함수는 단순 for-loop보다는 더 복잡하기때문에 10배 정도 복잡하다고 한다면 4500초 정도로 볼 수 있는데, 이는 1시간이 3600초임을 감안하면 2시간이 좀 안되는 시간이라고 볼 수 있다.

 

즉 모든 경우의 수를 다 해보는 레인보우 테이블을 만드는데 다소 무식해 보이긴 하지만, 시간적으로 해볼만 하다는 뜻이다.

 

용량적으로 따져보자.

 

90,000,000Byte는 90,000KB이고 90MB이다.

 

그리고 각 스트링 값과 해시값이 대충 200byte라고 쳐도 200*90MB = 18000MB = 1.8GB로 스토리지에 저장하기에도 부족함이 없고, 메모리에 올려도 가능하다.

 

고로 저 해쉬 값들을 모조리 만든 레인보우 테이블로 문제를 풀면 된다.

 

뭐 쓰레드를 사용하거나 해서 더 빠르게도 가능할 것이고, 스토리지에 Write하는 시간이 Bottle Neck이라면, 메모리에다가만 올리는 방식으로도 가능할 것이다.