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

From: David McGrew <[email-masked]>
Date: Thu, 02 Jan 2014 13:16:53 -0500

Hi Watson,

I think that we are in agreement on all of the main points here, but I 
did want to comment on a tangent:

On 12/30/2013 09:52 AM, Watson Ladd wrote:
> On Mon, Dec 30, 2013 at 8:56 AM, David McGrew <[email-masked]> 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.

If I understand your strawman here, the undermined DRBG would be 
detectable after 2^20 distinct invocations on distinct seeds, it would 
produce repeating values.   A test harness that could invoke the DRBG on 
a million distinct seeds could detect this fact, assuming of course that 
it was actually using different seed values.   Of course, it is not 
clear how the test harness could ensure that the DRBG was not "cheating" 
by e.g. just returning a pseudorandom value, such as the output of HMAC 
in couter mode.   A "cheating" DRBG would not be detectable.

It would be really valuable if there were a testing methodology for 
random sources and DRBGs that enabled a third party (such as the end 
user, or a verification lab that is unaffiliated with the manufacturer) 
to assess the quality of both of those components. This could make a 
significant positive impact IMO - would be interested to hear what other 
people think.

In my experience, most vendors who build random sources are very 
hesitant to provide the raw output of the source that would be needed to 
perform an independent statistical validation of the soundness of the 
source.  From what I can tell, this sometimes reflects a lack of 
confidence in the design.

David

> 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 [email-masked], 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
>> [email-masked]
>> http://www.irtf.org/mailman/listinfo/cfrg
>>
>
>

---

From: Dan Brown <[email-masked]>
Date: Fri, 3 Jan 2014 01:06:51 +0000

Happy New Year to all.

> From: Alyssa Rowan
> Sent: Monday, December 30, 2013 10:11 AM
> 
> 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).

1) I too wrote about the same bias in Appendix B of: 

http://eprint.iacr.org/2006/117 

At the end of that paper, I try to suggest that the bias does not have an impact for nonces or keys. I also try to say that if indistinguishability from uniform bit strings is needed, then more bits can be truncated from the point, which is consistent with what the standards allow.  

This indistinguishability, under sufficient amounts truncation, say half the bits, seems a reasonable conjecture.

To motivate a real-world need for such indistinguishability, my eprint cited one-time pads.  Certainly one-time pads (e.g. stream ciphers) do need full indistinguishability, but in real cryptographic systems, an RNG is not really meant to provide the service of a one-time pad, because, for a one-time pad to useful, i.e. to permit decryption, it has to be reproducible.  Reproducibility undermines the main service provided by an RNG, which is unpredictability, at least in the sense of forward secrecy.  So, in retrospect, it seems that I gave a false motivation.

Perhaps, a better motivation would have been some information-theoretic crypto scheme, such as secret sharing.  This is outside my area of expertise.  Also, neither ANSI nor NIST standardize such info-theoretic algorithms, so at the time I thought it irrelevant, though I see now that to be a too narrow view.

In summary, I agree that there are feasible distinguishers, but I fail to see how these particular distinguishers lead to practical attacks (see further specifics below "forbid") on uses of the RNG.

2) Though this is not a backdoor in the usual narrow sense (that somebody needs to possess a secret key to open), I am sympathetic to your concern that this is an intentional weakness.  Maybe somebody on this list knows of a better name for such an intentional open weakness?  

3) S&S [your ref 1] advanced the understanding of the bias by amplifying the distinguisher using longer outputs. That kind of amplification is fairly well known, and I should have thought about it.  

S&S also conclude that the Dual_EC_DRBG is insecure, but without giving an applied example attacks (see further specifics below "forbid"), and, IIRC, without acknowledging that that some truncation parameters seem to resist the bias attack.

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

1) What your does your ellipsis mean? (BTW, an elliptical implication, which is a clever, implicit pun.)

2) Your comment on k is a very interesting research question, at least to me.  My research on DSA|ECDSA indicates that there is a gap between the known necessary and sufficient conditions for the k value used in DSA and ECDSA signatures.  An impressive series of research papers, leading up to one by Bleichenbacher, shows it necessary that k avoids certain types of arithmetic bias.  My theoretical work (see ECC 2001, and Advances in ECC, Ch. 2) shows that a certain sets of conditions and models, including the k being chosen uniformly, may be sufficient for the security of ECDSA, against certain types of forgery.  The gap is that it is unknown whether certain other kinds of bias in k affect security, because they are not covered by the known attacks or the known security proofs.  

