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

[David Benjamin <[e-mail]>]

On Fri, Sep 11, 2026 at 1:03 PM David Benjamin <[e-mail]>
wrote:

> Hi Casey! This is really great feedback, thanks!
>
> For specifically the first deployments in the Web PKI (where we care about
> having a network of cosigners), I think it's important to define a mode
> that is compatible with RFC 6962 and tlog (i.e. SHA-256, no indices in the
> various hashes), so that we can reuse the wealth of existing software built
> around this tree construction. This is particularly important given the
> tight timelines for the PQ transition.
>
> But that's not to say that should be the only tree construction. The core
> ideas of MTCs would work just fine with SHA-384, SHA-384 truncated, more
> involved HashNode functions, etc. And the nice thing about this space is
> that you can very naturally key everything on the CA, so this all reduces
> to how to juggle different CAs and how to define the parameters for each
> CA. Maybe a different MTC CA would look like you describe, or maybe even
> the Web PKI would eventually support both.
>
> For that, I think one immediate conclusion here is that the CA format
> below was not right. It assumed the tree would *only* be parameterized by
> the underlying hash function, and you've described a host of other things.
>
> https://www.ietf.org/archive/id/draft-ietf-plants-merkle-tree-certs-05.html#name-representing-certification-
>
> I think I'm now fully convinced we should make the change outlined here:
> https://github.com/ietf-plants-wg/merkle-tree-certs/issues/293
>
> In that model, the hash construction defined in the draft today would be
> signaled by the id-pe-mtcCertificationAuthority-SHA256 extension. But then
> another construction with perhaps a wider hash, perhaps indices
> incorporated into the node hashes, perhaps truncation of said wider hash,
> etc., might be id-pe-mtcCertificationAuthority-SHA384-Casey (insert better
> name here :-) ). I think this is a much better extensibility model. I can
> put together a PR for that so we have something concrete to look at there.
>

Done here. https://github.com/ietf-plants-wg/merkle-tree-certs/pull/315


> A minor note:
>
> >  It seems like a best practice to include the leaf indices when
> performing the internal hash and also add serialNumber to
> TBSCertificateLogEntry.  For example, the NIST hash-based signatures
> incorporate addresses when performing a hash.
>
> I think, operationally, it would make sense to put the addresses (and
> possibly the log ID?) into the hash and then *not* put the serialNumber
> in the TBSCertificateLogEntry. Once you have the leaf index and the log ID,
> all information in the serialNumber is already represented. The reason to
> omit the serialNumber is mostly a layering problem. If you imagine the CA's
> log component, it probably has some general operation like
> `AddEntry(entryData []byte)` that adds the entry as an opaque byte string.
> AddEntry might potentially need to sequence concurrent calls, etc., and so
> the caller of AddEntry may not actually know the leaf index ahead of time.
> But if the leaf index needs to be swizzled into entryData in some complex
> way, this means some layer *after* sequencing needs to be aware of the
> details of TBSCertificateLogEntry.
>
> And so I think the right way to do this would be, similar to the
> hash-based signatures, to define it as part of the various HashNode and
> HashLeaf functions and keep the entry contents opaque.
>
> On Fri, Sep 11, 2026 at 11:40 AM [e-mail] <cwwynn=
> [e-mail]> wrote:
>
>> Hi all,
>>
>> I wanted to revisit the idea of incorporating leaf indices into hashing,
>> as previously mentioned by Scott.  There was only a bit of discussion at
>> the time, and I believe it's important to voice support for adding this
>> feature.  It seems like a best practice to include the leaf indices when
>> performing the internal hash and also add serialNumber to
>> TBSCertificateLogEntry.  For example, the NIST hash-based signatures
>> incorporate addresses when performing a hash.
>>
>> If used to protect data in NSS, we would recommend a MTC CA use one of
>> the (CNSA) SHA2 hash algorithms with a larger internal state (i.e. SHA-384
>> or SHA-512) possibly truncated when needed to maintain practical tree and
>> inclusion proof sizes while still mitigating the Antonov attack.  Adding
>> indices into the hashing process would further enhance security towards
>> multi-target second preimage resistance.  We would also prefer to use the
>> proposed CA-added 32 random bytes extension field.  One takeaway from the
>> Antonov attack was that SHA-256 often provides less security than presumed,
>> so it shouldn't be used with ML-DSA-87 keys.
>>
>> Best,
>> Casey
>>
>> ------------------------------
>> *From:* Bas Westerbaan <bas=[e-mail]>
>> *Sent:* Friday, March 27, 2026 1:32 PM
>> *To:* Scott Fluhrer (sfluhrer) <sfluhrer=[e-mail]>
>> *Cc:* Bas Westerbaan <bas=[e-mail]>;
>> [e-mail] <[e-mail]>
>> *Subject:* [Plants] Re: Higher forgery resistance almost for free?
>>
>>
>>
>> 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]
>>
>> _______________________________________________
>> Plants mailing list -- [e-mail]
>> To unsubscribe send an email to [e-mail]
>>
>