Points: Dynamic

Solves: 48

Description:

AES is unbreakable. Right?

nc 52.193.157.19 9999

flag format: hitcon{…} (use the one in GitHub as test)

Given:

secretserver-03f9e1472f1088fcf5571d3288e759e3.py

Solution:

(by L0rdComm4nder and majo)

TLDR

This attack has several steps

  1. Get the encrypted flag by IV manipulation
  2. Get the 1st block by IV manipulation using the fact that hitcon{ is as long as get-sha and use 128 average tries to find each byte of 1st block
  3. Find the length of padding
  4. Use 3. to get the 1st half of 2nd block using the fact that .strip() removes \n both at the beginning and at the end of a string
  5. Repeat 2. to get the 2nd half of 2nd block.

Description

There might be some more efficient solutions but the one that follows is the first that came to our mind and there is minor effort involved. Some interesting facts we get by looking at the given file.

  • Chall uses AES in CBC mode

  • Notice that the padding function looks like PKCS7 but the unpadding function does not check that. In particular, the unpadding function drops as many characters as the last one. This will be usefull in steps 3. and 4.

def pad(msg):
    pad_length = 16-len(msg)%16
    return msg+chr(pad_length)*pad_length

def unpad(msg):
    return msg[:-ord(msg[-1])]
  • Saddly, there is no padding error in decryption :-(

  • Send message uses always the same iv but the recv_msg decrypts with whatever iv is given.

def send_msg(msg):
    iv = '2jpmLoSsOlQrqyqE'
    encrypted = encrypt(iv,msg)
    msg = iv+encrypted
    msg = base64.b64encode(msg)
    print msg
    return

def recv_msg():
    msg = raw_input()
    try:
        msg = base64.b64decode(msg)
        assert len(msg)<500
        decrypted = decrypt(msg[:16],msg[16:])
        return decrypted
    except:
        print 'Error'
        exit(0)
  • Messages are always sent encrypted but

a. we can get the encryption of some fixed messages send_msg('Welcome!!') and send_msg('command not found')

b. we can get the encryption of the uknown flag send_msg(flag).

c. we can get the encryption of several different hash-functions

if __name__ == '__main__':
    proof_of_work()
    with open('flag.txt') as f:
        flag = f.read().strip()
    assert flag.startswith('hitcon{') and flag.endswith('}')
    send_msg('Welcome!!')
    while True:
        try:
            msg = recv_msg().strip()
            if msg.startswith('exit-here'):
                exit(0)
            elif msg.startswith('get-flag'):
                send_msg(flag)
            elif msg.startswith('get-md5'):
                send_msg(MD5.new(msg[7:]).digest())
            elif msg.startswith('get-time'):
                send_msg(str(time.time()))
            elif msg.startswith('get-sha1'):
                send_msg(SHA.new(msg[8:]).digest())
            elif msg.startswith('get-sha256'):
                send_msg(SHA256.new(msg[10:]).digest())
            elif msg.startswith('get-hmac'):
                send_msg(HMAC.new(msg[8:]).digest())
            else:
                send_msg('command not found')
        except:
            exit(0)

Step 1. Get the encrypted flag by IV manipulation

Recall the AES CBC mode of operation in particular the decryption.

Alt text

Recall that P_i = D(C_i) ^ C_{i-1} where C_0 is the IV block. It is known that changing the bit j of block C_i will affect bit j of block P_{i+1} while destroying block P_i as the decryption of C_i is now rubish. However, if we do it to IV, we are ok as IV is discarded in the end.

So after the proof of work we get IV + E('Welcome!!' + '\x07' * 7). In order to get the encrypted flag we need to transform it into IV2 + E('get-flag' + '\x08' * 8). This is simple to do.

One knows that P_1 = D(C_1) ^ IV and we know P1, C1 and IV. We want to get P1bar = 'get-flag' + '\x08' * 8. Defining IV2 = IV ^ P1 ^ P1bar we get

    D(C1) ^ IV2 = D(C1) ^ IV ^ P1 ^ P1bar = P1 ^ P1 ^ P1bar = P1bar

So done. We can get the flag ciphered.

target = 'get-flag' + '\x08'*8
source = 'Welcome!!' + '\x07'*7
iv2 = ''
for i in range(16):
  iv2 += chr(ord(target[i]) ^ ord(source[i]) ^ ord(iv[i]))

Step 2. Get the 1st block by IV manipulation

Now we have IV + E(hitcon{......}) Using the fact that the flag starts with hitcon{ we can get the 1st block iterating the technique of Step 1.

Notice that hitcon{ is as long as get-sha, and so transform the IV as above in order to get IV2 + E(get-sha......}). Now rotate the 8th character of IV among the 256 possible chars. Notice that if you send these 256 messages to the server, all but one will return send_msg('command not found'). The only one that will succeed and will be different is the one where the 8th character of D(C1) ^ IV2 = '1' as it will call the get-sha1 operation. This will allow us to get the 8th character of the flag

    (for char 8 of P1)   D(C1) ^ IV2 = '1'   and   D(C1) ^ IV = P1   ==>   P1 = IV ^ IV2 ^ '1'

You will get it on average 128 calls.

How to get the 9th character? The idea is to shift the get-sha one position to the right (using chars 2 to 8 instead of 1 to 7) and apply the same technique to the 9th char. Notice that at this stage we know chars 1 to 8 of the flag and so we can do it.

The problem is that if we do it then the message will not begin with get-sha1 as required in main. The trick here is to pad with \n to the left. Since main does strip() after decryption it will drop the \n at the beginning. (honestly do not know if this was the intended solution but it worked for us).

Iterate this and get the 1st block of flag: hitcon{Paddin9_1

Step3. Find the length of padding

For the next steps it will be important to find the length of the padding. Notice that if you control the last byte of the last block (in this case C3) you can discard as many bytes as you want while unpadding as unpadding only checks the very last byte of the plaintext to assess padding. So we apply Step 1. to transform the ciphered flag to get-sha1 and rotate the last byte of C2 among all the possible 256 values. This in turn will rotate the last byte of C3 among the possible 256 values and since

  • the length of the message is 48 (3 blocks)
  • the length of get-sha1 is 8

it will return

  • 40 different ciphers (we can remove up to 40 chars and still get a message that starts with get-sha1), each of them once.
  • one cipher repeated 216 times, the cipher of command not found, that is when we remove more than 40 chars.

Repeat for get-md5. Since get-md5 is of length 7 it will return

  • 41 different ciphers (we can remove up to 41 chars and still get a message that starts with get-md5), each of them once.
  • one cipher repeated 215 times, the cipher of command not found, that is when we remove more than 41 chars.

The char that is in MD5 and not in SHA1 is the one that gives us the length of the flag.

    (for char 16 of P3)   D(C3) ^ C2bar = '41'   and   D(C3) ^ C2 = pad_value   ==>   pad_value = C2 ^ C2bar ^ '41'

This requires 2 * 256 calls to the server, and in this case we got pad_value = 16.

Notice that the decryption of C2 will be garbage, hence it will not return P2 but in this case we do not care about it.

Step 4. Get the 1st half of 2nd block

This step is a mix of previous ones.

a. From IV + E(hitcon{Paddin9_1) (notice we know the 16 chars of P1), prepare IV2 + E('\n' * 9 + 'get-md5' + C2 + C3). From this we can manipulate the last byte of C2, to affect the last byte of P3, so that when unpad is done everything is discarded except the 1st byte of P2 and so we otain E(MD5(1st byte of P2)). If you want to keep just 1 byte of P2 (that is 17 of the whole message) just change the last byte of C2 to

    newchar = C2[-1] ^ (48 - 17) ^ pad_value  ==>  new_padding = D(C3) ^ C2bar = D(C3) ^ C2[-1] ^ (48 - 17) ^ pad_value = pad_value ^ (48 - 17) ^ pad_value = (48 -17)

The problem with this trick is that by changing the last byte of C2 we are damaging its decryption and so we do not get the original P2. The way we sorted this was to add a dummy block in the middle and prepare IV2 + E('\n' * 9 + 'get-md5' + C2 + C2 + C3) instead. By applying the tricks on the 2nd copy of C2, we do not damage the decryption of the 1st C2 and consequently can get the original P2 there. Notice that you need to discard 16 more chars in this case.

b. Now from IV + E('Welcome!!' + '\x07' * 7) prepare IV2 + E('get-md5' + char + '\x08' * 8) for all possible 256 chars and compare this to the cipher obtained above. One of them will match, and this will give us the 1st char of P2.

Use this char and prepare

a. with dropping one less char.

b. with IV2 + E('get-md5' + 1st char of P2 + char + '\x08' * 8)

This will return the 2nd char of P2. Iterate up to 9 chars (this is the most you can extend in b.)

We got P2 = '5_ve3y_h4r'

Step 5. Get the 2nd half of 2nd block

This is just the repetition of Step 2. discarding the 1st block of the encrypted flag and considering 5_ve3y_ instead of hitcon{. We will use in this case C1 as the IV.

This got us the remaining 9 chars: hitcon{Paddin9_15_ve3y_h4rd__!!}

VERY IMPORTANT: You can do all these decryption tricks with CBC only if you know what is the plaintext you want to match!