SHA1, 레인보우 테이블, 파이썬 multiprocessing

300점짜리를 이번에 한번 도전해보았다! 4번 문제다!! view-source를 눌러보았다.

view-source

 

php 코드가 있다. 해시 암호인 sha1과 관련이 있네? 자세히 분석해보면 암호문은 10000000과 99999999사이의 랜덤한 숫자와, "salt_for_you"라는 문자열을 concat 하고, 그 결과에 대해 500번 sha1을 적용해 암호화를 시킨 결과다. 이때 나온 결과가, 앞서 나온 페이지에 적혀있던 문자들이다. 그리고 이 문자열이 어떠한 문자열을 500번 sha1 암호화 했을 때 나오는 결과인지 맞춰야한다.

 

그러면 즉, sha1에 의해 암호화된 문자열을 복호화 하라는 뜻인데, 아니 sha1이 해시암호이고 해시 암호는 단방향 암호, 즉 oneway function인데 어떻게 복호화를 하란 말인가...처음에 오해하다가

원래의 문자열은 랜덤한 숫자와 salt_for_you로 이루어진 문자열이므로, 랜덤한 숫자만 찾으면 된다는 결론에 이르러, 결국 완전한 복호화를 진행 하라는게 아니고, 어느 정도의 힌트는 있는 상태니 충분히 구할 수는 있겠구나라는 생각이 들었다.

 

하튼, 그래서 어떻게 구할까 고민을 해보았다. 우선 그냥 10000000과 99999999 사이의 모든 경우를 다 구해서 저 위에 나온 문자열과 같은지 대조해보고 같으면 그 숫자를 출력하는 방식으로 하려고 했다.

 

 

 

 

 

 

밑에와같이 코드를 짰는데, 이렇게 하면 생기는 가장 큰 문제점이 결과가 나오기까지 기다리다가 로그인이 만료되는데, 세션유지가 안되면 새로운 문자열에 대해 다시 프로그램을 돌려야하는 가장 큰 문제가 있었다.

from hashlib import sha1


string="3af2b23a68b3a92a5ead35d8dfd486e0ee7c94b5"
entire = ""
k=10000000

while k<100000000:

    entire=str(k)+"salt_for_you"

    i=0
    while i<500:
        entire = sha1(entire.encode('utf-8'))
        entire=entire.hexdigest()
        i=i+1;

    if(entire)==string):
            print ("RANDOM NUM IS: ",k)
            break
    k=k+1;
          

(아 그리고 파이썬에서 sha1 암호화를 구현하려면  hashlib를 사용하면 되고, encoding해준 다음에 sha1 함수를 적용해주고, 또 그에 대해서 hexdigest()를 해주면 된다. 사실 이렇게 간단하게 sha1 암호화를 해줄 수 있으므로 파이썬을 사용했다.)

 

 

 

 

그래서 레인보우 테이블을 만들어야겠다는 생각을 하게 됐다. 결국 모든 평문들에 대한 암호문을 다 저장하고, 암호문을 검색했을 때 평문을 바로 찾을 수 있도록.

f= open("rainbow"+str(id)+".txt",'w')
    entire = ""
    for k in range (start,end):
        print(k,"LOADING"+'\n')
        entire=str(k)+"salt_for_you"
        i=0
        while i<500:
            entire = sha1(entire.encode('utf-8'))
            entire=entire.hexdigest()
            i=i+1;

        f.write(str(k)+"IS"+entire+'\n');

    f.close()

그래서 나온게 대충 위와 같은 코드다. 이렇게 계속 코드를 실행시키며 일명 "존버"를 하고 있었는데, 감사한 선배 한분이 디엠으로 먼저 연락 오셔서 시간이 너무 오래 걸리면 멀티쓰레드로 만드는 것도 좋은 방법일 것 같다, 그런데 파이썬이면 멀티쓰레드로 했을 때 성능이 안나오니 파이썬 스크립트를 동시에 여러개 돌리면 된다, "GIL" 이라는 키워드를 던져주시고 가셨다...넘나 감사했다ㅜㅜ

 

 

그래서 자료 찾아보고 multiprocessing 모듈로 멀티 프로세스를 구현하는 방식으로 코드를 다시 고쳤다 (이제 최종코드 맞음..ㅎ)

from hashlib import sha1
from multiprocessing import Process, Queue




