Subject: Re: DH group exchange (Re: SSH key algorithm updates)

From: Jeffrey Hutzelman <[email-masked]>
Date: Fri, 06 Nov 2015 22:50:37 -0500

On Sat, 2015-11-07 at 03:33 +0000, denis bider wrote:

> It is a fairly substantial problem that most dynamically generated
> groups aren't usable with our FIPS module.

What's broken about the groups that don't work?

---

From: denis bider <[email-masked]>
Date: Sat, 7 Nov 2015 03:33:14 +0000

Some info on DH group exchange that one might find useful:

- Our SSH Server does not generate groups. It just gives the client group14, or else group1 if client’s max size is below group14.

- Our SSH Client cannot reliably digest broken groups generated by most implementations that actually generate groups on the fly.

The Client (and Server, but this is not a problem in the Server) uses a FIPS-compliant crypto provider (Crypto++ 5.3.0) which performs DH parameter validation that cannot be disabled. This validation fails on DH parameters with groups generated by most server implementations (including but not limited to OpenSSH). It is possible to connect, but with something like 50% chance of failure.

Since we cannot disable the DH parameter validation without compromising the FIPS module, the Client de-prioritizes DH-gex methods in favor of any other enabled key exchange method (by default ecdh, dh-group14).

So, yes. From our point of view:

>  I was thinking of the receiver of the group list,
> it has to be prepared to handle any group,
> and make an intelligent choice. My gut
> feeling is that there may be some subtleties there.

... there are indeed such "subtleties". :)

It is a fairly substantial problem that most dynamically generated groups aren't usable with our FIPS module.

----- Original Message -----
From: Niels "Möller" 
Sent: Friday, November 6, 2015 00:50
To: Jeffrey Hutzelman 
Cc: Mark D. Baushke ; denis bider ; [email-masked] ; [email-masked] ; [email-masked] 
Subject: Re: SSH key algorithm updates

Jeffrey Hutzelman <[email-masked]> writes:

> On Fri, 2015-11-06 at 06:16 +0100, Niels Möller wrote:

[about hmac-sha1]

> Your understanding matches mine.  However, it's still only a 160-bit
> hash, and eventually that just stops being strong enough.  I'd like to
> have something stronger implemented and reasonably widely deployed
> before then.

Reasonable. We need to specify a new REQUIRED algorithm. Demoting
HMAC-SHA1 to recommended lets implementations drop support in due time
without formally departing from the standard. It would kind-of make
sense to specify a flag day "algothithm X is REQUIRED until date Y,
after which is is only RECOMMENDED", but not worth the effort to
formalize.

> SSH's 3des-cbc is three-key EDE 3DES.  It has an effective key length of
> 112 bits, and so is weaker than AES128.

But the "effective key bits" attack is a time/memory-tradeoff which
requires a huge table, right? So in practice I'm not sure a brute force
attack on 3DES really can be expected to be 16 times faster than a brute
force attack on aes128.

> It's also a CBC mode and AFAIK has the same problems as all of SSH's
> other CBC-mode ciphers.

Right, reprecating CBC makes sense. What's the status of 3des-ctr mode?
Not at all as widely deployed as 3des-cbc, I imagine.

> Group exchange doesn't have to mean live, dynamic group generation.  It
> can work fine with a set of fixed groups, either manually configured or
> compiled in.  

Hmm. I was thinking of the receiver of the group list, it has to be
prepared to handle any group, and make an intelligent choice. My gut
feeling is that there may be some subtleties there. But maybe there's no
issue to trust the server and just choose the largest group you think
you can afford to compute with.

> I'd have to go back and look, but I think the sense of the
> group at the time was that there was no reason to define more variations
> with the group baked into the algorithm names.

I can see that argument. Perhaps we shouldn't get into that now, but I
could see scenarious where client might have a preference like

  1. Large Z_p group (preferred option)
  2. curve25519      (acceptable)
  3. Small Z_p group (not acceptable)

Then negotiation fails in the case that they agree on group exchange,
but the server offers only small Z_p groups. While with named groups,
they might have agreed to use curve25519.

Feel free to ignore this discussion if you find in untimely or
distracting. There's a spec for it and noone on the list have raised any
serious security concerns.

>> Is that related to the (now expireed, I think) draft I and Simon wrote
>> some time ago? I'm not following the cfrg work.
>
> I'm not sure.  It's only a month old, and does have Simon's name on it.

