Paper 2013/586

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

Enes Pasalic and Yongzhuang Wei


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}.

Available format(s)
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Stream ciphersCryptanalysisChosen IV attacksRelated-key attacksTime-Memory-Data trade-off attacksDifferntiable polynomialsKey differentiation.
Contact author(s)
enes pasalic6 @ gmail com
2013-09-14: received
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.