• ECB block cipher mode
• Break ECB mode (easy level)
  • Find the block size
  • Check if oracle is using ECB mode
  • Break the first byte
  • Break the following bytes
  • Code
• Conclusion

Today, we will learn about the ECB block cipher mode, how it works, and how to break it. This post is related to https://cryptopals.com/sets/2/challenges/12.

ECB block cipher mode

The Electronic Code Book (ECB) is a block cipher mode of operation. Data is encrypted in blocks of fixed size and with the same key. Also, some bytes are added when the plaintext doesn’t have a length that is a multiple of the block size, known as padding.

Let p be the plaintext, c the ciphertext, k the key, and cipher any encryption algorithm. Assume that the ciphertext can be divided into blocks of length equal to k, without any leftover bytes. For each i from 0 to the number of blocks in the plaintext, we have that c[i] = cipher(p[i], k).

The main issue with this mode is that it reuses the same key for all blocks. You might think that this shouldn’t be a problem. However, identical plain blocks will return the same encrypted blocks. It becomes apparent when you see the following images.

Plain image

Image encrypted with ECB mode

The data was encrypted, but we can still see the penguin… more or less. Let’s see how we can break this block cipher mode.

Break ECB mode (easy level)

Let’s pretend we have access to an encryption oracle that encrypts data in a particular way. It encrypts the result of appending some data to the user input. This oracle also knows the secret key.

In rust, this could look like this.

// Cipher function
pub fn encrypt(data: &[u8], key: &[u8]) -> Vec<u8> {
    let unknown_string = BASE64_STANDARD.decode(UNKNOWN_STRING).expect("Valid data");
    let data = [data, &unknown_string].concat();

    encrypt_aes_128_ecb(&data, key)
}

fn main() {
  ...
  let key = random_bytes(16);
  let encryption_fn = |data: &[u8]| encrypt(data, &key); // encryption oracle
}

Of course, in a real scenario, we won’t implement the function ourselves. We will be given call access to it. With the preparation out of the way, let’s move into the first step for breaking ECB.

Find the block size

We are using 128-bit block size, but we won’t have this information available in every situation. There’s a very simple way to discover the block size. Remember, ECB encrypts data in blocks of fixed size. Thus, if we find two inputs that return ciphertexts of different lengths, the difference must be the block size.

To get familiar with this idea, let’s go to https://www.devglan.com/online-tools/aes-encryption-decryption and play around with it. You will see that the result of encrypting strings between 1 and 15 characters returns ciphertexts of equal length. But, as soon as you encrypt a string with 16 characters, the ciphertext length increases. Take into account that the result is in base64 by default. Hence, the length increase won’t match the block size.

"a"      -> "kc86jk6HnV9AtZ57SmbuJw=="
"aa"     -> "UAGUUSk778f9tDRGTVKvYw=="
...
"a" * 16 -> "UOrlU8c7SzBd+8BGIi4CAJHPOo5Oh51fQLWee0pm7ic="

Let’s see an implementation.

pub fn compute_block_size_and_padding_length<F>(encryption_fn: F) -> (usize, usize)
where
    F: Fn(&[u8]) -> Vec<u8>,
{
    let mut i = 0;
    let mut len_diff = 0;
    while len_diff == 0 {
        len_diff = encryption_fn(&vec![0; i + 1]).len() - encryption_fn(&vec![0; i]).len();
        i += 1;
    }

    (len_diff, i)
}

Computing the padding is not needed. It’s a nice-to-have. It helps with printing the original message, once broken, without the padding.

Check if oracle is using ECB mode

Again, we might not have this information readily available in a real situation. Thus, we must practice how we can check if ECB is being used.

We will feed the encryption oracle with an unnecessarily long input that uses the same character over and over again. In the resulting ciphertext, we will check if all blocks are equal. If that’s the case, the oracle uses ECB mode. Remember that ECB uses the same key to encrypt different blocks. Hence, the same plain blocks return the same encrypted blocks.

NOTE

In this particular exercise, the oracle appends some unknown data. We need to check if the number of repeated blocks is greater or equal than the number of input ones. Some encrypted blocks could have the same value.

pub fn is_ecb<F>(encryption_fn: F, block_size: usize) -> bool
where
    F: Fn(&[u8]) -> Vec<u8>,
{
    let plain = vec![0; block_size * 100];
    let ciphertext = encryption_fn(&plain);

    max_repeated_block(&ciphertext) >= 100
}

