> For the complete documentation index, see [llms.txt](https://docs.cooku222.kr/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://docs.cooku222.kr/security/crypto/dreamhack/dreamhack-40-birthdays.md). # \[DreamHack] 40 Birthdays #### 문제 링크 [ 40 Birthdays생일이 같은 두 친구를 찾아주세요! Exploit Tech: Birthday paradox에서 함께 실습하는 문제입니다.dreamhack.io](https://dreamhack.io/wargame/challenges/1124) #### 문제
#### #### Writeup ``` #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()) ``` -> 함수 birthday\_hash가 정의되어 있고, 서로 다른 두 메시지를 입력해, 같은 해시값을 가진다면 플래그를 획득할 수 있음 -> 해시함수 birthday\_hash는 SHA-256 함수를 32바이트로 나타내었을 때, 중간에 존재하는 5바이트만을 해시값으로 리턴함 5바이트는 40비트 -> 공역의 원소의 개수가 2^40인 함수 -> 비둘기집의 원리에 의해 2^40+1개의 메시지의 해시값을 구하면 충돌쌍이 무조건 생김을 보장할 수 있음 +but, 너무 오랜 시간과 많은 메모리를 소요해, 생일 역설을 통해 찾을 시 몇 개의 해시값이 필요한지 계산이 요구됨 \*30명의 생일이 모두 다를 확률 첫 번재 사람이 생일이 정해져 있는 상태에서 두 번째 사람의 생일을 결정한다고 생각하면? -> 365일 중에서 첫 번째 사람의 생일을 제외해야 하므로 364가지 선택지가 있고, 확률은 364/365 그렇다면 세 사람의 생일이 모두 다를 확률은? -> 먼저 두 사람의 생일이 다를 확률이 364/365인 상황에서 세 번째 사람의 생일을 골라야 함 365일 중 이미 선택된 2일을 제외해야 하기 때문에 363/365를 추가로 곱해야함(고등학교에서 배운 확률과 통계를 생각해보자)
\=> 30명의 생일이 전부 다를 확률
-> 계산하면 0.293... -> 다를 확률이니까 1-0.293... = 0.7 => 실제로 70% 이상의 확률로 생일이 같은 사람이 존재 해시 충돌을 위해 필요한 해시 연산의 수(공역의 원소 수가 N인 해시 함수에 대해) -> k개의 서로 다른 메시지의 해시값을 구했을 때, 서로 다른 해시값이 나올 확률?
k가 N보다 훨씬 작고 N의 값이 굉장히 클 때, 위 식을 계산하면 다음과 비슷한 값을 가짐
-> e = 2.7....(명칭 : 자연상수) \=> 따라서 k개의 표본에 충돌쌍이 존재할 확률은
\=> 계산하면 86% 익스플로잇을 설계하면, Python의 set 타입은 배열이 아닌 Hash table로 구현되어 있어, 삽입과 탐색에 짧은 시간이 소요(일반 배열은 전수 조사라서 오래 걸림) list에 해시값들을 저장한 후, 추가하면서 일일이 비교한다면, 한 원소당 리스트 전체와 한 번씩 비교해야 하기 때문에 O(N^2)의 시간이 소모됨. but, Hash Table을 사용하면 대부분의 상황에서 O(N)의 시간으로 해결 가능 ``` import hashlib from tqdm import trange def birthday_hash(msg): return hashlib.sha256(msg).digest()[12:17] hash_list = [] hash_set = set() for i in trange(2**21): msg = str(i).encode() result = birthday_hash(msg) if result in hash_set: msg1 = msg msg2 = str(hash_list.index(result)).encode() break hash_list.append(result) hash_set.add(result) assert birthday_hash(msg1) == birthday_hash(msg2) from pwn import * io = remote("host3.dreamhack.games", 14055) #본인에게 할당된 도메인 주소값 입력 io.sendlineafter(b": ", bytes.hex(msg1).encode()) io.sendlineafter(b": ", bytes.hex(msg2).encode()) io.interactive() ``` --- # Agent Instructions This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com. ## Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://docs.cooku222.kr/security/crypto/dreamhack/dreamhack-40-birthdays.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.