Paper 2017/702

Better Bounds for Block Cipher Modes of Operation via Nonce-Based Key Derivation

Shay Gueron and Yehuda Lindell


Block cipher modes of operation provide a way to securely encrypt using a block cipher. The main factors in analyzing modes of operation are the level of security achieved (chosen-plaintext security, authenticated encryption, nonce-misuse resistance, and so on) and performance. When measuring the security level of a mode of operation, it does not suffice to consider asymptotics, and a concrete analysis is necessary. This is especially the case today, when encryption rates can be very high, and so birthday bounds may be approached or even reached. In this paper, we show that key-derivation at every encryption significantly improves the security bounds in many cases. We present a new key-derivation method that utilizes a truncated block cipher, and show that this is far better than standard block-cipher based key derivation. We prove that by using our key derivation method, we obtain greatly improved bounds for many modes of operation, with a result that the lifetime of a key can be significantly extended. We demonstrate this for AES-CTR (CPA-security), AES-GCM (authenticated encryption) and AES-GCM-SIV (nonce-misuse resistance). Finally, we demonstrate that when using modern hardware with AES instructions (AES-NI), the performance penalty of deriving keys at each encryption is insignificant for most uses.

Available format(s)
Secret-key cryptography
Publication info
Published elsewhere. MINOR revision.ACM CCS 2017
modes of operationkey derivationnonce-misuse resistancesecurity bounds
Contact author(s)
lindell @ biu ac il
2017-08-31: revised
2017-07-21: received
See all versions
Short URL
Creative Commons Attribution


      author = {Shay Gueron and Yehuda Lindell},
      title = {Better Bounds for Block Cipher Modes of Operation via Nonce-Based Key Derivation},
      howpublished = {Cryptology ePrint Archive, Paper 2017/702},
      year = {2017},
      doi = {10.1145/3133956.3133992},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.