Hmm. It looks like like it's based on our earlier version. I think the python
reference implementation of ed25519 is the same. Nice.

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.

---

From: "Mark D. Baushke" <[email-masked]>
Date: Sat, 7 Nov 2015 11:32:49 -0800

> What's broken about the groups that don't work?

The root case is the selection of the generator g in RFC 4419 is not
sufficient to meet FIPS requirements.

Start here:

  http://dx.doi.org/10.6028/NIST.SP.800-56Ar2 

in section 5.6.2.3.1 "FFC Full Public-Key Validation Routine" you will
see the tests that must be run during DH negotiation. Given the public
value y sent from the client, validate 2 <= y <= p-2 and 1=y^q mod p. Of
course, if a generator g has been selected incorrectly, then the public
key y will not have the correct order and will therefore have the
incorrect subgroup. So, we really need to take a look at how g is to be
selected. This is specified in section 5.5.1.1 "FFC Domain Parameter
Generation" which in turn specified "FFC Domain parameters shall be
generated using a method specified in [FIPS 186]," and so we move to
the latest FIPS 186 here:

  http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf

Read section A.2 and note that a simple test for g is

  2 <= g <= (p-1)
  g^q = 1 mod p

The above two tests are mandatory in FIPS approved diffie-hellman.

For non-FIPS users, a g which is not a valid generator means that
the g^(ab) operation may be leaking one bit of the key (ab).

You may wish to read the thread here:

  https://lists.mindrot.org/pipermail/openssh-unix-dev/2015-June/034060.html

For our implementation of the /etc/moduli file, 

 * find prime candidates p and q where q=(p-1)/2 

 * (because we are not sure if all RFC 4419 implementations will
   accept a generator g which is not either g=2 or g=5),
   check g=2 and g=5 using the steps in
   A.2.2 "Assurance of the Validity of the Generator g"
   - if g=2 or g=5 meets the PARTIALLY VALID test,
     then use Elliptic Curve Primality Proving to validate that both p
     and q are provably prime rather than just probably prime.
     (The use of ECPP is not required, but does not hurt.)
     else throw away p and q and start over.

   If we were guaranteed that all RFC 4419 implementations were able to
   accept any small prime for g, then we could walk up the list of
   primes until we found one that meets the PARTIALLY VALID test.
   However, that might also be very slow for some embedded ssh
   processors to implement, so choosing a g=2 is a good idea in any
   case.

 * an alternative would be to populate the /etc/moduli file for RFC 4419
   with the MODP groups that are well constructed for generating
   q=(p-1)/2 So, adding RFC 3526 group15 (3072-bit MODP Group) and/or
   group16 (4096-bit MODP Group)... I do not see a good reason to add
   group17 (6144-bit MODP Group), but do it if you wish.

Because the SSH server is the one who provides the g and p values, if it
is using valid RFC 4419 moduli, the client will just work.

If the SSH server is NOT FIPS-compliant, then if the SSH client
implements the older test like A.2 where the provided g^x=1 (mod p) test
which was in older of testing the 'random' value of x as being one that
lets the g^(xy) = 1 (mod p) have a 50% of being wrong as the y^q mod p
operation will return either 1 or p-1 and all of the p-1 values are
wrong for FIPS.

I hope that you find this information useful.

----------%<----------%<----------%<----------%<----------%<----------
From: "Roginsky, Allen" <allen.roginsky at nist.gov>
Subject: RE: Question on SP 800-56A rev2

The reason the y^q=1 (mod p) tests exists is to verify that y is in the
required subgroup. In general, for any y mutually prime with p, it is
true that y^(p-1) = 1 mod p. (The Fermat's Little Theorem.) Of course,
when taking an arbitrary y into the power smaller than (p-1) the above
equality does not necessarily hold. Suppose, however, that y is a
generator of a cyclic subgroup that has q elements. This is subgroup of
a larger group that has (p-1) elements; (p-1) is a multiple of q). The
way y was selected was by taking an arbitrary number w into the power of
(p-1)/q mod p (to be sure that it is in the subgroup of order q) and
checking that the result is not 1 (mod p) (otherwise, it is in the right
subgroup but is a unit element there - not a useful case.) Now, to test
that y is in a subgroup of order q one has to check that y^q = 1 mod p.
This would indeed hold if, as designed, y=w^(p-1)/q) mod p and
therefore, y^q = [w^(p-1)/q]^q ] = w^(p-1) = 1 mod p. This is why this
test (y^q = 1 mod p) exists in FIPS 186-4. \

