Plaid CTF 2014 - parlor

gistfile1.txt

$ ruby solver.rb
[*] connected
[*] get hashes
base hash = 000000019fdbafe8e0a8adce0df2c053
extended hash = 00000009e17fc0d39d1f720c486e27ec
[*] recover hash
recovered base hash = 912d8dc19fdbafe8e0a8adce0df2c053
[*] get flag
flag = i_dunno_i_ran_out_of_clever_keys
[*] connection closed

Makefile

.PHONY: build

build: solver.c
	cc -o solver solver.c -lcrypto

solver.c

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <openssl/md5.h>

typedef struct {
    size_t length;
    unsigned char *data;
} blob;

#define ishexdigit(c) (('0' <= c && c <= '9') || ('a' <= c && c <= 'f'))

#define HIDDEN_BITS 28
#define NONCE_LENGTH 128

void log_ctx(MD5_CTX *ctx){
    int i;

    fprintf(stderr, "A = 0x%08x\n", ctx->A);
    fprintf(stderr, "B = 0x%08x\n", ctx->B);
    fprintf(stderr, "C = 0x%08x\n", ctx->C);
    fprintf(stderr, "D = 0x%08x\n", ctx->D);
    fprintf(stderr, "Nl = 0x%08x\n", ctx->Nl);
    fprintf(stderr, "Nh = 0x%08x\n", ctx->Nh);
    fprintf(stderr, "data = [");
    for(i = 0; i < sizeof(ctx->data) / sizeof(MD5_LONG); i++){
        fprintf(stderr, "%s0x%08x", i != 0 ? ", " : "", ctx->data[i]);
    }
    fprintf(stderr, "]\n");
    fprintf(stderr, "num = %d\n\n", ctx->num);
}

blob *hex2blob(char *hexstr){
    blob *b;
    size_t i;

    if(strlen(hexstr) % 2 != 0){
        return NULL;
    }

    b = malloc(sizeof(blob));
    b->length = strlen(hexstr) / 2;
    b->data = malloc(b->length);

    for(i = 0; i < b->length; i++){
        if(!ishexdigit(hexstr[2 * i]) || !ishexdigit(hexstr[2 * i + 1])){
            free(b->data);
            free(b);
            return NULL;
        }
        sscanf(hexstr + 2 * i, "%02hhx", b->data + i);
    }

    return b;
}

char *blob2hex(blob *b){
    char *buf;
    size_t i;

    buf = malloc(b->length * 2 + 1);
    memset(buf, 0, b->length * 2 + 1);
    for(i = 0; i < b->length; i++){
        sprintf(buf + 2 * i, "%02x", (unsigned char)b->data[i]);
    }

    return buf;
}

int print_blob(blob *b){
    char *buf;
    int result;

    buf = blob2hex(b);
    result = printf("%s", buf);

    free(buf);

    return result;
}

void usage(char *program_name){
    fprintf(stderr, "Usage:\n");
    fprintf(stderr, "    %s -phase1 data hash1 add hash2\n", program_name);
    fprintf(stderr, "        recover hash1 and hash2 when\n");
    fprintf(stderr, "            hash1 := md5(NONCE + data) & ((1 << %d) - 1)\n", 128 - HIDDEN_BITS);
    fprintf(stderr, "            hash2 := md5(NONCE + data + padding + add) & ((1 << %d) - 1)\n", 128 - HIDDEN_BITS);
    fprintf(stderr, "    %s -phase2 data initial_hash bits\n", program_name);
    fprintf(stderr, "        find a payload which meets the following conditions\n");
    fprintf(stderr, "            md5(NONCE + data) == initial_hash\n");
    fprintf(stderr, "            md5(NONCE + data + padding + payload) & ((1 << bits) - 1) == 0\n");
}

