Stripe CTF level0

build.sh

#!/bin/sh
gcc -O3 -static -static-libgcc -fdata-sections -ffunction-sections -s -march=native level0.c -o level0 -Wl,--gc-sections

level0.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <unistd.h>

#include <stdint.h>
#include <sys/mman.h>
#include <fcntl.h>

#define BUILD_DB

#ifndef HACH_TABLE_MAX
  #define HACH_TABLE_MAX 196608
#endif

typedef uint64_t uintHash_t;
#define USED_BITS 64

#ifdef BUILD_DB
inline static unsigned int jenkins_one_at_a_time_hash_lower(char *key, unsigned int len)
{
    uint32_t hash, i;
    for(hash = i = 0; i < len; ++i)
    {
        hash += key[i] | 0x20;
        hash += (hash << 10);
        hash ^= (hash >> 6);
    }
    hash += (hash << 3);
    hash ^= (hash >> 11);
    hash += (hash << 15);
    return hash;
}


inline static unsigned int DJBHashLower(char* str, unsigned int len)
{
   register unsigned int hash = 5381;
   unsigned int i    = 0;

   for(i = 0; i < len; str++, i++)
   {   
      hash = ((hash << 5) + hash) + (*str | 0x20);
   }   

   return hash;
}


inline static uint32_t hash_str(const void *key, int len, unsigned int (* hashfunc)(char *, unsigned int))
{
    return hashfunc((char *)key, len) % (HACH_TABLE_MAX*USED_BITS);
}


void build_db(const char *file)
{
    FILE *fd = fopen(file, "r");
    FILE *out_fd = fopen("build.db", "w+");

    size_t filesize;
    int i, j;
    char buffer[2048];

    if (!fd) {
        printf("Cant open file %s\n", file);
        return;
    }

    fseek(fd, 0L, SEEK_END);
    filesize = ftell(fd);
    fseek(fd, 0L, SEEK_SET);

    char *dict_content = (char *)malloc(filesize+1);
    uintHash_t *out = (uintHash_t *)malloc(HACH_TABLE_MAX * sizeof(uintHash_t));

    memset(out, 0, HACH_TABLE_MAX * sizeof(uintHash_t));

    if (fread(dict_content, 1, filesize, fd) != filesize) {
        return;
    }

    dict_content[filesize] = '\0';

    int nop = 0;

    for (i = 0, j = 0; i < filesize; i++) {
        if (dict_content[i] != '\n') {
            buffer[j] = dict_content[i];
            if (dict_content[i] < 0x61) {
                nop = 1;
            }
            j++;
        } else {

            if (!nop) {
                buffer[j] = 0;
                uint32_t key = hash_str(buffer, j, jenkins_one_at_a_time_hash_lower);
                uint32_t key2 = hash_str(buffer, j, DJBHashLower);

                /* Get bit position */
                int pos = key/USED_BITS;
                int bit = key%USED_BITS;

                int pos2 = key2/USED_BITS;
                int bit2 = key2%USED_BITS;

                out[pos] |= 1LL << bit;
                out[pos2] |= 1LL << bit2;
            }
            j = 0;
            nop = 0;
        }
    }

    fwrite(out, sizeof(uintHash_t), HACH_TABLE_MAX, out_fd);

    fclose(out_fd);
    fclose(fd);

    //printf("Db built !\n");
}
#endif

inline static uintHash_t *read_db()
{
    int fd = open("build.db", O_RDONLY);
    void *out;

    if (!fd) {
        printf("Cant open file %s\n", "build.db");
        return NULL;
    }

    out = mmap(NULL, HACH_TABLE_MAX*sizeof(uintHash_t), PROT_READ, MAP_SHARED, fd, 0);

    return (uintHash_t *)out;
}

int main(int argc, char **argv)
{
    char *dict;
    size_t filesize = 4096*4;
    char buffer[64];
    size_t i, j;
    int nop = 0, maj = 0, posOut = 0;
    uint32_t key = 5381, key2 = 0;

    char input[filesize];
    char output[filesize];


    dict = argc > 1 ? argv[1] : strdup("/usr/share/dict/words");
#ifdef BUILD_DB
    build_db(dict);
#endif

    uintHash_t *out = read_db();

    register int charin;
    size_t r = 0;
    i = 0, j = 0;


    r = read(0, input, filesize);

    input[r] = 0;

    for (i = 0; i < r; i++) {
        charin = input[i];

        if (charin != ' ' && charin != '\n') {
#if 1
            if (charin < 65 || charin > 122 || (charin > 90 && charin < 97)) {
                nop = 1;
            } else if (charin < 90 && j > 0) {
                maj = 1;
            }
#endif
/*
            Incremental hash (DJB + jenkins) (avoid calling hash function on the buffered word)
            "fast" lower case by just setting the bit 1 << 0x20
*/
            key = ((key << 5) + key) + (charin | 0x20);
            key2 += charin | 0x20;
            key2 += (key2 << 10);
            key2 ^= (key2 >> 6);

            buffer[j] = charin;
            j++;
        } else if (j > 0) {
            key2 += (key2 << 3);
            key2 ^= (key2 >> 11);
            key2 += (key2 << 15);

            key2 %= (HACH_TABLE_MAX*USED_BITS);
            key %= (HACH_TABLE_MAX*USED_BITS);

            int pos = key/USED_BITS;
            int bit = key%USED_BITS;

            int pos2 = key2/USED_BITS;
            int bit2 = key2%USED_BITS;


            if (!nop && !maj && ((out[pos]) & (1LL << bit)) && ((out[pos2]) & (1LL << bit2))) {
                buffer[j] = charin;
                memcpy(output+posOut, buffer, j+1);
                posOut += j+1;
            } else {
                output[posOut++] = '<';

                buffer[j] = '>';
                buffer[j+1] = charin;

                memcpy(output+posOut, buffer, j+2);

                posOut += j+2;
            }

            j = 0;
            nop = 0;
            maj = 0;
            // Reset DJB constant
            key = 5381;
            key2 = 0;
        } else {
            output[posOut++] = charin;
        }
    }

    output[posOut] = 0;

    write(1, output, posOut);

    return 0;
}