ECB Byte-at-a-Time Decryption

gistfile1.txt

Write an oracle function that encrypts buffers under ECB mode using a
consistent but unknown key (for instance, assign a single random key,
once, to a global variable), like so:

    RANDOM_KEY = <16 bytes from /dev/urandom>
    SECRET = <secret data>

    function oracle(data):
        return AES-128-ECB-encrypt(data || SECRET, RANDOM_KEY)

SECRET contains the Base64-decoded contents of the following string:

  Um9sbGluJyBpbiBteSA1LjAKV2l0aCBteSByYWctdG9wIGRvd24gc28gbXkg
  aGFpciBjYW4gYmxvdwpUaGUgZ2lybGllcyBvbiBzdGFuZGJ5IHdhdmluZyBq
  dXN0IHRvIHNheSBoaQpEaWQgeW91IHN0b3A/IE5vLCBJIGp1c3QgZHJvdmUg
  YnkK

SPOILER ALERT: DO NOT DECODE THIS STRING NOW. DON'T DO IT.

Base64 decode the string before appending it. DO NOT BASE64 DECODE THE
STRING BY HAND; MAKE YOUR CODE DO IT. The point is that you don't know
its contents.

Now provide the oracle function to the attacker.

You can decrypt SECRET with repeated calls to the oracle function!

Here's roughly how:

a. Feed identical bytes of data to the function 1 at a time ---
start with 1 byte ("A"), then "AA", then "AAA" and so on. Discover the
block size of the cipher. You know it, but do this step anyway.

b. Detect that the function is using ECB. You already know, but do
this step anyways.

c. Knowing the block size, craft an input block that is exactly 1 byte
short (for instance, if the block size is 8 bytes, make
"AAAAAAA"). Think about what the oracle function is going to put in
that last byte position.

d. Make a dictionary of every possible last byte by feeding different
strings to the oracle; for instance, "AAAAAAAA", "AAAAAAAB",
"AAAAAAAC", remembering the first block of each invocation.

e. Match the output of the one-byte-short input to one of the entries
in your dictionary. You've now discovered the first byte of
SECRET.

f. Repeat until the entire string is decrypted.