void recover_state(MD5_CTX *ctx, unsigned char *hash, unsigned long long length){
    MD5_LONG *state = (MD5_LONG*)hash;
    unsigned long long bits;

    memset(ctx, 0, sizeof(MD5_CTX));

    ctx->A = state[0];
    ctx->B = state[1];
    ctx->C = state[2];
    ctx->D = state[3];

    bits = (NONCE_LENGTH + length * 8 + 1 + 64 + 511) / 512 * 512;
    ctx->Nl = bits & 0xffffffff;
    ctx->Nh = (bits >> 32) & 0xffffffff;
}

void generate_mask(unsigned char *mask, int hidden_bits){
    int i;

    for(i = 0; i < 16; i++){
        if(i < hidden_bits / 8){
            mask[i] = 0;
        }else if(i == hidden_bits / 8){
            mask[i] = (1 << (8 - hidden_bits % 8)) - 1;
        }else{
            mask[i] = 0xff;
        }
    }
}

int is_same_hash(unsigned char *hash1, unsigned char *hash2, unsigned char *mask){
    int i;

    for(i = 0; i < 16; i++){
        if((hash1[i] & mask[i]) != (hash2[i] & mask[i])){
            return 0;
        }
    }

    return 1;
}

/*
 * md5(NONCE + data) & ((1 << HIDDEN_BITS) - 1) == hash1
 * かつ
 * md5(NONCE + data + "\x80\x00...\x00" + [(nonce + data).length * 8].pack("Q") + add) & ((1 << HIDDEN_BITS) - 1) == hash2
 * となるときの
 * md5(NONCE + data)をブルートフォース + length extension attackで探す
 */
int phase1(blob *data, blob *hash1, blob *add, blob *hash2){
    unsigned long i, j;
    unsigned char fullhash[16];
    unsigned char extended_hash[16];
    unsigned char mask[16];
    MD5_CTX ctx;

    generate_mask(mask, HIDDEN_BITS);

    for(i = 0; i < 1 << HIDDEN_BITS; i++){
        memcpy(fullhash, hash1->data, sizeof(fullhash));

        for(j = 0; j < (HIDDEN_BITS + 7) / 8; j++){
            if((j + 1) * 8 <= HIDDEN_BITS){
                fullhash[j] |= i >> (HIDDEN_BITS - (j + 1) * 8);
            }else{
                fullhash[j] |= i << (8 - HIDDEN_BITS % 8);
            }
        }

        recover_state(&ctx, fullhash, data->length);
        MD5_Update(&ctx, add->data, add->length);
        MD5_Final(extended_hash, &ctx);

        if(is_same_hash(hash2->data, extended_hash, mask)){
            printf("hash1 = ");
            for(j = 0; j < 16; j++){
                printf("%02x", fullhash[j]);
            }
            printf("\n");
            printf("hash2 = ");
            for(j = 0; j < 16; j++){
                printf("%02x", extended_hash[j]);
            }
            printf("\n");
            return 0;
        }
    }
    return 1;
}

/*
 * md5(NONCE + data) == initial_hash
 * が成り立つとき、
 * md5(NONCE + data + padding + payload) & ((1 << bits) - 1) == 0
 * となるような16byteのpayloadを探す
 * (重複を避けるため、payloadの先頭12byte分は/dev/urandomから取る)
 */
int phase2(blob *data, blob *initial_hash, int bits){
    int fd;
    unsigned long long i;
    unsigned char mask[16];
    unsigned char hash[16];
    blob *payload;
    MD5_CTX ctx;
    int found;

    generate_mask(mask, 128 - bits);

    payload = malloc(sizeof(blob));
    payload->length = 16;
    payload->data = malloc(16);

    fd = open("/dev/urandom", O_RDONLY);
    if(fd < 0){
        perror("open");
        return 1;
    }

    found = 0;
    while(!found){
        read(fd, payload->data, payload->length - 4);

        for(i = 0; i <= 0xffffffff; i++){
            *(unsigned int*)(payload->data + 12) = i;

            recover_state(&ctx, initial_hash->data, data->length);
            MD5_Update(&ctx, payload->data, payload->length);
            MD5_Final(hash, &ctx);

            if(is_same_hash(hash, "\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0", mask)){
                print_blob(payload);
                found = 1;
                break;
            }
        }
    }

    close(fd);

    return 0;
}

int main(int argc, char **argv){

    setbuf(stderr, NULL);

    if(argc < 2){
        usage(argv[0]);
        return 1;
    }

    if(!strcmp(argv[1], "-phase1") && argc == 6){
        blob *data, *hash1, *add, *hash2;
        blob **a[] = {&data, &hash1, &add, &hash2};
        int i;

        for(i = 0; i < sizeof(a) / sizeof(blob*); i++){
            *a[i] = hex2blob(argv[i + 2]);
            if(*a[i] == NULL){
                fprintf(stderr, "argparse failed\n");
                return 1;
            }
        }

        if(hash1->length != 16 || hash2->length != 16){
            fprintf(stderr, "hash length error\n");
            return 1;
        }

        return phase1(data, hash1, add, hash2);
    }else if(!strcmp(argv[1], "-phase2") && argc == 5){
        blob *data, *initial_hash;
        int bits;

        data = hex2blob(argv[2]);
        initial_hash = hex2blob(argv[3]);
        bits = atoi(argv[4]);
        if(data == NULL || initial_hash == NULL){
            fprintf(stderr, "argparse failed\n");
            return 1;
        }
        if(bits < 0 || bits > 64){
            fprintf(stderr, "bits must be between 0 and 64\n");
            return 1;
        }

        return phase2(data, initial_hash, bits);
    }else{
        usage(argv[0]);
        return 1;
    }

    return 0;
}

solver.rb

#coding:ascii-8bit
require "pwnlib"
require "open3"

host = "localhost"
port = 4321

class PwnTube
    def recv_until_prompt
        recv_until("====================\n\n")
    end
end

def set_odds(odds)
    @tube.recv_until_prompt
    @tube.sendline("1")
    @tube.recv_until(": ")
    @tube.sendline("#{odds}")
end

def set_bet(bet)
    @tube.recv_until_prompt
    @tube.sendline("2")
    @tube.recv_until(": ")
    @tube.sendline("#{bet}")
end

def play(nonce)
    @tube.recv_until_prompt
    @tube.sendline("3")
    @tube.recv_until("round!\n")
    @tube.send(nonce)

    if @tube.recv_until(/Wow!|Too bad/) =~ /Wow/
        return nil
    else
        return @tube.recv_capture(/we generated (\d+),/)[0].to_i
    end
end

def recover_hash(hash1, hash2)
    result, status = Open3.capture2("./solver -phase1 41 #{hash1} 41 #{hash2}")
    raise if status.exitstatus != 0
    return result.match(/hash1 = ([0-9a-f]+)\n/).captures[0]
end

def generate_payload(hash, odds)
    result, status = Open3.capture2("./solver -phase2 41 #{hash} #{odds}")
    raise if status.exitstatus != 0
    return result.strip
end

PwnTube.open(host, port){|tube|
    @tube = tube

    set_odds(100)
    set_bet(0)

    puts "[*] get hashes"
    base = "%032x" % play("A")
    puts "base hash = #{base}"

    extended = "%032x" % play("A" + "\x80".ljust(64 - 16 - 1 - 8, "\0") + [17 * 8].pack("Q") + "A")
    puts "extended hash = #{extended}"

    puts "[*] recover hash"
    base = recover_hash(base, extended)
    puts "recovered base hash = #{base}"

    puts "[*] get flag"
    money = 1000
    odds = 8
    set_odds(odds)
    while money < 1000000000
        set_bet(money)
        payload = ""
        payload << "A" + "\x80".ljust(64 - 16 - 1 - 8, "\0") + [17 * 8].pack("Q")
        payload << [generate_payload(base, odds)].pack("H*")
        play(payload)
        money = money * (2 << (odds - 1))
    end

    puts "flag = " + tube.recv_capture(/Here's a key: (\w+)\n/)[0]

    tube.recv_until_prompt
    tube.sendline("6")
}