Crypto - Shuffling as a Service

You'll be 'shuffed to bits after trying the Krusty Krab's new bit shuffling service™!

Full Implementation

Challenge

First, we see how the bits are being shuffled

class BitOfShuffling:
    def __init__(self, key_length):
        self.perm = [x for x in range(key_length)]
        shuffle(self.perm)

    def shuffle_int(self, input_int: int):
        shuffled_int = 0
        for x in range(len(self.perm)):
            shuffled_int |= ((input_int >> x) & 1) << self.perm[x]
        return shuffled_int

    def shuffle_bytes(self, input_bytes):
        return self.shuffle_int(int.from_bytes(input_bytes, 'big'))

First, a list perm is created with values from 1 to 1024, and is shuffled (key length is 1024)

for x in range(len(self.perm)):
    shuffled_int |= ((input_int >> x) & 1) << self.perm[x]

This loop basically takes the (1024-x) th bit of the input, and places it in the location of the value of perm[x] For example, the last bit of the input will go to the perm[0] location of the shuffled integer. By knowing all the values of perm, we can then map the shuffled bits to the original bits and hence decrypt the ciphertext.

def rand_string(length):
    return ''.join(
        random.choices(string.digits + string.ascii_letters + r"""!"#$%&'()*+,-./:;<=>?@[\]^_`|~""", k=length))


def pad_flag(flag, length):
    pad_size = length - len(flag)
    if pad_size == 0:
        return flag
    left_size = randbelow(pad_size)
    right_size = pad_size - left_size
    return rand_string(left_size) + flag + rand_string(right_size)

The flag is then padded so we can't rely on any known plaintext attacks

The challenge uses a server which encrypts the flag and gives us three inputs which the server encrypts and gives us the encrypted outputs.

KEY_LENGTH = 128
trials = 10
if __name__ == "__main__":
    with open("flag.txt", "r") as f:
        FLAG = f.read()
    FLAG = pad_flag(FLAG, KEY_LENGTH)
    shuffler = BitOfShuffling(KEY_LENGTH * 8)
    output_int = shuffler.shuffle_bytes(FLAG.encode())
    print("Quite a bit of shuffling gave us this hex string: ")
    print(f'{output_int:0{KEY_LENGTH * 2}x}')
    print(f"You too can shuffle your hexed bits with our {trials} free trials!")
    for i in range(trials):
        trial = input(f"Input {i + 1}:")
        bits_from_hex = bytes.fromhex(trial)
        print(f'{shuffler.shuffle_bytes(bits_from_hex):0{KEY_LENGTH * 2}x}')
    print("See you next time!")

Exploit

To fully understand how the bits are being shuffled, lets take a smaller input, with only 8 bits

From this example

$11111110 \rightarrow 11111101 \\ 11111111 \rightarrow 11111111$

Since everything is kept constant, we can conclude that the last bit is shifted to the second to last bit position

However, this approach is really inefficient, so we need some other way to figure out how its being shuffled. We can make a few observations from the example First, the same input returns the same output so there's no point using the same inputs Similarly, the same substrings used at the same location in two different inputs return the same output at that location

The idea is to make the inputs as unique as possible, so that we won't have any repeating input or any part of the inputs repeating so as to gain new information everytime.

One method to do this is to take half 1 , half 0 then quarter 1 quarter 0 quarter 1 quarter 0 and keep dividing it in this manner. The purpose of this is to make sure that we have no repeating substrings in the same locations for any of our inputs For example,

$11110000 \rightarrow 00111100 \\ 11001100 \rightarrow 10100101 \\ 10101010 \rightarrow 11101000$

But how do we get the shift pattern from these inputs?

We divide the input and outputs as column vectors of this format

Column vectors for input and output

Notice how all the vectors are unique from each other. This is due to the construction of the input. The reason for grouping all the column vectors is because they all shift to the same location. From this, we can now easily map the input to the output. For example, the last column vector in the input (0,0,0) is shifted once to the left in the output, and due to the all the vectors being unique, we ensure that (0,0,0) appears once only once and therefore figure out that that any bit in that position will be shifted once to the left. In other words, perm[0] = 1 (Here 1 represents the total shift amount from the right, where 0 is the number of bits to skip from the right). Similarly, we can map the rest of the vectors and we get perm value as [1,6,0,7,4,3,2,5] Also we require 3 inputs to do this. If we had 2 inputs for example, then atleast two of the vectors would have matched and we cant tell which is vector is being shifted. We require 3 inputs for 8 bits since 2^3 is 8 , which gives us all unique combinations. Similarly, for 1024 bits we require 2^10 = 1024 or 10 inputs , which is the number of trials provided by the server.

Implementation

First, we have to construct the inputs with alternating 0 s and 1 s

The general formulation is

$$2^i((2^{(10-i)})*"1"+ (2^{(10-i)})*"0")$$

where i is from 1 to 11

ans=[]
for i in range(1,11):
    ans.append((2**i)*((2**(10-i))*'1' + (2**(10-i))*'0'))

We get the outputs and pad them to ensure 1024 length

sans =[]
for i in range(10):
    t1=shuffler.shuffle_bytes(long_to_bytes(int(ans[i],2)))
    sans.append(bin(t1)[2:])
for i in range(len(sans)):
    sans[i]=sans[i].rjust(1024,'0')

We then map the output to the input and declare a variable to map the message from the encrypted flag

f1=[]
for i in range(1024):
    t2=''
    for j in range(10):
        t2+=sans[j][i]
    f1.append(int(t2,2))
h1=['0' for i in range(1024)]
oint = bin(oint)[2:]
oint=oint.rjust(1024,'0')
for i in range(len(f1)):
    h1[f1[i]] = oint[i]

Finally, we reverse the bits since we considered the MSB to be the 0th bit and the LSB to be the 1023rd bit and decrypt the ciphertext

print(long_to_bytes(int(''.join(h1)[::-1],2)))
#b'D`O>JK&*_B5Tz7n|~F6#`Eb2F%]Q?;djD6)yH<gJY*]h"\'blx%t$PC|~bl^BQ?vrp@4f(\',D4KTIZRLDF/tya>zlXfMgmUu^7+NVEES=h9&'