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

From: Dan Brown <[email-masked]>
Date: Fri, 27 Dec 2013 18:41:55 +0000

> -----Original Message-----
> From: Alyssa Rowan
> Sent: Friday, December 27, 2013 10:22 AM
> ___
> 1. Specific documented example: Dual_EC_DRBG - a backdoor that couldn't
>    have been more obvious if you'd erected a flashing neon sign and
>    driven a mounted parade with a marching band through it. We have no
>    reason to expect other 'enablings' to be as obvious, of course.

1. Dual_EC_DRBG, as specified in NIST SP 800-90A and ANSI X9.82-3, allows an alternative choice of constants P and Q.  As far as I know, the alternatives do not admit a known feasible backdoor.  In my view, it is incorrect to imply that Dual_EC_DRBG always has a backdoor, though I admit a wording to qualify the affected cases may be awkward.

2. Many things are obvious in hindsight.  I'm not sure if this was obvious.

3. The possibility of a backdoor was known quite early.  Such knowledge undermines the effectiveness of any backdoor.  For a backdoor to be effective, the implementer would have to be naïve or malicious.

4. A malicious implementer likely has many other means to subvert the security of the user.  I.e. this threat is not so specific to Dual_EC_DRBG.

5. Either CMVP or CAVP (I forget which) insisted on the default P and Q.  But the stated purpose of these validation programs, IIRC, is only to protect communication with USG/CAG, in which the user is already trusting these entities extensively.  I'm not aware of any promises to protect non-USG communication in the CMVP or CAVP.

6. Modern cryptography usually likes provable security, especially in refereed conferences like CRYPTO.  Well, Dual_EC_DRBG has such an assurance.    Can anybody in CFRG suggest another DRBG with published security proof?  I've seen a preprint proof for HMAC_DRBG, but forget if it has been refereed.

7. Note, just in case you're wondering, the proof above excludes the case of a backdoor relationship between P and Q: i.e. it applies only to the alternative choices of P and Q.

8. All considered, I don't see how the ANSI and NIST standards for Dual_EC_DRBG can be viewed as a subverted standard, per se.  But maybe that's just because I'm biased or naive.

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.

---

From: Adam Back <[email-masked]>
Date: Fri, 27 Dec 2013 20:09:07 +0100

Dan Brown wrote:
> [...]
> 8. All considered, I don't see how the ANSI and NIST standards for
> Dual_EC_DRBG can be viewed as a subverted standard, per se.

Of course they're subverted.  We have Ferguson et al show how they could be
backdoored.  We have internal NSA documents reported as talking about the
subversion.  We have confirmation of RSA (inadvertently or not) accepting
money to put a EC_DRBG as a default.  You yourself just said the validation
labs are demanding the backdoored P & Q be used (and rejecting the provably
uncooked implemented chosen parameters presumably).  NIST put the standard
forward (inadvertently or not) from NSA input.

I am non-plussed at what you could be trying to say with the above
statement.

Adam

---

From: Santosh Chokhani <[email-masked]>
Date: Fri, 27 Dec 2013 19:15:03 +0000

Validation labs do not get or want money for backdoors.

So, either quit your conspiratorial nonsense or take it to Hollywood,

-----Original Message-----
From: Cfrg [mailto:[email-masked]] On Behalf Of Adam Back
Sent: Friday, December 27, 2013 2:09 PM
To: Dan Brown
Cc: Adam Back; [email-masked]'
Subject: Re: [Cfrg] Dual_EC_DRBG ... [was RE: Requesting removal of CFRG co-chair]

> Dual_EC_DRBG can be viewed as a subverted standard, per se.

Of course they're subverted.  We have Ferguson et al show how they could be backdoored.  We have internal NSA documents reported as talking about the subversion.  We have confirmation of RSA (inadvertently or not) accepting money to put a EC_DRBG as a default.  You yourself just said the validation labs are demanding the backdoored P & Q be used (and rejecting the provably uncooked implemented chosen parameters presumably).  NIST put the standard forward (inadvertently or not) from NSA input.

I am non-plussed at what you could be trying to say with the above statement.

Adam
_______________________________________________
Cfrg mailing list
[email-masked]
http://www.irtf.org/mailman/listinfo/cfrg

---

From: Adam Back <[email-masked]>
Date: Fri, 27 Dec 2013 20:47:45 +0100

I think I stayed extremely far away from anything conspiratorial, and I
remind you to please keep your responses civil.

To counter your unfounded attack, now I have to explain, I quoted Dan Brown
who said in the mail I was replying to:

> 5. Either CMVP or CAVP (I forget which) insisted on the default P and Q. 
> But the stated purpose of these validation programs, IIRC, is only to
> protect communication with USG/CAG, in which the user is already trusting
> these entities extensively.  I'm not aware of any promises to protect
> non-USG communication in the CMVP or CAVP.

I do actually have multiple first hand experiences working with
certification labs, one of them may even have been cygnacom (I forget, was
some time ago but it rings a bell).  Anyway take up your complaint with Dan
who claimed the above (offlist if you like).  All I could say first hand is
the evaluation process is typically a documentation/tracing exercise
following the letter of the relevant standards and validation procedures. 
If a lab interpreted EC_DRBG spec as requiring that specific P & Q to be
used, that could be a neutral action (or not).  Its imposible to say.

