Paper 2026/2671

Beyond the Event Horizon of Keccak, Extending the Observation from 2011 and applications

Danilo Gligoroski, Norwegian University of Science and Technology (NTNU)
Abstract

In 2011 we observed that a single path in the Keccak sponge from a state whose capacity has all zero bits back to such a state yields an explicit, infinite family of second preimages for every message of at least one full rate block. Finding such a path costs about 2^(c/2), which lies "beyond the event horizon" for SHA3-256 (c = 512). In this paper we give four novel theorems around that observation. First, the capacity can have any value x: a two-block meet-in-the-middle loop from x back to x, found at heuristic cost ≈ sqrt(π)·2^(c/2), gives the same unlimited family of second preimages requiring no further search, with connectors to and from x at the same expected cost each (Theorem 1). Theorem 2 extends this to k-block loops and to cycles of the capacity map. A single-state bridge, a state S with cap(f(S)) = cap(f^(-1)(S)), where cap denotes the capacity part of the state, also gives such a family but costs ≈ 2^c. Theorem 3 gives cheap collisions and a bridge-amplified multicollision: one inner collision and one connector yield equal-length Joux-style 2^k-multicollisions for every k, instead of Joux's k collision searches. Given a prefix reaching x and k bridges on x with pairwise-distinct first rate inputs, Theorem 4 gives k^L distinct equal-length messages of 2L+1 blocks reaching one full state, for every L; in the balanced search model, finding the bridges costs about sqrt(4k)·2^(c/2) calls for large k, independently of L. A binary Joux construction producing at least as many messages needs about ⌈L·log2(k)⌉ collision searches, each of generic order 2^(c/2). To our knowledge, the k^L count of equal-length messages from k > 1 bridges at an arbitrary x is new. We give a verified full-round Keccak-f[1600] bridge with c = 80 and a full-round c = 80 example from the standard IV: an IV transition and three bridges (2^42.61 calls in total) give 3^3 = 27 distinct 1710-byte messages with a common digest. At c = 88 we found four bridges on one generalized capacity; two are published, and the other two are posed as one-sided forgery challenges, in which only the forward half of a bridge is public, with heuristic generic completion cost about 2^88 (and 2^92 for one of them, read at its larger effective capacity). Lemma 5 shows that a bridge at capacity c is a bridge at every smaller capacity. The bridges were found by an incremental distinguished-point search that resumes from its stored table; the soundness of its output and the distinctness of the first halves of the bridges it reports are machine-checked in Lean 4. The second part of the paper offers novel protocols built on the asymmetry between minting and forging Keccak bridges. They include proof of work with hardness-adaptive capacity, dual-capacity commitments anchored by the real SHA3-256 digest, bridges as zero-knowledge-committed tokens, and a self-enforcing bounty market for reduced-round security. To our knowledge, these are the first unkeyed Keccak-based protocols that deliberately set the capacity so that the generic bridge cost is a feasible, tunable hardness parameter. We give a list of 13 further protocol ideas for application of Keccak bridges. We prove the four theorems, machine-check the stated algebraic results in Lean 4, and provide reproducible experiments and open-source proof-of-concept code. The applications are design proposals whose end-to-end security remains open.

Note: Proving some new properties and publishing challenges.

Metadata
Available format(s)
PDF
Category
Attacks and cryptanalysis
Publication info
Preprint.
Keywords
KeccakSHA-3sponge constructionsecond preimagesmulticollisionszero-knowledge tokensLean 4
Contact author(s)
danilog @ ntnu no
History
2026-11-12: last of 3 revisions
2026-10-28: received
See all versions
Short URL
https://ia.cr/2026/2671
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2026/2671,
      author = {Danilo Gligoroski},
      title = {Beyond the Event Horizon of Keccak, Extending the Observation from 2011 and applications},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/2671},
      year = {2026},
      url = {https://eprint.iacr.org/2026/2671}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.