Cryptology ePrint Archive: Report 2017/702

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

Shay Gueron and Yehuda Lindell

Abstract: 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.

Category / Keywords: secret-key cryptography / modes of operation, key derivation, nonce-misuse resistance, security bounds

Original Publication (with minor differences): ACM CCS 2017

Date: received 13 Jul 2017, last revised 31 Aug 2017

Contact author: lindell at biu ac il

Available format(s): PDF | BibTeX Citation

Version: 20170831:082741 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]