[TLS] Re: [EXT] Re: [EXTERNAL] Re: Working Group Last Call for Post-quantum Hybrid ECDHE-MLKEM Key Agreement for TLSv1.3

["Bellebaum, Thomas" <[e-mail]>]

> Crypto is not the “one and only memory bug” – true. But we do not hold off from removing bugs on the grounds that there likely remain other bugs still un-remedied.

True. But we are not dealing with actual bugs - we are dealing with statistical bugs. As in "I expect an average of (say) 0.05 memory bugs per implementation of this particular feature" after accounting for implementations in memory safe languages, code reviews, etc. These will incur a loss in security insofar as they make the difference between a successful (or worse) attack and an unsuccessful attempt. I can not imagine the particular case of memory bugs making much of a difference in any risk-vs-cost threat analysis, especially because choosing an all-in PQ option also has statistical costs (see below).

> > When it comes to other kinds of attacks, a properly designed hybrid can actually be *safer* because instead of doubling the amount of wall you have to guard for your castle, you are building a second wall *behind* an existing one.
> 
> You need to maintain not one but two “walls” and worry about “interlacing/interfacing” between them.

The interface in this case is very simple. As part of the key schedule there is a hashing step combining the secrets. Any bug here is usually very easy to spot with a simple test against openssl s_client/s_server or whatever tests you have prepared to do a handshake. Then there is serialization and deserialization of the public key or ciphertext. All of these are fixed size for a given parameter set, which is good. All of the above represents the simplest way of implementing the hybrid functionality, so I do not expect much variety in implementation strategies. Maintenance of this interface should be very simple, and the expected costs from security-critical bugs here should be very low.

> When you know that one of those walls is dead (well, not quite yet – but “terminally ill with no hope for recovery”), and all your future safety depends on the other wall.

But we do not know that one wall is dead. Again, statistics. We expect with high probability that the EC-Wall is going to just topple over in a few years. We expect with some non-zero probability that the PQ-Wall has not been built right and never was that strong. Building up both walls will maximize the expected amount of time we can spend happily living inside the walls before the evil king gets to us.

> > On a more technical level, the primary use of a KEM in TLS is to derive a secret key, and as long as the PQ-KEM spits out anything at all during normal program flow, whatever output this is could be treated as part of the nonce, as far as security goes. So the additional attack surface is basically nonexistent.
> 
> Additional attack surface is not in the crypto theory, but in the implementation, particularly in the integrating the two “walls”.

See above. It would probably be helpful if you could describe a few bugs you consider likely. In case this LC does not pass immediately, it would be good to incorporate guidance against them.

> > This is now for any use case not requiring confidentiality for more than a few years.
> 
> Why would the users of that use case even bother with paying the cost of exchanged messages size increasing the by the orders of magnitude? For apparently zero benefit (as we don’t expect CRQC within the next few years)?

They would not, for the same reason that PQ signatures are not as time-critical right now (at least for TLS).

But consider the less obvious examples I mentioned, which distinguish not only between attacked and not attacked, but also consider the cost arising from a successful attack:
An ad-company would be more interested in my current situation and interests than in my situation five years ago, even though my interests from five years ago are correlated with my interests nowadays. Similarly, a dictator could execute anyone speaking against him right now, but would at least be interested to know who spoke against him before he came into power.
In such situations, you want to maximize the expected amount of time until your castle is breached, and a hybrid will do just that. Yes, any EC-Wall will likely fall in five years, but the damage will only occur if the other walls also fell (hence the PQ-Wall), and will be less than if the last wall fell tomorrow (hence the EC-Wall).

> > **and** PQ algorithms falls to a classic attack (like SIKE).
> 
> 
> 
> 
> Google KyberSlash, which is a classic attack.
> 
> That's how realistic this is.
> 
> That’s not an algorithmic attack – it’s an attack against implementations that have not plugged their timing side-channel. Such attacks exist against many (all?) Classic and PQ algorithms, they can be realistic, depending on your use case, and there are known defenses against them.

Above you wrote that "Additional attack surface is not in the crypto theory, but in the implementation". Hence the algorithm by itself is irrelevant (That will not stop me from praising said algorithm while an evil king hangs me, though). Again, statistics. There are differences in how often timing side channels occur in X25519 vs. DH on P256. Extrapolating from KyberSlash, we seem to have much less experience in designing PQ-algorithms which - implemented - do not suffer from such attacks. If it were possible to implement ML-KEM (or any other KEM) in a black-box-hand-it-to-a-mathematician-and-it-will-just-work way, I would implement it that way.

> > "Harvest now, decrypt later" plays no role in deciding between a hybrid and an all-in option.
> 
> It does, because in the end, only the PQ part determines whether your harvested-now data will remain safe or not.

...which is present in both aproaches.

-- TBB

===== IETF Stuff =====

This document may not be modified, and derivative works of it may not be  
created, except to format it for publication as an RFC or to translate it into  
languages other than English.