Paper 2022/1630

Finding Collisions for Round-Reduced Romulus-H

Marcel Nageler, Graz University of Technology
Felix Pallua, Graz University of Technology
Maria Eichlseder, Graz University of Technology
Abstract

The hash function Romulus-H is a finalist in the NIST Lightweight Cryptography competition. It is based on the Hirose double block-length (DBL) construction which is provably secure when used with an ideal block cipher. However, in practice, ideal block ciphers can only be approximated. Therefore, the security of concrete instantiations must be cryptanalyzed carefully; the security margin may be higher or lower than in the secret-key setting. So far, the Hirose DBL construction has been studied with only a few other block ciphers, like IDEA and AES. However, Romulus-H uses Hirose DBL with the SKINNY block cipher where only very little analysis has been published so far. In this work, we present the first practical analysis of Romulus-H. We propose a new framework for finding collisions in hash functions based on the Hirose DBL construction. This is in contrast to previous work that only focused on free-start collisions. Our framework is based on the idea of joint differential characteristics which capture the relationship between the two block cipher calls in the Hirose DBL construction. To identify good joint differential characteristics, we propose a combination of MILP and CP models. Then, we use these characteristics in another CP model to find collisions. Finally, we apply this framework to Romulus-H and find practical collisions of the hash function for 10 out of 40 rounds and practical semi-free-start collisions for up to 14 rounds.

Metadata
Available format(s)
PDF
Category
Attacks and cryptanalysis
Publication info
Published by the IACR in TOSC 2023
DOI
10.46586/tosc.v2023.i1.67-88
Keywords
Hash functionsDifferential cryptanalysisMILPSMTRomulus-H
Contact author(s)
marcel nageler @ iaik tugraz at
felix pallua @ student tugraz at
maria eichlseder @ iaik tugraz at
History
2023-03-13: last of 3 revisions
2022-11-23: received
See all versions
Short URL
https://ia.cr/2022/1630
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/1630,
      author = {Marcel Nageler and Felix Pallua and Maria Eichlseder},
      title = {Finding Collisions for Round-Reduced Romulus-H},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/1630},
      year = {2022},
      doi = {10.46586/tosc.v2023.i1.67-88},
      url = {https://eprint.iacr.org/2022/1630}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.