Stefan AlfboThis is the eighth and last crypto challenge in set 1 from cryptopals, 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.
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.
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.
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.
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.
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.
