Paper 2016/509

Chosen-Key Distinguishers on 12-Round Feistel-SP and 11-Round Collision Attacks on Its Hashing Modes

Xiaoyang Dong and Xiaoyun Wang

Abstract

Since Knudsen and Rijmen proposed the $known$-$key$ attacks in ASIACRYPT 2007, the $open$-$key$ model becomes more and more popular. As the other component of the $open$-$key$ model, $chosen$-$key$ model was applied to the full attacks on AES-256 by Biryukov \emph{et al.} in CRYPTO 2009. In this paper, we explore how practically the $chosen$-$key$ model affect the real-world cryptography and show that 11-round generic Feistel-SP block cipher is no longer safe in its hashing modes (MMO and MP mode) as there exist collision attacks. This work improves Sasaki and Yasuda's collision attacks by 2 rounds with two interesting techniques. First, we for the first time use the available degrees of freedom in the key to reduce the complexity of the inbound phase, which extends the previous 5-round inbound differential to a 7-round one. This results in a 12-round $chosen$-$key$ distinguisher of Feistel-SP block cipher. Second, inspired by the idea of Wang \emph{et al.}, we construct collisions using two blocks. The \emph{rebound attack} is used in the second compression function. We carefully balance the freedom of the first block and the complexity of the \emph{rebound attack}, and extend the $chosen$-$key$ attack to a 11-round collision attack on its hashing modes (MMO and MP mode).

Metadata
Available format(s)
PDF
Publication info
A minor revision of an IACR publication in FSE 2017
Keywords
Block CipherFeistel-SPChosen-KeyRebound AttackHash Mode
Contact author(s)
dongxiaoyang @ mail sdu edu cn
History
2016-08-31: last of 6 revisions
2016-05-25: received
See all versions
Short URL
https://ia.cr/2016/509
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/509,
      author = {Xiaoyang Dong and Xiaoyun Wang},
      title = {Chosen-Key Distinguishers on 12-Round Feistel-{SP} and 11-Round Collision Attacks on Its Hashing Modes},
      howpublished = {Cryptology {ePrint} Archive, Paper 2016/509},
      year = {2016},
      url = {https://eprint.iacr.org/2016/509}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.