[Toddler's Bottle] collision write-up

Toddler's Bottle의 두번째 문제 collision이라는 문제를 풀었다.

Daddy told me about cool MD5 hash collision today. 라고 해서 해시 충돌 공격에 관한 문제인듯 했다. 그래서 열심히 구글링을 했고 얻은 결과는 MD5는 MD4를 대체하기 위해 나왔고 노트북 한 대의 계산 능력으로 1분 내에 해시 충돌을 찾을 정도로 빠른 알고리즘이 되었다는 사실 정도..?

이 해시 충돌이라는 것은 서로 다른 두 입력값에 대해 동일한 출력값을 내는 상황을 의미한다. 해시 함수가 무한 가짓수의 입력값을 받아 유한한 가짓수의 출력값을 생성하는 경우, 비둘기집 원리에 의해 해시 충돌은 항상 존재한다.

https://ko.wikipedia.org/wiki/%ED%95%B4%EC%8B%9C_%EC%B6%A9%EB%8F%8C

위 내용을 공부해봤지만 어떻게 공격을 해야될지 생각이 나지 않았고 직접 바이너리의 소스 코드를 확인했다.

argv[1]의 값을 포인터 변수 ip에 넣고 res 변수에 5번 더해준뒤 res의 값을 반환한다. 그 후 hashcode와 같다면 cat flag로 플래그 값을 출력해준다.

풀이는 간단하다.

hashcode 0x21dd09ec를 5번 일정한 값을 더해 res에 넣어주면 되는 문제이다.

많은 방법이 있겠지만 계산기를 이용해서 5로 나눠보았다.

0x6c5cec8 이라는 숫자가 나왔고 정확한지 나머지값은 없는지 확인하기 위해 곱하기 5를 해보았다.

이렇게 원했던 결과가 나오지 않았고 나머지값 4가 나온다는 것을 확인하여 0x6c5cec8 을 4번, 0x6c5cec8 + 4 한 값을 1번으로 넘겨줬다.

./col `python -c 'print "\xc8\xce\xc5\x06"*4+"\xcc\xce\xc5\x06"'`

이렇게 넘겨주니 flag 파일을 열어볼 수 있었다.