HI Scott, > Sorry if I ask such an obvious question, but would McEliece perform better > against packet loss if we introduce > a more intelligent ack/retry method? For each, the ack would list which > segments of the packet have been > received (e.g. bytes 0-3240 and bytes 6780-9800), so that on a retransmit, we > only need to resend the > segments that were dropped? And, of course, we'd resend the ack multiple > times, in case that is dropped.
In draft-tjhai-ikev2-beyond-64k-limit-01 we proposed so called mixed transport mode. With this mode IKE starts from UDP 4500, but switches to TCP immediately after IKE_SA_INIT and continues to use TCP for all subsequent exchanges. At the same time ESP is still sent directly over IP or over UDP. This mode allows to reliably transfer large public keys with no additional transport complexities, but at the same time avoids performance penalties of using TCP for ESP. The mode is negotiated, so backward compatibility is preserved. Since IKE starts from UDP 4500, it allows to check whether UDP path really works (so that we won't get black hole for ESP) and detect whether NAT is present on it. > Of course, the complexity of all this wouldn't be warranted in the original > envisioned use cases of IKE > fragmentation (where it was never expected that there would be that many > fragments) - given that the use > case has changed, would it make sense to revisit this? I think that mixed mode is the simplest solution for this case and the problem of transferring large public keys in lossy networks is not the main concern with this mode. Regards, Valery. > Hi Daniel, > > > To give more insight about these measurements, we implemented all three > > drafts and tested the > performance of a medium-sized McEliece key exchange under different > networking conditions (variable > latency, packet loss, and throughput). Especially when packet loss or > throughput surpass specific threshholds > (~ above 1% packet loss and below 3Mbit of throughput), the overall > performance suffers significantly. Yet, > we deem those values acceptable, as long as we don't use cellular or > similarly unreliable networks. > Furthermore, we expect a gateway communicating with many peers to have higher > requirements to its > network uplink. Yet, as this will most likely be positioned in a data center, > this challenge should also be doable. > Altogether, this left us with a surprisingly positive view on the possibility > of adopting McEliece-sized key > exchanges at least for some use-cases. > > > The introduction of new Transform-IDs like SNTRUP761X25519 is a good > > short-term solution, as it > addresses the problem without requiring much effort in terms of > standardization or implementation. > > Understood. I am curious to see the measurements published btw. Are the > public somewhere? > > A couple counter arguments: > > Cloudflare's tests > (https://blog.cloudflare.com/the-tls-post-quantum-experiment/ ) showed a > bunch of > variability for way more compact KEMs than McEliece (SIKE, NTRU-HRSS) at the > 95% and 99% percentile. > https://www.ndss-symposium.org/wp-content/uploads/2020/02/24203-paper.pdf > tested similar things, but > the tails (9x% percentiles) looked better because it was a controller wired > environment. Similarly, the > datacenter using jumbo frames would not sweat at all, but the issues arise at > >90% percentile and affect folks > in infrastructures that are not as developed as in the western world. Also > think about congestion control and > how that could impact infrastructures. These are important challenges that > McEliece would bring. > > Also think of the loss probability. https://eprint.iacr.org/2019/1447 talks > about it. If you are sending 2-3 > packets for a few KB public key or ciphertext then the total loss probability > is 1-(1-p)^3 where p is the link loss > probability. Let's say p=1%, that becomes ~3% which is not too bad. Now with > 64KB and assuming 1400B > packets, the probability becomes 1-(1-p)^45 which is ~36% with p=1%. 36% loss > would slow down handshakes > significantly, especially UDP-based ones. > > BSI may be endorsing the algorithm. It is indeed very mature and trusted. I > am sure many others would > endorse it too. But it is impractical to say we will standardize McEliece for > the environments that can afford it > and the rest will pick something else. Migrating algorithms is painful and > cumbersome as we have seen in hash > and other algorithm migrations. Integrating two new PQ KEMs depending on > usecase is not straightforward. > History has shown that new algorithms that make sense get deployed in TLS, > IKEv2, SSH etc. > > Imo McEliece is not viable for the internet, unless there were significant > redesigns and no other options. > > As a great cryptographer told me one time, if we are to use McEliece what is > the point of all this work taking > place to come up with better and more efficient PQ KEMs? > > Rgs, > Panos > > > > -----Original Message----- > From: Daniel Herzinger <daniel_herzin...@genua.de> > Sent: Tuesday, October 26, 2021 8:26 AM > To: CJ Tjhai <c...@post-quantum.com>; Kampanakis, Panos <kpa...@amazon.com> > Cc: Valery Smyslov <smyslov.i...@gmail.com>; ipsec@ietf.org; i...@gazdag.de > Subject: [EXTERNAL] [UNVERIFIED SENDER] AW: [IPsec] Cost-efficient > quantum-resistant DoS protection > > > Hi, > > the fact is that accepting a significantly increased amount of data from an > unauthenticated peer also > significantly increases the surface to DoS attacks. Even without surpassing > the 64KB limit, this must be a > concern. IKEv2's cookie mechanism and puzzles try to increase the cost of the > attacker per each connection. > Now, an attacker must still accept these costs but can use one connection to > trigger several key exchanges, all > significantly larger than what we had with DH, making the trade-off way > better for them compared to non-pqc > IKEv2. So, the attacker could, e.g., negotiate several FrodoKEMs (all with > different parameters to circumvent > the rule that all key exchange methods must be different). Compared to > classical non-hybrid (EC)DH, such a > DoS attack requires significantly less cost to have the same effect. > The introduction of MB-sized key exchanges just amplifies this problem even > further (also allowing several > McEliece KEMs with different parameters circumventing this constraint). Thus, > while we should already > thoroughly asses and mitigate the risk of this possible weakness for > https://datatracker.ietf.org/doc/draft- > ietf-ipsecme-ikev2-multiple-ke/, we definitely must do it for > https://datatracker.ietf.org/doc/draft-tjhai-ikev2- > beyond-64k-limit/. > Currently, there is no place defined where a McEliece-sized key exchange can > take place. So, at least one of > the two drafts (probably beyond-64k or multiple-ke) or better both should > make this clear. At the moment, > beyond-64k defines how the transmission of such key exchanges could look like > but the question of where > these ideas could be put into action are left to the reader, leading to > inevitable confusion. The fact that there > are several drafts aiming at the same problem, without really defining their > contact points or interactions, > further exacerbates this. > > The most obvious way to prevent an attacker from exploiting the new attack > surface is to accept the larger > key exchanges only from an already authenticated peer. As mentioned before, > we think childless IKEv2 with > immediate rekeying would be a good compromise to achieve that. > > > Imo, McEliece is not practical for live protocols like TLS or IKEv2. > McEliece is more trusted than its pqc alternatives which also makes it the > favored choice of some agencies like > the German BSI. Obviously, they all know the challenges of integrating such > large key exchanges, still they > would surely appreciate any effort which goes into this direction. This > justifies pursuing the idea further, > especially since first measurements look better than one would probably > expect. > To give more insight about these measurements, we implemented all three > drafts and tested the performance > of a medium-sized McEliece key exchange under different networking conditions > (variable latency, packet loss, > and throughput). Especially when packet loss or throughput surpass specific > threshholds (~ above 1% packet > loss and below 3Mbit of throughput), the overall performance suffers > significantly. Yet, we deem those values > acceptable, as long as we don't use cellular or similarly unreliable > networks. Furthermore, we expect a > gateway communicating with many peers to have higher requirements to its > network uplink. Yet, as this will > most likely be positioned in a data center, this challenge should also be > doable. Altogether, this left us with a > surprisingly positive view on the possibility of adopting McEliece-sized key > exchanges at least for some use- > cases. > > The introduction of new Transform-IDs like SNTRUP761X25519 is a good > short-term solution, as it addresses > the problem without requiring much effort in terms of standardization or > implementation. This becomes even > more important, as intermediate exchanges and their high complexity, due to > their interconnectedness with > authentication, mean that especially the IKEv2 implementations of smaller > projects will take their time for its > integration. Thus, having an easier short-term solution at hand means a real > advantage. > Also, the constrained size of such transforms mostly eliminates the > aforementioned DoS risks. > Finally, should the beyond-64k draft be adopted, then having a small set of > such additional Tranform-IDs is > even more beneficial since it makes preventing the unlikely yet possible > attack described in our initial mail > easier. > > > Regards, > Stefan and Daniel > ________________________________________ > Von: CJ Tjhai <c...@post-quantum.com> > Gesendet: Donnerstag, 21. Oktober 2021 18:39:16 > An: Kampanakis, Panos > Cc: Valery Smyslov; Daniel Herzinger; ipsec@ietf.org; i...@gazdag.de > Betreff: Re: [IPsec] Cost-efficient quantum-resistant DoS protection > > Hi Panos, > > There are two drafts involved here. > > a) the main draft, > https://datatracker.ietf.org/doc/draft-ietf-ipsecme-ikev2-multiple-ke/, > cannot support any > public-key larger than 64KB, so it can never be used for KEMs like McEliece. > So the option 3 is implied here. > > b) on the other hand, > https://datatracker.ietf.org/doc/draft-tjhai-ikev2-beyond-64k-limit/ is an > attempt to > address the issue with transferring payload larger than 64KB. As you pointed > out, transferring large blob of > data in a live protocol is challenging and therefore it deservers separate > treatments and considerations. It was > deliberate that we split the hybrid key exchange drafts into two, the second > draft is there just in case there is > any interest in the working group on supporting the use KEMs like McEliece. > > Cheers, > CJ > > > > > On Thu, 21 Oct 2021 at 16:49, Kampanakis, Panos > <kpanos=40amazon....@dmarc.ietf.org<mailto:40amazon....@dmarc.ietf.org>> > wrote: > Hi Valery, Tero, > > > Not really. First, the situation with seven McEliece is not possible, since > > all negotiated Key Exchange > methods MUST be different. > Then, you seem to assume that the responder blindly accepts all the key > exchanges at the initiator's will. > This is not true. First peers negotiate which key exchanges they will perform > (including additional key > exchanges), and you can limit the types and the number additional key > exchanges the responder will accept > via its local policy. > > I think the point is valid though if the responder supports McEliece. A > miscreant can that way make the > responder put a lot of data on the wire like an amplification attack although > the initiator has not been > validated. QUIC has a 3x amplification protection limits for that matter. > > Sure, the issue existed even in ECDH exchanges, but the impact is much higher > when we talk MB of public > keys. > > Imo, McEliece is not practical for live protocols like TLS or IKEv2. Too many > packets mean pretty high loss > probability in unstable networks which means pretty bad performance unless > everything happens in the > datacenter or robust end-to-end network paths. The PQ KEMs that will end up > being standardized are likely to > have just a few KBs of public key and ciphertext which is better for the > general case. > > So, I would say option 3 (prohibit the use of very large KE payloads like > McEliece's MB sized public keys) is > more practical. > > Rgs, > Panos > > > > > > -----Original Message----- > From: IPsec <ipsec-boun...@ietf.org<mailto:ipsec-boun...@ietf.org>> On Behalf > Of Valery Smyslov > Sent: Tuesday, October 19, 2021 11:46 AM > To: 'Daniel Herzinger' > <daniel_herzin...@genua.de<mailto:daniel_herzin...@genua.de>>; > ipsec@ietf.org<mailto:ipsec@ietf.org> > Cc: i...@gazdag.de<mailto:i...@gazdag.de> > Subject: RE: [EXTERNAL] [IPsec] Cost-efficient quantum-resistant DoS > protection > > CAUTION: This email originated from outside of the organization. Do not click > links or open attachments > unless you can confirm the sender and know the content is safe. > > > > Hi Daniel and Stefan-Lukas, > > > Hi, > > > > in response to the new version of > > draft-ietf-ipsecme-ikev2-multiple-ke-04.txt, we wanted to emphasize > > the issue of DoS attacks during intermediate exchanges. The new > > version does address it by mentioning the option of simply avoiding > > intermediate exchanges altogether but still require additional key > > exchanges. Yet, this protects only against record-and-harvest attacks > > but not against an attacker with a strong quantum computer at the time > > of the handshake, regardless of quantum-resistant authentication > > (since they can break the initial shared secret and therefore > > recalculate the MAC which authenticates the followup exchanges, fully > > establishing a man-in-the-middle). We doubt that an attacker, even with a > > strong quantum computer, is > able to break a key exchange in such a short time period. Still, this > assumption is too theoretical to rely on. > This, together with the fact that Group-IKE is incompatible with key > exchanges during followup exchanges, > makes the option seem inferior to just sticking to intermediate exchanges > during the handshake. However, we > must also consider the draft-tjhai-ikev2-beyond-64k-limit-01.txt. > > An attacker who exploits the large key exchanges, e.g., by requesting > > seven additional maximum size McEliece key exchanges, can force a gateway > > to accept and process 1.4MB > of data per McEliece KEM. > > Not really. First, the situation with seven McEliece is not possible, since > all negotiated Key Exchange methods > MUST be different. > Then, you seem to assume that the responder blindly accepts all the key > exchanges at the initiator's will. > This is not true. First peers negotiate which key exchanges they will perform > (including additional key > exchanges), and you can limit the types and the number additional key > exchanges the responder will accept > via its local policy. > > > This leaves us at > > a situation where we must pick one of the following options: > > > > 1. Accept the highly increased risk of DoS attacks. > > 2. Prohibit the use of large KE payloads, hence the McEliece mechanism. > > 3. Prohibit the use of intermediate exchanges, leaving the IKE SA > > initially unprotected and being vulnerable to an attacker with a quantum > > computer during the handshake. > > > > To us, none of these options seems desirable. Thus, we propose another > > solution which sees one new transform type, e.g., SNTRUP761X25519, > > which then defines a combination of one classical algorithm (like > > I'm confused here - did you mean new transform type or new transform ID? > Transform types define a kind of algorithms (or other features, like ESN), > while transform IDs define a > particular algorithm of this type. > > Unless I'm missing something I presume you meant new transform ID which > defines a new key exchange > algorithm which is a combination of SNTRUP761 and X25519. > Correct me if I'm wrong. > > > ECDH based on curve25519) and one pqc algorithm which fits into > > IKE_SA_INIT without fragmentation (like sntruprime761). The two > > secrets get concatinated and then fed to a hash function. The > > resulting hash is used as the shared secret for further key > > derivation. This mechanism is low effort in terms of implementation > > and does not affect the state machine at all, but already offers a > > high level of protection against all attacks as long as there is no major > > break-through in cryptanalysis. > Furthermore, it is the accepted approach for most of the applications of > post-quantum key exchanges. For > higher long-term security, it can be combined with other, more conventional > algorithms which follow either in > intermediate or followup exchanges. > > I think that this combined key exchange algorithm can also be implemented > (with more flexibility) by doing > IKE_SA_INIT(X25519)+IKE_INTERMEDIATE(SNTRUP761). I don't think your approach > has real advantages in > terms of consuming responder's resources. The responder still needs to > perform both X25519 and > SNTRUP761 before it authenticates the initiator. > Yes, you save one round trip, but the amount of data sent on the wire and the > amount of CPU cycles are > roughly the same. I'd like also mention that while X25519 and SNTRUP761 > public keys are fit into a single > 1500 bytes IKE message, they leave relatively little space for SA payload, so > initiator may be limited in > expressing its proposals. > > > We then propose to restrict the use of large key exchanges to the > > context of option 3, which removes the risk of the described DoS > > attacks. Yet, to prevent the insecurities of plain option 3, we also > > propose to make it mandatory to combine > it with the new hybrid transform type, i.e., SNTRUP761X25519. > > Are you proposing to stick with these two particular algorithms? > I don't think it's a good idea, giving the algorithm agility requirements. > I think that the same result can be achieved with the current draft: > > IKE_SA_INIT(X25519 or whatever else) > IKE_INTERMEDIATE(SNTRUP761 or whatever else with small public key) > IKE_AUTH(Childless if you want) > CREATE_CHILD_SA+IKE_FOLLOWUP_KE(McEliece or whatever else with long public > key) > > This leaves much more flexibility in selecting particular algorithms. > > > The only downside of this approach is that G-IKE is then incompatible > > with the McEliece exchange. However, the fact that G-IKE exchanges > > sensitive information before authentication makes it impossible to be > > not vulnerable against the discussed DoS attack and, at the same time, > > support the McEliece algorithm. > Thus, we see that as a decision to be made in the G-IKE standardization > track, not in IKEv2. > > I agree that G-IKEv2 is very special, but I also agree with Tero's previous > message that protecting IKEv2 and > (G-IKEv2 too) against DoS attacks leaves in slightly different area. > We have some mechanisms for this (not perfect, but that is that). > > Regards, > Valery. > > > Regards, > > > > Stefan-Lukas Gazdag, Daniel Herzinger > > _______________________________________________ > IPsec mailing list > IPsec@ietf.org<mailto:IPsec@ietf.org> > https://www.ietf.org/mailman/listinfo/ipsec > > _______________________________________________ > IPsec mailing list > IPsec@ietf.org<mailto:IPsec@ietf.org> > https://www.ietf.org/mailman/listinfo/ipsec > > ________________________________ > PQ Solutions Limited (trading as 'Post-Quantum') is a private limited company > incorporated in England and > Wales with registered number 06808505. > > This email is meant only for the intended recipient. If you have received > this email in error, any review, use, > dissemination, distribution, or copying of this email is strictly prohibited. > Please notify us immediately of the > error by return email and please delete this message from your system. Thank > you in advance for your > cooperation. > > For more information about Post-Quantum, please visit > www.post-quantum.com<http://www.post- > quantum.com>. > > In the course of our business relationship, we may collect, store and > transfer information about you. Please > see our privacy notice at > www.post-quantum.com/privacy-notice<http://www.post-quantum.com/privacy- > notice> to learn about how we use this information. > > _______________________________________________ > IPsec mailing list > IPsec@ietf.org > https://www.ietf.org/mailman/listinfo/ipsec _______________________________________________ IPsec mailing list IPsec@ietf.org https://www.ietf.org/mailman/listinfo/ipsec