My guess is that the value of 5 in your vendor's example, does not
satisfy this test, so it is not a generator of a subgroup of order q.
This value 5 could not have then been generated using w^[(p-1)q] (mod p)
method.

I do not know why some other standards appear to impose the additional
requirements on g. To find a generator of the entire cyclic group of the
order of (p-1) one usually has to make many tries, so some specific
methods or restrictions may apply there, but any g not equal to 1 and
such that g = w^[(p-1)q] (mod p) is good to be a generator of the
smaller subgroup (size q), as far as I can tell.

Please do not hesitate to call me or let your vendor call if they have
any additional questions.

Regards,
Allen
----------%<----------%<----------%<----------%<----------%<----------

---

From: Peter Gutmann <[email-masked]>
Date: Sun, 8 Nov 2015 03:01:30 +0000

>sufficient to meet FIPS requirements.

Since RFC 4419 doesn't specify that q is included in the DH keying material,
how do you even verify that it meets FIPS requirements?  You can't actually
perform the FIPS tests on it because one of the parameters is missing.  At
best you can do a test on... well, I'll post my source code comment:

/* There is a further check that we can perform on p, but it's rather
   problematic because it only works for "safe" primes (primes of the form p =
   2p' + 1), and even then the checks depend on your religious inclinations,
   you've got the choice of either choosing a value where the generated DH
   secret is limited to half the possible values, or one where you leak a bit
   of the secret exponent.  For example for g=2, if p is congruent to 11 mod
   24 then g is a quadratic nonresidue and the DH secret covers all possible
   values but you leak the LSB of the secret exponent, but if p is congruent
   to 11 mod 23 then g is a quadratic residue and the DH secret only covers
   half the possible values, but you don't leak any bits of the exponent (for
   OpenSSH's g=5, the values are 3 and 7).

   Once you go to more general values of g, or FIPS 186 primes which should be
   easily verifiable but aren't because the PKCS #3 form discards the q value
   that you need for the verification, there isn't really any checking that
   can be done.  The result is an ugly yes-biased test that can say
   "definitely safe" but only "possibly unsafe" (unless we're willing to deal
   with lots of false positives).

   Because of this we only complain about problems in debug mode, if we
   enabled the rejection of unverifiable primes in release code we'd Get
   Letters... */
switch( BN_get_word( g ) )
	{
	case 2:
		/* Oakley primes, congruent to 11 mod 24 = leaks LSB, 
		   congruent to 23 mod 24 = only covers half the possible 
		   values */
		modWord = BN_mod_word( p, 24 );
		assert_nofuzz( modWord == 11 || modWord == 23 );
		break;

	case 5:
		/* Used by OpenSSH for no known reason */
		modWord = BN_mod_word( p, 10 );
		assert_nofuzz( modWord == 3 || modWord == 7 );
		break;

	default:
		assert_nofuzz( DEBUG_WARN );
	}

Oh, if anyone knows of any other commonly-used magic values I'm missing there,
let me know.

The real fix though would be to publish a quick update to '4419 specifying a
SSH_MSG_KEX_DH_GEX2_GROUP which includes the full set of DH parameters so that
the DH values could be fully verified.

Peter.

---

From: "Mark D. Baushke" <[email-masked]>
Date: Sat, 7 Nov 2015 20:34:04 -0800

Peter Gutmann <[email-masked]> writes:

> how do you even verify that it meets FIPS requirements? 
 
Perhaps I am misreading RFC 4419...

| 3.  Diffie-Hellman Group and Key Exchange
| 
|    The server keeps a list of safe primes and corresponding generators
|    that it can select from.  A prime p is safe if p = 2q + 1 and q is
|    prime.  New primes can be generated in the background.
| 
|    The generator g should be chosen such that the order of the generated
|    subgroup does not factor into small primes; that is, with p = 2q + 1,
|    the order has to be either q or p - 1.  If the order is p - 1, then
|    the exponents generate all possible public values, evenly distributed
|    throughout the range of the modulus p, without cycling through a
|    smaller subset.  Such a generator is called a "primitive root" (which
|    is trivial to find when p is "safe").
| ...
| 3.  C generates a random number x, where 1 < x < (p-1)/2.  It
|        computes e = g^x mod p, and sends "e" to S.

To me, the term '(p-1)/2' implies that we are calculating a value for
'q' ... in other words, I thought that q was a Sophie Germain prime and
an p was the safe prime.

