Re: [Cfrg] Dual_EC_DRBG

Alyssa Rowan <akr@akr.io> Mon, 30 December 2013 15:10 UTC

Return-Path: <akr@akr.io>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 57AAB1AE1B3 for <cfrg@ietfa.amsl.com>; Mon, 30 Dec 2013 07:10:38 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.902
X-Spam-Level:
X-Spam-Status: No, score=-1.902 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001] autolearn=ham
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id NLeRj5yz8YLA for <cfrg@ietfa.amsl.com>; Mon, 30 Dec 2013 07:10:30 -0800 (PST)
Received: from entima.net (entima.net [78.129.143.175]) by ietfa.amsl.com (Postfix) with ESMTP id 641CE1AE01F for <cfrg@irtf.org>; Mon, 30 Dec 2013 07:10:30 -0800 (PST)
Received: from [10.10.42.10] (cpc5-derb12-2-0-cust796.8-3.cable.virginm.net [82.31.91.29]) by entima.net (Postfix) with ESMTPSA id A04A360483 for <cfrg@irtf.org>; Mon, 30 Dec 2013 15:10:23 +0000 (GMT)
Message-ID: <52C18CF4.2010609@akr.io>
Date: Mon, 30 Dec 2013 15:10:44 +0000
From: Alyssa Rowan <akr@akr.io>
User-Agent: Mozilla/5.0 (Windows NT 6.3; WOW64; rv:24.0) Gecko/20100101 Thunderbird/24.2.0
MIME-Version: 1.0
To: cfrg@irtf.org
References: <810C31990B57ED40B2062BA10D43FBF5C18718@XMB116CNC.rim.net> <20131227190907.GA23840@netbook.cypherspace.org> <810C31990B57ED40B2062BA10D43FBF5C187DC@XMB116CNC.rim.net>
In-Reply-To: <810C31990B57ED40B2062BA10D43FBF5C187DC@XMB116CNC.rim.net>
X-Enigmail-Version: 1.6
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
Subject: Re: [Cfrg] Dual_EC_DRBG
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: Mon, 30 Dec 2013 15:10:38 -0000

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA512

On 27/12/2013 20:43, Dan Brown wrote:

> Repeating myself, nobody showed how the alternative P&Q could be
> backdoored.

Yes, they did. Even with another point, Dual_EC_DRBG still doesn't
produce uniform random numbers (2^28 distinguisher¹, and a p=0.0011
consecutive bit predictor² - both of which are practical attacks).

So, if you use it to generate k for (DSA|ECDSA) signatures... or,
heaven forbid, a key...

It is thoroughly unsuitable as a CSPRNG, and is obviously broken by
design, as was widely pointed out at the time, even before we knew for
sure NSA had a hand in it.

> I would even want them to clearer.

I would want it removing from the standard entirely, as thoroughly and
completely discredited.

> Reported, yes.  But AFAIK, not published.

Unless you know of another EC-based RNG published by NIST in 2006,
all doubt has been removed that it is, in the NSA's words, 'enabled'.

Moreover, the internal NSA memo discussed by NYT might literally name
you, given your name is on the patent³ along with Vanstone, so I would
understand why you might have a vested interest in its publication.
You'd have to ask NYT for that, I suppose.

I'm going to ask you directly, Dan: Have you had any contact with the
 SIGINT Enabling Project that you know of? I mean, you even talk
specifically about "escrow keys" in that patent. That seems directly
relevant to their work.

___
1. Shoenmakers & Sidorenko [2006] <http://eprint.iacr.org/2006/190.pdf>
2. Gjøsteen [2005], comments to draft NIST SP 800-90A
3. <http://patents.justia.com/patent/8396213>

- -- 
/akr
-----BEGIN PGP SIGNATURE-----

iQIcBAEBCgAGBQJSwYz0AAoJEOyEjtkWi2t6JPkP/115U2z4sYiiPdq0ARDZEqVD
ujklAkflEBPawWXFla9yfhYzek272f3y8W12iyPr9cA4GAfxiiZv4/ycoQC1Js6w
lWCW14lWoJv1RCs5wsZjGLLMAMCqa24oEVcVqcVgV9JEnpwTj7zSjLrJ/MMyI91w
vhtdspZSA1MI+ik3FpuSR89Ooqo65s/KCWXGrt3oDfI6myozenS50bV4QYMQCCjC
APU+WtcCg+yDhovjN653Y8ZnEWqtPgC3OsZ1cK5pNJxJ4lqL6z2bicgUXVfHmlCW
Eq3bmPLQ+PZ1qM1o7c+BjSsapgQl1eERxAXsLhrJ/qU28+BK5oStQjfldZE9B/pP
0XrW/ZfYaTbcK9qzVZXlF1vFHW2tAfl226Q2MiJRnieqaCwaXlEm7GkbcYc9WAwu
9JjHfpn6jJ1vQ6mAuCUcrG8INa9hYQdKr/a/eWxOhaBqeVLOfNfEEOifgsGzQiJJ
ne5lnrDNe+HfYXZZr1BA+Sf7VLi+EYL5BWWV+QtKCUOVGQNZKk9VX0hoxQUGzBoG
eSvlmbg8k/ADfWnrSXUA3pP6eMpKKpbKkSwRsJQO2GR2dQTLodjKLU2PlzPRLnBm
7E5iz24KqHaOwMC67ENLUTPZpbaOi62mlFAjT0Sr1q8Ys6ZT49oDFVwXIbMdqH1R
ScguPThvXkj95mxAcFwp
=/B2W
-----END PGP SIGNATURE-----