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
