Security of the Merkle-Damgård Combiner Under Constant-Length Salts
Statement: AI-written, not yet formalized. Proof: open – no attempt yet.
The source’s main construction XORs the Merkle-Damgård extensions of two salted hash functions together, and proves it a secure random oracle combiner as long as each salt is longer than the message by at least the security parameter. The proof genuinely needs that margin, but the authors have found no attack that exploits shorter salts either — not even at a small constant number of blocks, independent of the message length. They leave open which of the two is true: that short salts really do break the construction, or that it is secure with much shorter salts than its current proof requires.
View PDF · LaTeX source · Formal statement — not yet formalized
The construction (the source’s Theorem 3.1). For compression functions \(h_{1}, h_{2} : \{0,1\}^{n+\delta} \to \{0,1\}^{n}\) with Merkle-Damgård extensions \(h_{1}^{*}, h_{2}^{*}\), \[\widetilde C^{h_{1},h_{2}}_{Z_{1},Z_{2}}(M) := h_{1}^{*}(M, Z_{1}) \oplus h_{2}^{*}(M, Z_{2})\] is a secure random oracle combiner whenever \(|Z_{1}|, |Z_{2}| > |M| + \lambda\). No attack against \(\widetilde C\) is known for shorter salts, including salts of constant length, independent of \(|M|\).
Conjecture. Resolve which of the following holds: (i) there is a choice of \(|Z_{1}|, |Z_{2}| = O(1)\) blocks, independent of \(|M|\), together with an efficient adversary breaking the indifferentiability of \(\widetilde C\) from a random oracle; or (ii) \(\widetilde C\) remains a secure random oracle combiner even when \(|Z_{1}|, |Z_{2}|\) are a constant number of blocks, independent of \(|M|\).
How the source states it. Its conclusion (page 27) reads: “While our analysis of \(\widetilde C\) critically uses the fact that \(|Z_{i}| > |M| + \lambda\), we do not have any attacks against this construction, once the \(|Z_{i}|\) is a constant number of blocks, independent of \(|M|\). In particular, it is possible our construction \(\widetilde C\) provides a solution to” the broader, separately-tracked existence problem (see c/0063). It continues: “Thus, it would be very interesting to either show that \(\widetilde C\) is insecure unless \(|Z_{i}| > |M|\), or find a supporting proof of security for much shorter salts (ideally, constant number of blocks).”
The source’s dichotomy is not perfectly symmetric. It phrases the “insecure” alternative more broadly, as showing \(\widetilde C\) is insecure unless \(|Z_{i}| > |M|\) — over the whole sub-threshold range \(|Z_{i}| \le |M|\) — while narrowing the “secure” alternative specifically to the constant-blocks case, the regime where it reports no known attack. This page’s statement targets that constant-blocks extreme in both directions; resolving it there does not by itself settle the source’s broader-phrased alternative for every \(|Z_{i}|\) strictly between a constant and \(|M|\).
Sources
- Dodis, Goldin and Hall. Random Oracle Combiners: Merkle-Damgård Style. IACR ePrint 2025/609. The source. The construction and its security theorem are Section 3 (Theorem 3.1); the open problem is Section 4 (“Conclusion and Open Problems”), page 27.
View PDF — no proof written yet · LaTeX source — no proof written yet · Formal proof — not yet formalized
Open, with the source’s own proof technique the visible starting point for either direction.
Toward a proof of (ii). The source’s Theorem 3.1 bounds a simulator’s recursion depth using the \(|Z_{i}| > |M| + \lambda\) margin; a security proof at constant-length salts would need either a sharper bound on that same recursion, or a different simulation strategy entirely, since the current argument does not survive the salt shrinking below the message length.
Toward an attack for (i). An attack would need to exploit exactly what the current proof’s margin rules out: a way for an adversary to use the shortness of the salt relative to the message to distinguish \(\widetilde C\) from a random oracle, most plausibly by finding two messages that collide under a much shorter salt in a way the compression-function XOR does not mask.
Checked against the literature, 2026-08-24. No proof, refutation or resolution found in the months since the ePrint. This is a targeted check on a very recent paper, not an exhaustive sweep.
Why this is worth tracking separately from the general question. A proof of (ii) would answer c/0063’s existence question affirmatively, by exhibiting \(\widetilde C\) itself as the witness. An attack under (i) would not: some other combiner might still achieve short, message-independent salts by a different construction. So this page is strictly easier to attack (it is about one fixed, already-specified scheme) but only partially informative about the broader question.
What a reviewer should be suspicious of. The source’s own dichotomy is asymmetric (see the Statement tab); a careful reading should not treat a resolution at the constant-blocks extreme as settling the source’s literal “unless \(|Z_{i}| > |M|\)” phrasing for every value in between.
Attackability for an AI proof harness (conjecture-triage, 2026-08-25). Scored 26/31, verdict GO, difficulty band “routine” — this rates how tractable a bounded multi-agent campaign would find it, not the statement’s intrinsic mathematical difficulty. It fixes one already-specified construction rather than asking about combiners in general, which gives a Refuter a genuine, finite-instantiation-testable target: an explicit distinguisher against \(\widetilde C\) at constant-block salts is directly search-and-simulate friendly, unlike the sibling question on this hub. Recommended configuration: Refuter-first, attempting an attack in parallel with a Prover extending the source’s own simulator argument. Full record: latex/conjectures/short-salt-security-mdroc/triage.json.