Subject: [IPsec] PSK mode

From: "Dan Harkins" <[email-masked]>
Date: Tue, 18 Aug 2015 17:04:07 -0700 (PDT)

https://www.nsa.gov/ia/programs/suiteb_cryptography/index.shtml

  "CSfC deployments involving an IKE/IPsec layer may use RFC
   2409-conformant implementations of the IKE standard (IKEv1)
   together with large, high-entropy, pre-shared keys and the
   AES-256 encryption algorithm.  RFC 2409 is the only version
   of the IKE standard that leverages symmetric pre-shared keys
   in a manner that may achieve quantum resistant confidentiality."

  :-)

  Dan.

---

From: Michael Richardson <[email-masked]>
Date: Wed, 19 Aug 2015 13:16:37 -0400

> in a manner that may achieve quantum resistant confidentiality."

So, all of IKEv2 is out, according to them?
Or they just didn't consider it yet?

--
Michael Richardson <[email-masked]>, Sandelman Software Works
 -= IPv6 IoT consulting =-

---

From: Mike Borza <[email-masked]>
Date: Wed, 19 Aug 2015 17:32:09 +0000

They don't mention IKEv2.  I don't know IKEv2 well enough to know whether there are any symmetric PSK authentication schemes, but if not, perhaps there should be.  The point they're making is that the ECC-based authentication methods become insecure when quantum computers of sufficient power become available, and in light of recent progress in the field the indications are that they will become available in a reasonably short timeframe. (And they should know that timeframe better than just about anybody else.)  I view this as an indication that they believe there may be viable QCs of that capability in the five to ten years timeframe.

Mike

-----Original Message-----
From: IPsec [mailto:[email-masked]] On Behalf Of Michael Richardson
Sent: Wednesday, August 19, 2015 13:17
To: Dan Harkins <[email-masked]>
Cc: IPsecME WG <[email-masked]>
Subject: Re: [IPsec] PSK mode

--
Michael Richardson <[email-masked]>, Sandelman Software Works  -= IPv6 IoT consulting =-

---

From: <[email-masked]>
Date: Wed, 19 Aug 2015 17:49:20 +0000

> On Aug 19, 2015, at 1:32 PM, Mike Borza <[email-masked]> wrote:
> 

Could you point to references that discuss real quantum computers?  I spent a while reading on this subject within the past year, and as far as I could tell, quantum computers are a very interesting theory but none yet exist in practice.

I looked for a description of thise “Suite B algorithms” but it wasn’t obvious.

Doesn’t PSK involve Diffie-Hellman key agreement?  I thought that Shor’s algorithm (or a generalization of it) addresses the discrete log problem.

	paul

---

From: Mike Borza <[email-masked]>
Date: Wed, 19 Aug 2015 19:19:24 +0000

No, I can't point to real quantum computers larger than a handful of qubits.  When I saw these (http://www.nature.com/ncomms/2015/150429/ncomms7979/full/ncomms7979.html and http://www.nature.com/nature/journal/v519/n7541/full/nature14270.html) earlier this year, it was the first indication to me that the emergence of real quantum computers of significant capability may be closer than I previously expected.  I was not expecting the fidelity problem to be resolved for some time to come yet, but this is a (the?) fundamental impediment to real QCs.  If it's resolved (and I don't know for certain that it will be by these methods) then progress may be relatively quick.  With that in mind, I inferred from the suite B update that NSA judges progress in the area of producing viable quantum computers of sufficient capability to be on the horizon too.  Going back to, and expanding on, the text of the announcement that Dan quoted in kicking this all off:

"For example, CSfC deployments involving an IKE/IPsec layer may use RFC 2409-conformant implementations of the IKE standard (IKEv1) together with large, high-entropy, pre-shared keys and the AES-256 encryption algorithm.  RFC 2409 is the only version of the IKE standard that leverages symmetric pre-shared keys in a manner that may achieve quantum resistant confidentiality. Additionally, MACsec key agreement as specified in IEEE 802.1X-2010, and the RFC 4279 TLS specification provide further options for implementing quantum resistant security measures today. These options also involve key agreement schemes that leverage large symmetric pre-shared keys.

With respect to IAD customers using large, unclassified PKI systems, remaining at 112 bits of security (i.e. 2048-bit RSA) may be preferable (or sometimes necessary due to budget constraints) for the near-term in anticipation of deploying quantum resistant asymmetric algorithms upon their first availability."

A key part of Shor's algorithm that benefits from a QC is essentially parallelized brute force attack on the inversion of the "hard" problem on which the cryptosystem is based, whether that's computing a discrete factorization, discrete logarithm or an elliptic curve discrete logarithm.  In that case the time to compute a solution is proportional to O(N/2) for N-bits keys, and inversely proportional to the number of qubits that can be brought to bear on the problem.  As "small" QCs will almost certainly be available before larger ones, systems based on smaller keys will fall to those attacks earlier than larger ones, and the difference will be sizeable.  So large RSA keys, or DH keys, will require much larger quantum computers to break than for ECC keys of 256 or 384 bits.  If the error correction capabilities don't continue to scale up easily, then larger keys of other crypto systems may remain secure significantly longer.

Like you, I looked for some direct statement that the capability would be available in a reasonable timeframe, but I wasn't surprised not to see it.

Mike

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] 
Sent: Wednesday, August 19, 2015 13:49
To: Mike Borza <[email-masked]>
Cc: [email-masked]; [email-masked]; [email-masked]
Subject: Re: [IPsec] PSK mode

	paul

