[Plants] Re: Higher forgery resistance almost for free?

[Bas Westerbaan <[e-mail]>]

By the way, I agree with the randomizer idea (and also don't forget to
> include the Merkle tree position when you hash together two nodes - a cheap
> way to prevent multitarget attacks).
>

An earlier draft did, but the current one doesn't as it's based on
plain rfc6962 CT-log trees. Indeed there is a multi-target attack there:
say, find some x such that H_internal(H_leaf(leaf), x) matches an existing
internal node. Then we can create a fake inclusion proof, of course
updating the claimed index appropriately. That's similarly in the 256 -
lg(number of certificates in tree) regime as the multi-target attack on the
SPKI hash.

Some notes here:

This would be a surprisingly short authentication path, and a verifier
could detect it. That doesn't help much: restricting ourselves to only
targeting the lower nodes just removes half the targets.

Hashing the leaf index into the leaf would also prevent this. Still, the
other multi-target attack I mentioned still exists.

Best,

 Bas



>
>
> ------------------------------
> *From:* Bas Westerbaan <bas=[e-mail]>
> *Sent:* Friday, March 27, 2026 12:10 PM
> *To:* [e-mail] <[e-mail]>
> *Subject:* [Plants] Higher forgery resistance almost for free?
>
> Hey all,
>
> For the certificate transparency use case we need to make sure that a
> Certificate Authority can't issue a certificate without it being public. We
> don't want the CA to able to issue two completely different certificates,
> one harmless and one malicious at the same leaf. That requires
> collision resistance of the hash. Hence we use SHA-256 to gain 128-bit of
> transparency security.
>
> A 256-bit hash in Merkle trees can give much more than 128-bit forgery
> resistance—256 bits even. This is well known: CNSA 2 is even happy with LMS
> using SHA-256 truncated to 192 bits, which of course only achieves 192-bit
> security.
>
> So MTC as-is has 256-bit forgery resistance? Not quite: we need to make
> some changes, and there are some caveats.
>
> In the current draft, the leafs (TBSCertificateLogEntry) are mostly
> predictable by an attacker. Thus with 128-bit work, an attacker can find a
> collision: a harmless TBSCertificateLogEntry which it'll ask the CA to
> issue which has the same hash as a nefarious TBSCertificateLogEntry. [1]
>
> The standard way to solve this is to make the leaf unpredictable to the
> attacker, by including a CA-picked random value (randomizer) in each leaf.
> [2] That'll boost the forgery resistance above 192 bits and well along to
> 256-bits [3].
>
> The downside is that we need to add that 32-byte randomizer in each
> certificate.
>
> Worth it?
>
> I would say so.
>
> Best,
>
>  Bas
>
>
>
>
>
> [1] There are some minor hurdles: it'll need to guess the serial number
> correctly. And it'll need some immaterial field to vary to create attempts
> for the colission. Oh, and of course 128-bit work, but we're suspending
> disbelief for a moment.
>
> [2] Add 32-byte randomizer field in MerkleTreeCertEntry and MTCProof.
>
> [3] There is a multi-target attack against subjectPublicKeyInfoHash.
> Suppose there are 2^30 leafs with the same algorithm in
> subjectPublicKeyInfo. Then we only need to try 2^226 randomly generated
> subjectPublicKeyInfos to find a second preimage with some leaf. The
> standard way to thwart this is to add an * address* (leaf index) to the
> hash. That's not ideal, as plain SHA-256(subjectPublicKeyInfo) is quite
> standard now. The randomizer acts as an address for the leafs themselves.
> There is still an issue though.
>
> Even with addresses, SHA-256 isn't "distinct-function multi-target
> second-primage resistant" (DM-SPR) because it has a small internal state.
> This allows for a clever multi-target attack negating the addresses by
> finding successive colissions on the internal state, which was pointed out
> by Antonov, and improved by Perlner, Kelsey, and Cooper. See section 3.3 of
> ( https://eprint.iacr.org/2022/1061.pdf ). The attack requires room in
> the message for the logarithmically many collision values after the
> address. It'll depend on the algorithm whether that's feasable for the
> subjectPublicKeyInfo, and we can remove that room by moving
> subjectPublicKeyHash earlier in TBSCertificateLogEntry. The rigorous
> solution is not to use SHA-256, but a hash that is DM-SPR, such as
> SHAKE-256. But is that worth it? With a trillion certificates the attack is
> still in the order of 217-bit work.
>
> _______________________________________________
> Plants mailing list -- [e-mail]
> To unsubscribe send an email to [e-mail]
>