Crypto - 100 Points

Acid Burn found this AES-CBC encrypted text in the garbage file that Joey stole from the Gibson.
Sadly, Joey didn’t get the full S-BOX used by The Plague. Can you help them recover the text?

Writeup

This challenge wants us to dive into AES internals.

AES stands for Advanced Encryption Standard and it’s a subset of the Rijndael cipher.
Rijndael is a Simmetric-key Block-cipher algorithm.
AES standard uses 128, 192 and 256 bits keys, each with 10, 12 and 14 rounds.

The Ciphertext, IV and Key are given. The Key is 128 bits.

But…
The given ciphertext is encrypted using a custom SBox.

What is an SBox (Substitution Box) ?

AES works in rounds.
10 rounds if the key is 128 bit, as in this case.

For every round 4 operations are performed (note: except for the Initial and the Final round):

  • SubBytes
  • ShiftRows
  • MixColumns
  • AddRoundKey

Here we are interested in the SubBytes function that performs a non-linear substitution where each byte is replaced with another according to a lookup table (our SBox).

More on AES internals and Rijndael_S-box on Wikipedia :)

So, from the sbox.txt file we can see that the last 16 bytes are missing.

We need to bruteforce them but we have 16 bytes with 16 possible values (from 0x0 to 0xf).
16^16 = 1,844674407×10^19. Hold your processor.

In reality, SBox-es are matrices where each cell can only have 1 unique value, from 0x00 to 0xff.
So we don’t have to bruteforce the entire space.

For example, this is the standard Rijndael SBox: AES SBox

We can simply calculate what are the missing values and permutate their positions at the end of the SBox.

Another thing. We are given the SBox, but in decryption Rijndael uses the inverse-SBox.
We can calculate the inverse by looking up the table.

For example, looking at the standard Rijndael SBox above:

S[0x0][0x0] = 0x52
Sinv[0x5][0x2] = 0x00

The permutation of 8 values in 8 positions are 8! = 40320. Very bruteforceable :D

The steps to decrypt the ciphertext are:

  • Find the missing values in the SBox
  • Permute those values at the end of the SBox
  • For each permutation:
    • Invert the SBox
    • Try to decrypt the ciphertext with key and IV
  • Party Hard!

The password to access the swiss bank account is SECT{1_L0V3_FUN!_BUT_M0N3Y_15_B3773R!}. I shouldn't forget it.

Flag

Here the full script I wrote to solve the flag.
It was a nightmare finding a Pure-Python AES library and use custom SBox-es, I’ve forked and modified pyAES to do this.