---

From: Michael Richardson <[email-masked]>
Date: Wed, 19 Aug 2015 22:04:32 -0400

Mike Borza <[email-masked]> wrote:
    > They don't mention IKEv2.  I don't know IKEv2 well enough to know
    > whether there are any symmetric PSK authentication schemes, but if not,
    > perhaps there should be.  The point they're making is that the

There are PSK methods.
But, all the methods also use traditional DH, and IKEv2 defines ECDH methods
(AFAIK, haven't implemented yet).

I wonder if QC factoring of ECC easier than finding
SHA1/SHA2/etc. collisions, or if there is less effort being spent on the
secure hashes.

---

From: "Valery Smyslov" <[email-masked]>
Date: Thu, 20 Aug 2015 10:23:58 +0300

Hi,

IKEv2 has symmetrick PSK authentication method. However, it is different from IKEv1.
The difference is that in IKEv1 the session keys computation involves both preshared key
and DH shared secret

SKEYID = prf(pre-shared-key, Ni_b | Nr_b)
SKEYID_d = prf(SKEYID, g^xy | CKY-I | CKY-R | 0)
SKEYID_a = prf(SKEYID, SKEYID_d | g^xy | CKY-I | CKY-R | 1)
SKEYID_e = prf(SKEYID, SKEYID_a | g^xy | CKY-I | CKY-R | 2)

while in IKEv2 it involves only DH shared secret, so preshared key is used for
authentication only and is not used for session keys calculations

SKEYSEED = prf(Ni | Nr, g^ir)
{SK_d | SK_ai | SK_ar | SK_ei | SK_er | SK_pi | SK_pr} = prf+ (SKEYSEED, Ni | Nr | SPIi | SPIr)

This change was intentional, it was made by Hugo Krawczyk during work on IKEv2
due to complaints from the community that if IKEv1 PSK auth mode was used in IKEv2
then it would be impossible for responder to select proper preshared secret based on initiator's
identity (like in IKEv1 Main Mode). As far as I remember, when making this change Hugo mentioned,
that it would weaken security of the protocol.

Does NSA mean this difference when claiming that IKEv1 PSK mode is the only
QC-safe protocol? Should we add similar mode to IKEv2?

Regards,
Valery Smyslov.

> They don't mention IKEv2.  I don't know IKEv2 well enough to know whether there are
> any symmetric PSK authentication schemes, but if not, perhaps there should be.
> The point they're making is that the ECC-based authentication methods become insecure
> when quantum computers of sufficient power become available, and in light of recent progress
> in the field the indications are that they will become available in a reasonably short timeframe.
> (And they should know that timeframe better than just about anybody else.)
> I view this as an indication that they believe there may be viable QCs of that capability
> in the five to ten years timeframe.
>
> Mike
>
> _______________________________________________
> IPsec mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/ipsec

---

From: "Paul Hoffman" <[email-masked]>
Date: Thu, 20 Aug 2015 08:56:15 -0500

We should ask the NSA authors or their proxies before we do anything. 
Heck, maybe some NSA folks might even want to contribute to such an 
extension to IKEv2. We are in absolutely no rush, given how long it will 
be before serious researchers think there are practical quantum 
computers.

--Paul Hoffman

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Thu, 20 Aug 2015 14:26:37 +0000

> From: IPsec [mailto:[email-masked]] On Behalf Of Valery Smyslov
> Sent: Thursday, August 20, 2015 3:24 AM
> To: Mike Borza; Michael Richardson; Dan Harkins
> Cc: IPsecME WG
> The difference is that in IKEv1 the session keys computation involves both
> preshared key and DH shared secret
> 
> SKEYID = prf(pre-shared-key, Ni_b | Nr_b) SKEYID_d = prf(SKEYID, g^xy |
> CKY-I | CKY-R | 0) SKEYID_a = prf(SKEYID, SKEYID_d | g^xy | CKY-I | CKY-R |
> 1) SKEYID_e = prf(SKEYID, SKEYID_a | g^xy | CKY-I | CKY-R | 2)
> 
> This change was intentional, it was made by Hugo Krawczyk during work on
> IKEv2 due to complaints from the community that if IKEv1 PSK auth mode
> was used in IKEv2 then it would be impossible for responder to select proper
> preshared secret based on initiator's identity (like in IKEv1 Main Mode). As
> far as I remember, when making this change Hugo mentioned, that it would
> weaken security of the protocol.
> 
> Does NSA mean this difference when claiming that IKEv1 PSK mode is the
> only QC-safe protocol?

I believe so.

> Should we add similar mode to IKEv2?

I believe that there is an easier alternative; the problem is that IKEv2 is relying on the security of the (EC)DH exchange, and that is breakable with a Quantum Computer.  A cleaner approach would be to replace the DH exchange with something that does the same functionality, but in a Quantum Resistant manner.  NTRU (using an ephemeral key) can do precisely this (and performs quickly enough, and with small enough KE payloads not to cause fragmentation); we could negotiate NTRU as "yet another 'DH group'".  That way, we don't need to have this as a separate option to be negotiated. 

> perhaps there should be.
> > The point they're making is that the ECC-based authentication methods
> > become insecure when quantum computers of sufficient power become
> > available, and in light of recent progress in the field the indications are that
> they will become available in a reasonably short timeframe.
> > (And they should know that timeframe better than just about anybody
> > else.) I view this as an indication that they believe there may be
> > viable QCs of that capability in the five to ten years timeframe.
> >
> > Mike
> >

---

From: Andreas Steffen <[email-masked]>
Date: Thu, 20 Aug 2015 17:19:46 +0200

Hi Scott,

an NTRU Encryption-based IKEv2 key exchange is actually what the
strongSwan open source VPN software has been offering with the
ntru plugin for more than a year:

  https://wiki.strongswan.org/projects/strongswan/wiki/NTRU

For the four security strengths of 112, 128, 192 and 256 bits
strongSwan is using the private-use DH groups 1030..1033 in
conjunction with the strongSwan Vendor ID.

If you combine the NTRU key exchange with lattice-based BLISS
signatures in the AUTH payload

  https://wiki.strongswan.org/projects/strongswan/wiki/BLISS

than you arrive at a 100% Quantum Resistant IKEv2 protocol
without the use of any PSKs.

So the future has already arrived ;-)

