![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 argparseimport sys
parser = argparse.ArgumentParser()parser.add_argument("key")args = parser.parse_args()
RULE = [86 >> i & 1 for i in range(8)]N_BYTES = 32N = 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 PNRGkeystream = int.from_bytes(args.key.encode(),'little')for i in range(N//2):  keystream = next(keystream)
# Encrypt / decrypt stdin to stdoutplainte```
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 ustxt = 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 arraysdef 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.encdef 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 decryptdef 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 bytesdef 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.pyRULE = [(86 >> i) & 1 for i in range(8)]N_BYTES = 32N = 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 functiondct = {    #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 itdef 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 keycurr = base_keyfor 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)