Paper 2024/1776

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

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 $\widetilde{O}(p^{3/10})$ which is smaller than the complexity $\widetilde{O}(p^{3/2})$ the authors had claimed necessary to recover such a collision, where $p$ is the characteristic of the base field. In particular case where $p$ has a special form, then both the time and space complexities of our algorithm are polynomial in $\log{p}$. 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 $\widetilde{O}(p)$ currently.