Otherwise, I would have expected us to worry about 1 < x < (p-1)/r for
the case were p = qr + 1 ... and we have no way to make that calculation
without knowning either q or r in the first place.

> You can't actually perform the FIPS tests on it because one of the
> parameters is missing.

True, which also means that you would be unable to ensure that the
random number x is within the proper range for DH which wants 'p = rq +
1' and '1 < x < q' NOT '1 < x < rq' ... so, if the math in RFC 4419 is
using r=2, then we can calculae q as (p-1)/2 ...

> Oh, if anyone knows of any other commonly-used magic values I'm
> missing there, let me know.

I would also like this information.

> The real fix though would be to publish a quick update to '4419
> specifying a SSH_MSG_KEX_DH_GEX2_GROUP which includes the full set of
> DH parameters so that the DH values could be fully verified.

Sure. If you want to allow for things like group25 (RFC 5114), then
having all of the group parameters g,p,q would make it possible. I would
have no problems with that addition.

So far, we have FIPS certified our system with ssh a number of times
with RFC 4419 extensions being available, but assuming that q is derived
from (p-1)/2.

I still think that the update to RFC 4419 should deal with the selection
of the parameters and runtime validation checks per FIPS 186 and NIST SP
800-56A.

	Thanks,
	-- Mark

---

From: Peter Gutmann <[email-masked]>
Date: Sun, 8 Nov 2015 08:16:40 +0000

[email-masked] <[email-masked]> writes:

>To me, the term '(p-1)/2' implies that we are calculating a value for 'q' ...
>in other words, I thought that q was a Sophie Germain prime and an p was the
>safe prime.

Ah, yeah, it works if you're using safe primes and can assume that form.  I
use Lim-Lee primes (p = 2q * ( prime[1] * ... prime[n] ) + 1 rather than p =
2q + 1), for which an attempt to back-derive q from p will lead to funny
results.

>If you want to allow for things like group25 (RFC 5114), then having all of
>the group parameters g,p,q would make it possible. I would have no problems
>with that addition.

That would be a considerable help, particularly given the recent attacks on
PKCS #3 DH values in TLS (SSH uses the same form, but so far hasn't been found
vulnerable).

If no-one else has any objections, I'll work on a quick draft, all it'll do is
update '4419 to define a SSH_MSG_KEX_DH_GEX2_GROUP and a new identifier,
"diffie-hellman-group-exchange2-sha256" (I assume there's no demand for a
sha-1 version any more...).  The impact on an implemention should be no more
than a few lines of code changed, a new entry in an algorithm table for the ID
string and a call to read the extra q value.

Peter.

---

From: Peter Gutmann <[email-masked]>
Date: Sun, 8 Nov 2015 09:42:29 +0000

denis bider <[email-masked]> writes:

>If this new draft could specify group generation such that:
>
>- Windows built-in crypto (CNG) running under FIPS mode
>
>- and possibly, but not as critically, the Crypto++ 5.3.0 FIPS-certified module
>
>could reliably use parameters sent by servers that implement the new spec -
>that would be quite awesome.

I don't know if you need to specify the exact generation method, only the
verification checks to perform, which are given in FIPS 186.  The intent is to
create verifiable DH parameters, so the important thing is the verification
mechanism, not the generation one (both safe primes and Lim-Lee primes, for
example, will produce verifiable values).  It would certainly make sense, if
you're using { p, q, g } primes, to require that they be verified as per the
FIPS 186 checks, since that's the point to using them.

The annoying thing about this change is that it's going to take me about 20x
as long to do the spec describing it as it will to make the code changes,
sigh.

One other thing that'd be good to have, based on the Logjam paper, is to
specify some means of distinguishing g from q, since Logjam mentions that
there are implementations that confuse the two.  Does anyone have problems
with requiring that g = <small integer>?  This both makes the DH op much more
efficient, and makes it easy to quickly distinguish g from q without requiring
complex bignum ops.

Peter.

---

From: denis bider <[email-masked]>
Date: Sun, 8 Nov 2015 08:58:12 +0000

could reliably use parameters sent by servers that implement the new spec - that would be quite awesome.

I have not yet implemented DH using Windows CNG, so I can't verify if it has the same issues as Crypto++ has. However, I should get there in the next few weeks.

Peter.

---

From: "Mark D. Baushke" <[email-masked]>
Date: Sun, 8 Nov 2015 08:47:21 -0800

