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

From: Dan Brown <[email-masked]>
Date: Fri, 13 Jun 2014 15:36:25 +0000

Should we keep RNG discussions confined to the list [email-masked]?

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:[email-masked]] On Behalf Of Tanja Lange
> Sent: Thursday, June 12, 2014 4:38 PM
> To: [email-masked]
> 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?