Re: [Cfrg] Security proofs v DH backdoors

Dan Brown <> Thu, 27 October 2016 10:32 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id B7132129D4A for <>; Thu, 27 Oct 2016 03:32:25 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -3.032
X-Spam-Status: No, score=-3.032 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_LOW=-0.7, RP_MATCHES_RCVD=-0.431, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id KaBrzLa8B7m1 for <>; Thu, 27 Oct 2016 03:32:21 -0700 (PDT)
Received: from ( []) (using TLSv1 with cipher RC4-SHA (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 1238C129D4B for <>; Thu, 27 Oct 2016 03:32:20 -0700 (PDT)
Received: from ([]) by with ESMTP/TLS/DHE-RSA-AES256-SHA; 27 Oct 2016 06:32:09 -0400
Received: from ( by ( with Microsoft SMTP Server (TLS) id 14.3.319.2; Thu, 27 Oct 2016 06:32:18 -0400
Received: from ([fe80::45d:f4fe:6277:5d1b]) by ([fe80::459a:3e96:7706:5ba1%12]) with mapi id 14.03.0319.002; Thu, 27 Oct 2016 06:32:18 -0400
From: Dan Brown <>
To: "Mark D. Baushke" <>, Peter Gutmann <>
Thread-Topic: [Cfrg] Security proofs v DH backdoors
Thread-Index: AQHSL9+c3X+YapHg8EyMi8s5IjBNmqC8Gwj8
Date: Thu, 27 Oct 2016 10:32:17 +0000
Message-ID: <>
References: <>, <> <>, <>
In-Reply-To: <>
Accept-Language: en-US, en-CA
Content-Language: en-US
Content-Type: text/plain; charset="windows-1256"
Content-Transfer-Encoding: quoted-printable
MIME-Version: 1.0
Archived-At: <>
Cc: CFRG <>
Subject: Re: [Cfrg] Security proofs v DH backdoors
X-Mailman-Version: 2.1.17
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Thu, 27 Oct 2016 10:32:26 -0000

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 <> 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 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