Paper 2024/1776

An efficient collision attack on Castryck-Decru-Smith’s hash function

Ryo Ohashi, University of Tokyo
Hiroshi Onuki, University of Tokyo
Abstract

In 2020, Castryck-Decru-Smith constructed a hash function using the (2,2)-isogeny graph of superspecial principally polarized abelian surfaces. In their construction, the initial surface was chosen from vertices quite "close" to the square of a supersingular elliptic curve with a known endomorphism ring. In this paper, we propose an algorithm for recovering a collision on their hash function. Under some heuristic assumptions, the time complexity and space complexity of our algorithm are estimated to be which is smaller than the complexity the authors had claimed necessary to recover such a collision, where is the characteristic of the base field. In particular case where has a special form, then both the time and space complexities of our algorithm are polynomial in . We implemented our algorithm in MAGMA, and succeeded in recovering a collision in 17 hours (using 64 parallel computations) under a parameter setting the authors had claimed to be 384-bit secure. Finally, we propose a simple countermeasure against our attack, which is expected to restore the complexity required to recover a collision to currently.

Metadata
Available format(s)
PDF
Category
Attacks and cryptanalysis
Publication info
Published elsewhere. Minor revision. PQCrypto 2025
Keywords
Hash functionIsogeny-based cryptographySuperspecial abelian surfaceKani's lemma
Contact author(s)
ryo-ohashi @ g ecc u-tokyo ac jp
hiroshi-onuki @ g ecc u-tokyo ac jp
History
2025-03-13: revised
2024-10-31: received
See all versions
Short URL
https://ia.cr/2024/1776
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/1776,
      author = {Ryo Ohashi and Hiroshi Onuki},
      title = {An efficient collision attack on Castryck-Decru-Smith’s hash function},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/1776},
      year = {2024},
      url = {https://eprint.iacr.org/2024/1776}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.