Re: [Cfrg] Security proofs v DH backdoors

[Dan Brown <[e-mail]>]

For q=(p-1)/2, literally computing c^q for client public key is very slow.

Why not use a faster alternative, such as checking Legendre symbol (c/p), use cofactor DH,‎ or use even private keys?

Sent from my BlackBerry 10 smartphone on the Rogers network.
  Original Message
From: Mark D. Baushke
Sent: Wednesday, October 26, 2016 7:21 PM
To: Peter Gutmann
Cc: Ilari Liusvaara; Dan Brown; CFRG
Subject: Re: [Cfrg] Security proofs v DH backdoors


Peter Gutmann <[e-mail]> writes:

> Mark Bauschke mentioned they do checking on the OpenSSH list, taking

Minor typo. The lastname is Baushke without the "c" in it. Long story.

> (i.e. assuming) that q = ( p - 1 ) / 2.

I may have sent a confusing message.

OpenSSL 1.0.2f (to address CVE-2016-0701) added a check where a "q"
parameter is available.

The OpenSSH dh.c::dh_new_group() is able to setup a dh->q value by using
the q = (p - 1) / 2 math. The dh.c::dh_pub_is_valid() could also check
any incoming DH using the OpenSSL
crypto/dh/dh_check.c::DH_check_pub_key() functionality which does:

       /* Check pub_key^q == 1 mod p */
        if (!BN_mod_exp(tmp, pub_key, dh->q, dh->p, ctx))
            goto err;
        if (!BN_is_one(tmp))
            *ret |= DH_CHECK_PUBKEY_INVALID;

as is mandated by NIST SP 800-56A rev1 section 5.6.2.4 FCC Full Public
Key Validation Routine.

In the Juniper Networks OpenSSH implementation a "q" with q=(p-1)/2
parameter validation is performed in FIPS mode because we are mandated
to validate the DH parameters for FIPS 140-2.

This is true even if it is the well known DH group14 (which is not
required for TLS or IPsec).

DH parameter validate can cause some issues if users configure support
for RFC 4419 while in FIPS mode as most of those groups seem to have a
problems finding a proper set of parameters to use a which results in a
well formed q-ordered subgroup evaluation... the result of the DH mod p
operations is p-1 in those situations which is not good.

        -- Mark