문제
https://dreamhack.io/wargame/challenges/1124
문제 파일로 chall.py가 주어진다.
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())
코드 분석
사용자로부터 입력을 받아 각각 msg1, msg2에 저장하고, 각각의 값이 다르고 각 해시값 중 5자리가 일치하면 flag를 출력해준다.
값이 다른데 해시값이 같다고? 바로 hash colision이 생각난다. hash colision에서 중요하게 다뤄지는 이론이 Birthday Paradox이다. Birthday Paradox란, 모임에서 생일이 같은 두 사람을 찾는데 필요한 인원의 수가 직관과 달리 생각보다 적다는 것이다. 예를 들어 한 반에 30명의 학생들이 있다고 했을 때, 그 반 안에서 생일이 같은 학생쌍이 존재할 가능성이 무려 70% 이상이나 된다. 다음은 n명의 사람들의 생일이 모두 다를 확률을 구하는 식이다.
$$ \prod_{i=1}^{n-1} \left( 1 - \frac{i}{365} \right) $$
전체 집합의 크기를 $H$ 라고 하자. 위의 경우는 생일을 구하는 경우이기 때문에 $H = 365$이다.
이 중 n 개의 원소를 임의로 뽑았을때, 모든 원소 값이 다를 확률은
$$ \prod_{i=1}^{n-1} \left( 1 - \frac{i}{H} \right) $$
이다. $ i \ll H$ 라면 테일러 1차 근사를 이용해서 $ (e^{-x} = 1 - x + \frac{x^2}{2} - \cdots \approx 1 - x) $
$$ \prod_{i=1}^{n-1} \left( 1 - \frac{i}{H} \right) \approx \prod_{i=1}^{n-1} e^{-\frac{i}{H}} = e^{-\frac{n(n-1)}{2H}} \approx e^{-\frac{n^2}{2H}} $$
로 근사할 수 있다. 따라서 n개의 표본에 충돌쌍이 존재할 확률은 $ 1 - \frac{1}{e^{\frac{n^2}{2H}}} $이다. $ n = \sqrt{H} $일때 약 40%, $ n = 2\sqrt{H} $일때 약 86%의 확률로 충돌쌍이 존재한다.
보통 선택 평문/암호문 공격을 할 때 표본의 개수는 $ \sqrt{H} $ 정도가 되는 것이 가장 이상적이라고 한다. $ \sqrt{H} $ 보다 작으면 확률이 너무 적고, $ \sqrt{H} $ 보다 크면 충돌쌍을 찾기 위해 이미 너무 많은 쌍을 조사해야하기 때문이다.
익스플로잇
은 드림핵 정책에 따라 공개하지 않습니다,,
'dreamhack > crypto' 카테고리의 다른 글
[dreamhack] Double DES (0) | 2024.09.18 |
---|