CSAW Quals 2017 BabyCrypt Writeup

Solved by s0rc3r3r

Points: 350

In this challenge, we were given a ciphertext encrypted using AES in ECB mode. In ECB mode, encryption of each plaintext block does not affect the encryption of the next plaintext block. Mostly in challenges, the attack on ciphertexts encrypted using block size mode of encryption works as follows:

1. Mode Detection (ECB, CBC, CTR etc.)
2. Block size detection
3. The actual attack based on the facts collected from Step 1 and 2

Here is how ECB mode encryption works:

You can read more about ECB mode of encryption on this blog and here on Wikipedia

In this challenge, it was already given that the mode of encryption is ECB mode. So, we move on to step #2 which is Block Size Detection. In this step, we keep sending input, increasing the input’s size by one byte each time and noting the length of the ciphertext for the corresponding input, until the length of the ciphertext changes. The size of the block is then equal to the difference between the size of new ciphertext (number of bytes) and size of the previous ciphertext (number of bytes).

As you can see, as soon as a new character is added to the input, the size of the ciphertext changes, the difference between them is 32 hex characters or 16 bytes! So we have detected the block size to be 16 bytes! You can read more on this blog where I have explained about block size detection in detail.

In the server, the encryption takes place as follows:

1. Takes in input from the user
2. Append the secret (our flag) to the input
3. Pads it to make a multiple of the block size
4. Encrypts the resultant plaintext
5. Gives the output to the user.

The plaintext which is being encrypted in the server is as follows:

input | secret | padding

So, among all these points, we are only in control of Point #1 which is the input we give. And using this we need to get the secret which is there on the server.

Now comes the actual attack on the ciphertext. The block division is as follows:

      #1     |      #2      |      #3

16 bytes | 16 bytes | 16 bytes

What we give as the input, goes in block #1 if size(input) < 16 bytes. The secret is present in a block next to the block in which our input is present. What if we give an input which has a size one less than the block size? Then the last character in the first block is the first character of the secret. We know the first 15 bytes of block #1, we can simply brute force 255 possibilities of the 16th byte in block #1 by checking the corresponding ciphertexts. This happens as follows- Suppose I give the input as 15 times a, the block division becomes:

                                 #1                              |                      #2 , #3

“aaaaaaaaaaaaaaa” + 1 byte of secret | other bytes of secret | padding

The first 16 bytes(32 hex chars) of the ciphertext generated from this is the encrypted form of the first block. Now we can brute force the value of the last byte of the secret which is present in block #1. Here is the python code for brute forcing the last byte:

from pwn import *
import string 

string_sent = "a"*16
r.recv()
r.sendline(string_sent)
g1 = r.recvuntil("\n")[16:-1]
g1 = g1[:32]

for j in range(256):
            r.recv()
            r.sendline(string_sent + chr(j))
            g2 = r.recvuntil("\n")[16:-1]
            g2 = g2[:32]
            if g1 == g2 and chr(j) in string.printable and j!=10 and j!=0:
                print chr(j), j
                break

Then we move on to the next byte of the secret; this time we send the input as 14 * ‘a’ plus the last byte of secret(flag) which we get from the above code. Similarly, we get other bytes of the secret by giving the input as (16 – i) * ‘a’ + decrypted_bytes_of_secret, where i is the ith byte to be decrypted from the secret!

At this point of time, we have decrypted 16 bytes of the flag, now we can further move on to the next block of the secret using the same concept we applied above.

Here is the python code for the entire exploit:

from pwn import *
import string

r = remote("crypto.chal.csaw.io","1578")
plaintext = ""
blocksize = 16

# The flag occupies 2 blocks
for k in range(2):
    b = ""
    for i in range(1,17):
        string_sent = "a"*(16-i)

        r.recv()
        r.sendline(string_sent)
        g1 = r.recvuntil("\n")[16:-1]
        g1 = g1[:32+k*32]
        print "String sent: ",string_sent

        for j in range(256):
            r.recv()
            r.sendline(string_sent + plaintext + b + chr(j))
            g2 = r.recvuntil("\n")[16:-1]
            g2 = g2[:32+k*32]
            if g1 == g2 and chr(j) in string.printable and j!=10 and j!=0:
                print chr(j), j
                b += chr(j)
                break
    plaintext += b
    print plaintext

So, I ran the script and here is the output:

Block #1 of Secret:

Block #2 of Secret and the final flag:

Cheers!