> I don't know if you need to specify the exact generation method, only
> the verification checks to perform, which are given in FIPS 186. 

Actually, it depends on the evaluation lab somewhat, but they typically
want evaluations to use generation and verification based on FIPS 186-4
appendix A.1 and show the code that is doing the generation if it is
inside of the crypto module.

Validation of existing DH FCC domain parameters is expected to use the
methods in section A.1.

Section A.1.1.2 outlines the method of generation of probable primes.
However, it limits the values of the number of bits of p and q based on
L and N values taken from section 4.2. Where the max is L=3072 and N=256
apparnetly resuing the same table as for DSA parameters.

I would hope generating a lot of 2048-bit and 3072-bit DH primes would
be sufficient for now.

A possible method to generate larger DH parameters is to generate primes
in any way you can and then validate them using one of the primality
proving algorithms in http://cr.yp.to/primetests.html ... of course as
it is not FIPS-approved, that would need to be done outside of the
crypto boundary. :-(

There seems to be little use of DH primes being much bigger than 4096
bits right now in any case. It becomes easier to move to ECDH for
performance.

> The intent is to create verifiable DH parameters, so the important
> thing is the verification mechanism, not the generation one (both safe
> primes and Lim-Lee primes, for example, will produce verifiable
> values). It would certainly make sense, if you're using { p, q, g }
> primes, to require that they be verified as per the FIPS 186 checks,
> since that's the point to using them.

Yes. That said, I do not find any FIPS or NIST documents talking about
Lim-Lee primes for use in FIPS certified systems.

> The annoying thing about this change is that it's going to take me
> about 20x as long to do the spec describing it as it will to make the
> code changes, sigh.

That always seems to be the way of things.

> One other thing that'd be good to have, based on the Logjam paper, is
> to specify some means of distinguishing g from q, since Logjam
> mentions that there are implementations that confuse the two. Does
> anyone have problems with requiring that g = <small integer>? This
> both makes the DH op much more efficient, and makes it easy to quickly
> distinguish g from q without requiring complex bignum ops.

Well, if you look at group25, you see that g is larger than q.

I know that at one time, a few of our govenmental customers were
twisting arms over implemnting group25 everywhere and were not happy
that it was not possible for SSH at that time.

I would therefore really like to see it possible to express all of the
MODP groups via this new extension if possible.

	Just my $0.02,
	-- Mark

---

From: Peter Gutmann <[email-masked]>
Date: Mon, 9 Nov 2015 00:46:54 +0000

[email-masked] <[email-masked]> writes:

>That said, I do not find any FIPS or NIST documents talking about Lim-Lee
>primes for use in FIPS certified systems.

Sure, because it post-dates the original NIST docs that specified the keygen.
The idea is that if you need FIPS validation you use the NIST generation
method, if you don't, you use any method that works, one obvious example being
Lim-Lee (same result but much quicker because you're generating lots of small
primes, particularly useful if you want to generate a new DH parameter set on
each handshake).

Since the verification process for both 186 and Lim-Lee generated values is
identical, you can verify the keys either way.  So the spec would cover both
NIST and non-NIST options at the same time, depending on implementer
preference.

Peter.

---

From: "Mark D. Baushke" <[email-masked]>
Date: Sun, 8 Nov 2015 21:28:01 -0800

Hi Peter,

Peter Gutmann <[email-masked]> writes:

> >That said, I do not find any FIPS or NIST documents talking about

I am under the impression that Lim-Lee published their paper in 1997 "A
key recovery attack on discrete log-based schemes using a prime order
subgroup"

  FIPS 186   was published in 1994.
  FIPS 186-1 was published in December 1998.
  FIPS 186-2 was published in January 2000.
  FIPS 186-3 was published in June 2009.
  FIPS 186-4 was published in July 2013. 

so, for the last four editions of FIPS 186, no mention of the Lim and
Lee algorithm has been mentioned... I would have thought they might
mention generation of q in subsequent publications, but I only really
ever had to deal with FIPS 186-2, FIPS 186-3 and FIPS 186-4 myself.

> The idea is that if you need FIPS validation you use the NIST
> generation method, if you don't, you use any method that works, one
> obvious example being Lim-Lee (same result but much quicker because
> you're generating lots of small primes, particularly useful if you
> want to generate a new DH parameter set on each handshake).

Yup, a FIPS compliant system needs to generate new FCC Domain Parameters
for Diffie-Hellman using the method described in FIPS 186-4. A non-FIPS
compliant system would be free to sue Lim-Lee if they desired.

It is possible to generate the values outside of the crypto boundary in
which case only validation needs to be performed, but that does not
really live up to the expectations of RFC 4419 which wants to be
generating new DH parameters for each connection, or at least be able to
randomly selection a set of parameters that have been calculated in the
short term rather than the long term.

> Since the verification process for both 186 and Lim-Lee generated
> values is identical, you can verify the keys either way. So the spec
> would cover both NIST and non-NIST options at the same time, depending
> on implementer preference.

So, the RFC 4419bis would include both parameter generation techniques
as well as coming up with a better generator g that would always pass
for a non-FIPS compliant application talking to a FIPS compliant
application? That seems reasonable to me.

	-- Mark

---

From: "Mark D. Baushke" <[email-masked]>
Date: Mon, 9 Nov 2015 14:24:36 -0800

Hi Niels,

Niels Möller <[email-masked]> writes:

> > would cover both NIST and non-NIST options at the same time,
> > depending on implementer preference.
> 
> I'm not following the fine details here, but does the verification
> step include proving the primality of p (and q)?

There are two validations in FIPS 186-4:
a) Section A.1.1 Generation and Validation of Probable Primes
b) Section A.2.2 Assurance of the Validity of the Generator g

