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

[John Gray <[e-mail]>]

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]<mailto:[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]<mailto:[e-mail]>> On Behalf Of Stephen Farrell
Sent: Friday, June 23, 2023 8:37 AM
To: Yoav Nir <[e-mail]<mailto:[e-mail]>>
Cc: Mike Ounsworth <Mike.Ounsworth=[e-mail]<mailto:[e-mail]>>; Michael Richardson <[e-mail]<mailto:[e-mail]>>; David Woodhouse <[e-mail]<mailto:[e-mail]>>; Rifaat Shekh-Yusef <[e-mail]<mailto:[e-mail]>>; secdispatch <[e-mail]<mailto:[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]<mailto:[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]<mailto:[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$>