HITCON CTF 2014, WTF6

birthday.cpp

#include <cstdio>
#include <cstring>
#include <cassert>
#include <cstdint>
#include <algorithm>
#include <queue>
#include <openssl/sha.h>

#define LOG(fmt, ...) \
    fprintf(stderr, "[%.2f] %s:%d - " fmt, 1.0 * clock() / CLOCKS_PER_SEC, \
            __func__, __LINE__, ##__VA_ARGS__);

const int N_BLOCK = 33;
const int MAX_DATA_LEN = 192;
const int MAX_PATH_LEN = 1024;
const int MEM_LIMIT = 1 << 30;

FILE* my_fopen(const char *path, const char *mode) {
    FILE *fp = fopen(path, mode);
    assert(fp != NULL);
    return fp;
}

void my_fwrite(const void *data, size_t size, size_t nitems, FILE *fp) {
    size_t num = fwrite(data, size, nitems, fp);
    assert(num == nitems);
}

struct Block {
    int len;
    uint8_t data[MAX_DATA_LEN];
    void load(const char *path) {
        FILE *fp = my_fopen(path, "rb");
        len = fread(data, 1, MAX_DATA_LEN, fp);
        fclose(fp);
    }
} block[N_BLOCK][2];

struct Elem {
    uint64_t idx, val;
    bool operator <(const Elem &o) const { return val < o.val; }
    void save(const char *path) {
        FILE *fp = my_fopen(path, "wb");
        for (int i = 0; i < N_BLOCK; i++) {
            int j = (idx >> i) & 1;
            my_fwrite(block[i][j].data, block[i][j].len, 1, fp);
        }
        my_fwrite("HITCON", 6, 1, fp);
        fclose(fp);
    }
};

const int N_ELEM = MEM_LIMIT / sizeof(Elem);
Elem elem[N_ELEM];

const int N_CHUNK = (1LL << N_BLOCK) / N_ELEM;

struct Chunk {
    FILE *fp;
    Elem e;
    void init(int cid) {
        LOG("init chunk %d\n", cid);
        char path[MAX_PATH_LEN];
        snprintf(path, MAX_PATH_LEN, "chunk_%d", cid);
        fp = my_fopen(path, "wb");
        std::sort(elem, elem + N_ELEM);
        my_fwrite(elem, sizeof(elem[0]), N_ELEM, fp);
        fclose(fp);
        fp = my_fopen(path, "rb");
        advance();
    }
    void advance() { fread(&e, sizeof(e), 1, fp); }
    bool operator <(const Chunk &o) const { return o.e < e; }
} chunk[N_CHUNK];

void load_block() {
    LOG("load %d blocks\n", N_BLOCK);
    for (int i = 0; i < N_BLOCK; i++) {
        for (int j = 0; j < 2; j++) {
            char path[MAX_PATH_LEN];
            snprintf(path, MAX_PATH_LEN, "block_%d_%d", i, j);
            block[i][j].load(path);
        }
    }
}

inline SHA_CTX my_sha1_update(SHA_CTX ctx, const Block &blk) {
    SHA1_Update(&ctx, blk.data, blk.len);
    return ctx;
}

inline uint64_t my_sha1_final(SHA_CTX &ctx) {
    uint8_t md[20];
    SHA1_Final(md, &ctx);
    return *(uint64_t*)(md + 12);
}

void dfs_split(int bid, uint64_t idx, SHA_CTX ctx) {
    static int n_chunk, n_elem;
    if (bid == N_BLOCK) {
        SHA1_Update(&ctx, "HITCON", 6);
        elem[n_elem++] = Elem{idx, my_sha1_final(ctx)};
        if (n_elem == N_ELEM) {
            chunk[n_chunk].init(n_chunk);
            n_chunk++;
            n_elem = 0;
        }
        return;
    }
    dfs_split(bid + 1, idx, my_sha1_update(ctx, block[bid][0]));
    dfs_split(bid + 1, idx | (1LL << bid), my_sha1_update(ctx, block[bid][1]));
}

void split_chunk() {
    LOG("split %d chunks\n", N_CHUNK);
    SHA_CTX ctx;
    SHA1_Init(&ctx);
    dfs_split(0, 0, ctx);
}

void merge_chunk() {
    LOG("merge %d chunks\n", N_CHUNK);
    std::priority_queue<Chunk> pq(chunk, chunk + N_CHUNK);
    auto get_next = [&]() {
        auto c = pq.top();
        pq.pop();
        Elem e = c.e;
        c.advance();
        if (!feof(c.fp)) pq.push(c);
        return e;
    };
    Elem pre = get_next();
    uint64_t tot = 1LL << N_BLOCK;
    for (uint64_t i = 1; i < tot; i++) {
        if (i % (tot / 128) == 0) LOG("merged %ld / 128\n", i / (tot / 128));
        Elem cur = get_next();
        if (pre.val == cur.val) {
            LOG("Happy Birthday! %016lx\n", pre.val);
            pre.save("final_msg_0");
            cur.save("final_msg_1");
            return;
        }
        pre = cur;
    }
    LOG("unhappy :(\n");
}

int main() {
    load_block();
    split_chunk();
    merge_chunk();
    return 0;
}

gen_block.rb

#!/usr/bin/env ruby

require 'digest'
require 'fileutils'

N = 33

def md5(s)
  Digest::MD5.hexdigest(s)
end

def run(cmd)
  puts "run `#{cmd}`"
  out = `#{cmd}`
  fail if $? != 0
  out
end

def md5_coll(fin, fout_1, fout_2)
  20.times do
    run "./fastcoll #{fin}"
    FileUtils.mv('md5_data1', fout_1)
    FileUtils.mv('md5_data2', fout_2)
    s1 = IO.binread(fout_1)
    s2 = IO.binread(fout_2)
    next if s1.include?("\n") || s2.include?("\n")
    return
  end
  fail
end

run 'make -C clone-fastcoll-master clean'
run 'make -C clone-fastcoll-master'

FileUtils.rm_rf('run')
FileUtils.mkdir_p('run')
FileUtils.copy_file('clone-fastcoll-master/fastcoll', 'run/fastcoll')
FileUtils.chdir('run')

base_bin = "p `xxd fl*`\x00"
fail if base_bin.bytes.any?{|x| x % 2 != 0}
base_bin = base_bin.bytes.map{|x| (x / 2).chr}.join
IO.binwrite('base.bin', base_bin)

md5_coll('base.bin', 'md5_0_0', 'md5_0_1')
(1...N).each do |i|
  md5_coll("md5_#{i-1}_0", "md5_#{i}_0", "md5_#{i}_1")
end

FileUtils.cp('md5_0_0', 'block_0_0')
FileUtils.cp('md5_0_1', 'block_0_1')

(1...N).each do |i|
  l = File.size("md5_#{i}_0") - File.size("md5_#{i-1}_0")
  IO.binwrite("block_#{i}_0", IO.binread("md5_#{i}_0")[-l..-1])
  IO.binwrite("block_#{i}_1", IO.binread("md5_#{i}_1")[-l..-1])
end

HITCON{What The Fucking Secure Hash, called wtfsh?}