A FIPS implementation of ephemeral Finite Field Cryptography is expected
to generate p,q,g parameters using FIPS 186-4 methods.

There are two validations in NIST SP 800-56A:
a) Section 5.6.1.1 FFC Key Pair Generation
b) Section 5.6.2.4 FFC Full Public Key Validation Routine

A FIPS implementation of Diffie-Hellman is expected to generate a Key
Pair and do parameter validation using NIST SP 800-56A methods.

Right now, an implementation of RFC 4419 may assume a Sophie Germain
prime q with safe prime p such that p = 2q + 1. RFC 4419 section 6.1
Selection of Generator will often lead to values which are outside of
the q-ordered subgroup. Obviously, systems not using the Sophie Germain
and safe primes assumption does not have a q value on which to perform
validation, so from a FIPS point of view the key exchange would fail.

Niels Möller <[email-masked]> writes:

> "Mark D. Baushke" <[email-masked]> writes:
> 
> I still think it is inappropriate to use group-exchange for groups
> that are going to be widely used. 

I suppose we disagree on this subject.

I believe it to be desirable to make published groups available to the
RFC 4419 extension mechanism when there may not have been time or
sufficient entropy to generate key pairs of the selected size for
ephemeral groups.

> Widely used groups should be subject to negotiation. 

I have no objection to this approach.

As has been noted by Peter, there are many different mechanisms for
generation of the primes to be used for ephemeral groups. It should be
possible to perform FIPS validation on those p,q,g parameters, but to do
that would require an extension to the possible messages to send q to
the client from the server.

As to your suggestion, I have no objection if we also want to add
negotiaion for some more fixed DH MODP groups.

It may also be desirable to setup a way that RFC 3526 groups:

  diffie-hellman-group14-sha256 (2048-bit MODP group - 112 bits of security)
  diffie-hellman-group15-sha256 (3072-bit MODP group - 128 bits of security)

  diffie-hellman-group16-sha384 (4096-bit MODP group - ~150 bits of security)

or

  diffie-hellman-group16-sha512 (4096-bit MODP group - ~150 bits of security)

could be used.

I do not really see a strong need for these:

  group17 (6144-bit MODP Group - ~170 bits of security)
  group18 (8192-bit MODP Group - ~190 bits of security)

at the present time.

> Group-exchange should be used only for ephemeral groups which each
> server discard before they get "widely used".

This is not a bad idea, but right now there exists only the ecdh-sha2-*
KEX which are FIPS compliant. Not all implementations of SSH seem to
want or are able to use ECDH. It is somewhat desirable to have a DH
mechanism that is able to use sha256 which leaves only
diffie-hellman-group-exchange-sha256 at present.

As has been noted, diffie-hellman-group-exchange-sha256 may be difficult
to use in a FIPS compliant manner as many implementations are not
selection a g that allows a FIPS compliant implementation to always
interoperate between client and server.

	Thanks,
	-- Mark

---

From: [email-masked] (Niels Möller)
Date: Mon, 09 Nov 2015 19:22:44 +0100

> NIST and non-NIST options at the same time, depending on implementer

I'm not following the fine details here, but does the verification step
include proving the primality of p (and q)? 

