Security › hash-26 · Constant-time review · Performance: x86_1 · arm_1
The Hash Function CHIME (hash-26)
| Candidate | The Hash Function CHIME |
|---|---|
| Family | Symmetric (sponge and feed-forward sponge) |
| Archive | CHIME.zip (SHA-256: 3368eff8f86744eefba82825c11990a3b4d914e014ff184324ab3cb9af88b3a4) |
| Specification | hash-26-spec.pdf PDF |
| Performance | x86_1 · arm_1 |
hash-26-1: An invariant subspace reduces CHIME collision bounds to 64 and 160 bits
| Severity | Critical |
|---|---|
| Scope | design |
| Status | Confirmed |
| Affected | Submitted CHIME-512 and CHIME-1024 specifications and implementations |
| Discovery | Moderate |
| Exploitation | Approximately 2^64 and 2^160 evaluations; no full collision has been computed |
| Credit | Cryptanalysts001 (ISCAS) yufei2021@iscas.ac.cn; CHIME-1024 extension and CHIME-512 partial-collision witness by Markku-Juhani O. Saarinen markku-juhani.saarinen@tuni.fi, with AI assistance |
| Date | 2026-09-22 |
Original source: CryptHashForum report
In the submitted permutation, each 256-bit array remains in the repeated-word form (x,x,x,x): every layer preserves it and each round constant repeats one 64-bit word four times. This gives a 384-dimensional invariant subspace for the complete nonlinear, full-round permutation.
For CHIME-512, a 2^240-message family remains in the subspace through ordinary padding, while its digest contains only two independent 64-bit words. Sampling this family therefore gives a classical collision bound of about 2^64, rather than the claimed 256 bits. For CHIME-1024, the 448-bit rate occupies A0 and three lanes of A1; the remaining A1[0] and four B/C arrays form the capacity (CryptHash_AlgorithmInstance.c:780–815,829–867). Before each non-final permutation, choosing repeated words in A0 and adjusting the three rate lanes of A1 restores the invariant subspace, leaving 64 free message bits per block. Six controlled blocks thus give 2^384 distinct prefixes, but their capacities have only five independent 64-bit words. Sampling about 2^160 such prefixes yields a capacity match with probability above 0.39 for any output distribution; repeated prefixes contribute less than 2^-64. One further chosen block cancels the rate difference, and equal old capacities make the feed-forward outputs and final digests equal. This strengthens the earlier 2^224 bound. The full-size search has not been run.
A separate search produced two distinct 63-byte CHIME-512 messages whose first 256 digest bits agree under the submitted 15-round reference hash; the remaining 256 bits differ. It took 2^32.95 folded-permutation evaluations. This is a partial collision, not a full collision.
The archived Round 1 submission remains the target of this finding.
Further analysis: Yufei Yuan et al., Structural Analysis of Seven Hash Functions Submitted to the NGCC, Section 5 (2026-09-23), gives a greater-than-0.39 collision probability within 2^64 evaluations for CHIME-512. The paper does not cover this report's CHIME-1024 extension.
Proposed fixes
The submission team's erratum proposes replacing the repeated round constants with word-dependent constants. This section records the proposal without evaluating it.
Reproducing
Commands below run in a checkout of the ngcc-harness repository with the candidate built (see its README).
The local checks reproduce the reporters' 126-byte CHIME-512 invariant-state witness, verify the 256-bit partial collision on the submitted reference hash, and use the submitted CHIME-1024 source to test restricted chaining and chosen-block rate alignment. They do not execute either full collision search:
make -C hash-26 reproduce
python3 hash-26/reproduce_capacity_match.py
hash-26-2: Fixed-output wrappers ignore the requested digest length
| Severity | Low |
|---|---|
| Scope | implementation |
| Status | Confirmed |
| Affected | CHIME-512 and CHIME-1024 reference implementation; the optimized implementation rejects other lengths |
| Discovery | Trivial |
| Exploitation | A caller that sizes the output buffer from a shorter requested length receives a write beyond it; no secret disclosure or cryptographic break shown |
| Credit | Markku-Juhani O. Saarinen markku-juhani.saarinen@tuni.fi, with AI assistance; independently reported by LK-PQC-Hunter (NGCC CryptHash Forum sender), using the LKQ PQC Hunter automated tool |
| Date | 2026-11-17 |
Follow-up source: LK-PQC-Hunter's CryptHash Forum post, posted after this entry was published
The reference wrapper never reads digest_len_bits (CryptHash_AlgorithmInstance.c:15-22), returns 0 and always writes the full 64- or 128-byte digest. Both reference builds do this for 8- and 256-bit requests. The optimized C++ implementation returns −1 and writes nothing for the same requests, so the two trees disagree.
Fix: return an error unless digest_len_bits equals the instance's digest length.
Reproducing
Commands below run in a checkout of the ngcc-harness repository with the candidate built (see its README).
sh hash-26/reproduce_digest_length.sh
The driver never writes out of bounds itself; it measures the write extent inside a larger buffer.