Subject: [TLS] Extended random is NSA backdoor

From: Watson Ladd <[email-masked]>
Date: Mon, 31 Mar 2014 07:24:50 -0700

Dear all,
Reuters reports
"The NSA played a significant role in the origins of Extended Random.
The authors of the 2008 paper on the protocol were Margaret Salter,
technical director of the NSA's defensive Information Assurance
Directorate, and an outside expert named Eric Rescorla.

Rescorla, who has advocated greater encryption of all Web traffic,
works for Mozilla, maker of the Firefox web browser. He and Mozilla
declined to comment. Salter did not respond to requests for comment."

I'd like some explanation, particularly given that
draft-rescorla-tls-extended-random-02 contains nothing resembling an
explanation for why the randomness needs to be extended if ECDHE is
being used, which it is on all DoD applications. Furthermore, this
confirms that the IAD inserts backdoors into products.

For those who aren't aware, extended random makes it easier to exploit
the Dual EC PRNG.

Sincerely,
Watson Ladd

---

From: Paul Ferguson <[email-masked]>
Date: Mon, 31 Mar 2014 07:27:59 -0700

On 3/31/2014 7:24 AM, Watson Ladd wrote:

> Dear all, Reuters reports "The NSA played a significant role in the
> origins of Extended Random. The authors of the 2008 paper on the
> protocol were Margaret Salter, technical director of the NSA's
> defensive Information Assurance Directorate, and an outside expert
> named Eric Rescorla.
> 
> works for Mozilla, maker of the Firefox web browser. He and
> Mozilla declined to comment. Salter did not respond to requests for
> comment."
> 

Please provide a pointer for this reference.

Thanks,

- - ferg

> draft-rescorla-tls-extended-random-02 contains nothing resembling
> an explanation for why the randomness needs to be extended if ECDHE
> is being used, which it is on all DoD applications. Furthermore,
> this confirms that the IAD inserts backdoors into products.
> 
> For those who aren't aware, extended random makes it easier to
> exploit the Dual EC PRNG.
> 
> Sincerely, Watson Ladd
> 
> _______________________________________________ TLS mailing list 
> [email-masked] https://www.ietf.org/mailman/listinfo/tls
> 
> 

- -- 
Paul Ferguson
VP Threat Intelligence, IID
PGP Public Key ID: 0x54DC85B2

---

From: Adam Langley <[email-masked]>
Date: Mon, 31 Mar 2014 10:29:34 -0400

> Please provide a pointer for this reference.

http://www.reuters.com/article/2014/03/31/us-usa-security-nsa-rsa-idUSBREA2U0TY20140331
I believe.

Note that it's reporting on a paper that has yet(?) to be made public.

Cheers

AGL

---

From: Stephen Checkoway <[email-masked]>
Date: Mon, 31 Mar 2014 10:36:18 -0400

On Mar 31, 2014, at 10:24 AM, Watson Ladd <[email-masked]> wrote:

> Furthermore, this confirms that the IAD inserts backdoors into products.

Our results <dualec.org> say nothing about whether NIST, the NSA, or anyone else inserted a backdoor into dual ec. Instead, they say that if you know the relationship between P and Q, then some TLS implementations can be broken at a given cost. The precise results are more nuanced than that. You can read the website for a summary or the paper for the details.

-- 
Stephen Checkoway

---

From: Paul Ferguson <[email-masked]>
Date: Mon, 31 Mar 2014 07:39:08 -0700

On 3/31/2014 7:29 AM, Adam Langley wrote:

>>> Rescorla, who has advocated greater encryption of all Web
>>> traffic, works for Mozilla, maker of the Firefox web browser.
>>> He and Mozilla declined to comment. Salter did not respond to
>>> requests for comment."
>>> 
I believe.
> Note that it's reporting on a paper that has yet(?) to be made

I would very much appreciate a pointer to the paper when it becomes
available.

Thanks,

- - ferg

- -- 
Paul Ferguson

---

From: Tom Ritter <[email-masked]>
Date: Mon, 31 Mar 2014 10:40:49 -0400

Looks like this has the technical details: http://dualec.org/

-tom

---

From: Paul Ferguson <[email-masked]>
Date: Mon, 31 Mar 2014 07:45:16 -0700

> Looks like this has the technical details: http://dualec.org/