Best regards

Andreas

On 08/20/2015 04:26 PM, Scott Fluhrer (sfluhrer) wrote:
> 
> 
> I believe that there is an easier alternative; the problem is that
> IKEv2 is relying on the security of the (EC)DH exchange, and that is
> breakable with a Quantum Computer.  A cleaner approach would be to
> replace the DH exchange with something that does the same
> functionality, but in a Quantum Resistant manner.  NTRU (using an
> ephemeral key) can do precisely this (and performs quickly enough,
> and with small enough KE payloads not to cause fragmentation); we
> could negotiate NTRU as "yet another 'DH group'".  That way, we don't
> need to have this as a separate option to be negotiated.

======================================================================
Andreas Steffen                         [email-masked]
strongSwan - the Open Source VPN Solution!          www.strongswan.org
Institute for Internet Technologies and Applications
University of Applied Sciences Rapperswil
CH-8640 Rapperswil (Switzerland)
===========================================================[ITA-HSR]==

---

From: <[email-masked]>
Date: Thu, 20 Aug 2015 15:33:14 +0000

> On Aug 20, 2015, at 10:26 AM, Scott Fluhrer (sfluhrer) <[email-masked]> wrote:
> 
>> ...

Has the NTRU based exchange had enough validation by skilled cryptographers to be considered worth using in production?

Also, has it been shown not to be vulnerable to a generalization of Shor's algorithm, the way D-H is?  It would be rather silly to introduce a new mechanism, only to have someone come along and tell us that Shor's algorithm breaks it, too.

	paul

---

From: Mike Borza <[email-masked]>
Date: Thu, 20 Aug 2015 17:50:38 +0000

If I understand your point correctly, QC doesn't improve the rate at which hash collisions may be found, at least not by any currently known (to me) algorithm.  In the case of the asymmetric algorithms, Shor's algorithm and close variants make an attack on the keyspace more practical.  (When sufficiently capable QCs are practical). There are published results that support those statements.  For similar reasons, symmetric cryptography loses strength to N/2 bits for N bits keys.  So e.g. AES-256 will have 128 bits of security in a post-QC world.

Mike

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of Michael Richardson
Sent: Wednesday, August 19, 2015 22:05
To: Mike Borza <[email-masked]>
Cc: Dan Harkins <[email-masked]>; IPsecME WG <[email-masked]>
Subject: Re: [IPsec] PSK mode

    > perhaps there should be.  The point they're making is that the