Regards,
/Niels

---

From: [email-masked] (Niels Möller)
Date: Mon, 09 Nov 2015 19:26:17 +0100

> MODP groups via this new extension if possible.

I still think it is inappropriate to use group-exchange for groups that
are going to be widely used. Widely used groups should be subject to
negotiation. Group-exchange should be used only for ephemeral groups
which each server discard before they get "widely used".

Regards,
/Niels

---

From: Peter Gutmann <[email-masked]>
Date: Tue, 10 Nov 2015 06:33:49 +0000

>include proving the primality of p (and q)?

No (that would make ops incredibly expensive), just things like verifying that
g is a generator of order q.

Peter.

---

From: [email-masked] (Niels Möller)
Date: Tue, 10 Nov 2015 05:35:16 +0100

> I suppose we disagree on this subject.

Maybe not a very wide disagreement. I have no strong objection to
including *reviewed* fixed groups in the list of group-exchange
alternatives (even if I think using names to enable negotiation is
desirable, adn that it's unfortunate that the client isn't informed
whether a particular group is fixed or ephemeral). I do object to using
fixed groups which have not been properly reviewed, e.g., generated at
compile time for a widely used server binary.

>   diffie-hellman-group16-sha384 (4096-bit MODP group - ~150 bits of security)

I think that is highly desirable. Implementation burden should be quite
small. One of these could be RECOMMENDED or even REQUIRED.

Regards,
/Niels

---

From: Damien Miller <[email-masked]>
Date: Tue, 10 Nov 2015 18:30:40 +1100 (AEDT)

> >   diffie-hellman-group16-sha384 (4096-bit MODP group - ~150 bits of security)

FWIW OpenSSH has been using RFC3526 group 16 as the fallback group for
group-exchange when it can't find a local pre-computed group list.

-d

---

From: "Mark D. Baushke" <[email-masked]>
Date: Tue, 10 Nov 2015 00:48:21 -0800

Hi Damien,

> group-exchange when it can't find a local pre-computed group list.

Yes, I am aware that OpenSSH will fall back on group16 with either sha1
or sha2-256 depending on what key exchange method is being used.