Break the first byte

At a high level, what we want to do is isolate the first byte and brute-force the value. The general flow is more complex. Let’s start with the pseudocode to break the first byte.

prefix = string of length block size - 1
ciphertext = encryption_oracle(prefix)

every_possible_ciphertext = empty dictionary
for each possible character
  current_prefix = prefix + character
  possible_ciphertext = encryption_oracle(current_prefix)
  store possible_ciphertext in every_possible_ciphertext

for (character, possible_ciphertext) in every_possible_ciphertext
  if ciphertext == possible_ciphertext
    return character

Let’s walk through the pseudocode step by step.

First, we build an input to isolate the first byte of the unknown string. Since our input is one byte smaller than the block size, the first byte of the unknown string will move into the first block of data. Calling the oracle with that will give us the “actual” ciphertext.

Example

block_size = 16
unknown_string = "mydata..."
prefix = "a" x 15

Encryption oracle will use the following
data as input to be encrypted

data = "aaaaaaaaaaaaaaamydata..."
        | first block  | second block

We are in full control of the prefix. The only unknown is the last character. The one we want to decrypt.

Second, we want to construct every possible ciphertext. For that, we will call the encryption oracle with each possible character that could appear in the message, appended to the prefix.

Example

We call the oracle with

input = "aaaaaaaaaaaaaaaa"
input = "aaaaaaaaaaaaaaab"
input = "aaaaaaaaaaaaaaac"
...
input = "aaaaaaaaaaaaaaaz"
input = "aaaaaaaaaaaaaaa!"
...
input = "aaaaaaaaaaaaaaa:"

and we create a dictionary

"a" -> first possible ciphertext
"b" -> second possible ciphertext
...

Third and last step, we must find which of the possible ciphertexts is equal to the “actual” ciphertext. The one we got from calling the oracle with the prefix.

With that, we broke the first byte. Hurray!!!

In rust, it could look something like:

let prefix = vec![0; block_size - 1];
let ciphertext_block_to_character = brute_force_ciphertext_block(&encrypt_fn, prefix, 0, block_size);
let ciphertext = encrypt_fn(&prefix);
let character = ciphertext_block_to_character.get(&ciphertext[0..16]).expect("Exists");

I’m leaving some functions and extra details out. We will see them in the next section.

Break the following bytes

Breaking ECB is an iterative method. Breaking the second byte requires knowing the first byte. Breaking the third byte requires knowing the first and the second bytes. Breaking the nth byte requires knowing the previous “block size minus one” bytes.

To break the message, we have to generalize the method used to break the first byte. With a bit of arithmetic, we can handle it. Let’s see the modified mechanisms.

Extend crafted prefix

To break the following byte, we will use all previous decrypted bytes. Prefixes will still be one byte smaller than the block size, but they will include the decrypted bytes preceding the byte we want to break. To accomplish that, on each iteration, we will append the last decrypted character and remove the first byte. That assures us that the difference between all the possible ciphertexts in the dictionary and the ciphertext we are searching for is only one byte. The last one. All previous bytes are known to us. Otherwise, the dictionary must be built based on many unknowns instead of one. One for each unknown character. It quickly gets intractable. That’s the reason we go byte by byte.

In general, breaking the nth byte requires knowing the previous “block size minus one” bytes. This reduces the unknowns to one byte, which we can easily brute-force.

Example

block size = 16
unknown string = "random message data"

Iteration 1
prefix = "aaaaaaaaaaaaaaa"
          | used prefix |
we break the first byte and obtain "r"

Iteration 2
prefix = "aaaaaaaaaaaaaaar"
           | used prefix |
we break the second byte and obtain "a"

Iteration 3
prefix = "aaaaaaaaaaaaaaara"
            | used prefix |
we break the third byte and obtain "n"

...

Iteration n
prefix = "aaaaaaaaaaaaaaarandom message dat"
                            | used prefix |
we break the last byte and obtain "a"

Isolate following bytes

We need to accommodate the prefix to prepare the following byte we want to break. To accomplish that, we decrease the size of the prefix by one on each iteration. Once the prefix length is zero, we have broken all the bytes from the block. To break the following block, we come back to using a prefix of “block size minus one” characters and repeat the process.

Example

block size = 16
unknown string = "random message data"

