## Intro

We’re going to knock out three in one here as the other 1-star crypto challenges in this CTF weren’t incredibly complicated, and I can’t really justify 3 separate posts for each of them.

Android in the Middle was a cute little play on the Diffie-Hellman Man-in-the-middle attack where you could submit your own public key in the exchange and then need to provide an encrypted string, but you don’t have any other information aside from the public key of the server. So, we can use math to submit a public key of 1 so we can bootstrap the encryption ourselves to get the flag.

Jenny from the Block was a super simple custom block cipher that suffered from knowing a plaintext-ciphertext combination, which allows you to bruteforce the initial key, which you can then use to decrypt the following blocks as the encryption algorithm is super easy to reverse.

How the Columns Have Turned was an easy challenge that I just spent way too long on because I didn’t read closely enough. It features an ineffective PRNG to generate a key for a Columnar Cipher that’s been modified to operate on the transpose of the initial set of blocks. However, this isn’t that hard to reverse.

## Android-in-the-Middle

### Description

`Years have passed since Miyuki rescued you from the graveyard. When Virgil tells you that he needs your help with something he found there, desperate thoughts about your father and the disabilities you developed due to the disposal process come to mind. The device looks like an advanced GPS with AI capabilities. Riddled with questions about the past, you are pessimistic that you could be of any value. After hours of fiddling and observing the power traces of this strange device, you and Virgil manage to connect to the debugging interface and write an interpreter to control the signals. The protocol looks familiar to you. Your father always talked about implementing this scheme in devices for security reasons. Could it have been him?`

### Challenge

We’re given source code to a live instance.

The server will generate a public key for itself using a secure prime and generator value and tell us what it is. We’re then prompted with a field to submit our own public key, and then are expected to submit an encrypted string to get the flag back.

This challenge is making use of the Diffie-Hellman Key Exchange, which is a public key protocol commonly used to bootstrap symmetric encryption. I won’t go into the details here, but I’ll steal a quick slide from my Encryption class.

Here, we select a public prime p, and a generator for that mod-p group, g. Alice selects a secret value x, and Bob selects a secret value y (both are within the field). They both exchange exponentiated values, which are their public keys, and then each raises the other’s public key to the power of their own secret. Notice that x and y are never shared across the channel where an eavesdropper could be listening. This is secure because of what’s known as the Discrete Logarithm Problem. The gist of it is that you can’t just take the log of the value you get, because the mod p wraps it around such that it’s seemingly random.

Now that we understand Diffie-Hellman from a high level, how do we find the secret if Alice never gives us her public key? Well, it’s pretty simple. Just say your public key is 1.

$\begin{aligned} K \equiv 1 \equiv 1^x \pmod p \end{aligned}$1 to any power is 1, so we can then just use the value of 1 to bootstrap our AES encryption as shown in the challenge.

### Solution

Running it, we get the flag:

## Jenny From the Block

### Description

`Intrigued by the fact that you have found something your father made, and with much confidence that you can be useful to the team, you rush excitedly to integrate “Jenny” into the spaceship’s main operating system. For weeks, everything went smoothly, until you ran into a meteor storm. Having little to no data of training, the AI is now malfunctioning. Ulysses freaks out because he can no longer control the spaceship due to the AI overriding his manual commands. Big banging noises terrify your crew members. Everything is shaking. It’s time to act. Do you think you can temporarily shut down “Jenny” until she becomes more sophisticated?`

### Challenge

We’re given more source code to an instance.

The function of the instance isn’t terribly complicated, run one of four predetermined commands, get the output (concatenated with additional strings) back but encrypted. Interestingly, there isn’t any common block cipher in use, in fact, it’s custom. Luckily, the encryption function is fairly simple.

We begin by breaking up our message into 32 byte blocks. The initial password is the SHA256 hash a random 32 bytes. For each block in our set of blocks, we will encrypt the block by adding the bytes moduluo 256. We then set the new password to be the SHA256 sum of the encrypted block concatenated with the plaintext block. More visually:

We can actually recover the initial key very easily. Recall that our message is command is being preppended by “Command executed: “. Turns out, the length of “Command executed: cat secret.txt” is exactly 32 bytes. So, we can bruteforce the initial key because the algorithm is pretty fast, and from there, we can run the algorithm as shown in the source code to recover the rest of the plaintext keys. The modulus operation can be reversed by simply subtracting instead of adding, so we’re good to go!

### Solution

The first half of this code simply gets the output of `cat secret.txt`

and bruteforces the first block by running the encryption calculation on each byte until it lines up. Then, we simply iterate over the blocks we recieve, subtract the bytes modulo 256, set up our new key, and we’ve reversed the encryption. Running the script:

Note the weird `\x07`

’s at the end. This is because the plaintext was padded, meaning we added bytes at the end, to make sure it hit a multiple of 32. While it wasn’t absolutely necessary here, other algorithms might need it because they’re programmed to use all of bits in the block in a way that can’t really adapt to different lengths.

## How the Columns Have Turned

### Description

`A day before the memorial of the Dying Sun, Miyuki began talking about Broider, a death squad commander and a friend of Paulie’s capturer. He would be a party guest at Viryr’s palace. After examining a lot of different scenarios, Miyuki came up with a plan in which Paulie would lure Broider to a secluded location so the group could capture him. Following the plan, a wild chase had just begun when the two looked each other in the eye. After an extremely risky maneuver, Paulie outwitted Broider and led him into an alley in Vinyr’s undercity. The plan was a success. Your squad had managed to capture Broider and bring him back to the ship. After hours of interrogation by Ulysses, he revealed the final key to a series of encrypted messages. Can you find a way to decrypt the others? The flag consists entirely of uppercase characters and has the form HTB{SOMETHINGHERE}. You still have to add the {} yourself.`

### Challenge

There was no instance for this challenge. We were given the encryption script, a `dialog.txt`

, and `encrypted_messages.txt`

.

This challenge was a little interesting because of the use of the columnar cipher, a transposition cipher similar to the Railfence Cipher because of how you manipulate the plaintext. Explaining the entire algorithm is going to take a while because of how many images I’ll have to put up, but I’ll quickly describe it.

- Start by selecting a key that will act as a permutation for our plaintext
- Write the plaintext in a grid/matrix where the number of columns is the length of the key
- Using your key, go to the corresponding column, and read down to get ciphertext
^{Credit: link}

In this example, our plaintext is “The tomato is a plant in the nightshade family”, and our ciphertext is “TINESAX / EOAHTFX / HTLTHEY / MAIIAIX / TAPNGDL / OSTNHMX” (slashes included to make it easier to understand the breakdown).

For our challenge, we can immediately jump to analyzing the columnar cipher because the PRNG literally does not work. Since $a = p$, the modulus will always return $b$, and since we are given the last key, we know all of the keys before it.

What I struggled with for so long was understanding what `twistedColumnarEncrypt()`

was doing because of all of the Python one-liners. After deriving a key (the permutation), we break our plaintext into blocks, but then run `transpose()`

. If you’ve ever taken a Linear Algebra class or have worked with matricies before, you’ll remember that a transpose operation will basically flip the rows and the columns, which is exactly what the function does. The encrypt function then shifts the matrix around by rows, and spits out a ciphertext. I struggled to understand this via looking at the code, so I had to write it out by hand:

So, it’s really not that hard to actually reverse the encryption at all if you know the permutation. The red indicates how you shouldn’t reverse it. You should break it up into blocks of 4 instead of 3 because of the dimensions of the initial setup.

### Solution

The code basically does the reverse of what I showed on the whiteboard. The only big difference is the inclusion of the `inv_derived_key`

, which is just the inverse permutation of the initial key, which we can see by running the `deriveKey`

on the string in `dialog.txt`

. Running the script, we see a long block of text (we love lore ;-;).

Flag: `HTB{THELCGISVULNERABLEWENEEDTOCHANGEIT}`