It would not be the first time at least that for procedural reasons lab
decisions have actually hindered product security from what I've heard.  The
labs job is to certify adherence to a documented standard, not to help the
company make a secure product.  Sometimes standards inflexibility conflicts
with product security.  Often you can work around it - get certification and
make a secure product.  Certification is still a useful minimum bar and
accrediation process.

If you work for cygnacom in this area, I'm sure you've come across such
conflicts yourself.

Adam

---

From: Dan Brown <[email-masked]>
Date: Fri, 27 Dec 2013 20:43:56 +0000

> From: Adam Back [mailto:[email-masked]]
> Of course they're subverted.   

> We have Ferguson et al show how they could
> be backdoored.  
 
Repeating myself, nobody showed how the alternative P&Q could be backdoored.

In other words, even if subversion were attempted, it was effectively caught
and thwarted, at least in 800-90A and X9.82-3, by two things: (a) the
alternative points, and (b) the highly publicized potential backdoor.  Of
course, (b) is outside the standard, which is why I referred to naïve and
malicious implmenters.

Arguably, the specs do not do enough to warn naïve implementers of the
backdoor.  So, I went back to look at SP 800-90A.

Section 10.3.1, first paragraph states that Dual_EC_DRBG depends on it hard
to find a such that Q=aP.  On the same page, Figure 13 outlines the
Dual_EC_DRBG, using the same notation P and Q.

So, even if a naïve implementer hadn't heard of Ferguson et al., these two
parts of the spec together spell out to the implementer the need to ensure
that a is secret, no?

In other words, the specs are fairly clear to a thorough implementer.  

I admit that the specs could be made even clearer: they could have said that
there is a potential "backdoor".  

I would even want them to clearer. 

> We have internal NSA documents reported as talking about
> the subversion.  
 
Reported, yes.  But AFAIK, not published.

> We have confirmation of RSA (inadvertently or not)
> accepting money to put a EC_DRBG as a default.  

My conclusion was regarding the standards, per se, not about
implementations. I was not drawing any conclusions about implementations.

> You yourself just said the
> validation labs are demanding the backdoored P & Q be used (and rejecting
> the provably uncooked implemented chosen parameters presumably).  

 Yes, I should clarify, I was referring to the NIST SP 800 90A and ANSI
X9.82-4 as not being subverted.  I am only vaguely familiar with CAVP and
CMVP, and was not drawing any conclusions about them.  Aside: I do not deals
with labs personally, so have nothing to say about them.

> NIST
> put the standard forward (inadvertently or not) from NSA input.

Hmm, I'm biased towards to mainly looking at documents in a context-free
manner: i.e. what they say, not who is saying it.  The way I read the specs,
nothing is being is hidden.  
 
> I am non-plussed at what you could be trying to say with the above
 
Hope my response helps you.  

I am anticipating it is too narrow.

I am a bit perplexed too: I see many statements about Dual_EC_DRBG that seem
too broad.

---

From: Henrick Hellström <[email-masked]>
Date: Fri, 27 Dec 2013 21:58:24 +0100

> implementations. I was not drawing any conclusions about implementations.

I think that is a mistake. It is a problem if a library that is widely 
used and even got certified, are using default parameters that are 
potentially backdoored. The relevant question isn't whether *any* 
standard compliant implementation will have a backdoor, but if it is 
possible to have a backdoor in an implementation and still get it certified.

That said, I am not entirely convinced NSA actually intended to put a 
backdoor in Dual EC DRBG, or rather, that this standard was part of the 
SIGINT enabling program. For all I know, it could just as well be a case 
of them generating the parameters randomly because they for some reason 
didn't trust the usual binary expansion of pi approach.

---

From: David McGrew <[email-masked]>
Date: Fri, 27 Dec 2013 16:42:27 -0500

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.

David

---

From: "Dan Harkins" <[email-masked]>
Date: Fri, 27 Dec 2013 13:45:39 -0800 (PST)

> given to implementers and standards group on the subject of PRNGs.

  Indeed! And might this discussion move to [email-masked], the
mailing list formed to discuss just this very subject?

  Dan.

---

From: Dan Brown <[email-masked]>
Date: Fri, 27 Dec 2013 23:34:46 +0000

> From: Dan Harkins
> Sent: Friday, December 27, 2013 4:46 PM
>
> > 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, 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.

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

---

From: Watson Ladd <[email-masked]>
Date: Fri, 27 Dec 2013 18:50:18 -0500

> 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.
> paid to Dual_EC_DRBG, yet no major attack since that security analysis has

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.

> been published, despite their high profile in NIST specs.  The HMAC_DRBG

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

> constructions to build a PRNG from a PRF (where for a PRF, think RC4, or

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.

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

---

From: David McGrew <[email-masked]>
Date: Mon, 30 Dec 2013 08:56:42 -0500

Hi Dan,

On 12/27/2013 06:34 PM, Dan Brown wrote:
> Maybe I'm biased,

I love the pun there ;-)

> but for a PRNG, I'd recommend Dual_EC_DRBG with

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.

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

David

---

From: Watson Ladd <[email-masked]>
Date: Mon, 30 Dec 2013 09:52:32 -0500

On Mon, Dec 30, 2013 at 8:56 AM, David McGrew <[email-masked]> wrote:
> 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

> 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: Alyssa Rowan <[email-masked]>
Date: Mon, 30 Dec 2013 15:10:44 +0000

> Repeating myself, nobody showed how the alternative P&Q could be

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

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

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.

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

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

- -- 
/akr