Basic password cracking (MD5, SHA1, ..)

기본적인 password cracking과 같은 문제를 CTF에서는 종종 접할 수 있다. 과거에도 비슷한 코드를 작성했었지만 메모리 초과로 인해서 포기하곤 했는데 우연히 검색을 하다가 알게된 부분이 있어서 공유해보고자 한다. 

 

기본적으로 

 

   - MD5 : 32-bit hex digits

   - SHA1 : 40-bit hex digits

   - SHA256 : 256-bit hex digits

 

우선, 일부 문자열은 제공되어 있고 숫자만 padding하여 해쉬 값을 계산하는 것은 아래와 같다. 예제에서 주어진 것 처럼 실제 0000부터 9999까지 숫자만 붙여서 주어진 hash 값을 비교하는 것이므로 해당 예제는 상당히 간단하다.

 

import hashlib

prefix = "CTF-TEST-"

match = "bf9e167d0f5d634713a933c8a7ff073653eef1d"

for i in range(0, 10000):
  pad = str(i)

  original = prefix + pad.zfill(4)
  
  # hashlib.md5, hashlib.sha1, and etc.
  result = hashlib.sha256(original.encode()).hexdigest()
 
  if match == result:
    print("Match found!", original)
    break
 

 

만약, 패스워드가 될 수 있는 ASCII 코드에서 해쉬 값을 비교하자 한다면 파이썬에서 제공하는 itertools을 사용할 수 있다. itertools에서 제공하는 product 함수를 사용하여 Brute-force를 위한 데이터를 준비한다. 그 코드는 아래와 같다. 

 

import itertools
import hashlib

arr = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L',
'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z',
'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o',
'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', '-', '1', '2', '3', '4', '5',
'6', '7', '8', '9', '0']

match = "737c191aed52450b9c655083c9971bdd"
start = int(input("Enter start: "))
end = int(input("Enter end: "))

for i in range(start, end):
    nPr = itertools.product(arr, repeat=i)
    for elem, r in enumerate(nPr):		# IMPORTANT
        result = hashlib.md5(''.join(r).encode()).hexdigest()
        print(result)
        if result == match:
            print('match', ''.join(r))
            break

 

참고로, 위의 코드에서는 쉽게 설명하기 위해서 특수 기호는 '-'만 포함했다. 모든 원소에 대해서 product를 수행한 후 실제 MD5값을 비교하는 구문에서 enumerate형으로 반복문을 수행하고 있다. 나는 해당 구문을 처음에

for elem in list(nPr)로 작성했었는데 이렇게 하면 product 함수에서 사용되는 repeat parameter의 값이 5만 넘어가도 컴퓨터는 동작을 멈추게 된다. 기하급수적인 연산의 수행으로 인해서 말이다.

 

쉽게 말해서 list함수를 호출하지 말자가 주요 골자이다.

 

Stack Overflow에 참고할 만한 링크는 아래와 같다.

stackoverflow.com/questions/31303610/memoryerror-while-trying-to-using-itertools-permutations-how-use-less-memory