the_brewing_secrets (crypto)

Rumour has it Sakana stores the secret recipes for Phase Connect's coffee blends in his 'super secure laboratory'. Can you hack your way in?

5KB

the_brewing_secrets.zip

archive

The main program is made with the following C code:

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

int runChallenge(int passcodeLength)
{
    int EXTRA_ALLOWANCE = passcodeLength;
    int bitmask = (1 << passcodeLength) - 1;
    int maxTimeout = bitmask;
    int passCode = random() & bitmask;

    printf("WARNING: System will timeout after %d entries\n", maxTimeout + EXTRA_ALLOWANCE);
    printf("Enter %d-digit binary passcode  \n", passcodeLength);

    int timeout = 0;
    int userInput = 0;

    char received;

    while (timeout < maxTimeout + EXTRA_ALLOWANCE)
    {
        scanf(" %c", &received);

        // optimisation with bit shift
        userInput = bitmask & (userInput << 1 | (received != '0'));
        if (userInput == passCode)
        {
            return 1;
        }

        if (timeout % passcodeLength == (passcodeLength - 1))
        {
            printf("Passcode incorrect. Try again!\n");
        }

        timeout++;
    }

    printf("Timeout exceeded\n");

    return 0;
}

int main(int argc, char **argv) {
    srand(time(NULL));

    int PASSCODE_LENGTH = 6;
    int NUM_PHASES = 10;

    int phase_number;
    int result = 0;

    for (phase_number = 1; phase_number <= NUM_PHASES; phase_number++)
    {
        printf("\n\nStarting phase_number %d...\n", phase_number);
        result = runChallenge(PASSCODE_LENGTH);

        // flush stdin
        int c;
        while((c = getchar()) != '\n' && c != EOF);

        printf("Phase number %d - validation result: %d\n", phase_number, result);

        if (result == 0)
        {
            break;
        }
    }

    if (phase_number == NUM_PHASES + 1)
    {
        FILE *f = fopen("flag.txt", "r");
        if(f == NULL){

            printf("Flag not found: please run this on the server\n");
            exit(0);
        }
        char buf[128];
        fgets(buf, 127, f);
        printf("Validation successful. Unlocking garage door: %s\n", buf);
    }

    return 0;
}

We are essentially playing a game with 10 phases. In each phase the code calls runChallenge(6), which starts the phase.

In each phase, a random 6-bit integer is generated, and we need to guess it. In each phase we only have (1 << 6) - 1 + 6 = 69 chances to input characters.

userInput starts at 0. For each character we input, userInput is shifted left by 1 bit and an OR operation is done with our character. userInput is also AND with bitmask to ensure that it is always 6 bits. If userInput matches passCode in 69 tries, we clear the phase. At first glance, 69 tries is not enough to brute-force all 2^6 possible passcodes, since that would require 2^6 * 6 = 384 characters. However, notice that the check (userInput == passCode) is done with every character we input, instead of every 6 characters we input. Therefore, we can provide a sequence of characters which, on appending to userInput, keeps making userInput a different 6-bit integer. This is also a De Brujin Sequence.

I found one such sequence online. At each phase, I send characters from the sequence to the server, stopping only when I have cleared the phase. Below is my script:

from pwn import *
de_brujin_sequence = "0000001000011000101000111001001011001101001111010101110110111111" # length of 64
x = de_brujin_sequence[5:]
"""
Verification is done on every bit, rather than on every 5 bits entered. Use De Brujin sequence to 
efficiently bruteforce every possible 5-bit binary string
"""
context.log_level = "debug"

# fill in binary name
elf = context.binary = ELF("./the_brewing_secrets")
if args.REMOTE:
  # fill in remote address
  p = remote("chals.jellyc.tf", 6000)
else:
  p = elf.process()

for phase in range(10):
    # remote changed \n to \r\n :(
    # p.recvuntil(b"passcode  \n") 
    p.recvuntil(b"passcode  \r\n")
    for idx in range(len(x)):
        p.sendline(x[idx].encode())
        res = p.recvline(timeout=0.2)
        if b"Phase number" in res:
            break

p.recvall() # jellyCTF{mad3_w1th_99_percent_l0v3_and_1_percent_sad_g1rl_t3ars}
p.close()