# Crypto - Shuffling as a Service

## [Full Implementation](https://github.com/kinasant/THR34DR1PP3R/blob/main/2024/UMASS/Shuffling%20as%20a%20Service/publish.ipynb)

## Challenge

First, we see how the bits are being shuffled

```python
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)

```python
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.

```python
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.

```python
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&#x20;

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&#x20;

<figure><img src="https://2017398282-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FUn3m91wNDAeWCUHREmIX%2Fuploads%2FQXE9DYup6Z6wb9wL05vN%2Fimage.png?alt=media&#x26;token=83ca92d5-bcec-4ad7-988f-1836cdd39337" alt="Column vectors for input and output"><figcaption><p>Column vectors for input and output</p></figcaption></figure>

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&#x20;

The general formulation is&#x20;

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

where i is from 1 to 11

```python
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

```python
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

```python
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

<pre class="language-python"><code class="lang-python">print(long_to_bytes(int(''.join(h1)[::-1],2)))
#b'D`O>JK&#x26;*_B5Tz7n|~F6#`Eb2F%]Q?;djD6)yH&#x3C;<a data-footnote-ref href="#user-content-fn-1">UMASS{6Huff3d_2_b1t5}</a>gJY*]h"\'blx%t$PC|~bl^BQ?vrp@4f(\',D4KTIZRLDF/tya>zlXfMgmUu^7+NVEES=h9&#x26;'
</code></pre>

[^1]: Flag


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://thr34dr1pp3r.gitbook.io/ctf/umass-ctf-2024/crypto-shuffling-as-a-service.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.