Paper 2016/864

Salvaging Weak Security Bounds for Blockcipher-Based Constructions

Thomas Shrimpton and R. Seth Terashima


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.

Available format(s)
Publication info
Published by the IACR in ASIACRYPT 2016
blockcipherideal cipher modeltweakable blockcipherkey rotation
Contact author(s)
teshrim @ ufl edu
seth @ terashima us
2016-09-10: received
Short URL
Creative Commons Attribution


      author = {Thomas Shrimpton and R.  Seth Terashima},
      title = {Salvaging Weak Security Bounds for Blockcipher-Based Constructions},
      howpublished = {Cryptology ePrint Archive, Paper 2016/864},
      year = {2016},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.