2. 충돌 (collision) - Pwnable.kr 해설

 

티스토리 블로그는 PC 환경에 최적화되어 있습니다.

모바일 유저분들은 아래 네이버 블로그를 이용해 주세요.

2. 충돌 (collision)

 

문제 내용

Daddy told me about cool MD5 hash collision today.

I wanna do something like that too!

 

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

 

 

들어가기 전

what is MD5 hash collision?

 

1. hash function(해시 함수)

해시 함수(hash function)는 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는함수입니다.

이러한 해시 함수의 특성 덕분에 전자서명, 무결성 검증, 난수 생성 등 다양한 부분에서 활용되고 있습니다.

 

2.hash collision (해시 충돌)

해시 충돌이란해시 함수가 서로 다른 두 개의 입력값에 대해 동일한 출력값을 내는 상황을 의미합니다.

임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 것이 해시 함수의 기능인데, 함수 설계상의 문제로 인해 서로 다른 데이터에 대하여 똑같은 해시 값을 출력하는 경우 해시 충돌이 일어났다고 합니다.

 

MD5도 해시 함수의 한 종류인데 여러 구조적인 취약점으로 인하여 해시 충돌을 일으키는 알고리즘이 만들어졌다고 합니다.

 

MD5에 대한 정보를 알고 싶으시면 아래 링크를 이용해 주세요.

MD5 - 나무위키

 

 

문제 해설

리눅스 터미널 화면을 열어서ssh col@pwnable.kr -p2222로 접속하고 pw인 guest를 입력하여 시작합니다.

​ ls 명령어를 이용해서 디렉터리 내용을 확인해보니 (터미널 창에 ls 입력 후 엔터)col col.c flag세 가지가 존재합니다.

​우선 확장자가. c인 col.c 파일을 읽어 봅시다. (터미널 창에 cat 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;
}

음 소스코드가 저번 문제에 비해 좀 길어졌습니다.

천천히 살펴보도록 하겠습니다.

 

 

int main(int argc, char* argv[]){
    if(argc<2){
        printf("usage : %s [passcode]\n", argv[0]);
        return 0;
   }

main 함수의 인자의 개수가 2개 이하면 문자열을 출력해버리고 프로그램을 종료시켜 버립니다.

main 함수의 인자와 관련된 내용은 저번 시간의 fd 문제에서 상세히 다뤘습니다.

(자세한 설명은 아래 링크를 이용해 주세요.)

1. 파일 디스크립터(FD)

 

main 문에 전달되는 인자의 개수가 최소 2개 이상이어야겠군요.

다음 코드로 넘어가 보도록 하겠습니다.

 

 

if(strlen(argv[1]) != 20){
        printf("passcode length should be 20 bytes\n");
        return 0;
   }

main 문에 전달된 2번째 인자인 argv[1]의 길이를 비교하여 20byte가 아니면 문자열을 출력하고 프로그램을 종료해 버립니다.

여기서 제가 착각한 점이 main 문의 인자인 argv[]는 char*형이므로 어떤 값을 전달하는 4byte로 처리한다는 포인터 내용을 착각했습니다.

 

여기서 정리해야 될 점은 char*는 배열의 시작 주소만 가지기에 char*의 크기는 4byte가 되지만, strlen 함수는 문자열의 길이를 반환합니다.

보다 직관적인 이해를 위해 아래 소스코드와 링크를 올립니다.

(이번 기회에 포인터, 배열을 제대로 정리해 두세요!)

#include <stdio.h>
#include <string.h>
 
int main() {
    const char *aasdf[5] = { "asdf1111","ICMP","asdflkjh"};
 
    printf("%d\n", sizeof(aasdf)); //20을 출력 (4byte * 5)
    printf("%d\n", sizeof(aasdf[0])); //4를 출력
    printf("%d\n", strlen(aasdf[0])); //8을 출력
    
}

C 언어 코딩 도장: 41.1 문자열 길이 구하기

 

[C언어] 문자열과 char 포인터, 문자열을 다룰때 하는 실수들

문자열 설명을 하니 이야기가 길어졌습니다.

다음 포인트로 넘어가 보겠습니다.

 

 

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

if 문에 main 문의 인자 argv[1]의 문자열을 check_password 함수에 넣어 나온 리턴 값이 hashcode와 같으면 flag를 출력하는 것 같습니다.

그럼 check_password 함수 원형을 확인해 보겠습니다.

 

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;
}

여기서부터는 검증되지 않는 내용입니다. 정확한 내용을 아시는 분들은 댓글로 피드백 부탁드립니다.

 

앞서 char* 배열은 문자열 시작 주소를 저장하기에 모든 배열의 크기가 4byte입니다.

그러나 char*는 데이터를 1byte밖에 못 읽지만 int*는 4byte를 읽을 수 있습니다.

아래 예시를 확인하면 이해하기가 훨씬 수월할 것입니다.

#include <stdio.h>
#include <string.h>
 
int main() {
    int i = 0x1234;
    int* p = &i;
    char* q = (char*)p;
    printf("%x %x %d", *p, *q,sizeof(*q));
    //각각 1234 34 1을 출력
}

여기서 *q가 34로 출력되는 이유는 컴퓨터가 자료를 리틀 엔디언 방식으로 저장하기 때문입니다.

리틀 엔디언 방식, 포인터의 형 변환에 대한 내용은 아래 링크를 이용하시면 보다 상세히 알 수 있습니다.

리틀 엔디안 VS 빅 엔디안

[C언어] 포인터(2) - 포인터의 형변환

 

C 언어 코딩 도장: 58.2 포인터 변환하기

 

 

다시 본론으로 돌아오겠습니다.

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* ip = (int*) p;는 포인터 형 변환을 하였으므로 char* p에 들어있는 값을 5등분 하겠다는 말입니다.

char* 1byte 4개를 int*로 변환하니까 위에서 언급한 argv가 조건문을 만족한다는 가정을 하면 20byte,

형 변환을 통해 20byte / 4byte = 5입니다.

이후 반복문을 통해서 5등분 한 값을 모두 더한 후 res로 반환합니다.

 

 

-만약 여기까지 보고 방법이 떠오르셨다면 아래 내용을 보지 말고 한 번 더 다시 풀어보세요!!!

그럼collision문제의 공략을 세워보도록 하겠습니다.

 

1.argv[1]에0x21DD09EC의 값을 임의로 5등분 나누어 넣어준다.

(어떻게든 5등분의 합이0x21DD09EC이기만 하면 됩니다. 단 전달되는 인자의 크기가 20byte 여야 합니다.)

 

0x21DD09EC = 568134124 = 0x06C5CEC8‬ * 4 + 0x06C5CECC

그러면 이 데이터를 파이썬에 리틀 엔디언 방식으로 넣어줍시다!!!

 

터미널 창에 다음과 같이 입력해 줍시다.

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

데이터를 16진수 리틀엔디언으로 넣어야 하기에 구분을 위한 메타 문자 \x와 순서를 지켜서 넣으면 됩니다.

 

python의 옵션인 -c, 메타 문자 \x에 대한 내용은 아래 링크를 참고해 주세요.

2. 파이썬 인터프리터 사용하기 — Python 3.8.2 문서

 

정규 표현식(Regex) 강좌 4편. 메타 문자(meta character)

 

 

터미널에 입력 후 flag가 출력된 모습입니다.

 

오늘 내용은 여기까지입니다.

다음 시간에는 collision을 풀어보도록 하겠습니다.

이상 ICMP였습니다!!

​