Tags: crypto

Rating: 5.0

# Queensarah2

**Category**: Crypto \
**Points**: 200 \
**Solves**: 37 \
**Author**: UnblvR

## Challenge

The secret mainframe for a distributed hacker group has been discovered. We
have managed to exfiltrate some of the code that it runs, but we don't have a
physical copy of their access badges. Can you still get the flag?

Remote: nc queensarah2.chal.perfect.blue 1

Note: enter flag as pbctf{lower_case_flag_text}

By: UnblvR

## Solution

Looks like a home-rolled crypto algorithm. Basically it creates this dictionary
called S_box that maps all possible bigrams to another bigram from a shuffled
set.

python
bigrams = [''.join(bigram) for bigram in product(ALPHABET, repeat=2)]
random.shuffle(bigrams)

S_box = {}
for i in range(len(ALPHABET)):
for j in range(len(ALPHABET)):
S_box[ALPHABET[i]+ALPHABET[j]] = bigrams[i*len(ALPHABET) + j]


Then the encryption step is like this:
python
rounds = int(2 * ceil(log(len(message), 2))) # The most secure amount of rounds

for round in range(rounds):
# Encrypt
for i in range(0, len(message), 2):
message[i:i+2] = S_box[''.join(message[i:i+2])]

# Shuffle, but not in the final round
if round < (rounds-1):
message = \
[message[i] for i in range(len(message)) if i%2 == 0] + \
[message[i] for i in range(len(message)) if i%2 == 1]


So basically, it's like this:

![encrypt](imgs/encrypt.png)

The challenge server will encrypt anything for us, so what happens if we just
send it one bigram?

![two](imgs/two.png)

Ok, what happens if we take the encrypted output (az in the image above), and
send it to the server over and over again? Then eventually we'll get back to
where we started.

Turns out this is all we need to crack the encryption.
1. Make a set of all bigrams
2. Remove a bigram (store it in a var as the starting point) and send it to the
server
3. Take the returned value and remove it from the set
4. Send that bigram to the server
5. Repeat until we get back to the start
6. Go to step 2 and repeat until we checked all 729 bigrams
7. If we're lucky, we can bruteforce all possible values of S_box and get 1
correct decryption

The idea goes like this:
- S_box maps bigrams to another bigram (no two bigrams map to the same one)
- So there has to be at least one cycle
- Each cycle can either have even or odd length

![even_odd](imgs/even_odd.png)

Since sending a single bigram to the server will make it go through
S_box twice, we have to jump over 1 element in the cycle each time.
- If the cycle has odd length, we can still get to every element in the cycle
- If the cycle has even length, we can only get two halves of the cycle. What
can we do?

![even](imgs/even.png)

Yeah, we can just bruteforce by rotating one of halves n times. But what if we
have more than one even cycle? Then we have to bruteforce all of them. If we're
lucky, the total number of iterations will be small.

Here are cases for the types of cycles in S_box we'll encounter. If we get a
bad S_box then we just close the connection and try again.

![cycles](imgs/cycles.png)

I wrote a semi-working script in [guess.py](guess.py), and during the CTF I just
let it run in the background. After around 20 minutes it got lucky:

atmxovxmydgu_colfvllcxdffczoachaatekepcveppptfirxzhbuinv__
merftbsckhmidlylpn_smzjcguxbhgefekgwjypqqkswoeoyl_wwsofbpj
brmecffzjpeewxbsispphlygeeetbl_fbwlhmdlqyowkdcejixrrjxkihw
slide_attack_still_relevant_for_home_rolled_crypto_systems
uwqnnykpzr_jwuieitlkfdsfahuywguoqnaomqhxpriruwnkuxbpbhhuoz
a_egexqtpazpvkkodgibwvxi_c_sfcphrthinnjzeglecdggaa_d_vsfvj
awqnqrmjmeikmgdjrc_ojviatxtwkmrjajuoi_buewwamyzlqvzuatpihe

...

> slide_attack_still_relevant_for_home_rolled_crypto_systems
You got it. The flag is pbctf{slide_attack_still_relevant_for_home_rolled_crypto_systems}


Thanks perfect blue for the cool challenge!

Original writeup (https://github.com/qxxxb/ctf/tree/master/2020/pbctf/queensarah2).