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

Watson Ladd <watsonbladd@gmail.com> Mon, 30 December 2013 14:52 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 4F6311ADFA6 for <cfrg@ietfa.amsl.com>; Mon, 30 Dec 2013 06:52:42 -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 FJ0GikSK5lrT for <cfrg@ietfa.amsl.com>; Mon, 30 Dec 2013 06:52:40 -0800 (PST)
Received: from mail-we0-x22e.google.com (mail-we0-x22e.google.com [IPv6:2a00:1450:400c:c03::22e]) by ietfa.amsl.com (Postfix) with ESMTP id D73FA1AE0DA for <cfrg@irtf.org>; Mon, 30 Dec 2013 06:52:39 -0800 (PST)
Received: by mail-we0-f174.google.com with SMTP id q58so10336367wes.33 for <cfrg@irtf.org>; Mon, 30 Dec 2013 06:52:32 -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; bh=PFDFHu5qAkGN0LZmqEAuFC3FrzR+OGRu8X8dUNMPx3Q=; b=Y1+AwZuKsQ5n0sF2W2hZeG+g0xLTvI9DAbWoQwZVYa6m61LqzEkCJwLN80mS8ZZzH7 CkcSlW1JvmG8AW6ZJWUMRQRrKsQ+4dbnU4qJN2MKs/TdvnS0P0PZdg2hgtEKO2EWswvf 6DXG5EPfKgCyojfLnFK7m0XtcpYPtFawI8Inl1txUyObGQWyNVFgYzn8U2HYOnrt+baO Gx6UKHLkKLxLVuxtnOYPRwg1qOHY8v22z/flisVWyUdT8gxPLOE4DA/k6PzIiOkChVKe E+cE6RhRYKoY7R4ApR7RXYan9nPCyXocQ47KsNb/tbZahNMmiiIdspGtQiEWtvnqgY97 UT6w==
MIME-Version: 1.0
X-Received: by 10.194.175.66 with SMTP id by2mr19730084wjc.59.1388415152405; Mon, 30 Dec 2013 06:52:32 -0800 (PST)
Received: by 10.194.242.131 with HTTP; Mon, 30 Dec 2013 06:52:32 -0800 (PST)
In-Reply-To: <52C17B9A.1020303@cisco.com>
References: <810C31990B57ED40B2062BA10D43FBF5C18718@XMB116CNC.rim.net> <52BDF443.6080304@cisco.com> <3c96bfce5622182ffcad22267d37aaa4.squirrel@www.trepanning.net> <810C31990B57ED40B2062BA10D43FBF5C18883@XMB116CNC.rim.net> <52C17B9A.1020303@cisco.com>
Date: Mon, 30 Dec 2013 09:52:32 -0500
Message-ID: <CACsn0ckuECZwLXEXLBfcDQTLupzp4U-=49i2diPHjF-TFy6sYg@mail.gmail.com>
From: Watson Ladd <watsonbladd@gmail.com>
To: David McGrew <mcgrew@cisco.com>
Content-Type: text/plain; charset="UTF-8"
Cc: Dan Brown <dbrown@certicom.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: Mon, 30 Dec 2013 14:52:42 -0000

On Mon, Dec 30, 2013 at 8:56 AM, David McGrew <mcgrew@cisco.com> wrote:
> Hi Dan,
>
>
> On 12/27/2013 06:34 PM, Dan Brown 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.
>
> Maybe I'm biased,
>
>
> I love the pun there ;-)
>
>
> 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.
>
>
> I respectfully disagree.   We need to keep in mind a holistic security model
> that considers all of the threats to information security, and one such
> threat is the possibility that the P and Q parameters in a particular
> implementation might be changed by an untrustworthy software provider
> (either a vendor or an open-source contributor), hardware provider (in the
> case that the software is pre-installed on the hardware), a reseller, or
> someone else in the supply chain.   If those parameters are set correctly by
> the initial developer, but then changed by someone else, the unwitting end
> user might be compromised.   It is doubtful that this change would be
> detected.

There is a distinguishing attack on Dual_EC_DRBG taking time 2^28 with
good success probability.
See http://eprint.iacr.org/2006/190 for details. This alone makes it
unacceptable.
Also note that Certicom has IPR. Dan Brown hasn't disclosed this, but
his name is on the patent
on the alternate parameters. There isn't a single good reason for
Dual_EC_DRBG to even be
considered.

>
> One could counter-argue that 1) software boot-time integrity can be provided
> through boot-time signature checking and 2) a malicious actor in the supply
> chain could undermine the efficacy of any DRBG.   However, boot-time
> integrity is absent on many systems at this time, it does not address
> run-time integrity even when it is present, and if a DRBG based on symmetric
> cryptography is undermined, that fact will be noticeable (at least in
> principle).

I don't think this is quite true. Imagine a HMAC-DRBG implementation
with all but 40 bits of the
key hardwired to a fixed value. Given an external seed it gets the
wrong answers, but if the key is
generated internally you would never know.
Sincerely,
Watson Ladd

>
> David
>
> 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.
>
> 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).
>
> 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