Gracias.

- - ferg

- -- 
Paul Ferguson

---

From: Rene Struik <[email-masked]>
Date: Mon, 31 Mar 2014 11:33:07 -0400

Dear colleagues:

Not sure what is new here. The paper (with an impressive list of nine 
(!) co-authors) seems to be simply a validation of results already 
described in the Crypto 2007 rump session paper by Ferguson et al and in 
the teachings of a 2005 US patent application.

Best regards, Rene

On 3/31/2014 10:45 AM, Paul Ferguson wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA256
>
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v2.0.22 (MingW32)
> Comment: Using GnuPG with Thunderbird - http://www.enigmail.net/
>
> iF4EAREIAAYFAlM5f3wACgkQKJasdVTchbKYNgEAiwR5zR2qfSRfdEkXQx7CihyY
> QD3xZG9bkx8+40Gc+BYA/Avz/59WC1sv8KodlV4Z81rJqMF8uKrrxn2A6SR80lgC
> =NxYj
> -----END PGP SIGNATURE-----
>
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tls

-- 
email: [email-masked] | Skype: rstruik
cell: +1 (647) 867-5658 | US: +1 (415) 690-7363

---

From: Jacob Appelbaum <[email-masked]>
Date: Mon, 31 Mar 2014 15:46:24 +0000

> the teachings of a 2005 US patent application.

I was unaware that Ferguson et al did an internet wide scan or found
the speedup for the vulnerabilities? It seems to me that this work
confirms and expands on the previous research.

The intentions for such an implemention are also seemingly confirmed
thanks to the bravery of the whistleblower Edward Snowden.

Context is everything.

All the best,
Jacob

---

From: Trevor Perrin <[email-masked]>
Date: Mon, 31 Mar 2014 09:06:24 -0700

Hi Rene,

The revelation that NSA used this Working Group in an attempt to
promote TLS extensions which amplify the backdoor is new:

https://datatracker.ietf.org/doc/draft-rescorla-tls-opaque-prf-input/
https://datatracker.ietf.org/doc/draft-rescorla-tls-extended-random/

Trevor

On Mon, Mar 31, 2014 at 8:33 AM, Rene Struik <[email-masked]> wrote:
> Dear colleagues:
>
> Not sure what is new here. The paper (with an impressive list of nine (!)
> co-authors) seems to be simply a validation of results already described in
> the Crypto 2007 rump session paper by Ferguson et al and in the teachings of
> a 2005 US patent application.
>
> Best regards, Rene
>
>
>
>> - -- Paul Ferguson

---

From: Stephen Checkoway <[email-masked]>
Date: Mon, 31 Mar 2014 12:22:25 -0400

Hi all,

I can't speak to anyone's intentions, but note that these aren't the only I-Ds that add more randomness. As described in our paper, <http://tools.ietf.org/html/draft-hoffman-tls-additional-random-ext-01> is quite similar.

The idea of adding more random bits seems to have been fairly popular in the 2006-2010 timeframe.

There may be more proposals to do this, for example using <http://tools.ietf.org/html/rfc6358>, that I missed.

S

-- 
Stephen Checkoway

---

From: "Dan Harkins" <[email-masked]>
Date: Mon, 31 Mar 2014 09:55:58 -0700 (PDT)

Hi Trevor,

> https://datatracker.ietf.org/doc/draft-rescorla-tls-extended-random/

  By "backdoor" do you mean Dual_EC:DRBG? If so, what do you mean by
"amplify the backdoor"?

  Dan.

>> (!)

---

From: "Dan Harkins" <[email-masked]>
Date: Mon, 31 Mar 2014 10:02:15 -0700 (PDT)

Strike that; I found it.

  Dan.

On Mon, March 31, 2014 9:55 am, Dan Harkins wrote:
>>> co-authors) seems to be simply a validation of results already
>>> described
>>> in

---

From: Stephen Farrell <[email-masked]>
Date: Mon, 31 Mar 2014 20:04:47 +0100

On 03/31/2014 05:22 PM, Stephen Checkoway wrote:
> There may be more proposals to do this, for example using 
> <http://tools.ietf.org/html/rfc6358>, that I missed.

