I implemented this really cool Rubiks CBC encryption algorithm and tested it on a document with my flag in it, but my dog ate my hard drive so I couldn’t decrypt the file :(. Luckily I backed up the encrypted file. Can you recover my data?
First Blood: 1 hour, 36 minutes after release by team aetjia
We are given 2 files, a file of scrambled data and a README file.
IV = “ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuv”
SCRAMBLE = D R2 F2 D B2 D2 R2 B2 D L2 D’ R D B L2 B’ L’ R’ B’ F2 R2 D R2 B2 R2 D L2 D2 F2 R2 F’ D’ B2 D’ B U B’ L R’ D’
What can we gleam from this file:
The example scramble and IV tells use that the cipher uses a block size of 54 bytes, one byte per tile on the rubiks cube.
The algorithm must translate a flat block of data to a net of a cube in the following way:
That the encryption operation most likely is just a rubiks cube permutation of each block
Defining a Rubiks Cube in Python
Keeping in mind we are in a CTF competition and solving the problem is time sensitive, lets build a quick and dirty rubiks class to represent movement of the cube.
First we need a way to translate a block into a rubiks cube net
Lets test the above code
So we have a way to load a block into the cube net and out again.
The next step is to implement movement. The good news is that actually we can implement every possible move on a 3x3 rubiks cube with combinations of only 3 moves. We just need to be able to rotate a face, and to rotate the cube on 2 axes. More on this later. Add the below move functions to our class:
For the rot_x and rot_y functions, we simply define rotating the entire cube on the X and Y axis. The numpy array has a convenient rot90 function which handles rotating the tiles on a face, in rot_F we just need to worry about the tiles perpendicular to our rotated face tiles, you can see the code for this in the for loop in that function.
After some testing to confirm rot_x, rot_y and rot_F permute the cube how we expect, we can go about implementing the rest of the moves required for a barebones rubiks cube to work
If it isn’t clear what is happening, it might become clear if you have a look at this website or played around with one you have lying around. The point is, we can combine the moves x, y and F in such a way that we can define any other possible move on a rubiks cube. Take the rot_U function as an example:
U means “rotate the U face (upward face) 90 degrees clockwise” and U' means the same but counterclockwise. If we run the x' move first, however, the U face becomes the F face, for which we have already defined rotation. From there it is as simple as running our rot_F function and returning the face to its U position by running x
After testing these to confirm they work we can move on to the final step: defining a way to apply an entire algorithm to the cube in one go.
Lets test it:
Running the above script:
So as far as reasonable testing would demonstrate, this works. There is however one more small modification that needs to occur for our cube object to be used in the decryption algorithm we are about to implement: we need it to work with blocks of bytes not strings.
Specifically we want to construct a cube with 54 bytes of data, not 54 characters, and we want to be able to get the permutated bytes out again in the right format.
To do that we simply make sure our numpy arrays in the __init__ function take bytes as a data type, and modify the flat_str function to get the bytes rather than a string.
Lets review CBC decryption to understand the algorithm we need to implement:
So the process in steps is as follows:
Take the final cipher block and unscramble it
xor the unscrambled block with the previous cipher block
Save the plaintext
repeat with next cipher block
When we reach the first cipher block, xor with the IV
Running the above code against the encrypted data successfully decrypts a valid PDF, see the test below:
The decrypted document is RFC 2549, IP Over Avian Carriers with QoS. On page 4 there is a QR code containing the flag.
If you want to play around with this toy cipher, you can access the code used for encryption and decryption in this repository . Otherwise if its the simple rubiks cube implementation you are looking for, you can access it from the link in this post or from this repository