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

["Mark D. Baushke" <mdb%juniper.net@localhost>]

Hi Peter,

Peter Gutmann <pgut001%cs.auckland.ac.nz@localhost> writes:

> mdb%juniper.net@localhost <mdb%juniper.net@localhost> 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.

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