Problem F
A Block Cipher

The Final Layer

The final layer between you and decrypted files is a block cipher that the ransomware developers have constructed. The library implementing this routine was reverse engineered and the details are below. There was no associated code in the malware report, so your task is to implement both the encryption and decryption routines.

A block cipher is an encryption method that works on chunks of fixed sized data called blocks, rather than encrypting one byte at a time as we saw in the RC4 stream cipher. Similar to the stream cipher, it is a symmetric algorithm, meaning that the same key is used to encrypt and decrypt the data. Block ciphers are sometimes easy to recognize, since the total length of the encrypted data is often a multiple of the block length.

It appears as though the developers have done their research on block ciphers and have decided to use a Feistel cipher. This is a symmetric encryption construct common in other block ciphers such as DES and Blowfish. They are naturally invertible and the decryption process is essentially the same as the encryption process with only a slight adjustment involving reversing the key schedule. Details below should be sufficient to accurately build the routines and test against some blocks of data.

The Block Cipher

This block cipher is a series of repeated “rounds” which take a $64$-bit block and encrypts it using some pre-defined parameters and the user-defined key $K$. The input block of data is split into two equal halves ($32$ bits each) which we will call $L_0$ (left) and $R_0$ (right). For each “round” of the cipher, we transform into the next layer in the following manner:

where $\oplus $ is XOR and $F$ is defined as:

where $\Delta _ i$ is a changing value, $k_ a$ and $k_ b$ are subkeys, all variables are $32$-bit unsigned integers, $\sim $ is negation, and $\boxplus $ is addition of $32$-bit unsigned integers.

To decrypt a block, we take our output through a similar process with an altered key schedule. See the wire diagrams (Figures 1 and 2) below to visualize a single encryption and decryption round of this algorithm.

Figure 1: An encryption “round”

Figure 2: A decryption “round”

For the complete algorithm (Algorithm 1), take one block of input, put it through the encryption round $64$ times, and swap the final output block halves. For the $\Delta _ i$, we use a value that is constantly incremented by ${\tt 0xBB40E64D}$ (the first 10 digits of $\pi $ as a whole number). This is commonly referred to as a “nothing-up-my-sleeves” number, since by its construction, is above suspicion of hidden properties.

For decryption, the process is almost exactly the same except now we are decrementing $\Delta _ i$ from an accumulated value ${\tt 0xD0399340}$ and we use the decryption round $64$ times (which uses the keys in a different order) before finally swapping the final output block halves again.

Test Vectors for F

The F function plays a large role in the algorithm above. Here are some test vectors to check against when setting everything up.

Input

The input consists of 3 lines. The first line is ENCRYPT or DECRYPT, use this to determine if the data should be encrypted or decrypted. The second line is the HEX representation of the KEY. The last line will be the single block of data in HEX which you will encrypt or decrypt.

Output

Output the HEX representation of the output of either ENCRYPTing or DECRYPTing the data block using the KEY.

ENCRYPT
4558414d504c452054455354204b4559
4558414d504c4521

9e8aee15025da3a8

DECRYPT
4558414d504c452054455354204b4559
9e8aee15025da3a8

4558414d504c4521

ENCRYPT
01020304050607080102030405060708
0102030405060708

f57d877b03a95625

DECRYPT
3661cbda25091dd9c7daf74e3cfb8f95
32be98e97079d472

8dfa25437efa5f44