There are PSK methods.
But, all the methods also use traditional DH, and IKEv2 defines ECDH methods (AFAIK, haven't implemented yet).

I wonder if QC factoring of ECC easier than finding SHA1/SHA2/etc. collisions, or if there is less effort being spent on the secure hashes.

---

From: Michael Richardson <[email-masked]>
Date: Sun, 23 Aug 2015 20:13:49 -0400

> conjunction with the strongSwan Vendor ID.

Cool... an ID explanining things would be a really good thing to have.

    > without the use of any PSKs.

I don't know if the WG wants to add this to it's charter, but it sure
would be nice to have a spec...

---

From: Tero Kivinen <[email-masked]>
Date: Mon, 24 Aug 2015 17:19:44 +0300

Valery Smyslov writes:
> This change was intentional, it was made by Hugo Krawczyk during
> work on IKEv2 due to complaints from the community that if IKEv1 PSK
> auth mode was used in IKEv2 then it would be impossible for
> responder to select proper preshared secret based on initiator's
> identity (like in IKEv1 Main Mode). As far as I remember, when
> making this change Hugo mentioned, that it would weaken security of
> the protocol.

Yes, the problem was that PSK was needed to decrypt the IKE packet to
be able to see the ID, so ID was useless for selecting PSK. Because of
this people used aggressive mode in IKEv1, so PSK could be selected
based on the ID. Also if the PSK was wrong then the decryption simply
failed and that made it hard to know what went wrong. For the
responder he just needed to know which PSK to use based on the source
IP address, and that worked fine with fixed vpn links, but not with
mobile users. 

In IKEv2 we decided to use the PSK only for the authentication, and
not tie it up to the key generation. Most of the PSKs used in real
world are not cryptografilly strong enough to provide that much more
security for the SKEYSEED calculation. 

When we were talking about the draft-nagayama-ipsecme-ipsec-with-qkd
draft (now expired) we discussed that we should just add the QKDdata
SKEYSEED calculation.

(Hmm... it seems that my comments (attached) about the
draft-nagayama-ipsecme-ipsec-with-qkd draft never made to the list).

In that email I proposed changing the SKEYSEED calculation so ti would
include QKDdata:

   SKEYSEED = prf(Ni | Nr, g^ir | QKDdata)

On the other hand this would still bring exactly same problems we had
with IKEv1 related to what happens if QKDdata do not match. We would
not have the ID issue, as the QKDdata is selected based on the
different payload, i.e. QKD KeyID would select what QKDdata is used,
and that is sent in the IKE_SA_INIT which is not encrypted.

I also proposed to change the QKD draft to be more generic, i.e.
generic out of band one time shared key usage protocol, i.e. not
specifically tied to the QKD. I.e. we discussed about distributing
strong shared data using DVDs or similars, and just sending offsets
for the shared data to be used. 

Other option is to only augment the KEYMAT, i.e. the actual IPsec
traffic key materials used. I.e. change

   KEYMAT = prf+(SK_d, Ni | Nr)

to

   KEYMAT = prf+(SK_d, Ni | Nr | QKDdata)

I.e in that case attacker who can break DH would be able to see the
IKEv2 SA traffic, i.e. the IDs, key exchanges etc, but still would not
be able to decrypt the actual ESP traffic without getting the QKDdata
too.

The only secret thing in the IKE SA traffic is the IDs, but if we use
the QKDdata to generate encryption keys, then that QKD KeyID is a form
of ID, that most likely can already be used to derive the actual user
id (depends how that QKD KeyID is generated).

The IKE SA traffic needs to be protected for real time changes, but
there is not that big value for protecting them for long term
decryption. On the other hand ESP traffic is the one that really
benefits from long term decryption protection. 

> QC-safe protocol? Should we add similar mode to IKEv2?

I think we should continue pushing the
draft-nagayama-ipsecme-ipsec-with-qkd forward, and specify it as
generic method where out of band shared keys can be brought in to the
SKEYSEED or KEYMAT.
-- 
[email-masked]

---

From: Paul Wouters <[email-masked]>
Date: Mon, 24 Aug 2015 11:36:26 -0400 (EDT)

> generic method where out of band shared keys can be brought in to the

+1

Paul

---

From: Yaron Sheffer <[email-masked]>
Date: Mon, 24 Aug 2015 18:45:24 +0300

Even in a world where quantum computers are a risk that we need to 
consider in our crypto, QKD will still remain a niche.

So to go back to the original question, NTRU+BLISS are a possible 
solution if we care about this problem. QKD is not.

Thanks,
	Yaron

---

From: Michael Richardson <[email-masked]>
Date: Mon, 24 Aug 2015 15:02:37 -0400

> https://wiki.strongswan.org/projects/strongswan/wiki/NTRU

I read a bit about NTRU on wikipedia, of which I knew nothing before.

There are patents involved, I don't know which ones and I don't know when
they expire, but it seems like it isn't that new
an idea. Apparently they wrote some kind of exemption for open source.