# InsomniHack Teaser CTF 2018 - Rule86

Category: writeupsTags: insomnihack-teaser-2018 crypto

Crypto

Kevin is working on a new synchronous stream cipher, but he has been re-using his key.

In this challenge, you are provided with 4 files:

```
hint.gif.enc - An encrypted GIF
super_cipher.py.enc - An encrypted python script
rule86.txt - A cleartext file
rule86.txt.enc - The encrypted version of said file
```

- Get the encryption’s keystream
- Decrypt the GIF and the python script
- Where is the flag???

### Writeup

This challenge was very original and well thought.

We didn’t solve it in time, but here it is our writeup.

#### Step 1

We started by getting the keystream from the `rule86.txt`

file and its encrypted counterpart.

```
p1 = open('rule86.txt', 'rb').read()
c1 = open('rule86.txt.enc', 'rb').read()
keystream = []
for a, b in zip(p1, c1):
keystream.append(a ^ b)
```

And then, decrypting the other encrypted files

```
c2 = open('super_cipher.py.enc', 'rb').read()
p2 = []
for a, b in zip(keystream, c2):
p2.append(a ^ b)
print(bytes(p2))
```

Since the `rule86.txt.enc`

file is smaller then `super_cipher.py.enc`

and `hint.gif.enc`

we don’t have enough keystream to decrypt the latters.

#### Step 2

We noticed that the decrypted script was generating a 32-byte integer with a PRNG from the `key`

(aka the flag) and using that as keystream.

```
RULE = [86 >> i & 1 for i in range(8)]
N_BYTES = 32
N = 8 * N_BYTES
def next(x):
x = (x & 1) << N+1 | x << 1 | x >> N-1
y = 0
for i in range(N):
y |= RULE[(x >> i) & 7] << i
return y
# Bootstrap the PNRG
keystream = int.from_bytes(args.key.encode(),'little')
for i in range(N//2):
keystream = next(keystream)
```

The simple way to solve this and decrypt the gif and the script was to retrive the starting 32-byte integer from the known keystream and then using the PRNG function to reproduce the keystream by generating all the integer we wanted.

We didn’t think about that because we noticed that the now-known piece of the gif had a pattern. (and I also love forensics :(

So I’ve made a little script that recreate part of the gif following this pattern.

All went smooth and without problem so I kept thinking it was the good approach, beside that the gif was corrupted, but the keystream was right and we decrypted all the script.

**Note:** This was the correct gif, the hint was pretty useless for us

Here the scrypt for recovering the `super_cipher.py`

file

#### Step 3

Now we know that the flag is the seed of the PRNG used as encryption keystream.

We only need to reverse it and get the previous number for each step. *Easy.*

Let’s start from this line.

`x = (x & 1) << N+1 | x << 1 | x >> N-1`

`(x & 1)`

get the lsb from `x`

(our starting number)

`(x & 1) << N+1`

will shift it 257 positions left (N = 256)

if `x`

lsb is **0**, `(x & 1) << N+1`

will be `0`

if `x`

lsb is **1**. `(x & 1) << N+1`

will be `1 << 257`

`x << 1`

shift `x`

by **1 position** to the left

`x >> N-1`

will take the **2 msb**, shift them by **255** positions right and **OR** them as **lsb**

Turns out this is very easy to reverse and also **the output number** has its **2 msb equals** to its **2 lsb**.

The reverse operation is the following: `x = (x >> 1) & ((1 << N)-1)`

`x >> 1`

shift `x`

by 1 position right, eliminating the **2 lsb** added above.

The **AND** operation filters the first operand’s bits where the second operand has bits set to `1`

. (I hope you know how AND works)

`(1 << N)`

is `0b1000000`

with N zeros. Minus one will result in `0b111111`

with **N** ones.

We are effectively filtering only the **N** bits we wanted, eliminating the **2 msb** added above.

Then the PRNG takes 3 bits at a time from the right and substitute them by the **RULE** array.

```
for i in range(N):
y |= RULE[(x >> i) & 7] << i
```

For example if we have `0b1100`

, the for works like this:

```
y[0] = RULE[0b100] # 0bXXX100
y[1] = RULE[0b110] # 0bXX110X
y[2] = RULE[0b11] # 0bX011XX
y[3] = RULE[0b1] # 0b001XXX
y = y[::-1] # reverse y
```

Output y will be `0b1011`

Reversing this is pretty easy too, just scan **y** and get the possible preimage values of **RULE** mapping function that result in either **1** or **0**.

If the current **y** bit is **1**, check what value in RULE output **1** and check if that value is consistent with the previous ones (since chosen bits form **x** are overlapping)

Are you starting having an headache? Me too.

Bonus script that recover the integer keystream

Final script that reverse the PRNG and get the seed/flag

Flag is: `INS{Rule86_is_W0lfr4m_Cha0s}`