Iteration 1
input = "a" x 15
encryption_oracle will encrypt "aaaaaaaaaaaaaaarandom message data"
                                | first block  | second block  |
we break the first byte and obtain "r" (first block)

Iteration 2
input = "a" x 14
encryption_oracle will encrypt "aaaaaaaaaaaaaarandom message data"
                                | first block  | second block  |
we break the second byte and obtain "a" (first block)

Iteration 3
input = "a" x 13
encryption_oracle will encrypt "aaaaaaaaaaaaarandom message data"
                                | first block  | second block  |
we break the third byte and obtain "n" (first block)

...

Iteration 16
input = ""
encryption_oracle will encrypt "random message data"
                                | first block  | second block  |
we break the sixteenth byte and obtain "d" (first block)
first block completed, we have to break the second block now

Iteration 17
input = "a" x 15
encryption_oracle will encrypt "aaaaaaaaaaaaaaarandom message data"
                                | first block  | second block  |
we break the seventeenth byte and obtain "a" (second block)

...

Brute-force the correct block

I didn’t show it, but the function that creates the dictionary with all the possible ciphertexts only stores one block of data, not the whole ciphertext. That remains the same, but we have to make sure that we compare the correct ciphertext block against each possible ciphertext block in the dictionary.

let start = (i / block_size) * block_size;
let end = start + block_size;
let character = ciphertext_block_to_character.get(&ciphertext[start..end]).expect("Exists");

That’s about it. We are ready to see the final implementation.

Implementation

Before moving forward, let me explain an important detail about the brute_force_ciphertext_block function. This function returns a dictionary with every possible ciphertext. If you read the implementation, you will see that we always store the first block of the ciphertext. That might be confusing, but it has a simple explanation. The encryption oracle doesn’t prepend any information. Besides, to get every possibility, we only care about the prefix plus any given letter. At this step, the string appended by the oracle is irrelevant. We only care about the ciphertext of the data we are feeding in, which becomes the first block of the resulting ciphertext.

That’s it. I just wanted to explain the inner workings of that function, so that’s clear what’s going on.

pub fn attack_ecb_one_byte_at_a_time<F>(encrypt_fn: F) -> String
where
    F: Fn(&[u8]) -> Vec<u8>,
{
    let (block_size, padding_length) = compute_block_size_and_padding_length(&encrypt_fn);
    if !is_ecb(&encrypt_fn, block_size) {
        panic!("Data not encryped with ECB");
    }

    let mut plain = vec![0; block_size - 1];
    let num_target_bytes = encrypt_fn(&[]).len() - padding_length;
    for i in 0..num_target_bytes {
        let crafted_prefix = &plain[plain.len() - (block_size - 1)..];
        let ciphertext_block_to_character =
            brute_force_ciphertext_block(&encrypt_fn, crafted_prefix, 0, block_size);

        let raw_prefix = vec![0; block_size - 1 - (i % block_size)];
        let ciphertext = encrypt_fn(&raw_prefix);
        let start = (i / block_size) * block_size;
        let end = start + block_size;
        let character = ciphertext_block_to_character
            .get(&ciphertext[start..end])
            .expect("Exists");

        plain.push(*character);
    }

    String::from_utf8(plain[block_size - 1..].to_vec()).expect("Valid plain message")
}

pub fn brute_force_ciphertext_block<F>(
    encryption_fn: F,
    prefix: &[u8],
    block_position: usize,
    block_size: usize,
) -> HashMap<Vec<u8>, u8>
where
    F: Fn(&[u8]) -> Vec<u8>,
{
    let mut encrypted_block_to_character = HashMap::new();
    for i in 0..=255u8 {
        let prefix_with_character = [prefix, &[i]].concat().to_vec();
        let encrypted_data = encryption_fn(&prefix_with_character);
        let start = block_position * block_size;
        let end = start + block_size;
        let encrypted_block = encrypted_data[start..end].to_vec();
        encrypted_block_to_character.insert(encrypted_block, i);
    }

    encrypted_block_to_character
}

Code

You can check the whole implementation https://github.com/danielorihuela/cryptopals/blob/main/src/set2/challenge12.rs.

Conclusion

The ECB cipher is simple but highly insecure due to its deterministic nature, which leaks patterns in the plaintext. This exercise demonstrates how easily it can be broken. Modern cryptographic systems should avoid ECB mode entirely and instead use secure modes of operation like Galois Counter Mode (GCM) or Counter Mode (CTR).