Tags: crypto

Rating:

# Crypto - Rule86


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:
* An [encrypted GIF](https://raw.githubusercontent.com/YoloSw4g/writeups/master/2018/Insomni%27hack-Teaser-2018/crypto-Rule86/resources/hint.gif.enc)
* An [encrypted python script](https://raw.githubusercontent.com/YoloSw4g/writeups/master/2018/Insomni%27hack-Teaser-2018/crypto-Rule86/resources/super_cipher.py.enc)
* A [cleartext file](https://raw.githubusercontent.com/YoloSw4g/writeups/master/2018/Insomni%27hack-Teaser-2018/crypto-Rule86/resources/rule86.txt)
* The [encrypted version of said file](https://raw.githubusercontent.com/YoloSw4g/writeups/master/2018/Insomni%27hack-Teaser-2018/crypto-Rule86/resources/rule86.txt.enc)

The goal appears to be quite clear: decrypt the GIF to find the flag.
I've put some utils functions in a [Python script](https://github.com/YoloSw4g/writeups/blob/master/2018/Insomni%27hack-Teaser-2018/crypto-Rule86/files/utils.py) to be used for the rest of the chall.

## Step 1/2: read the Python source
Rule86 is announced to be a stream cipher, so the keystream is derived from an original key and xored with the text.
We can retrieve the keystream used to encrypt rule86.txt by XOR-ing the file with rule86.txt.enc.
This can be found [here](https://github.com/YoloSw4g/writeups/blob/master/2018/Insomni%27hack-Teaser-2018/crypto-Rule86/files/decpy.py), and gives the following result for super_cipher.py (truncated since rule86.txt keystream is shorter than super_cipher.py):

python
#!/usr/bin/env python3

import argparse
import sys

parser = argparse.ArgumentParser()
args = parser.parse_args()

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)

# Encrypt / decrypt stdin to stdout
plainte


## Step 2/2: decrypt the GIF
Let's analyse a bit the encryption script.
A function next is used to generate a 32-byte integer from a 32-byte integer. The function next is applied 128 times to the Initialization Vector, and then used a stream cipher.
Since we know the key has been reused, we know that the keystream will be identical for the encryption of rule86.txt and hint.gif.
We can retrieve the first value of the keystream, and derive the rest since we have the next function.
Actually, the provided script is in Python 3, which I don't like, so I wrote the equivalent of from_bytes (and its counterpart from_int in [utils.py](https://github.com/YoloSw4g/writeups/blob/master/2018/Insomni%27hack-Teaser-2018/crypto-Rule86/files/utils.py)).

The script used to decipher hint.gif.enc can be found [here](https://github.com/YoloSw4g/writeups/blob/master/2018/Insomni%27hack-Teaser-2018/crypto-Rule86/files/decgif.py).
The deciphered GIF is:

## Step 3/3: finding the flag
Ok, at this point, I really tried to avoid reversing the function next, but it know appears unavoidable.
The function is composed of two separate parts:
* First one takes the input on 256 bits, and extends it to 258 bits by shifting some
* Second one build the 256-bit output by relying on groups of 3 bits from the intermediate output and the 86 Rule, which is an array of the bits of 86

### Step 3.1: bit shift
Let's take a look at what performs the first one. For the sake of simplicity, we use a number with far less than 256 bits, and try to see what it becomes. Each letter, such as a or b represents a bit:

| Operation | Result |
| ------------- |----------------|
| x | 00abcdefghij |
| (x&1)<<N+1 | j00000000000 |
| x<<1 | 0abcdefghij0 |
| x>>N-1 | 00000000000a |
| **Result** | jabcdefghija |

Reversing that is easy, we only have to perform x = (y>>1) & 0xffffffffffffffffffffffffffffffff.

This one is a little trickier. The algorithme takes the rightmost group of three bits, which forms a number between 0 and 7, and takes the correspoding bit value in the RULE array and sets this bit a the LSB in the final result.
Then it moves to the next group of three bits (overlapping on two bits with the previous one) and repeats the process to compute the second LSB bit. Etc.

if we want to reverse this step, we have to take into account multiple things:
* 86 is balanced, its binary representation has as many 1s as 0s
* The pre-image of a single bit can be 4 values
* Knowing that the pre-images of two consecutive bits overlap on two bits, we have a first condition to reduce the possible number of values
* The result of the first step has a final condition which is that the two leftmost bits are identical to the two rightmost bits, which drops the number of possible solutions to 1

A [really dirty Python script](https://github.com/YoloSw4g/writeups/blob/master/2018/Insomni%27hack-Teaser-2018/crypto-Rule86/files/revnext.py) takes all that into account to reverse the 128 first iterations of next, and retrieve the flag:

\$ python revnext.py
INS{Rule86_is_W0lfr4m_Cha0s}


Original writeup (https://github.com/YoloSw4g/writeups/tree/master/2018/Insomni'hack-Teaser-2018/crypto-Rule86).