> For the complete documentation index, see [llms.txt](https://elijahchia.gitbook.io/ctf-blog/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://elijahchia.gitbook.io/ctf-blog/jelly-ctf-24/the_brewing_secrets-crypto.md).

# the\_brewing\_secrets (crypto)

{% file src="/files/Pve1nZdto3rgm3oneHXz" %}

The main program is made with the following C code:

```c
#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.&#x20;

`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.&#x20;

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:

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