[Pwnable.kr] collision

Description

Daddy told me about cool MD5 hash collision today.
I wanna do something like that too!

ssh col@pwnable.kr -p2222 (pw:guest)

Solution

이 문제는 입력값이 아닌 인자를 계산해서 hashcode 값과 비교하는 문제이다.

int res = 0;
char str[20] = "";
for (int i=0; i<5; i++) {
    res += str[i];
}
if (res == 0x21DD09EC)

인자 문자열은 20 byte 이고 앞에서부터 4 byte씩 더한다.
문자열을 (int)로 변환하면 ASCII Code가 된다.
또한, 리틀엔디안 c언어로 재구성해서 테스트 해보았을 때 리틀엔디안 방식으로 계산된다.
예를 들어, "ABCD"가 입력했을 때, (int *)로 변환한다면 0x67666564 가 된다.

 

int는 4byte 크기의 자료형이기 때문에 1byte가 입력할 수 있는 최소 값 0x21(!)를

다섯 번 더한 0xa5 보다 작을 경우 오버플로우시켜 값을 구한다.
오버플로우시키는 방법은 int 자료형에 0xFFFFFFFF 에 1을 더하면 0x100000000지만

4byte밖에 저장하지 못하기 때문에 0 이 된다.

 

이를 이용하여 첫번째 바이트는 0x21로 0xaf보다 작기 때문에 0x121로 생각하고

5로 나눈 값에 해당하는 문자(chr(0x121//5) 4개와 5로 나눈 값에

나머지 값을 더한 값에 해당하는 문자(chr(0x121//5+0x121%5)) 1개로 구성하면 된다.

 

두번째 바이트인 0xDD는 세번째 바이트에서 오버플로우시켜 0x109로 계산할 것이기 때문에 0xDC로 계산한다.

 

따라서, 위의 조건을 따라 1byte씩 나누어 계산해보면 다음과 같은 코드로 hashcode를 만족하는 문자열을 구할 수 있다.

arr = [ [] for i in range(4) ]
arr[0] = [ chr(0x121//5) for i in range(5) ]
arr[0][0] = chr(0x121//5+0x121%5)
# 3번째 byte가 오버플로우로 0x109이기 때문에 0xDD가 아닌 0xDC로 계산한다.
arr[1] = [ chr(0xDC//5) for i in range(5) ]
arr[1][0] = chr(0xDC//5+0xDC%5)
arr[2] = [ chr(0x109//5) for i in range(5) ]
arr[2][0] = chr(0x109//5+0x109%5)
arr[3] = [ chr(0xEC//5) for i in range(5) ]
arr[3][0] = chr(0xEC//5+0xEC%5)

for i in range(5):
    for j in range(4):
        print(arr[3-j][i],end='')

출력: 05,=/5,9/5,9/5,9/5,9

 

FLAG

Two_hash_collision_Nicely