For a contrived example, what if k was chosen such that its SHA-3 digest ends in the bits 011.  This is bias that anybody could test, yet would not seem to lead to any attack on DSA or ECDSA.  

More to the point, if k was the output of Dual_EC_DRBG, and this led to an attack, then in my view this would be a new, and major result, surpassing Bleichenbacher's attack by a long shot because it exploits much less bias, and more importantly a much different type of bias.  If you are aware of such an attack, then maybe inform the CFRG (or just remind me if it is well known).

3) Schnorr has a very interesting result, albeit rather theoretical and in the generic group model, that most forms of bias in an ECC key do not make the ECDLP any easier.  It is known that some forms of bias, such as a small key lead to weaker ECDLP.  So, again there is a gap.  Any further closure of this gap would be significant.  Again, I am forced to wonder if you know something here that I don't.  I couldn't find such an attack in S&S.

4) I am less familiar with other key types, e.g. RSA, AES, and HMAC.  I vaguely recall that certain types of bias in RSA and RC4 secret keys undermine the security. I feel that this is an important area of research.  If it could be shown that the bias from Dual_EC_DRBG undermines some similar computational-based crypto scheme, then this would be an improvement in research.

5)  Of course, it is always prudent to try to make all keys to uniform, if only because that maximizes the min-entropy.  (Also, it makes security proofs easier, I think.)  That's why I formulated that TPP in the my eprint of the Dual_EC_DRBG, and used the indistinguishability as the security definition.  I think now, I would also examine unguessability specifically (see next point).

6) I've since wondered a little what the more important threat models, i.e. security definitions, for a DRBG would be.  Indistinguishability is certainly very nice, especially for information-theoretic crypto, but unguessabiltiy is more important.  So, if unguessability can rely one weaker assumptions than indistinguishability, then this would be worthwhile to understand.  I touched upon the unguessabilty of Dual_EC_DRBG in my 2006 eprint, but haven't looked at the problem since 2007.  Anyway, I don't yet know what the best security definition for a DRBG would be.  Maybe the researchers on "randomness extractors" have something that could be converted over to DRBG, namely entropy condensation.

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

1) Just wondering: do you also dispute that benefit of having an RNG whose security basis is number-theoretic?  What about just for algorithm agility?

I still personally recommend number-theoretic RNGs for security: mainly because I feel more confidence in ECC, and other number-theoretic algorithms, than in symmetric crypto algorithms.  My feeling here is rather vague, and largely based on familiarity, but also philosophically based on ECC and RSA being something innate, whereas symmetric key seems devised.  But I could easily understand how others have the exact opposite feeling.  So, I generally did not expect much adoption of number-theoretic RNGs.

There are other number-theoretic algorithms.  If they have been standardized and proven secure, then they deserve consideration too.  But I doubt that their standards have received as much attention as the Dual_EC_DRBG.  Anyway, I haven't studied any of these, so cannot recommend them personally.

Have there been any advances in the security analysis of the Dual_EC_DRBG algorithm since 2007?  Even though people seem motivated to discredit it?  If not, then I would argue that is a good sign, but also for other unaffected NIST DRBGs.

I haven't really studied the HMAC_DRBG, Hash_DRBG or CTR_DRBG from NIST SP 800-90A.

2) Over the last few days, I've been trying to see things from a wider perspective. 
  
My position on the standard has recently changed.

Implementers (and users) may have placed more trust in the standard than I thought, and they may have been less informed about the widely publicized potential backdoor than I thought.  

In other words, all the publicity may have been ineffective at preventing the alleged backdoor from being exploited, contrary to my belief.  The standard should not have included the default P&Q.

That all said, despite the deficiency of the standard, I feel implementers still have some responsibility to keep up with the news and research about crypto, given that standards need to be stable documents for interoperability.

In summary, my position on the standards, and standards process, is not well-defined.  

To clarify my past position, I said "not subverted standard", but I did not mean to rule out a backdoor in the default P&Q, just that the publicity would render any subversion inoperable, and that there could other things than standards enabling such subversion.  But now I see that I was wrong. 

My position on the algorithm Dual_EC_DRBG, with properly random, backdoor-free, P&Q is the same as in 2007 (see also bias discussion above), which is that it is secure.

> 
> > 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'.
> 

Reports I've seen say "suggest" or "reported", which leaves doubt.  Please send me the links to the correct reports.

Personally, I still don't know for sure if the default P&Q are backdoored, but it would be prudent for implementers and users to assume that they are.

