CHAMP

champ-1

Collisions through the triangular subgroup

Practical · Tested at small scale · Cause: construction

Property: collision resistance

Cost against claim: CHAMP-512 collision ≈2⁶⁸ against the required 2²⁵⁶

CHAMP hashes a message as a product of two public 2×2 matrices modulo a safe prime p. Words whose product is upper triangular are found in about √p by a claw search. Two such words, multiplied in the two possible orders, give products with the same diagonal, and a birthday search on the remaining entry yields two distinct messages of equal length with the same matrix, hence the same digest.

Parameter set	Claim	Attack cost	Verdict
CHAMP-512	no numeric claim; the call requires collision 2²⁵⁶	≈2⁶⁸	Practical
CHAMP-1024	no numeric claim; the call requires collision 2⁵¹²	≈2¹³²	Theoretical

What causes it

The digest is the matrix product with an entrywise inversion, over generators of determinant 2 and a safe prime of 128 or 256 bits. Nothing in the construction prevents the triangular-subgroup method, whose principle is published for Cayley hashes; the specification gives no numeric security level and states that no general collision method is known.

Evidence

More than 190 real collisions on safe primes of 24 to 44 bits, with CHAMP's own generators; measured work grows as p^0.51, which the full-size figures extrapolate.
A model rebuilt from the specification reproduces every official test vector of both instances.

Cause in the specification: the attack also works on a model built from the specification alone.

Limits

The full-size collisions are extrapolated from the toy primes, not computed.

What PQC-X adds

A measured work exponent behind the full-size estimate: p^0.51, over more than 190 collisions on safe primes of 24 to 44 bits.

Credit

First public report: M.-J. Saarinen (ngcc.dev hash-04-2, 2026-09-21). Found independently by PQC-X.

Related public reports:

Mounir Idrassi (champ-cryptanalysis, 2026-09-22): the subgroup collision search adapted to CHAMP, with collision certificates on reduced parameters.
Tsinghua Hash Lab (CryptHash forum, 2026-09-22): a heuristic collision estimate of about 2⁶⁴ for CHAMP-512 through commuting matrices.
M.-J. Saarinen (ngcc.dev hash-04-1, 2026-09-21): fixed-length outputs lie on a set of about p³ matrices, which caps generic collisions at about 2¹⁹² / 2³⁸⁴ (also in ePrint 2026/2152).

The method follows Petit, Quisquater, Tillich and Zémor (CT-RSA 2009) on the Zémor-Tillich hash.

champ-2

Short or mostly known inputs are recovered from the digest in seconds

Minor break · Demonstrated · Cause: construction

Property: the specification's own one-wayness claims for partly known inputs; preimages of random digests unaffected

Cost against claim: seconds for up to ~90 unknown bits (CHAMP-512) or ~180 (CHAMP-1024)

For a short input no modular reduction takes place, so the matrix read back from the digest can be lifted to the integers exactly, and its factors peel off one by one by parity and magnitude. With known context before and after, any unknown window inside a longer message is recovered the same way.

Parameter set	Claim	Attack cost	Verdict
CHAMP-512	specification §7.1 (claim 2) and §7.2	seconds, ≤ ~90 unknown bits	Minor break
CHAMP-1024	specification §7.1 (claim 2) and §7.2	seconds, ≤ ~180 unknown bits	Minor break

What causes it

The digest is the matrix product with entrywise inversion (both public and invertible), and the length is read off the determinant 2ⁿ. Nothing mixes short inputs. The specification claims that recovering even the first or last bit of a message of at least 1000 bits is infeasible, and that the determinant and negative eigenvalues defeat length attacks; both claims fall when a short window is unknown.

Evidence

20/20 recoveries of 80 unknown bits (CHAMP-512) and of 160 unknown bits (CHAMP-1024) from digests of the reference code.
Three 128-bit secrets recovered from CHAMP-1024 reference digests with an independent implementation.

Cause in the specification: the attack also works on a model built from the specification alone.

Limits

Not a preimage attack on random digests: the input must be short, or known except for a short window.

What PQC-X adds

Recovery in seconds rather than 2^m/2: the exact integer lift replaces meet-in-the-middle for short inputs, and extends to unknown windows inside known context.

Credit

Found by PQC-X.

Related public reports:

Mounir Idrassi (ngcc.dev hash-04-3, 2026-09-22): an exact meet-in-the-middle preimage search costing 2^m/2 for an m-bit input of known length.

Lifting attacks on Cayley hashes: Tillich and Zémor (1993); Petit and Quisquater's survey (2013), §3.4.

Design

Collisions through the triangular subgroup

What causes it

Evidence

Limits

What PQC-X adds

Credit

Short or mostly known inputs are recovered from the digest in seconds

What causes it

Evidence

Limits

What PQC-X adds

Credit