Cryptology ePrint Archive: Report 2016/864

Salvaging Weak Security Bounds for Blockcipher-Based Constructions

Thomas Shrimpton and R. Seth Terashima

Abstract: The concrete security bounds for some blockcipher-based constructions sometimes become worrisome or even vacuous; for example, when a light-weight blockcipher is used, when large amounts of data are processed, or when a large number of connections need to be kept secure. Rotating keys helps, but introduces a ``hybrid factor'' $m$ equal to the number of keys used. In such instances, analysis in the ideal-cipher model (ICM) can give a sharper picture of security, but this heuristic is called into question when cryptanalysis of the real-world blockcipher reveals weak keys, related-key attacks, etc.

To address both concerns, we introduce a new analysis model, the ideal-cipher model under key-oblivious access (ICM-KOA). Like the ICM, the ICM-KOA can give sharp security bounds when standard-model bounds do not. Unlike the ICM, results in the ICM-KOA are less brittle to current and future cryptanalytic results on the blockcipher used to instantiate the ideal cipher. Also, results in the ICM-KOA immediately imply results in the ICM _and_ the standard model, giving multiple viewpoints on a construction with a single effort. The ICM-KOA provides a conceptual bridge between ideal ciphers and tweakable blockciphers (TBC): blockcipher-based constructions secure in the ICM-KOA have TBC-based analogs that are secure under standard-model TBC security assumptions. Finally, the ICM-KOA provides a natural framework for analyzing blockcipher key-update strategies that use the blockcipher to derive the new key. This is done, for example, in the NIST CTR-DRBG and in the hardware RNG that ships on Intel chips.

Category / Keywords: blockcipher, ideal cipher model, tweakable blockcipher, key rotation

Original Publication (in the same form): IACR-ASIACRYPT-2016

Date: received 6 Sep 2016, last revised 10 Sep 2016

Contact author: teshrim at ufl edu, seth at terashima us

Available format(s): PDF | BibTeX Citation

Version: 20160910:153254 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]