Re: [Secdispatch] [EXTERNAL] Re: IETF117 - Call for topics

[Phillip Hallam-Baker <[e-mail]>]

PQC is the latest bright shiny object, that doesn't mean it is the most
important thing for IETF to work on.

There are two separate use cases that we need to consider, Authentication
and Non Repudiation.

Quantum cryptanalysis of the signature doesn't worry me in the slightest as
far as protocols like TLS go where all we need to do is authenticate the
server keys (and possibly the client). Quantum cryptanalysis of the payload
encryption is a bit of a bigger worry. But that is fairly easy to fix, all
we need to do is use Kyber for the forward secrecy key exchange.

Non Repudiation is a very different application area and one that I don't
see IETF really addressing right now, well not until we start with
KEYTRANS. If I care about non-repudiation for an application signature, I
almost certainly want to enroll the signature into a notary log and get it
fixed in time. And if the signature is notarized, I really don't much care
about using Dilithium or Ed448. The notary enrollment is sufficient.

So yes, I am interested in doing signatures right. But I am not seeing a
whole heap of added value in doing hybrid Ed448 plus PQC signatures. And
getting the notarized signatures is the priority for me.

In fact the one area where I am really interested in PQC signatures is the
one where I don't want hybrid at all because it is the 'how do I transition
my system in the unlikely event someone manages to make a QCRC.' That is
not a very high probability event in my view but it is nonzero and we have
to address it in critical infrastructure.




On Tue, Jun 27, 2023 at 3:57 PM Eric Rescorla <[e-mail]> wrote:

> Hi John,
>
> The point I am trying to make here is that the realities of software
> deployment require
> two credentials/keys.
>
> - A standard "classical" credential that is acceptable to existing endpoint
> - A post-quantum credential (that might be combined with a classical
> credential) that will only be acceptable to more modern endpoints
>
> For interactive protocols which can negotiate credentials, only the
> classical one is needed, and for performance reasons will generally be
> favored up until the point where we believe a sufficiently powerful quantum
> computer exists, at which point you will want to switch over to the
> post-quantum credential and distrust the classical credential. However, at
> this point, hybrid isn't doing anything for you, so you might as well just
> have a pure post-quantum credential.
>
> For non-interactive protocols, you don't know what the recipient supports,
> so you need to send either the classical credential or *both* because
> otherwise the RP may not be able to process the message. So, here again,
> hybrid isn't doing much for you.
>
> I think perhaps your argument here is that there is some risk that the
> pure PQ algorithm will be broken but the classical one will not, and so the
> hybrid mechanism provides better security than the PQ algorithm alone? I
> agree that this is true, but this is always to some extent to true for any
> algorithm and yet we don't usually double up like this, so what makes the
> PQ case different? Given that for the foreseeable future, anyone doing
> signing will need to have a classical credential, it seems like it will be
> fairly straightforward to distrust the PQ algorithm if we discover it is
> insecure.
>
> -Ekr
>
>
>
>
>
>
>
> On Mon, Jun 26, 2023 at 3:03 PM John Gray <[e-mail]> wrote:
>
>> Hi Eric,
>>
>>
>>
>> Thanks for your reply,
>>
>>
>>
>> >My argument here starts with the threat model: unlike confidentiality,
>> >what matters for security is the state of the algorithm at the time of
>> >signature verification rather than at the time of signature
>> >generation. In fact, it doesn't matter much what signature algorithms
>> >were initially used, but rather what the relying party will accept.
>>
>> I agree with this, it matters on the verifier side (whether interactive
>> or non-interactive).  A bad verifier could decide it doesn’t need to
>> validate anything, and that’s always a risk.  A good verifier must validate
>> the signature(s) correctly.
>>
>>
>>
>> >As a concrete example, suppose that Alice signs a document with
>> >classical algorithm C and quantum-resistant algorithm Q. If both
>> >algorithms are secure, then it doesn't matter which the RP accepts or
>> >verifies. So, the RP can simply adopt a policy of verifying whatever
>> >signatures are there from its accepted set.  However, if C is broken
>> >then it matters what the RP does. Specifically, if the RP accepts
>> >C-only signatures, then the Q signature doesn't help because the
>> >attacker can generate a new document just signed by C, either de novo
>> >or by stripping the Q signature. What is required for security is for
>> >the RP to reject C.
>>
>> I agree with you, that is why in a hybrid signature, I think the most
>> secure approach is what we often refer to as the “AND” mode, where both the
>> C and Q algorithms are required to be verified .  It is much simpler, and
>> removes all the complication you have described above.   That is why we
>> removed “OR” modes from our latest composite signature proposal (which has
>> not yet passed consensus for adoption).   If one of the algorithms is
>> broken, and the RP (verifier) must verify both, then you still retain the
>> desired security property.   That is exactly what we had proposed in the
>> latest composite hybrid signatures draft.  However, a bad “verifier” could
>> still be a bad verifier (either by malicious intent or by a implementation
>> bug).
>>
>>
>>
>> >There are, however, two reasons to sign with both C and Q:
>>
>> >1. If you don't know what the other side supports and you want
>>  >  the peer to able to verify it whatever its policies.
>> >2. If you are worried that *either* C or Q might be broken
>> >   in the future and you want the RP to be able to verify
>> >  in either case (this is roughly the rationale for using
>> >   both classical and PQ algorithms for key establishment).
>>
>> >However, neither of these rationales applies to interactive protocols
>> >like TLS, IPsec, etc. because they already negotiate the signature
>> >algorithm, so the RP can just tell the peer what signature algorithm
>> >to use (and by extension, which credential to send).
>>
>>
>>
>> The explicit composite signature we had envisioned is just a signature
>> algorithm.  It just happens to use existing algorithms like EC or any set
>> of the PQ algorithms as components that make up the algorithm.  The
>> verifier doesn’t get to choose which component to verify.   They should be
>> treated as a single atomic signature and key, not as a bunch of independent
>> signatures and keys.  The RP would decide if it supports the signature
>> algorithm just like it does for any other signature algorithms.    CQ
>> together is not the same a C + Q independently.  If C is broken, CQ still
>> verifiers and is still safe because of Q, if Q is broken CQ still verifies
>> and is safe because of C.  Only when CQ are both broken together is it a
>> problem, and we believe  the probability of that happening is less than an
>> independent algorithm C or Q.
>>
>>
>> >Moreover, because there are peers which only support the existing non-PQ
>> >algorithms and thus *neither* hybrid nor PQ-only signatures, you
>> >still need to be able to generate non-PQ signatures and to have a
>> >non-PQ credential, so it's equally (perhaps more) convenient to just
>> >have two credentials (assuming certificates here).
>>
>> Yes, I agree with this.  There will still be all the old systems out
>> there.  A hybrid signature format won’t solve all issues.   Have you taken
>> a look at this draft which proposes a new delta certificate extension?  It
>> would allow you to do what you propose above if you put a non-PQ
>> certificate in the extension and sent it to legacy clients when needed.
>> https://datatracker.ietf.org/doc/draft-bonnell-lamps-chameleon-certs/
>>
>>
>>
>> >Finally, let's consider the case of non-interactive protocols,
>> >where you don't necessarily know the state of the RP, so it's
>> >plausible you would want to sign with both C and Q regularly.
>> >However, the problem here is the same backward compatibility
>> >issue that you have with the interactive protocols, namely that
>> >there are some RPs which will only be able to verify C, so
>> >this means that you have to generate at least one pure classical
>> >signature, and if you want to add a PQ signature then you need
>> >some way to have two signatures, at which point why not just
>> >have the second one be pure PQ.
>>
>>
>> I agree, a hybrid signature is not backwards compatible.  A PQ signature
>> is not backwards compatible either.  If we aren’t sure we fully trust the
>> new PQ algorithm because of things like implementation bugs, or enough
>> algorithm scrutiny, or anything else that could go wrong with any singular
>> algorithm, combining them means both of them would have to be broken.
>> Combining them into a single signature is a convenience, not having to add
>> extra logic at the protocol level is attractive.   Most protocols or
>> non-interactive protocols are already designed to accept new algorithms
>> (support a new Algorithm Identifier and you are ready to go!).  The type of
>> hybrid signature we have envisioned is just a new type of signature
>> algorithm.   So yes, it is not backwards compatible, but it doesn’t need to
>> be designed to be backwards compatible.  Adding it into any existing
>> protocol is no more work than adding support for a new PQ signature
>> algorithm, and the overhead of doing this is small compared to the size of
>> PQ signature algorithms.  Better Security + little overhead = win/win
>> situation.
>>
>>
>>
>> >Can you explain why you think that hybrid is a better design in
>> >these cases?
>>
>>
>>
>> I am not saying it is a better design in all cases.  It can definitely
>> work in all cases (TLS or IP sec or anything that uses a signature
>> algorithm), but I don’t think any one solution will be the best design for
>> all use-cases.   It is just another tool in the toolbox of security
>> considerations.  Supporting multiple certificate chains will require
>> updates to every type of security protocol, which can definitely be done,
>> and maybe in some cases that is better.   Realized as a signature, a
>> composite/hybrid signature is a drop-in replacement once the new signature
>> algorithm is supported.
>>
>>
>>
>> Thanks for your response Eric, your input is greatly appreciated!
>>
>>
>>
>> John Gray
>>
>> Entrust
>>
>>
>>
>> *From:* Eric Rescorla <[e-mail]>
>> *Sent:* Sunday, June 25, 2023 7:48 PM
>> *To:* John Gray <[e-mail]>
>> *Cc:* secdispatch <[e-mail]>; Stephen Farrell <
>> [e-mail]>; Yoav Nir <[e-mail]>; Rifaat
>> Shekh-Yusef <[e-mail]>
>> *Subject:* Re: [Secdispatch] [EXTERNAL] Re: IETF117 - Call for topics
>>
>>
>>
>>
>>
>>
>>
>> On Sun, Jun 25, 2023 at 2:17 PM John Gray <John.Gray=
>> [e-mail]> wrote:
>>
>> This caught my eye:
>>
>> >> I think a BoF about hybrid signatures is appropriate as long as one of
>> >> the topics is “do we really need them?”
>>
>> >So one of the problems with that is it'd be about a specific mechanism
>> that may or may not
>> >form part of a sensible response to the possibility of a CRQC but it'd
>> omit consideration of the
>> >systemic impacts of adopting such signatures, esp. in PKI and in other
>> protocols that make use
>> >of PKI. We'd also be passing up the very rare opportunity to consider
>> significant changes to
>> >PKI that might actually get deployed, which I think would be fairly
>> unwise of us.
>>
>> I agree there is an opportunity to consider changes to PKI, but I don't
>> think it is time boxed by the Quantum threat.   I think there is always an
>> opportunity to consider significant changes to PKI.  I don't think it
>> should prevent us from enhancing existing PKI infrastructure until such
>> newer systems become feasible.
>>
>> It has been clear to many of us, (since at least 2017), that hybrid
>> signatures were going to be needed:
>>
>>
>>
>>  Hi John,
>>
>> >>I do agree we need post-quantum certificates, but I'm less persuaded
>> >>that *hybrid* signatures are the way to go, especially for online
>> >>protocols like TLS or IPsec.
>>
>> >My argument here starts with the threat model: unlike confidentiality,
>> >what matters for security is the state of the algorithm at the time of
>> >signature verification rather than at the time of signature
>> >generation. In fact, it doesn't matter much what signature algorithms
>> >were initially used, but rather what the relying party will accept.
>>
>> As a concrete example, suppose that Alice signs a document with
>> classical algorithm C and quantum-resistant algorithm Q. If both
>> algorithms are secure, then it doesn't matter which the RP accepts or
>> verifies. So, the RP can simply adopt a policy of verifying whatever
>> signatures are there from its accepted set.  However, if C is broken
>> then it matters what the RP does. Specifically, if the RP accepts
>> C-only signatures, then the Q signature doesn't help because the
>> attacker can generate a new document just signed by C, either de novo
>> or by stripping the Q signature. What is required for security is for
>> the RP to reject C.
>>
>> There are, however, two reasons to sign with both C and Q:
>>
>> 1. If you don't know what the other side supports and you want
>>    the peer to able to verify it whatever its policies.
>> 2. If you are worried that *either* C or Q might be broken
>>    in the future and you want the RP to be able to verify
>>    in either case (this is roughly the rationale for using
>>    both classical and PQ algorithms for key establishment).
>>
>> However, neither of these rationales applies to interactive protocols
>> like TLS, IPsec, etc. because they already negotiate the signature
>> algorithm, so the RP can just tell the peer what signature algorithm
>> to use (and by extension, which credential to send). Moreover,
>> because there are peers which only support the existing non-PQ
>> algorithms and thus *neither* hybrid nor PQ-only signatures, you
>> still need to be able to generate non-PQ signatures and to have a
>> non-PQ credential, so it's equally (perhaps more) convenient to just
>> have two credentials (assuming certificates here).
>>
>> - A classical key pair that chains up through classical signatures.
>> - A PQ key pair that chains up through PQ signatures
>>
>>
>> Finally, let's consider the case of non-interactive protocols,
>> where you don't necessarily know the state of the RP, so it's
>> plausible you would want to sign with both C and Q regularly.
>> However, the problem here is the same backward compatibility
>> issue that you have with the interactive protocols, namely that
>> there are some RPs which will only be able to verify C, so
>> this means that you have to generate at least one pure classical
>> signature, and if you want to add a PQ signature then you need
>> some way to have two signatures, at which point why not just
>> have the second one be pure PQ.
>>
>> Can you explain why you think that hybrid is a better design in
>> these cases?
>>
>> -Ekr
>>
>>
>>
>> 1)  We need to evolve our systems, I can't imagine telling customer x to
>> throw away their PKI infrastructure to use this new thing to ensure they
>> are protected from the quantum threat.   Do you think that is realistic?
>>  Maybe if we knew what the new thing looked like now and had 25 years for
>> people to transition to it.  So adding support for the NIST approved PQ
>> signature algorithms (when available) seems like a mandatory requirement
>> for future PKI systems, and is a natural way to enhance existing systems
>> against the quantum threat.
>> 2)  Given the uncertainty when a QRCQ will become available, and lack of
>> mature implementations of quantum resistant algorithms, it seems prudent to
>> add existing signature algorithms (RSA, EC) in combination with the newer,
>> larger PQ algorithm.   Adding EC only adds about 128 extra bytes which is a
>> small overhead and gives extra security and peace of mind in case problems
>> are found in the new PQ algorithm.  This can help to further enhance
>> existing PKI systems.
>> 3) In the call for adoption, we did have a lot of support for the work
>> and it looks like many organizations are planning to deploy hybrid
>> signatures of some kind.   We have proven this works in all the existing
>> PKI structures we have tested it with as part of our Hackathon which
>> currently has at least 6 different vendor supplied implementations of
>> composite "hybrid" signatures:
>> https://github.com/IETF-Hackathon/pqc-certificates
>> <https://urldefense.com/v3/__https:/github.com/IETF-Hackathon/pqc-certificates__;!!FJ-Y8qCqXTj2!YGHlBh04eZjm-2rrZrWe7wcxjtyEdYfR-17qin4Hu10cQGwS31BOZ_KLyWethwtBtkN3oFaLaA$>
>> We are simply trying to work out a common standard for what this looks
>> like.  Isn't that the point of the working group (LAMPS in this case has a
>> charter item 5.b.ii. for hybrid signatures).
>>
>> Cheers,
>>
>> John Gray
>>
>>
>> -----Original Message-----
>> From: Secdispatch <[e-mail]> On Behalf Of Stephen
>> Farrell
>> Sent: Friday, June 23, 2023 8:37 AM
>> To: Yoav Nir <[e-mail]>
>> Cc: Mike Ounsworth <Mike.Ounsworth=[e-mail]>;
>> Michael Richardson <[e-mail]>; David Woodhouse <
>> [e-mail]>; Rifaat Shekh-Yusef <[e-mail]>;
>> secdispatch <[e-mail]>
>> Subject: Re: [Secdispatch] [EXTERNAL] Re: IETF117 - Call for topics
>>
>>
>> Hiya,
>>
>> On 23/06/2023 10:29, Yoav Nir wrote:
>> >
>> >
>> >> On 22 Jun 2023, at 21:06, Stephen Farrell <[e-mail]>
>> >> wrote:
>> >> On 22/06/2023 19:01, Mike Ounsworth wrote:
>> >>> I also support a BoF about hybrid signatures.
>> >>
>> >> FWIW: I would not support the above. The BoF I think we need would
>> >> address evolving PKI in the face of a CRQC.
>> >>
>> >> Discussion of hybrid signatures would be a part of that, but just a
>> >> part.
>> >
>> > That’s not going to happen. If everything’s in scope then the BoF will
>> > discuss everything all at once, and take forever and not reach any
>> > conclusions.
>>
>> Of course, an ocean-boiling BoF is always possible, but I don't think one
>> on how to evolve PKI in the face of a possible CRQC is likely to be that.
>>
>> > I think a BoF about hybrid signatures is appropriate as long as one of
>> > the topics is “do we really need them?”
>>
>> So one of the problems with that is it'd be about a specific mechanism
>> that may or may not form part of a sensible response to the possibility of
>> a CRQC but it'd omit consideration of the systemic impacts of adopting such
>> signatures, esp. in PKI and in other protocols that make use of PKI. We'd
>> also be passing up the very rare opportunity to consider significant
>> changes to PKI that might actually get deployed, which I think would be
>> fairly unwise of us.
>>
>> Cheers,
>> S.
>>
>> >
>> > Yoav
>> >
>> >
>> >
>> >
>> Any email and files/attachments transmitted with it are confidential and
>> are intended solely for the use of the individual or entity to whom they
>> are addressed. If this message has been sent to you in error, you must not
>> copy, distribute or disclose of the information it contains. Please notify
>> Entrust immediately and delete the message from your system.
>> _______________________________________________
>> Secdispatch mailing list
>> [e-mail]
>> https://www.ietf.org/mailman/listinfo/secdispatch
>> <https://urldefense.com/v3/__https:/www.ietf.org/mailman/listinfo/secdispatch__;!!FJ-Y8qCqXTj2!YGHlBh04eZjm-2rrZrWe7wcxjtyEdYfR-17qin4Hu10cQGwS31BOZ_KLyWethwtBtkMLxezIZA$>
>>
>> _______________________________________________
> Secdispatch mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/secdispatch
>