2014 동계 해킴캠프 미니 CTF - 출제 실패한 문제

서버 상 문제로 출제가 안됬다고 들었습니다 ㅠㅠ 아쉽네요.

이번 문제는 HashDOS 컨셉의 문제인데, HashDOS가 어떤 원리인지에 대한 문제입니다.

해시 테이블을 이용할 때 주의할 점은, 해시 충돌이 일어날 때 어떻게 처리할지, 그리고 해시값 연산의 속도에요.

이번 문제의 컨셉은 "해시테이블 + 링크드 리스트" 에서 해시가 충돌할 때 HashDOS가 발생할 수 있다! 라는 컨셉이에요. 문제 자체를 강조하기 위해 코드는 제공하려고 했구요!

코드는 아래와 같아요.

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

struct table {

    char *src;

    int len;

};

struct linked {

    struct table *tb;

    struct linked *next;

};

struct linked *hashtable[65536];

void register_table(unsigned short hash, struct table *tb) {

    struct linked *link;

    int depth = 0;

    if(tb!=NULL)

        printf("Registering table - hash: %d, length: %d\n", hash, tb->len);

    if(hashtable[hash] != NULL) {

        link = hashtable[hash];

        struct linked *header = link;

        struct linked *tmp = header;

        if(link->next != NULL)

            do {

                link = link->next;

            } while(link->next != NULL);

        link->next = (struct linked*)malloc(sizeof(struct linked));

        link = link->next;

        link->tb = tb;

        link->next = NULL;

        do {

            puts(tmp->tb->src);

            puts(link->tb->src);

            if(tmp->tb != NULL && tmp->tb->src != NULL)

                if(strncmp(tmp->tb->src, link->tb->src, tmp->tb->len)!=0) {

                    puts("depth increasing");

                    depth++;

                } else { break; }

        } while (tmp->next != NULL);

        if(depth > 100) {

            puts("Key is HashDOS_art");

        }

    } else {

        link = (struct linked*)malloc(sizeof(struct linked));

        link->tb = tb;

        link->next = NULL;

        hashtable[hash] = link;

    }

}

unsigned short compute_hash(char *buf, int len) {

    unsigned short hash_value;

    hash_value = 0;

    if(buf == NULL) return 0;

    while(len>0) {

        hash_value = hash_value * 501;

hash_value ^= *buf ^ 100;

        len--;

    }

    return hash_value;

}

void process_table(char *buf, int len) {

    char *pr_buf=buf;

    struct table *my_table=NULL;

    unsigned short hash = 0;

    if(buf == NULL) return;

    pr_buf = buf;

    while(len) {

        switch(*buf) {

            case '=':

                puts("oh, what a value!");

                if(my_table==NULL) {

                    hash = compute_hash(pr_buf, buf - pr_buf);

                    my_table = (struct table*) malloc(sizeof(struct table));

                    my_table->src = pr_buf;

                    pr_buf = buf;

                }

                break;

            case '&':

                if(my_table!=NULL) {

                    my_table->len = buf-pr_buf;

                    register_table(hash, my_table);

                    my_table = NULL;

                    pr_buf = buf + 1;

                }

                break;

        }

        buf++;

        len--;

    }

    if(my_table!=NULL) {

        my_table->len = buf-pr_buf;

        register_table(hash, my_table);

        my_table = NULL;

        pr_buf = buf + 1;

    }

}

int main() {

    char *buf;

    unsigned int len;

    puts("Do you know HashDOS?");

    puts("Giv me length, plz");

    printf(">> ");

    scanf("%d", &len);

    printf("ok, length is %d\n", len);

    if(len>100000) {

        puts("Too large!");

        exit(1);

    }

    buf = (char*)malloc(len+1);

    if(buf == NULL) {

        puts("malloc error");

        exit(1);

    }

    memset(buf, 0, len+1);

    puts("Give me your table");

    read(0, buf, len);

    process_table(buf, len);

}

네, 해쉬 충돌이 100번 이상 일어나면 키를 출력해요.

키는 바꾼 상태로 코드가 제공될 예정이었죠.

음.. 풀이를 올려보자면 compute_hash 함수가 보이는데 이 함수를 분석해서 같은 해쉬값이 여러개 나오게 하면 되구요. 해쉬값은 아래의 형식 중 "이름"값들에서 구해져요.

이름=값&이름다른거=값다른거&...

이런식으로 넣을 수 있죠.

후후.. 출제되면 난이도가 어땠을지 궁금하네요!