ECB Oracle

An oracle is a type of tool or service that can provide information about a cryptographic algorithm, often with the goal of breaking it.

Most of the time, an attacker might use a chosen plaintext attack to submit carefully-crafted plaintexts to the encryption function and observe the resulting ciphertexts in order to build a dictionary of plaintext/ciphertext pairs that can be used to decrypt other blocks.

Some elements are required to exploit an oracle :

• Ability to submit plaintext messages

• Ability to observe ciphertexts

• Ability to repeat these actions

Exploitation

As explained here, AES using ECB mode will always produce the same ciphertext for the exact same plaintext input.

So the attacker can list every single possibility for each block and then break the cipher.

As AES cipher block of size 16 bytes. there is 340282366920938463463374607431768211456 ( $256^{16}$) possibilities.

What if the attacker can inject some data directly into the targeted cipher message such as :

data = user_input + secret
ciphertext = cipher.encrypt(data)

The user can inject as many byte as he want.

Furthermore, AES will always encrypt blocks of size 16. If the input block is shorter than 16 bytes, then it will be padded, typically using PKCS#7.

Retrieve the last block

By injecting enough data, the last block can be known :

b'\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10'

This block correspond to the padding when the cipher data match match exactly with the block size ( $plaintext \mod 16 = 0$)

The attacker can inject this block as plaintext input + enough padding to make the plaintext match the block size and then compare his injected block and the last one.

i = 16
cipher_size = len(encrypt(b'\x10' * i))
cur_size = cipher_size
while cipher_size == cur_size:
    i += 1
    data = encrypt(b'\x10' * i)
    cur_size = len(data)
    if cur_size > cipher_size :
        print("injected block :", data[0:32])
        print("last block     :", data[-32::])
        assert(data[0:32] == data[-32::])

Using this behavior, if the user add 1 byte to the input, the last block will be :

b'X\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f'

X is here the last char of the unknown part of the ciphered data : "secret"

As it is the only unknown char of the block, there is only 256 possibilities.

i = 16
cipher_size = len(encrypt(b'\x10' * i))
cur_size = cipher_size
while cipher_size == cur_size:
    i += 1
    data = encrypt(b'\x10' * i)
    cur_size = len(data)
    if cur_size > cipher_size :
        print("injected block :", data[0:32])
        print("last block     :", data[-32::])
        assert(data[0:32] == data[-32::])
        for c in range(256):
            data = encrypt(c.to_bytes(1,'big') + b'\x0f' * i)
            if data[0:32] == data[-32::]:
                print("Last secret char is : ", c.to_bytes(1,'big'))
                break

Then the user can go on. If he add again one byte to the input he will have :

b'YX\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e'

Where X is the previously retrieve char.

He can continue until he retrieve the enire block.

Retrieve the first block

Just has the last block, the user can manipulate him input in order to know exactly what there is as second block :

i = 16
cipher_size = len(encrypt(b'\x10' * i * 2))
    print("first block :", data[0:32])
    print("second block     :", data[32:64])
    assert(data[0:32] == data[32:64])

Here, the user has injected two block with the exact same value. If he inject just 1 less byte he will have :

b'\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10X'

as second block, where X is the first char of the secret value.

The method here is the same as for retrieve the last block.

The only difference is instead of adding byte and brute-forcing the first char of the last block, the user will remove one char from him input and brute-force the last char of the second block.

for c in range(256):
    data = encrypt(b'\x10' * 15 + c.to_bytes(1,'big') + b'\x10' * 15)
    if data[0:32] == data[32:64]:
        print("First secret char is : ", c.to_bytes(1,'big'))
        break

What for secret longer than 2 block ?

Once the first or the last block is fully decrypted, it's possible to start again with the direct next block such as sending enough data to obtain the following block :

b'ECRETDATABLOCK1X'

Where SECRETDATABLOCK1 is the first decrypted block so ECRETDATABLOCK1 are the last 15 bytes of the first block and X is the first byte of the next block.

To obtain this block the user may send 16 bytes ( block used to bruteforce the targeted byte ) + 15 bytes to have :

Injection block    Padding         Targeted block  Rest...
+----------------+----------------+---------------+----------------+
|ECRETDATABLOCK1X|VVVVVVVVVVVVVVVS|ECRETDATABLOCKX|................|
+----------------+----------------+---------------+----------------+

Then, when the second block is obtain, it's possible to continue till the obtention of the entire secret value.