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?

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()

Last updated