Given that OpenSSH is using group16 with sha2-256 preserves 128 bits of
security, should there be a group16 using either sha2-384 or sha2-512 so
that the maximum number of security bits is retained (security bits
estimate for RFC 3526 is in this table:

   +--------+----------+---------------------+---------------------+
   | Group  | Modulus  | Strength Estimate 1 | Strength Estimate 2 |
   |        |          +----------+----------+----------+----------+
   |        |          |          | exponent |          | exponent |
   |        |          | in bits  | size     | in bits  | size     |
   +--------+----------+----------+----------+----------+----------+
   |   5    | 1536-bit |       90 |     180- |      120 |     240- |
   |  14    | 2048-bit |      110 |     220- |      160 |     320- |
   |  15    | 3072-bit |      130 |     260- |      210 |     420- |
   |  16    | 4096-bit |      150 |     300- |      240 |     480- |
   |  17    | 6144-bit |      170 |     340- |      270 |     540- |
   |  18    | 8192-bit |      190 |     380- |      310 |     620- |
   +--------+----------+---------------------+---------------------+

so, group16 is nominally somewhere between 150-240 bits of security
sha2-384 preserves 192 bits of security and sha2-512 preserves 256 bits
of security.

For that matter, I wonder if we want to take the time to specify
"diffie-hellman-group-exchange-sha512" for the larger group sizes
while we have RFC4419bis in discussion?

	Curious,
	-- Mark

---

From: [email-masked] (Niels Möller)
Date: Tue, 10 Nov 2015 21:08:32 +0100

"Mark D. Baushke" <[email-masked]> writes:

> security,

How do you reason about that halving, from 256 to 128? For the key
expansion, I'd expect that you can count very close to 256 bits of
entropy in the generated keys (assuming the secret dh values were
generated randomly).

Now, you will start to get some repeated session keys, i.e., collisions,
after about 2^128 sessions. But that has little to do with the hash
function: if we had a crypto system which for each session generated a
256-bit session key from a truly random source, we'd also get collisions
after about 2^128 sessions. But I think the conventional way to assign a
security level to such a system is 2^256 (the difficuly of exhaustive
key search), not 2^128.

Am I missing something?

Regards,
/Niels

---

From: "Mark D. Baushke" <[email-masked]>
Date: Tue, 10 Nov 2015 23:18:43 -0800

Hi Niels,

Niels Möller <[email-masked]> writes:

> How do you reason about that halving, from 256 to 128? 

sha2-256 has 128 bits of security per NIST SP 800-107-rev1.

> For the key expansion, I'd expect that you can count very close to 256
> bits of entropy in the generated keys (assuming the secret dh values
> were generated randomly).

Attacks on the signature hash will only need to brute force about half
of the keyspace on average to recover the key.

> security level to such a system is 2^256 (the difficuly of exhaustive

I have always been told that one should choose a signature mechanism
which provides the same number of bits of security as the asymmetric or
symmetric encryption keys.

See also:

  http://csrc.nist.gov/publications/nistpubs/800-107-rev1/sp800-107-rev1.pdf
  Section 4.2 table 1.

Or look at the tables in these documents:

  http://www.keylength.com/en/4/
  https://wiki.mozilla.org/Security/Guidelines/Key_Management

I suppose I may have been over conservative in my numbers...

	-- Mark

---

From: [email-masked] (Niels Möller)
Date: Fri, 13 Nov 2015 09:32:22 +0100

>   http://csrc.nist.gov/publications/nistpubs/800-107-rev1/sp800-107-rev1.pdf

It's not clear to me why the "collision resistance strength" rather
than "preimage resistance strength" or "second preimage strength" apply
when using sha2 for generating session keys and the exchange hash.

Regards,
/Niels

---

From: "Mark D. Baushke" <[email-masked]>
Date: Sat, 14 Nov 2015 13:02:33 -0800

> when using sha2 for generating session keys and the exchange hash.

Looking more carefully at what is being hashed in the exchange, I agree
with you that collision resistance strength is not involved here.

So, that only leaves open if choosing to use sha256 as a hash for larger
diffie-hellman MODP groups...

For now, does it seem reasonable to add RFC 3526 group15 & group16 to
the protocol?

  diffie-hellman-group15-sha256 (3072-bit MODP group ~130 bits of security)
  diffie-hellman-group16-sha256 (4096-bit MODP group ~150 bits of security)

I do not see a need at present for using:

 * group17 (6144-bit MODP group ~170 bits of security)
 * group18 (8192-bit MODP group ~190 bits of security)

IMO, it just takes too long to do calculations with them.

	-- Mark

---

From: "Mark D. Baushke" <[email-masked]>
Date: Sat, 14 Nov 2015 23:48:33 -0800

Niels =?utf-8?Q?M=C3=B6ller?= <[email-masked]> writes:

> >   diffie-hellman-group15-sha256 (3072-bit MODP group ~130 bits of securit=
> y)
> >   diffie-hellman-group16-sha256 (4096-bit MODP group ~150 bits of securit=
> y)
> 
> I think it makes sense. It's good to have some specified algorithms
> with security a bit beyond what's currently used, to make it easy to
> move if/when needed attacks on the current algorithms emerge.

Agreed.

> Next question is what status they should have. I think it makes sense to
> have group15 as RECOMMENDED.

I agree with this suggestion.

> (By the same argument, I think it makes sense to specify some
> alternative to sha256 too, which I guess would be either sha512 or
> sha3-384 (sha384 makes litte sense to me, since it's essentially a
> truncated sha512, with same performance and shorter output)).

Given your point about sha2-384, I think there are three possibilities
that remain:

  sha2-512
  sha3-256
  sha3-512

There are aguments both in favor and against each of the alternatives.

fwiw: I have no idea if the SSH community is ready to consider the use
of sha3 (FIPS PUB 202 style) at this time, but it is more likely to
be a challenge to the attacks on diffie-hellman I heard of to date.

	-- Mark

---

From: [email-masked] (Niels Möller)
Date: Sun, 15 Nov 2015 08:16:19 +0100

>   diffie-hellman-group16-sha256 (4096-bit MODP group ~150 bits of security)

I think it makes sense. It's good to have some specified algorithms with
security a bit beyond what's currently used, to make it easy to move
if/when needed attacks on the current algorithms emerge. 

Regards,
/Niels

---

From: [email-masked] (Niels Möller)
Date: Sun, 15 Nov 2015 09:14:01 +0100

> Given your point about sha2-384, I think there are three possibilities

sha3-384 could also be on that list. Unlike for sha*2*-384, it's a
different security/performance tradeoff than sha3-512.

> of sha3 (FIPS PUB 202 style) at this time,

Me neither.

Regards,
/Niels