목표 : SHA1, 암호학 이해, 소스코드 독해, 코딩
1. 문제 파악
우선 입력이 있으면 뭐부터? SQL Injection부터.
치트시트를 몇 개입력을 돌려도 나오는 랜덤값만 바뀔 뿐, 별다른 변화는 없다.
친절하게 아래에 View Source가 있으니 소스코드를 확인해보자
<?php
include "../../config.php";
if($_GET['view-source'] == 1) view_source();
?><html>
<head>
<title>Challenge 4</title>
<style type="text/css">
body { background:black; color:white; font-size:9pt; }
table { color:white; font-size:10pt; }
</style>
</head>
<body><br><br>
<center>
<?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);
?><br>
<form method=post>
<table border=0 align=center cellpadding=10>
<tr><td colspan=3 style=background:silver;color:green;><b><?=$hash?></b></td></tr>
<tr align=center><td>Password</td><td><input name=key type=text size=30></td><td><input type=submit></td></tr>
</table>
</form>
<a href=?view-source=1>[view-source]</a>
</center>
</body>
</html>
PHP
복사
2. 문제풀이
sleep(1); // anti brute force
PHP
복사
bruteforce로 무작위 대입을 막는 코드가 기본적으로 설정돼있고,
if((isset($_SESSION['chall4'])) && ($_POST['key'] == $_SESSION['chall4'])) solve(4);
PHP
복사
chall4의 세션값과 입력하는 key값이 동일하면 해결된다.
$hash = rand(10000000,99999999)."salt_for_you";
$_SESSION['chall4'] = $hash;
for($i=0;$i<500;$i++) $hash = sha1($hash);
PHP
복사
chall4의 세션값은 다음 메커니즘에 의해 생성된다.
1천만부터 1억-1 값 중에서 숫자 랜덤 값 + “salt_for_you” 문자열을 합친 hash 값을 sha1로 500번 암호화한 값이 chall4의 세션값과 동일해야한다.
그냥 9천만번 * 500 sha 돌려서 맞는 값 찾으면 되는거 아닌가?
그래서 실제로 돌렸다.
import hashlib
chall4 = "dacd5e34bff3fd270ef8d6a71ec79f3cf8ee61dd" #나타난 랜덤 세션값
for i in range(10000000,99999999+1):
hash = (str(i)+"salt_for_you")
for j in range(500):
chall4_2 = hashlib.sha1(hash.encode()).hexdigest()
if(chall4 == chall4_2):
print("{}".format(hash))
break
Python
복사
시간복잡도상 9천만 * 500 = 450억회 SHA1
알고리즘 공부하던 당시 10년 전에 보통 1억이 1초가 걸린다했으니 지금은 450초? 단순 더하기가 아닌 sha1니까 10배라 쳐도 75분이면 되네.
하고 밥이나 먹고왔지만 4시간째 끝이 안났다.
다른 방법이 있나했지만 단방향 해시값으로 돌아가는 코드에 소스코드까지 보여줬으니 이 방법이 맞겠지 싶었고,
멀티쓰레딩해야지 싶어서 찾다 다음 블로그의 코드를 참조했다.
수정사항
•
멀티쓰레드 개수를 늘렸으며
•
진행도를 확인할 수 있는 프린트 명령어를 넣었다 (프로그레스바 넣으려면 pip install해야해서 있는걸로 했다)
from hashlib import sha1
from multiprocessing import Process, Queue
def work(id, start, end, result):
f = open("sha_1_"+str(id)+".txt",'w')
print(id,start,end)
cnt = end - start
percent = 0
for i in range(start,end):
thash = str(i)+"salt_for_you"
temp = thash
for k in range(0,500):
thash = sha1(thash.encode('utf-8')).hexdigest()
data = temp+" - "+thash+"\n"
if (i-start)/cnt*100 > percent+1 and id==4:
percent = percent + 1
print("{}%".format(percent))
f.write(data)
f.close()
return
if __name__ =="__main__":
START, END = 10000000, 100000000
result = Queue()
gap = (END-START)//12
th1 = Process(target=work, args=(1, START, START+gap*1, result))
th2 = Process(target=work, args=(2, START+gap*1, START+gap*2, result))
th3 = Process(target=work, args=(3, START+gap*2, START+gap*3, result))
th4 = Process(target=work, args=(4, START+gap*3, END, result))
th1.start()
th2.start()
th3.start()
th4.start()
th1.join()
th2.join()
th3.join()
th4.join()
Python
복사
레인보우 테이블을 만들은 결과 텍스트로만 5.44GB, 12쓰레드 기준 1시간 정도 소요됐다.
어떤 값이 나오건 findstr 명령어(윈도우)를 통해 바로바로 찾을 수 있었으나 실제 대회나 이런 곳에서는 1시간이나 컴퓨터의 프로세스를 모두 투자할 수 없으므로 개선 방법이 없을까 고민했고
어차피 랜덤값 중 하나만 맞추면 되는거고 랜덤값은 계속 바뀌니까
1.
전체 범위의 10분의 1정도만 테이블을 구한다
2.
문제의 랜덤값을 바꾸면서 테이블에 있는 값인지를 찾아본다
3.
확률적으로 10번 정도면 찾는다.
로 모든 걸 컴퓨터에게 맞기기보다는 시행착오를 어느정도하는게 효율적이란 판단이 들었다.
︎ 더 많은 게시물을 보려면