Paper 2013/586

Generic related-key and induced chosen IV attacks using the method of key differentiation

Enes Pasalic and Yongzhuang Wei

Abstract

Related-key and chosen IV attacks are well known cryptanalytic tools in cryptanalysis of stream ciphers. Though the related-key model is considered to be much more unrealistic scenario than the chosen IV model we show that under certain circumstances the attack assumptions may become equivalent. We show that the key differentiation method induces a generic attack in a related-key model whose time complexity in the on-line phase is less than the exhaustive key search. The case of formal equivalency between the two scenarios arises when so-called {\em differentiable polynomials} with respect to some subset of key variables are a part of the state bit expressions (from which the output keystream bits are built). Then the differentiation over a key cube has the same effect as the differentiation over the corresponding IV cube, so that a generic nature of a related-key model is transferred into a more practical chosen IV model. The existence of such polynomials is confirmed for the reduced round stream cipher TRIVIUM up to some 710 rounds and an algorithm for their detection is proposed. The key differentiation method induces a time/related-key trade-off (TRKTO) attack which (assuming the existence of differentiable polynomials) can be run in a chosen IV model. The resulting trade-off curve of our TMDTO attack is given by $T^2M^2D^2=(KV)^2$ ($V$ denoting the IV space), which is a significant improvement over the currently best known trade-off $TM^2D^2=(KV)^2$ \cite{IVDunkel08}.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Stream ciphersCryptanalysisChosen IV attacksRelated-key attacksTime-Memory-Data trade-off attacksDifferntiable polynomialsKey differentiation.
Contact author(s)
enes pasalic6 @ gmail com
History
2013-09-14: received
Short URL
https://ia.cr/2013/586
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2013/586,
      author = {Enes Pasalic and Yongzhuang Wei},
      title = {Generic related-key and induced chosen IV attacks using the method of key differentiation},
      howpublished = {Cryptology ePrint Archive, Paper 2013/586},
      year = {2013},
      note = {\url{https://eprint.iacr.org/2013/586}},
      url = {https://eprint.iacr.org/2013/586}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.