> 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) No contact that I know of.  I never heard of "SIGINT Enabling Project" until the recent news.

2) At some point, I clued into the possibility of a backdoor, and, among other things, tried to make sure the possibility was at least publicly known, at first quietly: with a patent, and with a comment within my March 2006 eprint.  Later, others raised much more publicity, which seemed sufficient to me.  I had expected such publicity to cause the proposers, X9F1 and NIST to withdraw the default P&Q from the standard.

> 
> ___
> 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>

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

---

From: Watson Ladd <[email-masked]>
Date: Thu, 2 Jan 2014 21:34:43 -0500

> This indistinguishability, under sufficient amounts truncation, say half the bits, seems a reasonable conjecture.

The standard actually says that for efficiency only 16 bits should be
removed. Tanja Lange points out that at the time "everyone" knew that
much more truncation was required.

> To motivate a real-world need for such indistinguishability, my eprint cited one-time pads.  Certainly one-time pads (e.g. stream ciphers) do need full indistinguishability, but in real cryptograph…

You do realize this is about expanding a short seed to a longer
sequence indistinguishable from random and not constantly feeding in
data?

> More to the point, if k was the output of Dual_EC_DRBG, and this led to an attack, then in my view this would be a new, and major result, surpassing Bleichenbacher's attack by a long shot because i…

I don't trust schemes because they haven't been attacked, but because
they have reductions.

> 4) I am less familiar with other key types, e.g. RSA, AES, and HMAC.  I vaguely recall that certain types of bias in RSA and RC4 secret keys undermine the security. I feel that this is an important…

Why bother when we can use something that doesn't have these issues
like HMAC_DRBG?

> 6) I've since wondered a little what the more important threat models, i.e. security definitions, for a DRBG would be.  Indistinguishability is certainly very nice, especially for information-theor…

Do you understand how cryptographic proofs work? At each step two
games are shown equivalent, with some success probability reduction.
Most of the equivalences depend on indistinguishability from random.
Replace with unguessability and the whole edifice drops apart. The
whole game is based on each piece fitting into the slot carved out
from it. What does the weaker notion of "unguessability" let you do?
Unguessability is also equivalent to indistinguishability: if a
polynomial-time algorithm cannot predict a sequence of bits with
greater than .5 probability at each bit, it cannot distinguish it from
random.

By contrast, the ROM is a nicer model to work in than the standard
model: some schemes get slower to make them work in the standard
model. This is worth having the ROM.
> I still personally recommend number-theoretic RNGs for security: mainly because I feel more confidence in ECC, and other number-theoretic algorithms, than in symmetric crypto algorithms.  My feelin…

If AES breaks a number-theoretic RNG doesn't help us here. In for a
penny, in for a pound.

> That all said, despite the deficiency of the standard, I feel implementers still have some responsibility to keep up with the news and research about crypto, given that standards need to be stable…

A major vendor of cryptographic software was paid $10 million to make
it the default, and didn't change it until this year. And you call
that unexploited? What on earth was that $10 million for? The CMPV
process was insisting implementors use the default P&Q.

> My position on the algorithm Dual_EC_DRBG, with properly random, backdoor-free, P&Q is the same as in 2007 (see also bias discussion above), which is that it is secure.

And of course your employer has the patent on it.

> 1) No contact that I know of.  I never heard of "SIGINT Enabling Project" until the recent news.

So you discover this backdoor in a NIST standard, and then do what?

> 2) At some point, I clued into the possibility of a backdoor, and, among other things, tried to make sure the possibility was at least publicly known, at first quietly: with a patent, and with a co…

And you didn't submit a public comment to NIST or a letter to CRYPTO?
You had a footnote in your March 2006 paper, not a note explaining
that the backdoor was real as your patent indicates you knew. The
discovery by S&F in 2007 got publication: why not a two-for-one in
2006? In 2005 you filed for a patent instead of telling everyone this
was broken. These actions don't seem like the actions of someone
trying to promote strong cryptography in an open process: they seem
like the actions of someone trying to set up then an excuse that
"well, I told you but you didn't listen" when the truth finally
emerged.

This is really a big tangent from the work of the CFRG, but it
illustrates that we should be very conservative in what we do and not
accept a few member's word as gospel. Well-known implementors and
cryptographers have been known to make big blunders, and if they do
not say they know of an attack, they might be lying. By contrast, if
they have a proof or an attack, you can always ask them to show it.

Sincerely,
Watson

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