Roeckx: State of encryption

[Posted September 10, 2013 by jake]

On his blog, Kurt Roeckx rounds up the current state of encryption, especially as it relates to Secure Sockets Layer/Transport Layer Security (SSL/TLS). He looks at key lengths, techniques (like Diffie-Hellman for perfect forward security), ciphers, random numbers, and existing software, showing where the likely vulnerabilities lie. "A lot of the algorithms depend on good random numbers. That is that the attacker can't guess what a (likely) random number you've selected. There have been many cases of bad RNG [random number generator] that then resulted in things getting broken. It's hard to tell from the output of most random number generators that they are secure or not. One important thing is that the RNGs gets seeded with random information (entropy) to begin with. If it gets no random information, very limited amount of possible inputs or information that is guessable as input it can appear to give random numbers, but they end up being predictable There have been many cases where this was broken."

Roeckx: State of encryption

Posted Sep 11, 2013 11:09 UTC (Wed) by Seegras (guest, #20463) [Link] (8 responses)

He's recommending using Elliptic Curve Algorithms.

Bruce Schneier says: "Prefer conventional discrete-log-based systems over elliptic-curve systems; the latter have constants that the NSA influences when they can."

See here
http://www.wired.com/politics/security/commentary/securit...
And here:
http://rump2007.cr.yp.to/15-shumow.pdf

Roeckx: State of encryption

Posted Sep 11, 2013 12:14 UTC (Wed) by Otus (subscriber, #67685) [Link] (7 responses)

He also linked to a proposal [1] that suggests making elliptic curve key exchange the default for browsers. Seems it already is for mine. That document explains the rationale: only the EC protocol supports parameter negotiation.

[1] https://briansmith.org/browser-ciphersuites-01.html

Roeckx: State of encryption

Posted Sep 11, 2013 12:38 UTC (Wed) by gidoca (subscriber, #62438) [Link] (6 responses)

It seems that the documents Seegras linked to only talk about elliptic curve-based PRNGs. Is there any specific reason to assume that other elliptic curve-based algorithms might also be compromised, other than "it makes sense from the NSA's point of view to do so"?

Roeckx: State of encryption

Posted Sep 11, 2013 15:43 UTC (Wed) by Seegras (guest, #20463) [Link]

See also: http://cr.yp.to/talks/2013.05.31/slides-dan+tanja-2013053...
So there are specific seeds for NIST-standardized curves, that were supplied by the NSA. No explanations given.

To be fair, the NSA also supplied the S-boxes for DES, and it turned out years later that they made DES much stronger.

However, I think the NSA has gone over the dark side some time in the last few years. There was a paradigm shift from an "open" NSA in service of the public ("let's make everyone more secure, so our allies will be more secure too") to a cyberwar operation ("let's hoard exploits and subvert everything so we can attack everyone"). With "allies" I include all other US government agencies; with "everyone" also...

Roeckx: State of encryption

Posted Sep 11, 2013 17:29 UTC (Wed) by intgr (subscriber, #39733) [Link] (2 responses)

The EC PRNG really was elephant in the room. Other elliptic curve crypto is much, much less suspicious -- when used purposefully for public-key encryption. (Though classical RSA/DSA/DH/ElGamal are still more proven)

PRNGs are usually based on symmetric cryptography components (ciphers or hash functions), which are fast and straightforward. Conversely, elliptic curve math is used in public-key cryptography, which is relatively slow, but allows for separating private and public keys.

Why would anyone design a PRNG that's over 100 times slower than the rest, using techniques that are totally inappropriate to its problem domain? Techniques which are intended for two-party communication. Who's the "other party" to a PRNG? Well, it's the NSA of course!

Fortunately, due to its bad performance and complexity, the PRNG probably wasn't used in any significant places.

RSA Security and DUAL_EC_DRBG

Posted Sep 11, 2013 23:25 UTC (Wed) by brugolsky (guest, #28) [Link] (1 responses)

Apparently, RSA Security BSAFE Share for Java 1.1 has DUAL_EC_DRBG as a default:

"The default Pseudo Random Number Generator (PRNG) is the Dual EC-DRBG using a P256 curve with prediction resistance off."

I didn't find an obvious link for the equivalent C/C++ library documentation, but the RSA BSAFE CNG Cryptographic Primitives Library 1.0 FIPS 140-1 Security Policy document from RSA Security at the NIST site says (p.14):

"The Module provides a default RNG, which is the Dual EC DRBG, using a P256 curve and SHA-256."

Additionally, the RSA BSAFE Crypto-C Micro-Edition 3.0.0.2 FIPS 140-1 Security Policy says (p.17):

"For R_FIPS140_MODE_FIPS140_ECC and R_FIPS140_MODE_FIPS140_SSL_ECC, Crypto-C ME implements a Dual ECDRBG (Cert. #137) internally"

I'd be more than a bit wary of any product using RSA Security libraries.

RSA Security and DUAL_EC_DRBG

Posted Sep 11, 2013 23:31 UTC (Wed) by brugolsky (guest, #28) [Link]

Oops, sorry, wrong link:

RSA Security BSAFE Share for Java 1.1

Roeckx: State of encryption

Posted Sep 11, 2013 17:54 UTC (Wed) by lsl (subscriber, #86508) [Link] (1 responses)

> Is there any specific reason to assume that other elliptic curve-based algorithms might also be compromised, other than "it makes sense from the NSA's point of view to do so"?

Bruce explained the statement over at his blog (in the comments). His reasoning was along the line of: there are constants involved and he has no idea how and why the designers arrived at those constants.

From that you can conclude to which ECC algorithms his suggestion applies.

Roeckx: State of encryption

Posted Sep 12, 2013 2:49 UTC (Thu) by wahern (subscriber, #37304) [Link]

You can see the problem yourself in Appendix A of the standard: http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf

Basically, Appendix A specifies the PRNG algorithm for generating the curve constants. You generate a seed and iteratively hash it with a counter. But the seed chosen which generated the specified constants is completely opaque. For all we know, the NSA tried billions of different seeds until one generated parameters to its liking within the odd 4096 iteration limit. Then they tied it up in a bow and handed it off to NIST.

Why limit the counter for each seed to 4096? It seems downright Rube Goldbergian. Why nobody found this fishy before is beyond me. Or maybe people did but the community couldn't bring itself to care.

The Open Source community should be using its own curves. DJB published a curve that he says is more secure _and_ faster. OpenSSL and libgcrypt should support this and other similar ones, as well as usher their addition into open standards.

Roeckx: State of encryption

Posted Sep 11, 2013 13:10 UTC (Wed) by Lennie (subscriber, #49641) [Link] (8 responses)

So what is a good way to check if a random number generator produces good random numbers ? Or what is a good random source ?

I found dieharder but it clearly isn't a 'run a few times and if everything passes life is good' tool.

For example I found out the Raspberry Pi has a hardware random number generator.

I took 3.1 GB of random data from the Raspberry Pi hardware random number generator (which isn't very fast or enough to prevent some tests rewinding the data) and it said 2 tests failed.

While the Linux 3.10 kernel /dev/random on my i7 desktop machine (no RdRand) with haveged running had 4 tests fail.

Does that mean I should trust the Raspberry Pi more ?

It just isn't that simple is it ? ;-)

Roeckx: State of encryption

Posted Sep 11, 2013 15:13 UTC (Wed) by cesarb (subscriber, #6266) [Link] (7 responses)

A good cryptographic random number generator will return results indistinguishable from random noise, even if it is hopelessly broken.

For instance, the popular cryptographic random number generator Yarrow (and its successor Fortuna, which is the one I would recommend) uses as its core a common block cipher in counter mode, with the state as the key. Good block ciphers have an output which are indistinguishable from random noise.

When a cryptographic RNG is broken, the problem is usually not with the part which generates the output, but with the state. If for instance some bug within the RNG causes the state to only have 65536 possible values, you cannot discover it by just looking at the output - it will look as random as the output of a working RNG, no matter which test you use. But if you know just *how* the state is broken, you will be able to guess it.

So, no, sorry, you cannot prove a cryptographic RNG as secure just by looking at its output. You really have to audit the code. A few test vectors help checking that it is implementing the algorithm correctly, but they cannot test the important part: that it is actually being seeded, and with enough bits of entropy.

Roeckx: State of encryption

Posted Sep 11, 2013 22:26 UTC (Wed) by nix (subscriber, #2304) [Link] (2 responses)

And, of course, if the 'code' includes tables of constants, you have to know how the constants were derived, and even if that looks safe enough you have to trust that those constants were not derived using that method entirely *because* the attacker has a means of breaking that method that nobody else knows about. (Sure, the latter would be excessive paranoia... except when dealing with major government crypto agencies. Having ways, ideally multiple ways, of breaking cryptographic algorithms that nobody else knows about is what they are *for*, and always have been, ever since the Bletchley Park days.)

With the NSA's constants (be it the S-boxes provided for DES, or the NIST curves) we know none of this.

Roeckx: State of encryption

Posted Sep 12, 2013 14:37 UTC (Thu) by robbe (guest, #16131) [Link] (1 responses)

A link to https://en.wikipedia.org/wiki/Nothing_up_my_sleeve_number is apropos here.

Roeckx: State of encryption

Posted Sep 16, 2013 16:56 UTC (Mon) by nix (subscriber, #2304) [Link]

Thank you for that, a lovely term I wasn't aware of.

Roeckx: State of encryption

Posted Sep 12, 2013 14:39 UTC (Thu) by robbe (guest, #16131) [Link] (3 responses)

> If for instance some bug within the RNG causes the state to only have
> 65536 possible values, you cannot discover it by just looking at the output

Wouldn't a cycle length of 65536 be detected pretty easily?

Roeckx: State of encryption

Posted Sep 12, 2013 17:42 UTC (Thu) by Cyberax (✭ supporter ✭, #52523) [Link]

Khm. Do you remember the OpenSSL fiasco?

(PS: yes, it was actually caused by Kurt Roecxx, so you he's speaking from experience)

Roeckx: State of encryption

Posted Sep 12, 2013 18:00 UTC (Thu) by nybble41 (subscriber, #55106) [Link]

> Wouldn't a cycle length of 65536 be detected pretty easily?

I imagine the 65536 states would not include the previous output of the RNG, which is generally part of the input for the next round. Due to the feedback there wouldn't necessarily be an obvious cycle. However, given a part of the RNG's output, you would only have to search 2**15 values on average to find the state corresponding to that point in the stream, allowing you to predict all the RNG's output from that point on.

Roeckx: State of encryption

Posted Sep 12, 2013 18:49 UTC (Thu) by wtanksleyjr (subscriber, #74601) [Link]

Not if the whitening function had a relatively prime period, or worse, a variable period. And cycle lengths are only one of the possible problems.

Roeckx: State of encryption

Posted Sep 12, 2013 22:46 UTC (Thu) by zooko (guest, #2589) [Link]

This was a relatively uninformative article about the state of encryption. Here are some recent articles that I found to be more interesting:

* Matthew Green: http://blog.cryptographyengineering.com/2013/09/on-nsa.html
* Matthew Green's follow-up: http://blog.cryptographyengineering.com/2013/09/a-note-on...
* Bruce Schneier: https://www.schneier.com/blog/archives/2013/09/the_nsas_c...
* Bruce Schneier again: http://www.theguardian.com/commentisfree/2013/sep/05/gove...
* EFF recent blog post: https://www.eff.org/deeplinks/2013/08/tahoe-and-tor-build... (disclosure: that blog entry is praising my project — Tahoe-LAFS, so of *course* I think it is a good post!)
* EFF "surveillance self-defense" (precedes the Snowden leaks): https://ssd.eff.org/wire/protect
* Freedom Of The Press Foundation "Encryption Works": https://pressfreedomfoundation.org/encryption-works

Roeckx: State of encryption

Posted Sep 16, 2013 5:38 UTC (Mon) by glaesera (guest, #91429) [Link] (1 responses)

In my opinion elliptic curve cryptography is not recommended at this time, because free implementations do not exist yet. Maybe the mathematics are not fully understood, on my behalf I confess, that I don't understand them, but I am not a coder, so it is less of a problem.
Possible vulnerabilities to quantum-computer attacks are a minor issue, also it would be possible to use longer keys there, too, if necessary.

Roeckx: State of encryption

Posted Sep 16, 2013 21:52 UTC (Mon) by wahern (subscriber, #37304) [Link]

Free (i.e. FOSS) implementations absolutely exist, including OpenSSL, libnettle (GnuTLS), libgcrypt (GnuPG)... they're too numerous to mention.

They're also largely free from patent encumbrances because the algorithms and most of the tricks have been around for longer than 20 years.