Paper 2026/2713

CHAMPing at the Bit: Short Square-Root Collisions for Two-Generator Cayley Hashes

Abstract

For $A,B\in\text{GL}(\mathbb{F}_p)$, a Cayley hash $\text{HM}(w)$ maps a bit string $w \in \{0,1\}$ to the corresponding product of $A$ and $B$. We construct collisions by finding two palindromes whose matrix products commute. A symmetric form shared by the two generators places the hash of every palindrome in a three-dimensional subspace containing the identity. Two such hashes commute when their traceless parts are proportional, which defines a class map with $p+2$ values, so the pigeonhole principle gives collisions of $4\lceil\log_2(p+3)\rceil$ bits. Under a uniformity heuristic, a dictionary search finds such a pair after about $\sqrt{\pi p/2}$ class evaluations. Adding one bit to each half-message gives an expected bound of $O(\sqrt p)$ evaluations, with no assumption on how the classes are distributed. When the common form is singular, the generators are simultaneously triangular and the same argument applies to ordinary words. For CHAMP-512 and CHAMP-1024, the heuristic search finds collisions of $512$ and $1024$ bits after about $2^{64}$ and $2^{128}$ class evaluations, and the one-bit-longer, distribution-independent variant finds collisions of $516$ and $1028$ bits at the same leading cost. This matches the asymptotic cost of an earlier commuting-product search for CHAMP, whose messages have $O(\log^2(p))$ bits, and improves on the bound of about $p$ given by an earlier palindrome restriction. For every pair over an odd prime field, this also shortens the collisions of the general algorithm of Mullan and Tsaban from $O(\log^2(p)/\log(\log(p)))$ to $4 \lceil \log_2(p+3) \rceil$ bits. Since the argument applies to every pair $A,B$, no pair of generators gives a $2\times2$ Cayley hash over $\mathbb{F}_p$ with collision resistance greater than $O(\sqrt p)$. We give an explicit proof-of-concept collision for the CHAMP matrices at a $36$-bit prime, and prove that every sufficiently short message can be recovered from its digest for the main CHAMP pair. To close, we demonstrate that since reversal and symbol exchange act as sign changes on quaternion coordinates, the alternative CHAMP pair possesses a much greater degree of symmetry, but do not yet see how to utilize this to find collisions below the square-root bound.