Re: [dsfjdssdfsd] [Cfrg] IPR regarding Dual EC

Dan Brown <dbrown@certicom.com> Fri, 13 June 2014 15:36 UTC

Return-Path: <dbrown@certicom.com>
X-Original-To: dsfjdssdfsd@ietfa.amsl.com
Delivered-To: dsfjdssdfsd@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 79D5A1B2921 for <dsfjdssdfsd@ietfa.amsl.com>; Fri, 13 Jun 2014 08:36:31 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.3
X-Spam-Level:
X-Spam-Status: No, score=-1.3 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, J_CHICKENPOX_34=0.6] autolearn=no
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 JQ98plrzcGE5 for <dsfjdssdfsd@ietfa.amsl.com>; Fri, 13 Jun 2014 08:36:30 -0700 (PDT)
Received: from smtp-p01.blackberry.com (smtp-p01.blackberry.com [208.65.78.88]) by ietfa.amsl.com (Postfix) with ESMTP id F19E91B2952 for <dsfjdssdfsd@ietf.org>; Fri, 13 Jun 2014 08:36:29 -0700 (PDT)
Received: from xct102cnc.rim.net ([10.65.161.202]) by mhs212cnc.rim.net with ESMTP/TLS/AES128-SHA; 13 Jun 2014 11:36:26 -0400
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.0174.001; Fri, 13 Jun 2014 11:36:25 -0400
From: Dan Brown <dbrown@certicom.com>
To: "'tanja@hyperelliptic.org'" <tanja@hyperelliptic.org>, "'cfrg@irtf.org'" <cfrg@irtf.org>
Thread-Topic: [Cfrg] IPR regarding Dual EC
Thread-Index: AQHPhn42aj+iD9cwuESPcc9Ig13I2ZtvEZFQ
Date: Fri, 13 Jun 2014 15:36:25 +0000
Message-ID: <810C31990B57ED40B2062BA10D43FBF5C921A1@XMB116CNC.rim.net>
References: <20140612203756.GS5794@cph.win.tue.nl>
In-Reply-To: <20140612203756.GS5794@cph.win.tue.nl>
Accept-Language: en-CA, en-US
Content-Language: en-US
X-MS-Has-Attach: yes
X-MS-TNEF-Correlator:
x-originating-ip: [10.65.160.252]
Content-Type: multipart/signed; protocol="application/x-pkcs7-signature"; micalg=SHA1; boundary="----=_NextPart_000_0005_01CF86FB.B5659380"
MIME-Version: 1.0
Archived-At: http://mailarchive.ietf.org/arch/msg/dsfjdssdfsd/5NflQawoQG6Mwvdu6DNxjCPjIe8
Cc: "dsfjdssdfsd@ietf.org" <dsfjdssdfsd@ietf.org>
Subject: Re: [dsfjdssdfsd] [Cfrg] IPR regarding Dual EC
X-BeenThere: dsfjdssdfsd@ietf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: "The dsfjdssdfsd list provides a venue for discussion of randomness in IETF protocols, for example related to updating RFC 4086." <dsfjdssdfsd.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/dsfjdssdfsd>, <mailto:dsfjdssdfsd-request@ietf.org?subject=unsubscribe>
List-Archive: <http://www.ietf.org/mail-archive/web/dsfjdssdfsd/>
List-Post: <mailto:dsfjdssdfsd@ietf.org>
List-Help: <mailto:dsfjdssdfsd-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/dsfjdssdfsd>, <mailto:dsfjdssdfsd-request@ietf.org?subject=subscribe>
X-List-Received-Date: Fri, 13 Jun 2014 15:36:31 -0000

Should we keep RNG discussions confined to the list dsfjdssdfsd@ietf.org?

I responded on the list CFRG (see below) because I think CFRG is interested
in the forward secrecy of key agreement schemes. My comments consider the
impact of RNGs upon forward secrecy.

> -----Original Message-----
> From: Cfrg [mailto:cfrg-bounces@irtf.org] On Behalf Of Tanja Lange
> Sent: Thursday, June 12, 2014 4:38 PM
> To: cfrg@irtf.org
> Subject: [Cfrg] IPR regarding Dual EC
> 
> Just in case somebody thought that Dual EC wasn't dead enough:
> * Dual EC escrow avoidance is patented in US, JP and EU, more in the
making.
> * Dual EC escrow usage is included in the EU patent.
> * The patent application including the full description of the back door
>   was public and online since summer 2006, a month after the first
>   version of SP800-90.
> * I can't find any notification to NIST.
> * Patent history shows review by NSA.
> * The patent is being maintained, most recent fees spring 2014 (wonder
>   why some people keep bringing up tweaks to Dual EC?).
> 
> Oh, yes, shouldn't forget:
> Patent authors: Dan Brown and Scott Vanstone from Certicom.
> 

Sounds correct from what I recall off-hand.

To answer your "wonder why" question, e.g., why I've argued for saving some
form of escrow-avoiding version of Dual_EC, despite the unpopularity that it
has acquired, I'll re-express, and expand upon, my previous arguments:

Forward secrecy needs either (1) a trustworthy live entropy source or (2) a
trustably-seeded deterministic RNG with a one-way state update function, or
(3) both, i.e. combination of (1) and (2).  Consider the case (2) of a
deterministic RNG, which ANSI and NIST call a DRBG.  Using ephemeral ECDH
key agreement (and some derivatives like ECMQV) to achieve forward secrecy
requires assuming the ECDHP and ECDLP to be hard, regardless of the
symmetric encryption used (be it AES+HMAC or OCB or ChaCha ...).  So, if one
can afford the cost, e.g. in a user's personal computer, then using a
state-update function that only requires the ECDLP or ECDHP to be hard
results in an implementation that can achieve forward secrecy in a modular
way from the symmetric crypto.  If one cannot afford the cost, (e.g. the
power or time cost in low-end device, a real-time device, a high-volume
server, or the IPR regime), then one rely some instead rely on some other
one-way function.  E.g. maybe HMAC, as in the HMAC-DRBG or AES as in the
CTR-DRBG, or something hashing used in the Linux RNG.  In that case, one
would instead rely on one particular kind of one-way function, AES, that one
might not need to rely upon when one uses other forms of symmetric-key
crypto, e.g. ChaCha.  

Hmm, now that I wrote the argument that way, some alternatives occur to me.
Perhaps a symmetric-key-based DRBG could be devised whose one-way function
was the maximum hardness of all the various symmetric-key crypto candidates
being used in an implementation.  The resulting DRBG might be rather
awkward, but would still have a lack-of-single-point-of-weakness in an
implementation that supports multiple symmetric-key algorithms.  Or maybe
better, have a separate symmetric-key-based DRBG to use with each different
symmetric-key algorithm.  

Aside: the ANSI/NIST CTR-DRBG state update function seems to create new AES
key related to the old AES key.  I expect that the underlying hardness
problem for CTR-DRBG state updating should be hard, but I am not sure if it
is equivalent to what one usually relies upon for symmetric-key encryption.
Does anybody here know?