I took a quick look and didn't yet find any in
Jari's RFC references thing [1] or the tools WG
draft dependency thing [2] or the datatacker
equivalent. [3] Not much to see in Google scholar
either. [4]

S.

[1] http://www.arkko.com/tools/allstats/citations-rfc6358.html
[2] http://www.fenron.net/~fenner/ietf/deps/viz/tls.pdf
[3] https://datatracker.ietf.org/doc/rfc6358/referencedby/
[4]
http://scholar.google.com/scholar?q=http%3A%2F%2Fwww.hjp.at%2Fdoc%2Frfc%2Frfc6358.html&btnG=&hl=en&as_sdt=0%2C5

---

From: Russ Housley <[email-masked]>
Date: Mon, 31 Mar 2014 15:12:42 -0400

I'd like to make a few observations about the extended random extension.  At the time, I supported the creation of the extension.  I was concerned about one of the TLS parties having a poor random source (which is quite different than random number generator with a backdoor).  Recall that a predictable random number generator was discovered in the Debian release about this time [1].  It is rather scary that it took so many months for this flaw to be noticed after it was released in September 2006; the problem was not reported until May 2008.  In this context, I was interested in getting as enough quality bits from the good random source into the calculation of the session values to overcome the poor contribution from the other side.

No one was talking about the possibility of the additional public random values disclosing the state of a random number generator with a backdoor.  While that seems like a relevant question today, it was not considered at the time.  We were discussion weak random sources and quality random sources.  If a random number generator with a backdoor was raised back then, I'm not sure it would have gotten the same attention as today.  I might have said: if you think ABC_DRNG might have a backdoor, then use a different one instead.

So the same extended random extension might have:
(1) provided additional random from one other side to compensate for poor values from the other, and at the same time
(2) provided a means for a a random number generator with a backdoor to disclose state.

As the IETF decided at the time, the better answer is quality random numbers all around.

Russ

[1] http://en.wikinews.org/wiki/Predictable_random_number_generator_discovered_in_the_Debian_version_of_OpenSSL

---

From: Marsh Ray <[email-masked]>
Date: Mon, 31 Mar 2014 23:28:46 +0000

-----Original Message-----
From: Russ Housley

> Recall that a predictable random number generator was discovered in the Debian release
> about this time [1].  It is rather scary that it took so many months for this flaw to be
>  noticed after it was released in September 2006; the problem was not reported until
>  May 2008.  In this context, I was interested in getting as enough quality bits from the
>  good random source into the calculation of the session values to overcome the poor
>  contribution from the other side.

It's the old difficult distinction between 'entropy' and 'pseudorandomness'.

IIRC, the Debian bug put a ceiling of only 15 bits of entropy, ever, for the entire process. So it was too broken to really matter there. But Dual EC is an example of a PRNG with a feature where observing more bits makes life easier for an attacker who knows the backdoor key. Is there another mainstream example since 64-bit block ciphers?

The short 96-bit Finished message data in TLS is an example of the design limiting the number of bits which emerge from a PRNG. The only explanation I can see for it being so short is that someone didn't want to emit near as much output as there was entropy going into the master secret.

If there is an invisible hand at work here (across the decades) it is either schizophrenic or wants us to believe so.

> If a random number
> generator with a backdoor was raised back then, I'm not sure it would have gotten the same
> attention as today.

I think you may be right.

http://rump2007.cr.yp.to/15-shumow.pdf
On the Possibility of a Back Door 
in the NIST SP800-90 Dual Ec Prng 
Dan Shumow, Niels Ferguson, Microsoft

Schneier even had a whole article about it in Wired, but the link seems broken now.
http://www.wired.com/politics/security/commentary/securitymatters/2007/11/securitymatters_1115

- Marsh
My own personal opinions, usual disclaimers apply.

---

From: Nico Williams <[email-masked]>
Date: Mon, 31 Mar 2014 19:31:44 -0500

