Codegate CTF 2011 Crypto 400

The attacker got a secret!

File

Summary: Padding oracle attack analysis

In this challenge you should have heard about oracle padding attacks. Else it’s rather hard to understand what is going on.

I’ll give a short description how it works.
Easy to guess, that path in HTTP request is encoded with base64 and if decoded, it has 32 bytes. Let’s decode it:

#!/usr/bin/env python
#-*- coding:utf-8 -*-

import re
import sys
from base64 import b64decode

lst = re.findall("GET /(.*0) HTTP/1.0\" (\d+)", open("text.txt").read())

for block, answer in lst:
    block = block.replace("-", "+").replace("_", "/")
    block += "=" * (4 - (len(block) % 4))
    block = b64decode(block)
    
    h = block.encode("hex")
    print h[:len(h)//2], h[len(h)//2:], int(answer)

hellman $ py analyze.py | head
f0b53b2da041fca49ef0b9839060b345 a21ea2b4605f8441751b2661d6738f1d 200
6e063ff5921ef69cfc3feafd933ebb40 a21ea2b4605f8441751b2661d6738f1d 500
6e063ff5921ef69cfc3feafd933ebb41 a21ea2b4605f8441751b2661d6738f1d 500
6e063ff5921ef69cfc3feafd933ebb42 a21ea2b4605f8441751b2661d6738f1d 500
6e063ff5921ef69cfc3feafd933ebb43 a21ea2b4605f8441751b2661d6738f1d 500
6e063ff5921ef69cfc3feafd933ebb44 a21ea2b4605f8441751b2661d6738f1d 500
6e063ff5921ef69cfc3feafd933ebb45 a21ea2b4605f8441751b2661d6738f1d 500
6e063ff5921ef69cfc3feafd933ebb47 a21ea2b4605f8441751b2661d6738f1d 403
6e063ff5921ef69cfc3feafd933e0044 a21ea2b4605f8441751b2661d6738f1d 500
...

Ok, if you quickly look through the output, you can see that all sequental requests with answer code 500 differ only in one byte – it’s increasing, until 403 is got. Then, next (it’s going from the end of the first block, so you can call it’s previous) byte becomes \x00 and some small changes to the following bytes are made. And, it goes again. So, requests with answer code 500 are not important. Let’s sieve them:

hellman $ py analyze.py | grep -Ev '500$'
f0b53b2da041fca49ef0b9839060b345 a21ea2b4605f8441751b2661d6738f1d 200
6e063ff5921ef69cfc3feafd933ebb47 a21ea2b4605f8441751b2661d6738f1d 403
6e063ff5921ef69cfc3feafd933eb244 a21ea2b4605f8441751b2661d6738f1d 403
6e063ff5921ef69cfc3feafd9360b345 a21ea2b4605f8441751b2661d6738f1d 403
6e063ff5921ef69cfc3feafdf167b442 a21ea2b4605f8441751b2661d6738f1d 403
6e063ff5921ef69cfc3feae3f066b543 a21ea2b4605f8441751b2661d6738f1d 403
6e063ff5921ef69cfc3fd6e0f365b640 a21ea2b4605f8441751b2661d6738f1d 403
6e063ff5921ef69cfc9cd7e1f264b741 a21ea2b4605f8441751b2661d6738f1d 403
6e063ff5921ef69ca693d8eefd6bb84e a21ea2b4605f8441751b2661d6738f1d 403
6e063ff5921ef69da792d9effc6ab94f a21ea2b4605f8441751b2661d6738f1d 403
6e063ff5921ec69ea491daecff69ba4c a21ea2b4605f8441751b2661d6738f1d 403
6e063ff59209c79fa590dbedfe68bb4d a21ea2b4605f8441751b2661d6738f1d 403
6e063ff5f50ec098a297dceaf96fbc4a a21ea2b4605f8441751b2661d6738f1d 403
6e063f6df40fc199a396ddebf86ebd4b a21ea2b4605f8441751b2661d6738f1d 403
6e06416ef70cc29aa095dee8fb6dbe48 a21ea2b4605f8441751b2661d6738f1d 403
6edb406ff60dc39ba194dfe9fa6cbf49 a21ea2b4605f8441751b2661d6738f1d 403
a5c45f70e912dc84be8bc0f6e573a056 a21ea2b4605f8441751b2661d6738f1d 403

Ok, but what happens with the rest of a block? You can notice that each pair of bytes (e.g. last two bytes) int the rest of a block isn’t changed much. I tried to xor them – and yes, this value doesn’t change! For example,

b2 ^ 44 = f6
b3 ^ 45 = f6
b4 ^ 42 = f6
...

This means, that both bytes are xored with some value after each 403 answer. We should extrapolate it on the whole rest of a block, and we can get the values, with which they are xored:

6e063ff5921ef69cfc3feafd933ebb47 a21ea2b4605f8441751b2661d6738f1d 403
                             ^03  
6e063ff5921ef69cfc3feafd933eb244 a21ea2b4605f8441751b2661d6738f1d 403
                           ^0101
6e063ff5921ef69cfc3feafd9360b345 a21ea2b4605f8441751b2661d6738f1d 403
                         ^070707
6e063ff5921ef69cfc3feafdf167b442 a21ea2b4605f8441751b2661d6738f1d 403
                       ^01010101
6e063ff5921ef69cfc3feae3f066b543 a21ea2b4605f8441751b2661d6738f1d 403
                     ^0303030303
6e063ff5921ef69cfc3fd6e0f365b640 a21ea2b4605f8441751b2661d6738f1d 403
...

It’s not obvious, but if the first block is xored with something when decrypting (usual thing in different block modes, e.g. CBC) and the last byte is \x01, and we additionally xored it with \x03 – it becomes \x02. Then, xor with \x01 becomes \x03, then \x04, \x05, \x06… Looks meaningfull! If it’s really CBC, than the second block is firstly decrypted with some crypto function (e.g. AES) and then xored with the ciphertext of first block. So, it will be decrypted as:

XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX01
XXXXXXXXXXXXXXXXXXXXXXXXXXXX0202
XXXXXXXXXXXXXXXXXXXXXXXXXX030303
XXXXXXXXXXXXXXXXXXXXXXXX04040404

Now you must recognize a PKCS7 padding.

It means that 403 (forbidden) is sent when the padding is right but the key is invalid. Code 500 (Internal Error) means that padding is wrong. And 200 (OK) means that padding and key are ok. (Padding check is made by the last byte of a block). Such thing is called a padding oracle.

Let’s look closely at CBC mode scheme from wikipedia:

The attacker bruteforces byte-by-byte first block of ciphertext – C0, because he can determine whether padding is right. Also he knows the right padding for each case, so he knows and the second block of plaintext – P1 (it’s not real block of plaintext, but a padding generated by attacker). Thus, he can determine each byte of decrypted with crypto function second block of ciphertext (C1) – let’s call it E1:

AES_Decrypt(C1) = E1 = C0 ^ P1 //P1 is padding

Ok, we also know one ciphertext, which returned 200 code (let’s call it CT0|CT1). We can emulate last stage of decryption by using it’s first block:

RP1 = E1 ^ CT0 //RP1 is right plaintext

Let’s do it on blocks. The last ciphertext, which returned 403 code, decrypted the second block as just padding: 16 bytes of 16 = \x10. So,

E0 = a5c45f70e912dc84be8bc0f6e573a056 Last attacker's Ciphertext[0]
   ^ 10101010101010101010101010101010 Plaintext[1] - padding
   = b5d44f60f902cc94ae9bd0e6f563b046 AES_Decrypt(Ciphertext[1])

And, at last:

RP0 = b5d44f60f902cc94ae9bd0e6f563b046 AES_Decrypt(Ciphertext[1])
    ^ f0b53b2da041fca49ef0b9839060b345 Good Ciphertext[0]
    = 4561744d59433030306b696565030303 Good Plaintext[1]

Unhex it: EatMYC000kiee\x03\x03\x03 (\x03 is padding, hehe)

The flag: EatMYC000kiee

Another writeups on this:
Writeup by Bojan
Nice article about padding oracle attack