[Cfrg] Dual_EC_DRBG ... [was RE: Requesting removal of CFRG co-chair]

Dan Brown <dbrown@certicom.com> Fri, 27 December 2013 18:42 UTC

Return-Path: <dbrown@certicom.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com []) by ietfa.amsl.com (Postfix) with ESMTP id 291481AE248 for <cfrg@ietfa.amsl.com>; Fri, 27 Dec 2013 10:42:09 -0800 (PST)
X-Quarantine-ID: <WEd_sPXWMzUR>
X-Virus-Scanned: amavisd-new at amsl.com
X-Amavis-Alert: BAD HEADER SECTION, Duplicate header field: "MIME-Version"
X-Spam-Flag: NO
X-Spam-Score: 0.81
X-Spam-Status: No, score=0.81 tagged_above=-999 required=5 tests=[BAYES_50=0.8, T_TVD_FUZZY_SECURITIES=0.01] autolearn=ham
Received: from mail.ietf.org ([]) by localhost (ietfa.amsl.com []) (amavisd-new, port 10024) with ESMTP id WEd_sPXWMzUR for <cfrg@ietfa.amsl.com>; Fri, 27 Dec 2013 10:42:07 -0800 (PST)
Received: from smtp-p01.blackberry.com (smtp-p01.blackberry.com []) by ietfa.amsl.com (Postfix) with ESMTP id CB6AB1ADF73 for <cfrg@irtf.org>; Fri, 27 Dec 2013 10:42:06 -0800 (PST)
Content-Type: multipart/mixed; boundary="===============0964631035=="
MIME-Version: 1.0
Received: from xct102cnc.rim.net ([]) by mhs210cnc.rim.net with ESMTP/TLS/AES128-SHA; 27 Dec 2013 13:41:56 -0500
Received: from XMB116CNC.rim.net ([fe80::45d:f4fe:6277:5d1b]) by XCT102CNC.rim.net ([fe80::2066:5d4f:8c45:af55%17]) with mapi id 14.03.0158.001; Fri, 27 Dec 2013 13:41:55 -0500
From: Dan Brown <dbrown@certicom.com>
To: "'akr@akr.io'" <akr@akr.io>, "'cfrg@irtf.org'" <cfrg@irtf.org>
Thread-Topic: Dual_EC_DRBG ... [was RE: [Cfrg] Requesting removal of CFRG co-chair]
Thread-Index: Ac8DLw6zrELDTKY9RcOiLU6mG9wN5w==
Date: Fri, 27 Dec 2013 18:41:55 +0000
Message-ID: <810C31990B57ED40B2062BA10D43FBF5C18718@XMB116CNC.rim.net>
Accept-Language: en-CA, en-US
X-MS-Has-Attach: yes
x-originating-ip: []
MIME-Version: 1.0
Subject: [Cfrg] Dual_EC_DRBG ... [was RE: Requesting removal of CFRG co-chair]
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <http://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <http://www.irtf.org/mail-archive/web/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <http://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Fri, 27 Dec 2013 18:42:09 -0000

> -----Original Message-----
> From: Alyssa Rowan
> Sent: Friday, December 27, 2013 10:22 AM
> ___
> 1. Specific documented example: Dual_EC_DRBG - a backdoor that couldn't
>    have been more obvious if you'd erected a flashing neon sign and
>    driven a mounted parade with a marching band through it. We have no
>    reason to expect other 'enablings' to be as obvious, of course.

1. Dual_EC_DRBG, as specified in NIST SP 800-90A and ANSI X9.82-3, allows an alternative choice of constants P and Q.  As far as I know, the alternatives do not admit a known feasible backdoor.  In my view, it is incorrect to imply that Dual_EC_DRBG always has a backdoor, though I admit a wording to qualify the affected cases may be awkward.

2. Many things are obvious in hindsight.  I'm not sure if this was obvious.

3. The possibility of a backdoor was known quite early.  Such knowledge undermines the effectiveness of any backdoor.  For a backdoor to be effective, the implementer would have to be naïve or malicious.

4. A malicious implementer likely has many other means to subvert the security of the user.  I.e. this threat is not so specific to Dual_EC_DRBG.

5. Either CMVP or CAVP (I forget which) insisted on the default P and Q.  But the stated purpose of these validation programs, IIRC, is only to protect communication with USG/CAG, in which the user is already trusting these entities extensively.  I'm not aware of any promises to protect non-USG communication in the CMVP or CAVP.

6. Modern cryptography usually likes provable security, especially in refereed conferences like CRYPTO.  Well, Dual_EC_DRBG has such an assurance.    Can anybody in CFRG suggest another DRBG with published security proof?  I've seen a preprint proof for HMAC_DRBG, but forget if it has been refereed.

7. Note, just in case you're wondering, the proof above excludes the case of a backdoor relationship between P and Q: i.e. it applies only to the alternative choices of P and Q.

8. All considered, I don't see how the ANSI and NIST standards for Dual_EC_DRBG can be viewed as a subverted standard, per se.  But maybe that's just because I'm biased or naive.

Best regards,



This transmission (including any attachments) may contain confidential information, privileged material (including material protected by the solicitor-client or other applicable privileges), or constitute non-public information. Any use of this information by anyone other than the intended recipient is prohibited. If you have received this transmission in error, please immediately reply to the sender and delete this information from your system. Use, dissemination, distribution, or reproduction of this transmission by unintended recipients is not authorized and may be unlawful.