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

What it is

ePrint 2026/2713 (Freeman Slaughter, received 1 November 2026, approved 4 November 2026, preprint) attacks 2x2 Cayley hashes over F_p. It covers CHAMP and every other pair of generators A, B. The paper claims that no such pair gives collision resistance above O(√p).

How it works

The two generators share a symmetric form. Because of it, the hash of every palindromic message lies in a three-dimensional subspace that contains the identity. Two such hashes commute when their traceless parts are proportional. That defines a class map with p+2 values. By pigeonhole, two palindromes in the same class give a collision, and the collision is 4⌈log2(p+3)⌉ bits long.

Two search variants are given:

• Heuristic: a dictionary search finds a matching pair after about √(πp/2) class evaluations, assuming the classes are uniformly distributed.
• Distribution-independent: adding one bit to each half-message gives an expected O(√p) evaluations with no assumption on the class distribution.

If the common form is singular, the generators are simultaneously triangular and the same argument works on ordinary words, not only palindromes.

Concrete numbers

• CHAMP-512: a 512-bit collision after about 2^64 class evaluations. The distribution-independent variant gives 516 bits at the same leading cost.
• CHAMP-1024: a 1024-bit collision after about 2^128 evaluations. The distribution-independent variant gives 1028 bits.
• The paper includes an explicit proof-of-concept collision for the CHAMP matrices at a 36-bit prime.

Relation to earlier work

• The cost matches an earlier commuting-product search against CHAMP, but that attack needed messages of O(log²(p)) bits. These collisions are much shorter.
• It improves on an earlier palindrome restriction that cost about p.
• For every pair over an odd prime field, it shortens the collisions of the Mullan and Tsaban general algorithm from O(log²(p)/log(log(p))) to 4⌈log2(p+3)⌉ bits.
• The paper also proves that every sufficiently short message can be recovered from its digest for the main CHAMP pair.

Caveats

• The 2^64 and 2^128 figures for the heuristic variant rest on the uniformity assumption. The paper presents the one-bit-longer variant as the one that avoids it.
• The alternative CHAMP pair has more symmetry, because reversal and symbol exchange act as sign changes on quaternion coordinates. The author does not yet see how to use this to beat the square-root bound, so no sub-√p attack on that pair is claimed.
• The proof of concept is only at a 36-bit prime. No collision at CHAMP-512 or CHAMP-1024 parameters is reported.