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

Watson Ladd <watsonbladd@gmail.com> Fri, 27 December 2013 23:50 UTC

Return-Path: <watsonbladd@gmail.com>
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 F14E81AE911 for <cfrg@ietfa.amsl.com>; Fri, 27 Dec 2013 15:50:25 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2
X-Spam-Level:
X-Spam-Status: No, score=-2 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=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 27Ylz_gu-wLy for <cfrg@ietfa.amsl.com>; Fri, 27 Dec 2013 15:50:24 -0800 (PST)
Received: from mail-wi0-x233.google.com (mail-wi0-x233.google.com [IPv6:2a00:1450:400c:c05::233]) by ietfa.amsl.com (Postfix) with ESMTP id B2B0F1AE966 for <cfrg@irtf.org>; Fri, 27 Dec 2013 15:50:23 -0800 (PST)
Received: by mail-wi0-f179.google.com with SMTP id z2so10033643wiv.0 for <cfrg@irtf.org>; Fri, 27 Dec 2013 15:50:18 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type:content-transfer-encoding; bh=vJNWNmyTY4fStUmySzelB5Kk6EvKWsXkqZ/61FtCD9g=; b=zh/oELCEOsleaXvs0QxuXvQyo8/B8msqwOK/Gv6ISKmKPCPXxhkZv3/psJxax7tjn8 9mOGvxFObjHBL6k3W6MUaAumDvewTJ+ryz5JJDmtvdxBP9gEA3tMHTiIciiDBc+AgnV0 5He+/8nKXqmlvmIFZoqwY6hsTLHmZO/hBjS2dA7y4+Yp4mbeyLSWAlm8ZrXvOPu7IBO1 q0qJAMgqe+3nzVVYaW/60XdXefuNR6WMm+VacFCLemEBwAyGZV5lDnqf57rnAC8Jsu7I sQ6NEWJQo6CrMImOFv2yC9I9AqPurWZb5ZGTCPXKituP7BjNaACJGOzzGOwmqDXXt6Ce sbqg==
MIME-Version: 1.0
X-Received: by 10.180.90.230 with SMTP id bz6mr31739034wib.17.1388188218231; Fri, 27 Dec 2013 15:50:18 -0800 (PST)
Received: by 10.194.242.131 with HTTP; Fri, 27 Dec 2013 15:50:18 -0800 (PST)
In-Reply-To: <810C31990B57ED40B2062BA10D43FBF5C18883@XMB116CNC.rim.net>
References: <810C31990B57ED40B2062BA10D43FBF5C18718@XMB116CNC.rim.net> <52BDF443.6080304@cisco.com> <3c96bfce5622182ffcad22267d37aaa4.squirrel@www.trepanning.net> <810C31990B57ED40B2062BA10D43FBF5C18883@XMB116CNC.rim.net>
Date: Fri, 27 Dec 2013 18:50:18 -0500
Message-ID: <CACsn0ckzUHPkqZwHKyDP4qWaSbnmm_GpB0CHT005L11XMy+3Bg@mail.gmail.com>
From: Watson Ladd <watsonbladd@gmail.com>
To: Dan Brown <dbrown@certicom.com>
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
Cc: "mcgrew@cisco.com" <mcgrew@cisco.com>, "cfrg@irtf.org" <cfrg@irtf.org>
Subject: Re: [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 23:50:26 -0000

On Fri, Dec 27, 2013 at 6:34 PM, Dan Brown <dbrown@certicom.com>; wrote:
>
>
>> -----Original Message-----
>> From: Dan Harkins
>> Sent: Friday, December 27, 2013 4:46 PM
>>
>> On Fri, December 27, 2013 1:42 pm, David McGrew wrote:
>> > I understand that these topics deserve discussion, but in the long
>> > term it might be more fruitful to consider what recommendations should
>> > be given to implementers and standards group on the subject of PRNGs.
>
> Yes, I just wanted to clarify.
>
> Now, since you asked about recommendations ...
>
> PRNGs are not needed for interoperability, but the some of the core
> "schemes" standards that I am familiar with, such as ANSI X9.62 and SEC1,
> make normative requirements about the PRNGs and entropy used to generate
> keys.  I think that's reasonable for the sake of security.  In theory, if
> IETF "protocols" specs reference these core "schemes" standards, then they
> would inherit the PRNG requirements.  I'd recommend IETF "schemes" specs
> similarly follow suit, although an alternative is just to require a (secure)
> randomly generated key, but that could be little risky to ask implementers
> to do this without sufficient guidance.

Please, do not do this. /dev/random on unix-likes should be used
instead: it is one
place to patch and improve, vs. thousands of independent implementations.
I understand that for hardware manufacturers this isn't enough. But
there we have
Fortuna and Yarrow. I believe Yarrow was an RFC.

Honestly I think the available sources of random numbers change so often:
my current machine has a hardware source in the CPU, but doesn't have
a disk drive with
turbulence, and for older machines it is the reverse.
>
> Maybe I'm biased, but for a PRNG, I'd recommend Dual_EC_DRBG with
> alternative P&Q, at least on systems that can afford the extra latency, e.g.
> high-end user equipment, if only because of the refereed security analysis.
> Also, considerable attention, because of the potential backdoor, has been
> paid to Dual_EC_DRBG, yet no major attack since that security analysis has
> been uncovered.

Huh? Making a DRBG is easy given a PRF: hash a bunch of values, then reseed.
It's easy to show that there is a distinguisher on the DRBG only if
there is one on
the PRF. In practice we trust PRFs exist: no one is using BBS to
encrypt messages.
Dual_EC_DRBG is not compelling: it has a bias in some of the bits, is
slow compared
to BBS (one square mod a big number vs. an exponentiation), and even
in hardware a
few gates for something else (say a sense amplifier generator) isn't that bad.

>
> The three other DRBG algorithms now in SP 800-90 should be much faster, if
> such speed is needed, and should also be secure, since no major attacks have
> been published, despite their high profile in NIST specs.  The HMAC_DRBG
> also has a proof.

So why not HMAC_DRBG over Dual_EC_DRBG? Your recommendation doesn't seem
to make a whole lot of sense to me.

>
> I'm also aware of other research into comparable alternatives:
>
> http://eprint.iacr.org/2013/338
> http://eprint.iacr.org/2005/029
>
> but I'm not sure if these have been standardized anywhere.  If I had to
> summarize these in a few words, I would hazard to say that they provide
> constructions to build a PRNG from a PRF (where for a PRF, think RC4, or
> AES-CTR).

Don't think RC4 or AES-CTR. RC4 has the Fluer-McGrew bias, and AES-CTR is
a PRP, not a PRF. Yes, it's a minor detail, but it does substantially
reduce the security
of CTR mode beyond 2^64 blocks.

>
> There's also lots of research into "randomness extractors", but that's
> something slight different.
>
>
>>
>>   Indeed! And might this discussion move to dsfjdssdfsd@ietf.org, the
> mailing
>> list formed to discuss just this very subject?
>>
>
> Thanks. I completely forgot about that mailing list, I saw the announcement
> but never looked into it.  Is there a WG site?
>
> Best regards,
>
> Dan
>
> ---------------------------------------------------------------------
> 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.
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> http://www.irtf.org/mailman/listinfo/cfrg
>



-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin