Google CTF Final 2017 - slotmachine

gen.c

#include <stdlib.h>
#include <stdint.h>
#include <unistd.h>
#include <fcntl.h>
#include <sys/mman.h>
#define TABLE_SIZE 0xFFFFFFFF

uint32_t seed = 0;

uint16_t _rand()
{
    seed = 0x41c64e6d * seed + 31337;
    return ((seed >> 16) ^ (seed & 0xffff));
}

uint32_t get_rand()
{
    uint32_t r = _rand();
    if (r >= 0xFD70)
        return 3;
    else if (r >= 0xF0A3)
        return 2;
    else if (r >= 0xBAE0)
        return 1;
    return 0;
}

int main(int argc, char *argv[])
{
    int fd = open("/tmp/ranbow", O_RDWR | O_CREAT, S_IRUSR | S_IWUSR);
    if (fd == -1) {
        perror("open failed");
        exit(EXIT_FAILURE);
    }

    if (lseek(fd, TABLE_SIZE - 1, SEEK_SET) == -1) {
        close(fd);
        perror("lseek failed");
        exit(EXIT_FAILURE);
    }

    if (write(fd, "", 1) == -1) {
        close(fd);
        perror("write failed");
        exit(EXIT_FAILURE);
    }

    char* table = mmap(0, TABLE_SIZE, PROT_WRITE, MAP_SHARED, fd, 0);
    if (table == MAP_FAILED) {
        close(fd);
        perror("mmap failed");
        exit(EXIT_FAILURE);
    }

    for (uint32_t i = 0; i < TABLE_SIZE; ++i)
        table[i] = "0123"[get_rand()];

    close(fd);
    return 0;
}

search.c

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <unistd.h>
#include <fcntl.h>
#include <sys/mman.h>
#define TABLE_SIZE 0xFFFFFFFF

/*
  board index
    0 3 6
    1 4 7
    2 5 8
*/

const char target[] = {
    "102001002"
    "000010100"
    "000100001"
    "101100011"
};

uint32_t get_seed_by_index(uint32_t index)
{
    uint32_t seed = 0;
    for (uint32_t i = 0; i < index; ++i)
        seed = 0x41c64e6d * seed + 31337;
    return seed; 
}

int main(int argc, char *argv[])
{
    int fd = open("/tmp/ranbow", O_RDONLY);
    if (fd == -1) {
        perror("open failed");
        exit(EXIT_FAILURE);
    }
    char* table = mmap(0, TABLE_SIZE, PROT_READ, MAP_PRIVATE, fd, 0);
    if (table == MAP_FAILED) {
        perror("mmap failed");
        exit(EXIT_FAILURE);
    }

    // Search initial seed
    for (uint32_t i = 0; i < TABLE_SIZE; ++i) {
        if (i % 0x10000000 == 0) printf("searching 0x%x...\n", i);
        if (memcmp(table + i, target, strlen(target)) == 0){
            uint32_t seed = get_seed_by_index(i);
            printf("Found initial seed: 0x%x\n", seed);

            // get seed after 4 rounds
            for (int i = 0; i < strlen(target); ++i )
                seed = 0x41c64e6d * seed + 31337;
            
            printf("Searching for jackpot seed...\n");
            for (uint32_t j = 0; j < TABLE_SIZE; ++j) { // 777
                if (!memcmp(table + j, "030030030", 9)) {
                    uint32_t delta = get_seed_by_index(j) - seed;
                    if (delta <= 9999999) {
                        printf("Usable seed found!!\n");
                        printf("Delta = %d\n", delta);
                        break;
                    }
                }
            }
            break;
        }
    }

    return 0;
}