Re: [TLS] Options for negotiating hybrid key exchanges for postquantum

["Scott Fluhrer (sfluhrer)" <[e-mail]>]

From: Watson Ladd <[e-mail]> 

> On Tue, Jul 30, 2019, 8:21 AM Scott Fluhrer (sfluhrer) <mailto:[e-mail]> wrote:
>> During the physical meeting in Montreal, we had a discussion about postquantum security, and in particular, on how one might want to negotiate several different ‘groups’ simultaneously (because there might not be one group that is entirely trusted, and I put ‘groups’ in scarequotes because postquantum key exchanges are typically not formed from a Diffie-Hellman group).
>> 
>> At the meeting, there were two options presented:
 >> 
>> Option 1: as the supported group, we insert a ‘hybrid marker’ (and include an extension that map lists which combination the hybrid marker stands for)
>>                For example, the client might list in his supported groups hybrid_marker_0 and hybrid_marker_1, and there would be a separate extension that lists hybrid_marker_0 = X25519 + SIKEp434 and hybrid_marker_1 = X25519 + NTRUPR653.  The server would then look up the meanings of hybrid_marker_0 and 1 in the extension, and then compare that against his security policy.
>>        In this option, we would ask IANA to allocate code points for the various individual postquantum key exchanges (in this example, SIKEp434 and NTRUPR653), as well a range of code points for the various hybrid_markers.
 >>
>> Option 2: we have code points for all the various combinations that we may want to support; hence IANA might allocate a code point X25519_SIKEp434 and another code point for X25519_NTRUPR653.  With this option, the client would list X25519_SIKEp434 and X25519_NTRUPR653 in their supported groups.
>>                 In this option, we would ask IANA to allocate code points for all the various combinations that we want allow to be negotiated. 
>> 
>
> Are people actually going to use hybrid encryption post NIST? The actual deployments today  for experiment have all fit option 2 and hybrids are unlikely in the future. 

it sounds like you are questioning, not between option 1 or option 2, but instead whether we need either of them at all.  Those are both methods of negotiating multiple keygroups; it appears that you don’t see any need for such an option.

Perhaps we need to have such a debate.  Here is one opinion (mine, but I'm pretty sure it is shared by others): the various NIST candidates are based on hard problems that were only recently studied (e.g. supersingular isogenies, Quasicyclic codes), or have cryptanalytic methods that are quite difficult to fully assess (e.g. Lattices).  Even after NIST and CFRG have blessed one or more of them, it would seem reasonable to me that we wouldn't want to place all our security eggs in that one basket.  We currently place all our trust in DH or ECDH; however those have been studied for 30+ years - we are not there yet for most of the postquantum algorithms.

Hence, it seems reasonable to me that we give users the option of being able to rely on multiple methods.

>
> My objection to 1 is it gets very messy. Do we use only the hybrids we both support? What if I throw a bunch of expensive things together? No reason we need a hybrid scheme! 

Actually, I personally don't see the messiness; if the client wants to propose X25519 + NTRUPR653, he places hybrid_marker_1 in the supported groups list, and adds hybrid_marker_1 = X25519 + NTRUPR653 to his hybrid group extension.  If the server sees hybrid_marker_1 in the client's supported group list, he looks for the definition in the hybrid group extension, and processes the policy accordingly.  The logic in both direction would appear (at least to me) to be reasonably simple (and it doesn’t get more complex if we feel the need to negotiate three or more key exchanges).

As for the expense, that is for the user to judge.  If the user decides that he is willing to pay for a series of expensive key exchanges, that should be his decision to make.  Option 1 gives the user the ability to negotiate a series of expensive (but perhaps more trusted) algorithms, it doesn't mandate that the user do so.

And, as for a need for a hybrid scheme (either option 1, option 2 or something else), I do believe that there will be a demand for it, even after NIST and CFRG has given their blessing, as their will be users who will not fully trust a new scheme that was just endorsed (but they do want some protection against future quantum computers).