Note: All the related files that are mentioned in this post can be found here.
Category: Rev
The task:
Like in the good old days, but faster.
SSE_KEYGENME - https://kaf-public.s3-eu-west-1.amazonaws.com/SSE_KEYGENME/SSE_KEYGENME
In this challenge, we were given a binary:
$ ./SSE_KEYGENME
###############################
### WELCOME TO SSE_KEYGENME ###
### ENJOY YOUR STAY ###
###############################
Enter key:
> AAAAAAAAAAAA
Wrong key, try again...
The flag
is a static variable, lays in the .rodata
section:
+pwndbg> x/32xb &flag
0xe40 <flag>: 0x43 0x51 0x43 0x36 0x40 0x52 0x21 0x55
0xe48 <flag+8>: 0x24 0x42 0x5b 0x68 0x7d 0x67 0x1f 0x7b
0xe50 <flag+16>: 0x5d 0x7e 0x4e 0x0e 0x58 0x04 0x22 0x40
0xe58 <flag+24>: 0x1e 0x14 0x16 0x2c 0x20 0x22 0x26 0x34
However, this is an encrypted version of the flag.
What the program does is:
- gets a string input from the user
- encrypt the input
- checks whether the encrypted input == the flag
- if it does, it prints
Success! Enjoy the rest of the competition :)
- if it doesn’t, it prints
Wrong key, try again...
- if it does, it prints
There are two approaches of solving this challenge:
- Brute-force techniques(the nasty way): guessing each letter at a time in a dynamic analysis/ugly GDB scripting until you’ll get the full decrypted string.
- Reverse engineer the program and learn how the encryption is implemented so you can write your own decryption script.
This write-up covers the 2nd approach.
Technical Analysis
Prerequisites
In order to read this writeup without being too frustrated, you’ll need to understand:
- A little bit about the Concepts of Substitution–permutation Networks . In the binary, it is implemented using the variables
p_box
andx_box
(which are also mentioned in this video. Referred as “S box and X box”)- More background here: http://www.eng.tau.ac.il/~yash/crypto-netsec/blockciphers1.htm
- Basic stuff about SSE registers (being familiar with
xmm0
,xmm1
registers is enough) pshufb
instruction(awesome demo at 8:05): https://www.youtube.com/watch?v=rBYrQ1OEhik
How the program encrypts our input
The program uses a 128bit block cipher and the flag length is 2 blocks / 32 bytes(0x20
).
The cipher implementation goes as follows(each step is covered below):
- Step 1, Padding - if the input text is less than 32 bytes(
0x20
), the program will be pad it with extra bytes. - Step 2, Shuffling - Shuffles our input to add complexity using the
pshufb
instruction. - Step 3, XORing - Adding more uniqueness to each byte in the final ciphertext.
Padding is kinda boring, so I’ll jump straight to the interesting steps: Shuffling & XORing
Step 2 - Shuffling
The program takes the first 16 bytes of the input(block of 128 bits) and shuffles the order of the characters using the pshufb
instruction:
-
First, the program “generates” a 16-byte variable using the following instructions sequence:
It’s doing a lot of repetative left shifting until it completes a full 128bit block.(which is made out of0x01
s). Essentially, the following one-liner will yield the same result:some_var = 0x01010101010101010101010101010101
. -
Then, the program takes the
p_box
variable and substract0x01010101010101010101010101010101
from it:
p_box: 0x4090a0d0f0b081003060c010e050702
mask: 0x1010101010101010101010101010101
p_box "masked": 0x308090c0e0a070f02050b000d040601
3. It’s using the result(0x308090c0e0a070f02050b000d040601
) as the shuffle map when the shuffle is performed. If you’re wondering how the pshufb
instruction works and what exactly that map is: you should check out the URLs in the “Prerequisites” section above.
Step 3 - XORing
When the shuffle is completed, the binary XORing the result with x_box
.
The contents of x_box
is below:
+pwndbg> x/16xb &x_box
0xe30 <x_box>: 0x02 0x03 0x05 0x07 0x0b 0x0d 0x11 0x13
0xe38 <x_box+8>: 0x17 0x1d 0x1f 0x25 0x29 0x2b 0x2f 0x00
As can be seen in the screenshot below, the program uses (again) the SSE registers here as well to perform the XOR operation on 16 bytes at a time:
And that’s it, we’re done cooking one cipher block :D now the same process repeats itself for the next 16 bytes/128bits of your input.
Writing a decryption script
If we want to decrypt the cipher flag, we can just perform the steps above in reverse order:
- Recover the original characters: XOR the blocks of the cipher flag with
x_box
- Invert the permutation: Reverse shuffle the blocks and clean up the mess that the
pshufb
instruction made.
Below is the decryption script:
Output:
plaintext: KAF{F0R_0LD_T1M3S_S4K3}
Special Kudos
When I solved this challenge, I didn’t know why my decryption script f**ked up and showed only part of the flag. It was really weird.
After the CTF ended, I showed @lior5654 (random dude I found on the discord channel) my solution and he said that I was actually on the right track. However, I used the wrong endianness + flipped the array indexes when trying to recover the permutation, it created a weird output that might look like the flag, but not exactly the flag (more like a drunk flag lol). So thanks for taking the time to correct my (shitty) python syntax at the middle of the night :D