Extensive Cryptanalysis of Authenticated Encryption With Associated Data Algorithm Colm

Abstract

The main objective of an Authenticated Encryption with Associated Data (AEAD) algorithm is to keep the encrypted plaintext secret until its tag is validated. There are two main methods related to the cryptanalysis of AEAD algorithms that can render this objective invalid. These methods are plaintext recovery attacks (simulating the decryption oracle) and tag guessing attacks (producing the valid tag of a given ciphertext). There are also various kinds of forgery attacks against AEAD algorithms in which the adversary tries to construct a valid ciphertext. The resistance of COLM against these methods is studied in this thesis. COLM is one of the AEAD algorithms that won the CAESAR Competition in the Defense in Depth use case. The ciphers chosen in the Defense in Depth portfolio are supposed to contain multiple security layers to provide robust security. The main motivation of this thesis is to examine if COLM indeed satisfies defense-in-depth security. In this thesis, we show that COLM is as secure as its secret whitening parameter L. We demonstrate that COLM cannot resist any attacks mounted against AEAD algorithms once L is known. To the best of our knowledge, we give the first example of querying an EME/EMD (Encrypt-linearMix-Encrypt/Decrypt) AEAD scheme in its decryption direction for arbitrary ciphertext, namely, either a forgery or tag guessing attack. Moreover, we construct SEBC/SDBC (Simulation models of Encryption/Decryption oracle of the underlying Block Cipher) of COLM. These models are the first examples of an authenticated EME scheme simultaneously. The combination of SEBC/SDBC is a powerful tool to mount a universal forgery attack, a tag guessing attack, and a plaintext recovery attack. All of these attacks have O(N) time complexities once L is recovered in the offline phase, indicating that the security of COLM against plaintext recovery and tag guessing attacks is limited by the birthday bound. Besides exploiting SEBC/SDBC, we mount a pair of plaintext recovery attacks and another universal forgery attack by taking advantage of weaknesses in the structure of COLM. Finally, we suggest some improvements to prevent our attacks and build stronger EME schemes.