def work(id,start,end,result):

    f= open("rainbow"+str(id)+".txt",'w')
    entire = ""
    for k in range (start,end):
        print(k,"LOADING"+'\n')
        entire=str(k)+"salt_for_you"
        i=0
        while i<500:
            entire = sha1(entire.encode('utf-8'))
            entire=entire.hexdigest()
            i=i+1;

        f.write(str(k)+"IS"+entire+'\n');

    f.close()
    return 
          
if __name__ == "__main__":
    START, END = 10000000,100000000
    result = Queue()
    th1 = Process(target=work, args=(1, START, END//2, result))
    th2 = Process(target=work, args=(2, END//2, END, result))
    
    th1.start()
    th2.start()
    th1.join()
    th2.join()

 

 

이렇게 하고도 기다려보니, 컴퓨터가 기괴한 소리를 내며 속도도 너무 느려졌다ㅜㅜCPU를 엄청나게 괴롭히는듯 했다. 그래서 레인보우 테이블 전부를 완성하는건 사실상 불가능해보였다. 9천만개 이상에 대한 결과가 나올 테니...

 

 

일단은 계속 페이지 새로고침해서 레인보우 테이블에서 값을 찾아보고 하는 식으로 했고, 결국 레인보우 테이블을 모두 저장하지 않고도 문제를 풀 수 있었다.

 

 

 

 

rainbow2.txt 파일에서 값이 발견됐다. 즉 계속 멀티 프로세싱을 안했더라면 굉장히 늦게 발견했을 것ㅜㅜ

 

 

 

 

 

그래서 결국 앞에 있는 8자리 숫자인 57316432을 알아낼 수 있었고 뒤에 salt_for_you 까지 붙여 제출하고 300점을 얻을 수 있었다. 정말 재밌었다!!

 

---

[레인보우 테이블]

사실 문제 풀면서 해시 값을 모두 저장하는게 맞나...싶었는데 나중에 찾아보니 진짜 제대로 풀려면은 다 그렇게 풀어야하는 것 같더라...그렇다면 이 기회를 통해 레인보우 테이블에 대해 더 자세히 알아보자.

레인보우 테이블은 해시 함수를 이용해 만들어 낼 수 있는 해시 값들을 대량으로 저장한 표다. 

이번 문제를 풀며 느꼈듯이 만드는데 많은 시간이 걸리기 때문에 특성상 기업, 단체에서 주로 사용한다고 한다.

그리고 이러한 단점을 보완하고 레인보우 테이블을 작은 크기로 줄이는데 사용하기 위해 나온게 R(reduction) 함수라고 한다. 일정한 패턴이나 유사한 것들을 이용해 모든 값이 아닌, 특정한 값을 저장하는 방법!

 

도움이 될만한 링크는 해시넷.

wiki.hash.kr/index.php/%EB%A0%88%EC%9D%B8%EB%B3%B4%EC%9A%B0_%ED%85%8C%EC%9D%B4%EB%B8%94

 

 

[파이썬의 GIL]

monkey3199.github.io/develop/python/2018/12/04/python-pararrel.html

위 사이트 내용을 정리해 보았다. 좋은 자료 찾아주신 선배님도 땡큐...

 

파이썬에서 병렬 처리를 위해선 threading이나 multiprocessing 모듈을 사용해야한다.

Thread 함수로 구현하는 멀티 쓰레드의 경우, 파이썬에서는 하나의 쓰레드로 동작시킨 것과 쓰레드를 더 추가해 동작시킨것의 실행시간은 별반 다르지 않다.

 

이것은 GIL(Global Interpreter Lock) 때문인데, "파이썬에서는 하나의 프로세스 안에 모든 자원의 락(Lock)을 글로벌 하게 관리함으로써 한번에 하나의 쓰레드만 자원을 컨트롤하여 동작하도록 한다." 라고 한다.

한마디로 파이썬의 정책 때문에, 한번에 여러 쓰레드를 동시에 실행할 수 없다는 뜻이다.

 

다만, GIL이 적용되는건 cpu 동작이고 I/O 작업을 실행할때에는 다른 쓰레드가 cpu 동작을 동시에 실행할 수 있다고 한다.

---

이제 4300점이다! 곧 계절학기 기말고사 준비 때문에 바쁘겠지만 그전까지 문제 더 풀어야겠다!