[Dreamhack] 40 Birthdays

풀이

import hashlib

def birthday_hash(msg):
	return hashlib.sha256(msg).digest()[12:17]

msg1 = bytes.fromhex(input("Input message 1 in hex: "))
msg2 = bytes.fromhex(input("Input message 2 in hex: "))

if msg1 == msg2:
	print("Those two messages are the same! >:(")

elif birthday_hash(msg1) != birthday_hash(msg2):
	print("Those two messages don't have the same birthday! T.T")

else:
	print("Finally! They have the same birthday ^o^")
	print(open("flag.txt").read())

제공된 코드를 살펴보면 문제에서 다이제스트의 12부터 16까지 5 바이트를 떼어서 반환하는 birthday_hash를 사용한다. 여기서 나온 값이 동일한 충돌쌍을 찾아 입력하면 flag를 얻을 수 있는 문제이다.

 

문제에서 생일역설(Birthday paradox)가 나오는 것을 보고 이에 관해 알아보았다. 

생일 역설에 따르면, N이 가능한 값의 수일 때, 서로 다른 입력값 중 약 √N개 정도를 시도하면 두 값이 같은 해시 출력을 가질 확률이 높아진다고 한다.

여기서 5바이트 (40비트)에 대하여 충돌쌍을 찾기 때문에 N = 2**40 인데, 생일 역설에 따라 √N =2**20 정도를 시도하면 충돌쌍을 찾을 수 있을 것이다.

import hashlib

def birthday_hash(msg):
    return hashlib.sha256(msg).digest()[12:17]

l = [] 
s = set() # 빠른 검색을 위해 추가

for i in range(2**20): # sqrt(N) = 2**20까지 전수조사
    msg = str(i).encode()
    tmp = birthday_hash(msg)

    if tmp in s: # 해시값이 이전에 나온적 있는지 확인
        msg1 = msg
        msg2 = str(l.index(tmp)).encode() # 이전에 저장돼 있던 충돌값 불러오기
        break

    l.append(tmp)
    s.add(tmp) # 해시값을 리스트와 세트에 저장

if birthday_hash(msg1) == birthday_hash(msg2) :
    print("ok") # 충돌쌍이 맞는 확인
    
print("msg1:",bytes.hex(msg1).encode())
print("msg2:",bytes.hex(msg2).encode())

충돌하는 값 찾는 과정을 빠르게 진행하기 위해서 set을 이용하였다. 위 코드를 실행해보면 아래와 같은 결과를 확인할 수 있다. 

위의 값을 입력해주면 flag를 얻을 수 있다.