Detect AES in ECB mode
Tags: 100daystooffload, cryptopals, challenge, security
Published: 2024-05-14 18:17:10

This is the eighth and last crypto challenge in set 1 from [cryptopals](cryptopals.com), which is the qualifying set. 

The difficulty level is relatively easy, to solve this problem I have used the programming language Go.

# Problem description

In the given file there are a bunch of hex-encoded ciphertexts.

One of them has been encrypted with ECB.

Detect it.

Remember that the problem with ECB is that it is stateless and deterministic; the same 16 byte plaintext block will always produce the same 16 byte ciphertext.

# Solution

First step is to refactoring the code from the previous challenge so we can reuse some of the functions in this challenge. We will need encrypt and decrypt functions that are using AES with ECB mode.

```golang
func EncryptAESWithECBMode(plaintext []byte, key []byte) ([]byte, error) {
	block, err := aes.NewCipher(key)
	if err != nil {
		return nil, err
	}

	ciphertext := make([]byte, len(plaintext))
	blockSize := len(key)

	for start, end := 0, blockSize; start < len(plaintext); start, end = start+blockSize, end+blockSize {
		block.Encrypt(ciphertext[start:end], plaintext[start:end])
	}

	return ciphertext, nil
}

func DecryptAESWithECBMode(ciphertext []byte, key []byte) ([]byte, error) {
	block, err := aes.NewCipher(key)
	if err != nil {
		return nil, err
	}

	plaintext := make([]byte, len(ciphertext))
	blockSize := len(key)

	for start, end := 0, blockSize; start < len(ciphertext); start, end = start+blockSize, end+blockSize {
		block.Decrypt(plaintext[start:end], ciphertext[start:end])
	}

	return plaintext, nil
}
```

And to verify that it works we can reuse the input from last challenge here too.

```golang
func TestEncryptAESWithECBMode(t *testing.T) {
	plaintext, err := basics.DecryptAESWithECBModeFile("7.txt", []byte("YELLOW SUBMARINE"))
	if err != nil {
		t.Errorf("Unexpected error: %v", err)
	}

	ciphertext, err := basics.EncryptAESWithECBMode(plaintext, []byte("YELLOW SUBMARINE"))
	if err != nil {
		t.Errorf("Unexpected error: %v", err)
	}

	decryptedPlaintext, err := basics.DecryptAESWithECBMode(ciphertext, []byte("YELLOW SUBMARINE"))
	if err != nil {
		t.Errorf("Unexpected error: %v", err)
	}

	if string(decryptedPlaintext) != string(plaintext) {
		t.Errorf("Expected plaintext: %s, got: %s", string(plaintext), string(decryptedPlaintext))
	}
}
```

Here we test that we can decrypt the file and then encrypt it with the encrypt method defined earlier, and finally we use the decrypt function to verify that we get the same plaintext once again.

With these function it is possible to write a unit test for validating our detection function.

```golang
func TestDetectAESInECBMode(t *testing.T) {
	plaintext := []byte("YELLOW SUBMARINEYELLOW SUBMARINE")
	key := []byte("YELLOW SUBMARINE")

	ciphertext, _ := basics.EncryptAESWithECBMode(plaintext, key)
	keySize := len(key)

	if !basics.DetectAESInECBMode(ciphertext, keySize) {
		t.Errorf("Expected to detect ECB mode")
	}
}
```

Now we have to implement the actual solution to the given problem, however, let's first recall this from the problem description.

> the problem with ECB is that it is stateless and deterministic; the same 16 byte plaintext block will always produce the same 16 byte ciphertext.

So we need to write function that can check to see if there are any repeating blocks in the given ciphertext.

```golang
func DetectAESInECBMode(ciphertext []byte, keySize int) bool {
	blocks := make(map[string]bool)

	for i := 0; i < len(ciphertext); i += keySize {
		block := string(ciphertext[i : i+keySize])
		if blocks[block] {
			return true
		}
		blocks[block] = true
	}

	return false
}
```

This function uses a `map` as a "lookup table" where we store each block from the ciphertext while we are looping through it. If the block already exists in the `map` we will now that a block has been repeated and therefore the ciphertext is encrypted with AES in ECB mode.

The complete solution can be found on [GitHub](https://github.com/stefanalfbo/cryptopals).

# Conclusion

This problem highlights the problem with the AES in ECB mode encryption, and that patterns in the ciphertext might leak information about the plaintext.

# References

* [Set 1 - Challenge 8](https://cryptopals.com/sets/1/challenges/8)
* [crypto/aes](https://pkg.go.dev/crypto/aes)
* [Electronic codebook (ECB)](https://en.wikipedia.org/wiki/Block_cipher_mode_of_operation#Electronic_codebook_(ECB))