Click to expand challenge code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
from random import Random
from Crypto.Util.number import bytes_to_long, long_to_bytes
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
import os

FLAG = os.getenv("FLAG", "FL1TZ{dummy_dum_dum}")
COLOR_BLACK = "\x1b[30m"
COLOR_RED = "\x1b[31m"
COLOR_GREEN = "\x1b[32m"
COLOR_YELLOW = "\x1b[33m"
COLOR_BLUE = "\x1b[34m"
COLOR_MAGENTA = "\x1b[35m"
COLOR_CYAN = "\x1b[36m"
COLOR_RESET = "\x1b[0m"
BOLD = "\x1b[1m"
RESET_BOLD = "\x1b[22m"

class Jigsaw:
    def __init__(self):
        self.dealer = Random()

    def get_piece(self):
        return self.dealer.getrandbits(32)

    def and_enc(self, pt):
        return pt & self.get_piece()

    def or_enc(self, pt):
        return pt | self.get_piece()


    def encrypt(self, pt):

        out = bytearray()
        methods = self.dealer.getrandbits(len(pt) // 4)
        for i in range(0, len(pt), 4):
            pick = (methods >> (i // 4)) & 1
            method = [self.and_enc, self.or_enc][pick]
            int_pt = bytes_to_long(pt[i:i+4])
            block = method(int_pt)
            out += long_to_bytes(block,4)
        return out

    def get_flag(self):
        iv = long_to_bytes(self.dealer.getrandbits(128),16)
        key = long_to_bytes(self.dealer.getrandbits(256), 32)
        cipher = AES.new(key, AES.MODE_CBC, iv)
        encrypted_flag = cipher.encrypt(pad(FLAG.encode(),16))
        return iv + encrypted_flag

HEADER = f"""
{COLOR_YELLOW}{BOLD}IN/ RAINBOWS
{COLOR_BLUE}IN RAIN/BOWS
{COLOR_RED}IN RAINBOW/S
{COLOR_GREEN}IN RAINBOWS/
{COLOR_YELLOW}IN RAIN_BOWS
{COLOR_RED}RA D IOHEA_D
{COLOR_CYAN}_RAD IO HEA D{RESET_BOLD}{COLOR_RESET}
"""

def main():
    jig = Jigsaw()
    enc_flag = jig.get_flag()
    print(HEADER)
    print(f"This is the only piece you'll ever get, make good use of it: {enc_flag.hex()}")
    remaining = 7200
    while remaining > 0:
        pt = input("Come on and let it out (hex) > ").strip()
        try:
            pt_bytes = bytes.fromhex(pt)
            if len(pt) % 4 != 0 and len(pt) >= 4:
                print("Plaintext length must be a multiple of 4 bytes.")
                continue
            if len(pt_bytes) > remaining:
                print(f"Don't get carried away, max {remaining} bytes allowed.")
                continue
            enc = jig.encrypt(pt_bytes)
            print(f"A sliver of light: {enc.hex()}")
            remaining -= len(pt_bytes)
        except ValueError as e:
            print(f"Looks like you got lost in between the notes: {e}")
            exit(0)
    print("Go ahead, run away from me...")

if __name__ == "__main__":
    main()

Ahh yes, the infamous Jigsaw puzzle than many players spent hours bashing their head against xd. This is one of the two challenges I made that remained unsolved for the entire competition.

So as promised, here’s a writeup 😉
I also wanted to follow a musical theme across all challenges (this one about radiohead, the ZKP one about Green Day, Toxicity about System of a Down…), I hope you appreciated it 😁

Analysis

Functionality

Before trying anything, we gotta understand what we’re working with, aswell as our limitations:

We have a centralized “dealer” (which you can think of as a single prng state) responsible for generating all of our random numbers
The first random outputs are used to generate the AES key and iv used to encrypt the flag
We get access to an oracle that “encrypts” our input using a random keystream provided by the dealer
There is a limit on the length of our input (7200 bytes)
The “encryption” is done an unconventional method, juggling AND and OR

Lossy Encryption

The encryption method is pretty unconventional, so let’s break it down in detail:

After each input, a random methods integer is generated
for each block of 4 bytes, the ith bit of methods will determine which operation we’re gonna perform between a random 32 bit integer and the plaintext block
- if the bit is 0, we perform an AND operation
- if it’s 1, we perform an OR
We concatenate the resulting ciphertext blocks and return them to the player

What you’ll notice it that we didn’t use a classic XOR operation, otherwise the challenge would be trivial!
Contrary to a XOR operation, & and | are not bijective! (aka, we lose information after the operation), meaning, given $x$ and $y$ with $x = y$ & $c$ or $x = y \vert c$ for some unknown $c$, it is mathematically impossible to pinpoint $c$!

Unless….

The Split

Here’s the neat thing, we know that $c$&$y$ gives us no information regarding $c$, but what if $y=1$? Suddenly, $x=1$&$c = c$!
Same thing goes for OR: $x=0 \vert c = c $

How could this be helpful though? Think about it for a second: We don’t know which operation is performed on each plaintext block, but think about what happens if we encrypt 0xffff0000!! Let’s consider the random number for each block $x_i$:

If the operation is AND: We get $$ \text{0x????0000} = \left( \left( x_i \gg 16 \right) \mathbin{\&} \text{0xFFFF} \right) \ll 16 $$ which essentially translates to The 16 Most Significant Bits of $x_i$, shifted to the left by 16 bits
If the operation is OR: We get $$ \text{0xFFFF????} = \left(x_i\mathbin{\&} \text{0xFFFF} \right) \vert \text{0xFFFF0000} $$ AKA The 16 Least Significant Bits of $x_i$

This ultimately gives us half of each randomly generated number by the dealer, aswell as methods since we now know the exact order of the methods used!

Here’s the second challenge though: How do you recover a Mersenne Twister RNG state given partial information about the outputs?
Here, we call for symbolic modeling of the problem, aka Z3

Symbolic Solution

If you’re not familiar with symbolic solvers like z3 and or-tools, basically they’re what we call SAT solvers used to model a set of equations and try their best to find a solution.

There are plenty of mersenne solvers online, but most of them try algebraic solutions that require the full prng output in sequential order for them to work. We don’t have that privilege here so we resort to SAT solvers that help us recover the missing half of each entry.

Note: There are methods to solve this using linear algebra over $GF(2)$, but they are waaaay too complicated, and are outside the scope of this writeup.

There is this repo that has a great implementation for symbolic mersenne solver that works even with missing bits or even entirely skipped states!. It’s very heavy duty though, so it works best the more information you give it.

Luckily for us, we have plenty!

It should be noted that the symbolic solver will give us the state of the rng at the end of its executon. We still need to walk back in states to reach the one used to generate the AES key!

Solution

Plan

Get as many encrypted blocks as possible, $900$ in our case, but even $624$ would be enough, but will take a lot longer to solve.
Recover the state at the end
Walk back in states with a simulated MT implementation
Regenerate the key (use the iv to verify that it’s correct), and decrypt the flag!

Solver

Click to expand solver code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
from Crypto.Util.number import bytes_to_long, long_to_bytes
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
from untwister import Untwister # Source: https://github.com/icemonster/symbolic_mersenne_cracker/ (slightly modified)
from mersy import MT19937 # Source: https://github.com/twisteroidambassador/mt19937-reversible (slightly modified)
from pwn import *

io = remote("20.218.234.6", 1000)
pt = b'FFFF0000'*1800
io.recvuntil(b"This")
enc_flag = bytes.fromhex(io.recvline().strip().decode().split(": ")[1])
io.sendlineafter(b" (hex) > ", pt)
io.recvline()
k = io.recvline().strip().decode().split(": ")[1]
enc = bytes.fromhex(k)
io.close()
blocks = [enc[i:i+4] for i in range(0, len(enc), 4)]
print(len(blocks), "blocks of 4 bytes each")
ut = Untwister()

for b in blocks:
    test = bytes_to_long(b) & 0xFFFF
    meth = 1 if ( test == 0) else 0
    if meth:
        tb = bytes_to_long(b) >> 16
        known_bits = bin(tb)[2:].rjust(16, '0')
        sub = known_bits + "?"*16
        ut.submit(sub)
    else:
        known_bits = bin(test)[2:].rjust(16, '0')
        sub =  "?"*16 + known_bits
        ut.submit(sub)

r2, seed_tuple = ut.get_random()
rt = MT19937()
out = []

for _ in range(624):
    r = r2.getrandbits(32)
    out.append(r)
print("Random state cloned successfully!")
rt.clone_state_from_output_and_rewind(out)
rt.rewind(len(blocks) + 1800//32 + 8 + 4 + 1)
recon_iv = 0
for i in range(4):
    recon_iv = (rt.get_next_random() << 32 * i) | recon_iv
recon_key = 0
for i in range(8):
    recon_key = (rt.get_next_random() << 32 * i) | recon_key
iv = enc_flag[:16]
enc_flag = enc_flag[16:]
print(f"IV          : {iv.hex()}")
print(f"Recovered IV: {long_to_bytes(recon_iv, 16).hex()}")

recon_aes = AES.new(long_to_bytes(recon_key, 32), AES.MODE_CBC, long_to_bytes(recon_iv, 16))
dec_flag = unpad(recon_aes.decrypt(enc_flag), 16)
print(f"Recovered flag: {dec_flag.decode()}")

FL1TZ{atl3Ast_g1mme_th3_S33D_bef0R3_y0u_run_4Way_fr0M_m3:(}