Cryptanalysis of the Counter mode of operation

Abstract : The counter mode of operation (CTR mode) is nowadays one of the most widely deployed modes of operation due to its simplicity, elegant design and performance. Therefore understanding more about the security of the CTR mode helps us understand the security of many applications used over the modern internet. On the security of the CTR mode, there is a well-known proof of indistinguishability from random outputs up to the birthday bound that is O(2 n/2) encrypted n-bit blocks. This acts as a proof that no attack that can retrieve useful information about the plaintext exists with a lower complexity. In other words, any attack that breaks the confidentiality of the plaintext will require Ω(2 n/2) blocks of ciphertext. Research problem While we have a lower bound on the complexity of a potential attack, it is not well understood how such attack would work and what would be its complexity not only in terms of data but also computationally (time and memory complexities). Most often the CTR mode is combined with the AES block cipher which acts on 128-bits blocks. In that setting, the birthday bound may appear sufficient to guarantee security in most if not all of today's internet applications as 2 128/2 × 128 bits = 256 exbibytes, a comfortable margin. However if used alongside a 64-bits block cipher, like 3DES, the birthday bound stands at 2 64/2 × 64 bits = 32 gibibytes, an amount of data quickly exchanged in today's internet. Moreover, the proof of indistinguishability says nothing at how quickly information on the plaintext is leaked when nearing the birthday bound. The goal of this internship is to devise efficient message recovery attacks under realistic assumptions and study their complexity to gain a better understanding of the security of the CTR mode. Contribution We give a concrete definition of the algorithmic problem naturally posed by the counter mode of operation, the missing difference problem, upon the resolution of which we can recover part of the unknown plaintext. Then we propose two algorithms to recover a block or more of secret plaintext in different settings motivated by real-life attacker models and compare the results with the work done by McGrew [McG12] on that same topic. We improve McGrew's results in two cases : the case where we know half of the secret plaintext, then we achieve time complexity of˜Oof˜ of˜O(2 n/2) compared tõ O(2 3n/4) for McGrew's searching algorithm and the case where we have no prior information on the secret where we achieve˜Oachieve˜ achieve˜O(2 2n/3) in time and query compared to the previous˜Oprevious˜ previous˜O(2 n/2) queries and˜Oand˜ and˜O(2 n) time. This improvement allows better attack on the mode for a realistic attacker model than what had been described so far in the literature. In fact, we found out that the CTR mode does not offer much more security guarantees than the CBC mode as real attacks are of similar complexities. We described these attacks on the CTR mode and could even extend those to some message authentication code (MAC) schemes GMAC and Poly1305 based on the Wegman-Carter style construction. Arguments supporting its validity Not only do we provide some proofs for the asymptotic complexity but also implementations of these algorithms show that they are practical for blocks sizes n 64 bits and so are the associated attacks. These attacks rely on the repeated encryption of a secret under the same key so frequent rekeying will prevent those attacks from happening and thus we encourage any implementation of the CTR mode to force rekeying well before the birthday bound. Summary and future work We formalized an algorithmic problem that is naturally encountered in some cryptographic schemes, we called it the missing difference problem, and developed tools to solve it efficiently. These tools then help the cryptanalysis of different modes of operation and thus help understanding the security of popular real-world protocols. Now we hope to publish these results and make users aware that using CTR is not much more secure than CBC (though CTR still offers other advantages). Especially when coupled with 64-bits block ciphers, it may not offer enough guarantee for most modern uses as 64-bits CBC mode was shown to be insecure in a recent work by Bhargavan and Leurent [BL16].
Type de document :
Mémoires d'étudiants -- Hal-inria+
Cryptography and Security [cs.CR]. 2017
Liste complète des métadonnées

Littérature citée [24 références]  Voir  Masquer  Télécharger
Contributeur : Ferdinand Sibleyras <>
Soumis le : mardi 12 décembre 2017 - 16:12:26
Dernière modification le : mercredi 13 décembre 2017 - 01:16:58


Fichiers produits par l'(les) auteur(s)


  • HAL Id : hal-01662040, version 1



Ferdinand Sibleyras. Cryptanalysis of the Counter mode of operation. Cryptography and Security [cs.CR]. 2017. 〈hal-01662040〉



Consultations de la notice


Téléchargements de fichiers