If this is in reference to Dual_EC, well, TLS has always had enough
bytes of nonce to exploit the conjectured Dual_EC backdoor (assuming
one did not feel forced to send the 32 bits of Unix time, which,
indeed, some libraries _don't_).

The Reuters article doesn't provide a real source, just a source of
speculation, so it's hard to say.  It seems like a plausible attack
because of the 32-bit Unix time, and because the normal 32-byte nonces
might not be a contiguous 32-byte output of Dual_EC.  And because
there was no pressing need for extra entropy.

Note that even if this really was the intention of RSA/NSA at the
time, EKR might not have known it.

Nico
--

---

From: Nico Williams <[email-masked]>
Date: Mon, 31 Mar 2014 19:46:11 -0500

On Mon, Mar 31, 2014 at 2:12 PM, Russ Housley <[email-masked]> wrote:
> [...]

Under no circumstance does sending more nonce bits help palliate a
weak RNG.  On the contrary, doing so can only make the sender more
susceptible to attack.  In 2006 we would all have understood this.

Now, the I-D in question are very explicit as to motivation:

   The United States Department of Defense has requested a TLS mode
   which allows the use of longer public randomness values for use with
   high security level cipher suites like those specified in Suite B
   [I-D.rescorla-tls-suiteb].  The rationale for this as stated by DoD
   is that the public randomness for each side should be at least twice
   as long as the security level for cryptographic parity, which makes
   the 224 bits of randomness provided by the current TLS random values
   insufficient.

That's not likely to have raised eyebrows much in 2006 -- that is
true.  Even with knowledge of backdoored RNG designs it might not now
(because that's a local problem now as ever).

(If we were to always use ECDHE then the nonces could be sent
encrypted in the ECDHE shared secret.  This wouldn't prevent either
party from using the nonce payload as a covert channel though, and
neither party can do anything to preclude the other from leaking state
in-band via their nonces, encrypted or otherwise, much less out of
band.)

Nico
--

---

From: Michael D'Errico <[email-masked]>
Date: Mon, 31 Mar 2014 18:51:19 -0700

> indeed, some libraries _don't_).

Would a mitigation be to take 64 bytes of DRBG output, run it through
SHA-256 and use the result as the 32-byte (client|server) random?

Mike

---

From: Watson Ladd <[email-masked]>
Date: Mon, 31 Mar 2014 19:02:58 -0700

> susceptible to attack.  In 2006 we would all have understood this.

That's why these remained I-Ds.

> (because that's a local problem now as ever).

Huh? Even if the RNG is perfectly fine, I don't see what adding more
random information in to the master secret derivation does. That
motivation was questioned in 2006 because it doesn't make any sense.
The reason server random and client random exist is to avoid replay
attacks, and 32 bytes is wildly overkill for this. They don't add
anything to the difficulty for an attacker. It's a completely
meaningless rationale.

The RFC permitting adding extra data into master secret derivation was
actually motivated: one would ideally hash identities in, as was
discovered very recently. But it doesn't take the extra step of
actually fixing the issues, which we still have to do.

Sincerely,
Watson Ladd

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

---

From: Nico Williams <[email-masked]>
Date: Mon, 31 Mar 2014 21:21:07 -0500

> SHA-256 and use the result as the 32-byte (client|server) random?

Yes.  You don't need 64 bytes either.  Just 32, or 24 even, would
suffice.  The Dual_EC outputs have structure which is needed in order
to exploit the putative backdoor.  Hashing makes that structure
inaccessible to the attacker.

Nico
--

---

From: Nico Williams <[email-masked]>
Date: Mon, 31 Mar 2014 21:26:56 -0500

> That's why these remained I-Ds.

I didn't do the necessary list archive-ology.  Good to know that my
supposition was right.

> anything to the difficulty for an attacker. It's a completely

For me the main problem with sending more nonce bytes is that it
increases the bandwidth of a covert channel -- a more general case of
making weak RNGs more susceptible to attack.  But it seems reasonable
_at first glance_ (which is what I meant above) to say that to get X
bits of security you need a cipher with X bits of key, PK algorithms
with X bits equivalent security, and X bits of nonce from each party.

> actually fixing the issues, which we still have to do.

Or channel binding.  But one need not send the channel binding data
when doing channel binding!

Nico
--

---

From: Nico Williams <[email-masked]>
Date: Mon, 31 Mar 2014 21:47:43 -0500

BTW, if the only concern is replay protection then much less entropy
will suffice since the birthday paradox is the only real concern then.
 Coarse timestamps do help increase the value of smaller nonces by
allowing the use of a replay cache, but reliable, high-performance
replay caching is very difficult to implement correctly.  Still,
assuming no replay caching I'd say that 28 bytes is overkill indeed.