Subject: [Curdle] Quantum computer resistance? (Re: I-D Action: draft-ietf-curdle-gss-keyex-sha2-00.txt)

From: Hubert Kario <[email-masked]>
Date: Tue, 02 May 2017 15:54:21 +0200

On Saturday, 29 April 2017 15:28:43 CEST [email-masked] wrote:
> A New Internet-Draft is available from the on-line Internet-Drafts
> directories. This draft is a work item of the CURves, Deprecating and a
> Little more Encryption of the IETF.
> 
>         Title           : GSS-API Key Exchange with SHA2
>         Authors         : Simo Sorce
>                           Hubert Kario
> 	Filename        : draft-ietf-curdle-gss-keyex-sha2-00.txt
> 	Pages           : 16
> 	Date            : 2017-04-28
> 
> Abstract:
>    This document specifies additions and amendments to SSH GSS-API
>    Methods [RFC4462].  It defines a new key exchange method that uses
>    SHA-2 for integrity and deprecates weak DH groups.  The purpose of
>    this specification is to modernize the cryptographic primitives used
>    by GSS Key Exchanges.
> 
> 
> The IETF datatracker status page for this draft is:
> https://datatracker.ietf.org/doc/draft-ietf-curdle-gss-keyex-sha2/
> 
> There are also htmlized versions available at:
> https://tools.ietf.org/html/draft-ietf-curdle-gss-keyex-sha2-00
> https://datatracker.ietf.org/doc/html/draft-ietf-curdle-gss-keyex-sha2-00

One of the nice properties of Kerberos, because it uses only symmetric 
cryptography, is that it is secure against quantum computer attacks.

Unfortunately, neither the previous gss-api kex scheme, nor the one we 
proposed here (as it is essentially the same), maintain that property.
This is because the input to the HASH function, with one exception, are 
transferred in clear. That only secret input is the value calculated using 
algorithm vulnerable to quantum computers - FF or EC version of Diffie-Hellman

Thus my question are, 
1). should we change the input provided to HASH to provide quantum computer 
resistance, or
2). should we prioritise ease of upgrade to SHA-2, ECDH, bigger primes (and 
forget about QC-resistance - that's the current draft), or
3). should we multiply the kex options further and provide QC-resistant 
variants of all the GSSAPI kex algorithms?

As for technical details, I was thinking of adding a step in which the peers 
each choose a random value, GSS_Wrap it, send it to peer, GSS_Unwrap peers 
value and append their value and the peers decrypted value to HASH input.
-- 
Regards,
Hubert Kario
Senior Quality Engineer, QE BaseOS Security team
Web: www.cz.redhat.com
Red Hat Czech s.r.o., Purkyňova 99/71, 612 45, Brno, Czech Republic

---

From: Benjamin Kaduk <[email-masked]>
Date: Sun, 21 May 2017 15:13:50 -0500

> cryptography, is that it is secure against quantum computer attacks.

[obligatory note that the GSS-API is generic, i.e., there are
non-Kerberos GSS mechanisms, some of which are even used with ssh
today.  AIUI, the GSI mech does not use symmetric crypto and could
not reasonably become quantum-computer-resistant.]

> 1). should we change the input provided to HASH to provide quantum computer 

We should probably provide a scheme that has some additional input(s) to
HASH, perhaps with a GSS_Pseudo_random() (RFC 4401) or a
GSS_Wrap()'d random value.

> forget about QC-resistance - that's the current draft), or

But, I'm not convinced that we want to make "gss-<group>-<hash>"
have different global semantics based on the particular group+hash
combination; 

> variants of all the GSSAPI kex algorithms?

it seems like it would make more sense to have a separate document
that creates a new family of gss-pq-<group>-<hash> keyex schemes,
though probably only of the new ones from this document and not the
SHA1 ones.

> value and append their value and the peers decrypted value to HASH input.

