[pwnable.kr]collision write up

문제 정보

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

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

문제

문제에 들어가서 ls -l를 사용하여 문제파일을 보면 이렇게 되어 있다.

col.c의 코드는 이렇게 되어 있다.

#include <stdio.h>
#include <string.h>
unsigned long hashcode = 0x21DD09EC;
unsigned long check_password(const char* p){
        int* ip = (int*)p;
        int i;
        int res=0;
        for(i=0; i<5; i++){
                res += ip[i];
        }
        return res;
}

int main(int argc, char* argv[]){
        if(argc<2){
                printf("usage : %s [passcode]\n", argv[0]);
                return 0;
        }
        if(strlen(argv[1]) != 20){
                printf("passcode length should be 20 bytes\n");
                return 0;
        }

        if(hashcode == check_password( argv[1] )){
                system("/bin/cat flag");
                return 0;
        }
        else
                printf("wrong passcode.\n");
        return 0;
}

분석

일단 문제 정보를 보면 md5 hash collision에 대한 내용이 있다. 그리고 문제 코드를 보면 hashcode가 있다. 그렇기 때문에 hash와 hash collision에 대해 알아보도록 한다.

hash 즉 해시 함수란 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다.
hash collision 즉 해시 충돌은 해시 함수가 서로 다른 두 개의 입력값에 대해 동일한 출력값을 내는 상황을 의미한다.

이번에는 코드를 분석해 본다.

col.c

코드를 분리해서 분석하기로 한다.

// ...중략...
int main(int argc, char* argv[]){
        if(argc<2){
                printf("usage : %s [passcode]\n", argv[0]);
                return 0;
        }
        if(strlen(argv[1]) != 20){
                printf("passcode length should be 20 bytes\n");
                return 0;
        }

        if(hashcode == check_password( argv[1] )){
                system("/bin/cat flag");
                return 0;
        }
        else
                printf("wrong passcode.\n");
        return 0;
}

일단 main함수를 보면 if문에서 argc로 인자를 확인한다. 2미만이면 passcode를 입력하라는 문구가 나온다(usage : %s [passcode]). argv로 입력을 받는데 길이가 20이 아니면 passcode의 길이가 20byte이다 라는 문구가 나온다.(passcode length should be 20 bytes)
그리고 나서 입력값을 check_password 함수에 넣은 뒤 그 리턴값과 hashcode와 비교한다. 만약 같으면 flag를 출력한다. 그리고 두 값이 다를 경우 "wrong passcode"라고 출력한다.

unsigned long hashcode = 0x21DD09EC;
unsigned long check_password(const char* p){
        int* ip = (int*)p;
        int i;
        int res=0;
        for(i=0; i<5; i++){
                res += ip[i];
        }
        return res;
}

hashcode는 0x21DD09EC로 고정되어 있다.
check_password함수의 리턴값을 hashcode와 비교하기도 하고, 입력값의 길이가 hashcode와 같은 unsigned long 으로 리턴되는 것으로 봤을 때 이 함수가 바로 hash함수다.

이제 hashcode를 복호화하면 된다. 하지만 이건 해시함수라서 복호화가 불가능한다. 해시 함수의 가장 큰 특징을 단방향 암호이기 때문에 암호화하는 건 가능하지만 복호화는 불가능하다.
그렇기 때문에 복호화 대신 hash collision 즉 출력값이 같은 입력값을 구하면 된다.
check_password 함수의 가장 눈에 띄는 건 입력받을 때는 const char형로 받는데 그것을 int형으로 바꿔서 int* ip에 넣는다.
char형의 크기는 1byte이고, int형의 크기는 4byte이다.
표로 설명하면 이렇게 된다.

char1	char2	char3	char4	char5	char6	char7	char8	char9	char10	char11	char12	char13	char14	char15	char16	char17	char18	char19	char20
A	A	A	A	B	B	B	B	C	C	C	C	D	D	D	D	E	E	E	E

이렇게 char형 에서 int형으로 변한다.

int1	int2	int3	int4	int5
AAAA	BBBB	CCCC	DDDD	EEEE

이런 식으로 int형으로 변한 값 5개를 다 더했을 때 hashcode 값인 0x21DD09EC가 나오면 flag를 획득할 수 있다.

코드를 변조해서 int 들어가는 값을 확인해 보면 값이 반대인 것을 볼 수 있다. 그 이유는 리틀엔디언이라 저장 순서가 반대로 되어 있는 것이다.

나는 직접 계산해서 값을 찾았다.
내가 찾은 입력값은 바로 이것이다. 2@@@20p@40p@"0p029L0
2라는 문자 0x32라는 hex 값을 같고 @는 0x40, 0은 0x30, p는 0x70, 4는 0x34, "는 0x22, 9는 0x39, L은 0x4C라는 hex값을 가진다.
저 입력값을 계산해 보면 0x21DD09EC가 나온다. 그래서 flag를 획득할 수 있다.

$ ./col 2@@@20p@40p@\"0p029L0

daddy! I just managed to create a hash collision :)