Rating:

![description](images/description.png)

# Getting Started:

We're given a link to an archive containing 4 files:

* hint.gif.enc
* rule86.txt
* rule86.txt.enc
* super_cipher.py.enc

Each of these files is included in this the sample_files folder in this repo: [Link](./sample_files/)

The only readable file is rule86.txt, but it just contains nonsense.

As stated in the challenge description, the provided *.enc files were encrypted with a synchronous stream cipher.

# Stream Ciphers

In a synchronous stream cipher, a key stream is generated with a pseudorandom number generator, and the generated stream of bytes is xored with the message to get the ciphertext.

In this scheme, the PRNG is parameterized by a secret key.

Since we know that ciphertext = keystream ^ message, and we know a ciphertext and message pair (rule86.txt and rule86.txt.enc), we can calculate part of the keystream by calculating keystream = ciphertext ^ message.

One we know part of the keystream, we can decrypt other ciphertexts by just xoring them with the keystream.

# Partial decryption

At this point, we can only decrypt as many bytes of a ciphertext as we have bytes of the keystream (aka the size of rule86.txt). Because of this, we can't fully decrypt any of the other files, as they're all too large.

As a start, we decrypted the super_cipher.py.enc file to see some of the code that was used for the cipher.

Here is the partially decrypted code:
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


From this code, we know how how the keystream is generated (just repeatedly calling next on the previous keystream block), and can thus generate a keystream of whatever length we want using the partial keystream that we recovered:

python

#read the sample data given to us
txt = open("./sample_files/rule86.txt", "rb").read()
enc = open("./sample_files/rule86.txt.enc", "rb").read()
hint = open("./sample_files/hint.gif.enc", "rb").read()
py_file = open("./sample_files/super_cipher.py.enc", "rb").read()

#xors two byte arrays
def xor(bytes1, bytes2):
return bytearray([(a ^ b) for (a, b) in zip(bytes1, bytes2)])

#gets the first N_BYTES of the keystream that was used to encrypt rule86.txt.enc
def get_base_keystream():
return xor(txt, enc)[0:N_BYTES]

#gets the base keystream that was used, and generates the whole length byte keystream that can be used to decrypt
def generate_stream(length):
keystream = get_base_keystream()
curr_int = int.from_bytes(keystream, 'little')
for i in range(ceil(length/N_BYTES) - 1):
curr_int = next(curr_int)
keystream += curr_int.to_bytes(N_BYTES, 'little')
return keystream

#decrypts an array of bytes
def decrypt(input_bytes):
length = len(input_bytes)
keystream = generate_stream(length)
return xor(input_bytes, keystream)



Using this, we were able to fully decrypt each of the encrypted files.

# Now we're done right?

At this point, we looked at the decrypted files, and were disappointed to find that the hint.gif did not contain the flag (and super_cipher.py didn't contain any more useful info):

![decrypted hint](images/hint.gif)

From the hint, we could see that the key that was input to bootstrap the "prg" is a flag for the challenge, and so we need to reverse the prg, and walk our way back through the keystream to get what the input key was.

# Reversing the "prg"

From the decrypted code, we could see that the next function does the following:

* Takes in a 256 bit input x
* Computes a 257 bit x' such that the first bit of x' is the 256th bit of x, the 257th bit of x' is the 1st bit of x and the remaining 255 bits of x' are x' left shifted by 1.
* Computes a value y, where each bit of y is determined by looking up 3 bits of x' in a table of 0's and 1's.

So in order to reverse this, we did the following:
* For the first bit of a 256 bit input y, determine what possible 3-bit codes of x' could have resulted in that bit of y and store them as possible decodings of y.
* Walk through y one bit at a time, and update the potential values of x' that could have resulted in what we've seen so far in y.
* At the end, look at all of our possibilities for x' and check that they match the following conditions:
* The 257th bit of x' == the 2nd to last bit of x' (both were set to be the first bit of x in next)
* The 256th bit of x' == the last bit of x' (both were set to be the 256th bit of x in next)
* After recovering the 1 valid possibility for x', undo the bit shifts that were done in next to recover the original x.

Here's the code that was written to solve this:
python
#given in super_cipher.py
RULE = [(86 >> i) & 1 for i in range(8)]
N_BYTES = 32
N = 8 * N_BYTES

# in y = next(x), each 3 bits of x determines 1 bit of y
# use this dictionary to store this relation for reversing this function
dct = {
#y x
"0" : ["000", "011", "101", "111"],
"1" : ["001", "010", "100", "110"]
}

#takes in an int value of keystream, reverses the "prg" to get the value that came before it
def prev(y):
#turn to bit string of 256 bits
y = "{0:b}".format(y)
y = y.zfill(N)

#the last bit can be decoded as any of the 4 values of x that could have set that bit
possibilities = dct[y[-1]]
#loop in reverse to get all possible values of x that could have created this y
for bit in reversed(y[:-1]):
new_possibilities = []
candidates = dct[bit]
for candidate in candidates:
for possibility in possibilities:
#if the last 2 bits of the candidate match the first two bits of an existing possibility,
#we can just append the first bit of the candidate to the possibility
if candidate[1:] == possibility[:2]:
new_possibilities += [candidate[0] + possibility]
possibilities = new_possibilities

#Do some more checks to see which possibilities are actually valid
real = []
for possibility in possibilities:
#the next function takes an input x, and turns it into x' such that the last bit of x' = the first bit of x, and the first bit of x' = the last bit of x
#so check that the values of possibility are valid x' values in this way.
if possibility[0] == possibility[-2]:
if possibility[1] == possibility[-1]:
real += [possibility]
if len(real) != 1:
print("there was an issue :(")
print(len(real))
sys.exit();

#convert back to an int
x = int(real[0], 2)

#reverse the bit operations done in next
#(move the first bit to be the N'th bit, shift the rest of the value to the right by 1)
x = ((x >> 1) & ((2**N) - 1)) | ((x & 1) << (N - 1))
return x



Once we could reverse the next function, we took the first keystream block used to encrypt, and reversed the bootstrapping loop to get back the original key:

python
#we can get part of the key stream by just Xoring together a plaintext and a ciphertext
# C = (M ^ K), so C ^ M = K, which lets us recover the keystream.
partial_keystream = xor(txt, enc)

#the first value of keystream used to encrypt the ciphertexts we've been given (the first 256 bits of the partial keystream)
base_key = int.from_bytes(partial_keystream[0:N_BYTES], 'little')

#use prev to reverse the key stream generation to get the original key
curr = base_key
for i in range(N//2):
curr = prev(curr)
print(curr.to_bytes(N_BYTES, 'little'))



And this outputs the key/flag:
![description](images/flag.png)

INS{Rule86_is_W0lfr4m_Cha0s}

The full solution code can be found here: [Link](./sol.py)

Original writeup (https://github.com/xPowerz/CTF-Writeups/tree/master/2018/Insomni'hack%20teaser/Rule86).