That probably suffices; I would have to think a bit harder about
where there is any value gained from using such wrapped random
values as input to GSS_Pseudo_random(), or whether just passing the
HASH inputs as the prf_in input would suffice (which would mean less
data going on the wire).

-Ben

---

From: Hubert Kario <[email-masked]>
Date: Mon, 22 May 2017 15:27:47 +0200

> not reasonably become quantum-computer-resistant.]

Yes, the change is necessary, but not sufficient, for QC resistance.

> GSS_Wrap()'d random value.

GSS_Pseudo_random() could be a neat solution. But I have some reservations, 
see below.

> have different global semantics based on the particular group+hash

What I was thinking, is that -sha1 ones are becoming insecure either way. So 
lets make sure that the only ones that remain have the same properties (and 
they are a superset of the -sha1 ones).
 
> though probably only of the new ones from this document and not the

yes, using sha-1 for PQ is quite silly. For gss-pq-* key exchanges I was 
thinking of something that is truly PQ, that is, provides PFS even against 
quantum computers. That means something that uses Ring-LWE or supersingular 
isogeny DH, not something that uses FFDH or ECDH. Even if that FFDH or ECDH is 
slightly augmented to provide minimum of QC resistance.

In other words, the intention was to make the hopeless situation survivable 
and provide a proper fix only after a clear winner for PQ KEX has been 
established.

Creating 3 documents is probably overdoing it.
 
> > As for technical details, I was thinking of adding a step in which the
> > peers each choose a random value, GSS_Wrap it, send it to peer,
> > GSS_Unwrap peers value and append their value and the peers decrypted
> > value to HASH input.

Yes, not requiring changes to the on-the-wire messages is a definite plus.
OTOH, I'd assume that all GSS-API implementations support GSS_Wrap() and 
GSS_Unwrap(), I don't know what's the support level for GSS_Pseudo_random().
Given the notes in RFC 7802, I see there were some problems with 
interoperability in Kerberos...
-- 
Regards,
Hubert Kario
Senior Quality Engineer, QE BaseOS Security team
Web: www.cz.redhat.com
Red Hat Czech s.r.o., Purkyňova 99/71, 612 45, Brno, Czech Republic

---

From: Benjamin Kaduk <[email-masked]>
Date: Mon, 22 May 2017 21:08:30 -0500

> they are a superset of the -sha1 ones).

Ah, I see the point better now.

> Creating 3 documents is probably overdoing it.

But yes, 3 documents is probably overdoing it, and there is
something of a desire to get a sha1 alternative out quickly so it
can be implemented and those implementations have a chance to
trickle out into deployment.  So maybe we will just hold off until
there is a winner for PQ KEX.

> interoperability in Kerberos...

Yeah, it is not as widely implemented/adopted as the original GSS
APIs.  But there is software out there actually using it, commercial
software even, so there has been some progress on that front.  The
two big open-source C Kerberos implementations have had it for a few
years (MIT and Heimdal), but I don't have a sense for whether (e.g.)
Java or the various closed-source GSSAPI implementations have picked
it up.

-Ben

---

From: Hubert Kario <[email-masked]>
Date: Tue, 23 May 2017 12:20:09 +0200

On Tuesday, 23 May 2017 04:08:30 CEST Benjamin Kaduk wrote:
> > isogeny DH, not something that uses FFDH or ECDH. Even if that FFDH or
> > ECDH is slightly augmented to provide minimum of QC resistance.
> > 

Ease of upgrade to SHA-2 was the primary reason we decided to propose the 
simple version of the draft.

> > GSS_Unwrap(), I don't know what's the support level for
> > GSS_Pseudo_random(). Given the notes in RFC 7802, I see there were some
> > problems with

At least one Java library claims that it supports it https://github.com/
cconlon/kerberos-java-gssapi and given it's a MIT wrapper, it should have no 
problems interoperating.

I couldn't find anything for the MS implementation...

Anyway, the PQ stuff will require new crypto implementations, so we probably 
should be OK with requiring the GSS_Pseudo_random() to go along with it.