Comments

Bill Zimmerman • September 25, 2013 9:28 AM

Maybe it’s the budding conspiracy buff in me, but is it possible that bitcoin is just distributing the math to break encryption algorithyms? Right now I’m the subject of what can only be described as extreme gov harassment and I’ve been thinking about these things.

Clive Robinson • September 25, 2013 9:45 AM

OK Devil’s Advocates hat on time 😉

Many assume that the weakness is “to ham fisted” and “lacks the subtal finess” that you would expect from an organisation that unofficialy bills it’s self as the best in the world.

So lets assume it was the NSA and it was deliberatly ham fisted, what does that get them?

It might be a lightening rod for other more subtal attacks on the same standard.

Or it might be to encorage people not to use any of the generators in the standard.

One thing we do know thanks to Stuxnet & Co is that the NSA know a lot more about hashes than the open crypto community does.

It’s possible they know not just another way to find collisions but potentialy how to partialy or fully reverse a hash. If they do then any DRNG based on hash functions is now going to be under the spot light.

Now taking of the DA’s hat, what we are left with is a mess equivelent to the opening text from the first Internet connected MUD hosted at Essex University UK.

The question iw which twisty little passage is the right one…

Wael • September 25, 2013 10:03 AM

@ Clive Robinson,

One thing we do know thanks to Stuxnet & Co is that the NSA know a lot more about hashes than the open crypto community does.

The military is at least 40 years ahead of the open crypto community. This is known before Stuxnet… Leave your hat on;)

It’s possible they know not just another way to find collisions but potentialy how to partialy or fully reverse a hash. If they do then any DRNG based on hash functions is now going to be under the spot light.

No one can reverse a hash under normal conditions. The information is lost and is irrecoverable. Even if you we’re successful in reversing a hash, you still would not be sure you reversed it properly, you may have found a collision. It’s called a one way trap door function for a reason. As Dr. Clifford Stoll said once: a hash is like guacamole and you can’t make an avocado out of guacamole — I’m paraphrasing, been so long since i read his book or saw him on tv. You can take the hat off now 🙂

Ssargon • September 25, 2013 10:53 AM

Fully reversing a hash would give us the worlds best compression algorithm by a huge margin so no, I am convinced that is totally impossible. 🙂

zuc • September 25, 2013 11:21 AM

The reverse of an N-bit hash is obviously not unique, but gives a series of solutions, ~1 N-bit string, ~2 N+1-bit strings, ~4 N+2-bit strings etc. If you know something about the expected result (eg it contains only ASCII characters) then it may be a severe enough constraint that the reverse hash is unique. Dont dismiss the devil so quickly.

Jacob • September 25, 2013 11:36 AM

@Ssargon – would you also be that convinced if we limit ourselves to a theoretical argument about reversing a hash of a password, which is normally shorter that the hash output?

Chris B • September 25, 2013 11:47 AM

Since Clive is one of the savviest posters here, I’m going to give him the benefit of the doubt, and say he meant “reverse” as in “generate collisions,” rather than “recover plaintext.”

Wael • September 25, 2013 12:15 PM

@ zuc,

Dont dismiss the devil so quickly.

If this comment is directed towards me, then I didn’t – I had a small disclaimer under normal conditions… Some of the not so normal conditions in the case of RND are:

  • An entropy input that is smaller than the output size of the hash, meaning information is not lost.
  • A known size of the input, gives another hint
  • Finding a collision is more likely to be the real input, given the above two conditions — I have not thought much about that, but seems rational

Wael • September 25, 2013 12:20 PM

@ Chris B,

Since Clive is one of the savviest posters here, I’m going to give him the benefit of the doubt, and say he meant “reverse” as in “generate collisions,” rather than “recover plaintext.”

This is not “Clive Robinson”, this is his Devils’ advocate 😉 who’s apparently not as savvy as @ Clive Robinson. lol

Wael • September 25, 2013 12:29 PM

@ Ssargon,

Fully reversing a hash would give us the worlds best compression algorithm by a huge margin so no, I am convinced that is totally impossible. 🙂

Strange argument! You are basing the impossibility of reversing a hash on the prdicate that the worlds best compression algorithm by a huge margin cannot exist…

Clive Robinson • September 25, 2013 12:42 PM

@ Wael,

In the supposed usage of a hash function in a chain of 2 or more hashes then yes the Clifford Stoll argument is correct.

However if you only use the hash once it’s a mapping function from input to output that means for any given input there is a single known output otherwise it would be usless as a hash.

Now as has been seen with passwords you can make a lookup dictionary of known inputs to outputs.

The more you constrainthe input the easier this task is.

However if you can work a bit backwards with beter than 0.5 probability even if it’s 5.00…1 you can use this as being indicative of an input or set of inputs.

Each bit you can make a better than even guess on reduces the size of the task.

Now I may be being overly cautious, but hashes were designed so that finding a collison was not supposed to be possible in a reasonable time frame even with exceptionaly large resources. We know that this criteria has been broken in atleast to different ways in what is fairly short order (just a handfull of years).

Now ask yourself a question if the likes of the NSA are X number of years ahead of the open community, who have broken one criteria of a hash in a fraction of X what else could the closed community of the NSA et al who arguably have several times the number of cryptographers there are in the open community have done in that time. Especialy when you consider that the closed comunity don’t have a “publish or be damed” ethos driving them down the “grab a quick result” route of research, which means they are in it for the season not the first kick of the first game of the season.

It would thus be prudent to take a few simple precautions when using hashes after random number generation that is suspected of deliberate bias or kleptography. So firstly consider chain hashing with a minimum of four hashes and whiten the input to each hash in some way that is unknown to potential attackers.

As I’ve said when it comes to RNGs verify the trust, and if you cann’t verify mitigate. Caution is your friend and it’s not exactly expensive in the total cost of the system.

Nick P • September 25, 2013 12:47 PM

Let me illustrate my line of thinking so it’s real simple for anyone still wondering about backdoor or not.

10+ Years Old News

  1. NSA has more math geeks & cryptographers than anyone.
  2. NSA has been ahead of public state of the art in the past.
  3. NSA has produced and evaluated more cryptosystems than any other organization.
  4. NSA pushed deliberately weak standards (e.g. DES 40/56) on Americans to allow an effective backdoor.

  5. NSA was accused of (& sometimes proven to be) working with companies, incl. crypto vendors, to weaken their crypto as a backdoor.

Post-Snowden Leaks

  1. NSA influenced companies, including Microsoft, to backdoor their products/services.

  2. NSA manipulated standards, including some NIST promote, to weaken their crypto.

So, it logically follows that…

  1. The amateurish and vulnerable RNG that NSA contributed to a standard, used in a Microsoft product, and promoted heavily is an intentional backdoor.

I mean, it’s the NSA. The crypto would be as good as they want it to be. If they didn’t want it secure, their previous track record says they’d subvert it and make it look accidental/esoteric. That’s what happened. They did it on purpose. QED.

Jeremy • September 25, 2013 2:36 PM

This quote from the article stuck out to me:

“What’s mathematically creative [with this algorithm] is that when you look at it, you can’t even prove whether there is a backdoor or not, which is very bizarre in cryptography,” he [Paul Kocher] says. “Usually the presence of a backdoor is something you can prove is there, because you can see it and exploit it…. In my entire career in cryptography, I’ve never seen a vulnerability like this.”

If I’ve understood the discussion, this backdoor (if that’s what it is) apparently has some interesting and unusual properties: you can’t definitively prove it exists, and you can’t take advantage of it unless you have the “secret numbers”. I.e. it is both deniable and unusable by third parties. Those both sound like extremely useful properties for a back door to have.

This makes all the arguments that the NSA wouldn’t do something so ham-fisted seem pretty weak to me; if no one else knows how to build a backdoor with those properties at all, then isn’t it plausible that the NSA could only get them by being ham-fisted, and that someone there decided that was worth it?

(This is a genuine question; I am not an expert.)

Given the choice between (1) a backdoor that will take years to be discovered but will subsequently be blamed on me and make the algorithm vulnerable to all attackers, and (2) a backdoor that will be discovered quickly but that only I can ever use and that no one can ever be sure really truly exists…I can at least imagine choosing the second option.

Douglas Knight • September 25, 2013 3:22 PM

Clive, what do stuxnet and flame demonstrate about hash capabilities? They had md5 collisions, but those could be achieved by open methods at government prices.

Wael • September 25, 2013 3:48 PM

@ Clive Robinson,

In the supposed usage of a hash function in a chain of 2 or more hashes then yes the Clifford Stoll argument is correct.

The Clifford Stoll argument was made about 24 years ago. Technology has advanced so much that I am leaning to agree with you, even more so under the not so normal conditions.

Ethos • September 25, 2013 4:48 PM

Jeremy
“What’s mathematically creative [with this algorithm] is that when you look at it, you can’t even prove whether there is a backdoor or not, which is very bizarre in cryptography,” he [Paul Kocher] says. “Usually the presence of a backdoor is something you can prove is there, because you can see it and exploit it….”

NSA must have some major geniuses working for them. Or space aliens;-P

Wael • September 25, 2013 5:18 PM

@ Jermey,

NSA must have some major geniuses working for them. Or space aliens;-P

The “Geniuses” are expected. The part about Aliens is not funny, sorry…

Replace the “or” with an “and”, then I am with you!
The truth is out there, trust no one — The X-files

Clive Robinson • September 25, 2013 5:41 PM

@ Jeremy,

    If I’ve understood the discussion, this backdoor (if that’s what it is) apparently has some interesting and unusual properties: you can’t definitively prove it exists, and you can’t take advantage of it unless you definitively prove it exists, and you can’t take advantage of it unless you have the “secret numbers”. I.e. it is both deniable and unusable by third parties. Those both sound like extremely useful properties for a back door to have.

The idea is not new it’s been around for atleast 15years in a nice clear easy to understand way with RSA keys and for this we have to thank Adam Young and his supervisor Moti Yung. It is part of what they call Kleptography and there is a wiki page and a nice easy to read book. In the book Adam Young credits the idea behind the RSA kleptography to what is as single sentance from a paper from IIRC 1980. I’ve described the process of doing it on this blog in the past.

But very simply in the RSA case it’s based on the simple premise that there is a very great deal of redundancy in the number of Primes for a PQ pair. Because of this you can pick a pair of primes that when multiplied together to make the PubKey have a portion of the result act as a short cut to factoring. For arguments sake lets say that one third of the resulting PubKey bits from the mid point plus two bits is a number that gives a start point to start your Prime search and is less than a million odd numbers away from either the P or Q prime. How long on modern hardware would it take to do a million trial divisions with numbers of 1000bits in size?

Even on a modern PC you would find on an average office desk you are talking a very very short period of time in comparison with doing a full factorisation of a 2000bit PubKey.

Now what I did when I built a PubKey generator for the MS command line was to include a BBS random number generator which uses the equivalent of a PubKey, and used it to encrypt the start point and then searched for two primes that would give me the required encrypted string.

The result being unless you had the equivalent Private key to the BBS PubKey you could not recover the start point nor could you even if I gave you the P and Q primes of the Pub/Pri Key I was generating prove there was a back door.

Because of the very general nature of the “redundancy” and the fact it’s an absolut must for general PubKey systems means that such a back door is an integral part of any PubKey system.

With the “proof of concept code” I wrote a careful examination of the code and a little lateral thinking would have revealed there was a back door. BUT without knowing the BBS private key you could not exploit it…

Now what I find puzzeling is the comment you quoted, either he was using public licence to make it sound dramatic or he is a singularly ill informed individual. In the UK we have a saying,

“Out of the mouths of babes and fools…”.

@ Douglas Knight,

I’m away from my “dead tree cave” at the moment, so I don’t have the info to hand. But IIRC when the (alledged) US Gov sponsored malware was examind in the case of Stuxnet the Private signing key was assumed to have been “stolen” however where the hash colision was found the person in the open community that had found a colision method said the method used in the malware was significantly different to his and then went on to say it looked like it used an entirely different fundemental method that was unknown.

I could go googling for it but it’s late in the UK so you would probably find it before I’m going to be awake with a bit of spare time (ie about 20hours from now).

Perseids • September 25, 2013 6:16 PM

@Jeremy
If you have some basic knowledge about group theory and discrete logarithms then the attack isn’t all that hard to follow. The concepts behind it are actually quite similar to the Diffie-Hellman key exchange protocol. Maybe you could read up on that first and if you believe you have a decent understanding you can take a look at the Dual_EC_DRBG attack.

Dirk Praet • September 25, 2013 7:11 PM

I think I have read enough to conclude that even absent probable cause there is “reasonable articulable suspicion” to believe there is something wrong with Dual_EC_DRBG and that ditching it would be the cautious thing to do.

For those interested, here is a list of products and companies who have gone through the effort of having their implementation of Dual_EC_DRBG validated by NIST. That’s 403 products coming from nearly all Silicon Valley players, but also including SAP, the OpenSSL FIPS Object Module and even some China-based operations. It’s going to be interesting to watch which ones will be issueing statements in the same line of what RSA did last week.

Wael • September 25, 2013 8:09 PM

@ Dirk Praet,

I read enough to reach the same conclusion. Ditch it! Problem is, what other algorithms are “back doored”?

Bauke Jan Douma • September 25, 2013 8:55 PM

The social contract (hi Bruce!)

Just a minor side note.

Fear is the raison d’ être of certain US institutions (wouldn’t even call them Government
institutions anymore) and a large cloud of mainly technology firms and coprorations
around them.

They create their own market, needs and demands. Mundus vult decipi ergo decipiatur
is their motto, although they don’t live by many motto’s, rules, law, morals.

Where’s the general public in this picture? Well, it delivers… It delivers its money (the
buck stops somewhere, after all — taxpayers are an asset), and it delivers its data.

Anyways, to get back on the subject.
With so many billions and that much power stacked against you, you know you’ll always
be behind on the curve.

So what does that lead you to: awareness, activism, naming names, whistleblowing,
socio-political engineering, etc. Let them know there’s a price to pay — one that’s paid
personally. Maybe we need publiclly declared ‘Berufsverbote’. Those who are tainted
should be blacklisted. McCarhtyism reversed — to get some anti-social elements
removed — to reviatlize the social contract.

bjd

Douglas Knight • September 25, 2013 9:54 PM

Nick, Clive: thanks.

They’re just saying that it’s different, not obviously better, right? They could have done this with open methods for a million dollars, right?

So they knew a different attack on MD5 than the open community. Of course they are ahead, since they have access to the open work. But are they far ahead? This is pretty weak evidence. The coincidence in timing (ie, release flame at the same time as the open work) is interesting. Perhaps the open knowledge that MD5 was exploitable made it low cost to reveal their knowledge. Why didn’t they use the open attack, to hide their capabilities? Perhaps they have great capabilities and it was a lot cheaper this way. Or perhaps they didn’t have time to assimilate the open work.

moo • September 25, 2013 10:00 PM

@Thomas:

I might be wrong, but I seem to recall that XKCD comic appeared shortly after the fail0verflow PS3 hack (where it turned out that Sony had inadvertently used the same “random” value for a parameter in their key generation for a lot of keypairs, which made it easy for fail0verflow guys to do some algebra and recover the super-secret private keys used to sign all the firmware etc. as “Sony-approved”).

http://arstechnica.com/gaming/2010/12/ps3-hacked-through-poor-implementation-of-cryptography/

Gweihir • September 26, 2013 1:05 AM

@Jeremy: The argument is not that the NSA may have been unable to come up with a good backdoored version. That seems pretty obvious as they pushed a bad one.

The argument for them being incompetent with regard to intelligence gathering is the decision to push the obviously bad version instead of protecting their other crypto-sabotage efforts by not making it obvious that they are doing crypto-sabotage. An alerted enemy is far harder to attack, so one of the first rules is to not even let the other side know what you are doing. That they violated this rule makes them incompetent.

Carlo Graziani • September 26, 2013 3:56 AM

What puzzles me here is, what about the technical documents of the original NIST review? Was there really no comment about performance, or about the basis for choosing those EC constants?

I freely admit that I haven’t examined the NIST review process in detail, only followed it in news/blogs — e.g. the AES review, as periodically covered by Bruce. I had formed the impression of a rigorous trial by fire conducted by clinically-paranoid crypto freaks, the sort of process that would have precluded this sort of fiasco. If something this weird can really hide in plain sight despite a public NIST review, it suggests that NIST-sponsored public reviews of cryptographic standards are really more theatrical exercises than real trials by fire.

Bruce, you saw the AES review up close. How should we think of the assurance that they provide?

Mike the goat • September 26, 2013 4:23 AM

Carlo: it is interesting it was even included despite it being at least an order of magnitude slower than the alternative PRNGs in the standard. Seems NIST is seriously pissed with the NSA given how they worded their press release.

Dirk Praet • September 26, 2013 7:23 AM

@Wael

Problem is, what other algorithms are “back doored”?

I don’t know, but I think some minor paranoia is currently in order over anything that even remotely sounds fishy. SHA-3 may be such an example.

It would seem that John Kelsey is having some sneaking suspicions that NIST is trying to change Keccak into something very different from what won the 5-year competition. He recently gave an invited talk at the Workshop on Cryptographic Hardware and Embedded Systems 2013 (CHES’13), where he described some of the changes NIST has made to Keccak in turning it into a standard. The changes were detailed in five slides (slides 44-48) of Kelsey’s slide deck for his talk. Two major changes puzzled some in attendance:

  • In the name of increased performance (running faster in software and hardware), the security levels of Keccak were drastically reduced. The four versions of the winning Keccak algorithm had security levels of 224-bits, 256-bits, 384-bits, and 512-bits. However, from Kelsey’s slides, NIST intends to standardize only two versions, a 128-bit and a 256-bit version.
  • Some of the internals of the algorithm had been tweaked by NIST – some in cooperation with the team that submitted Keccak – to improve performance and allow for new types of applications.

Clive Robinson • September 26, 2013 7:39 AM

@ Carlo,

    If something this weird can really hide in plain sight despite a public NIST review, it suggests that NIST-sponsored public reviews of cryptographic standards are really more theatrical exercises than real trials by fire.

The standards processes I’ve been involved with are not “trials by fire” thought that is what the contestants would want you to think because it lends an auror of the heroic struggle to their behaviour. What they inevitably are is the equivalent of a high stakes poker game where prestige is the lowest hanging fruit on the rewards tree. For commercial organisations it can be worth a fortune, for spys, spooks and their respective governments it’s economic and political power.

Now you need to remember something about the NSA and their Five Eyes relations, they know everything that the open crypto community know and one heck of a sight more that the open community does not.

In effect they know the deck is marked and can read all the others cards and thus know not just the strengths but also the weaknesses of all the other hands, but worse they are also like a crooked dealer who does sleight of hand on the pack as they deal.

If you come up with a new basic structure in your algorithm design they probably charecterised it twenty or thirty years ago. You only have to look at the design of DES and Skipjack to realise that.

Nearly all things that are realy strong are brittle, but make them thin in the right way and they are extreamly flexible. It’s why HD platters are made of glass not aluminium, you thin out aluminium enough you get tine foil with all it’s faults. The same reasoning applies to algorithms.

The easy way for the NSA to get rid of a candidate they don’t want is to have a friendly chat over a cup of tea and sow seeds of methods to investigate in others heads. Seeds that germinate and show something to be brittle or inflexible when used one way or soft a yielding/spongy when used another. It’s why they use the Bridge term Finessing for the process.

The problem the NSA had it appears was that nobody from the open community was interested in eliptic curve random number generators. BBS provides most desirable properties for a DTRNG but is as fast as a dog with only one leg, EC would only be one leg faster and as we all know a dog walking on only it’s hind legs is slow and ungainly imagine how bad it would be on it’s front legs only…

So the NSA had to push in an EC contender and it “appears” it was done in a “ham fisted” way.

But remember “Clowns are clumsy in apearance, but closer inspection shows they are up with the best tumblers, jugglers and tight rope artists in skill, they are often better but look clumsy as part of the act”.

What we don’t know with these NSA clowns is if they are acting or realy stumbled due to idiotic internal power play at short notice.

What we do know in the open community and have known for a considerable time is that Public Key systems have a hugh amount of redundancy in them, they have to or they would be of no use for Public Keys. We also know that redundancy can hide all manner of covert channels, as can anything that is casualy efficient. Further from this we should also know that all those systems that use Public Key techniques are likewise cursed with redundancy.

History has taught us this problem about redundancy with stream ciphers and it’s also why it’s very hard to backdoor block ciphers they don’t have the sort of redundancy that lends it’s self to that.

Wael • September 26, 2013 9:44 AM

@ Dirk Praet,

Slide 29 is interesting. It reads like, you guys did everything, we only chose based on your claims, research, and analysis. I.e., don’t blame us for your screw ups 🙂

Alex • September 26, 2013 9:53 AM

I know it’s simplistic compared to the discussion, but does anyone know what Apple uses for their IOS RNG? The reason I ask is that I’ve noticed patterns in how iPhones/iPods “Shuffle” songs feature works. It feels more like it’s looking up numbers in a table rather than being distinctly random. Could be that it uses a multiplier or some other constant. Either way, even out of 1,000 songs, I’m seeing a pattern in how it selects the next “random” song.

Thomas_H • September 26, 2013 12:02 PM

@ Clive:

Now what I find puzzeling is the comment you quoted, either he was using public licence to make it sound dramatic or he is a singularly ill informed individual. In the UK we have a saying,

“Out of the mouths of babes and fools…”.

“What’s mathematically creative [with this algorithm] is that when you look at it, you can’t even prove whether there is a backdoor or not, which is very bizarre in cryptography,” he [Paul Kocher] says. “Usually the presence of a backdoor is something you can prove is there, because you can see it and exploit it….”

If this should be taken literally…

Could it be that the backdoor consists of code that normally performs ‘normal’ tasks within the algorithm, but when certain circumstances present themselves (e.g. a certain key or external program made by the NSA) the backdoor is activated?

What I’m specifically thinking of is a mechanism similar to how real-world (biological) viruses hijack the DNA/RNA copying mechanism of the host cells to multiply the virus and cause damage to the host: basically an external factor changes the internal pathway(s) for nefarious purposes.

This would for all purposes be invisible to outside lookers, unless the trigger is present.

Just rambling, I’m not an expert…

Daz • September 26, 2013 12:15 PM

“Because this was really ham-fisted. When you put on your conspiratorial hat about what the NSA would be doing, you would expect something more devious, Machiavellian … and this thing is just laughably bad. This is Boris and Natasha sort of stuff.”

But this misses the entire point and makes me think worse of this fellow and not worse of the NSA. The goal of the NSA is not to create a single point of /failure/. It doesn’t need to do that because it out guns and outmans everyone else. Rather, all it has to do is create multiple points of /weakness/ knowing that no one who isn’t the NSA can cover all the points of weakness all the time. If one takes a step back and thinks about it, it is a version of death by a 1000 tiny cuts. The NSA only needs one of those tiny cuts to get the target.

So it makes far more sense for the NSA to litter the world with a 1000 Boris and Natashas then it does one James Bond. Someone uncovers James Bond and it is game over for the NSA. Good luck killing all the Boris and Natashas that exist and which the NSA can churn out at will.

MarkH • September 26, 2013 12:34 PM

@Wael:

“You are basing the impossibility of reversing a hash on the prdicate that the worlds best compression algorithm by a huge margin cannot exist…”

In truth, the capabilities of lossless compression algorithms are severely limited.

For example, it’s trivial to prove that there can be no such algorithm, able to compress any arbitrary input by even a single bit.

MarkH • September 26, 2013 2:02 PM

A Perspective on NSA

It’s an organization with a lot of people. They’re just human. They aren’t demigods who leap from mountain-top to mountain-top in a single bound.

One witness to this, is their wretched security (see Snowden, Edward).

• NSA is subject to the same laws of physics as everybody else.

• NSA is subject to the same mathematical laws as everybody else: they can’t square a circle by Euclidean construction, any more than you or I.

• Their budget is big, not infinite. As I’ve argued before, multiplying a pair of n-bit numbers consumes some minimum amount of energy costing some amount of money (energy efficiency improves over time, but it’s finite). Even with a 10^10 dollar budget, there’s a practical limit to how much computation they can do.

• People who’ve studied the history of organizations can assure you, their asymptotic tendency is to be as dangerous to themselves as to others.

• They spent decades being “the smartest guys in the room.” People who’ve studied the history of organizations can assure you, the arrogance bred by this condition is extremely conducive to self-destructive behavior.

RSA was published in 1975 (independent invention by open researchers). The world learned afterward that GCHQ invented it in 1974. Then, the rumor mill claimed that NSA had it before that, though we don’t know when.

Differential cryptanalysis was published in the late 1980’s. IBM had discovered it in 1974, and kept it to themselves. At the time DES was created in 1977, NSA reportedly was already “well aware” of differential cryptanalysis.

Those are two cases in which NSA had a several-years lead over the public crypto community. One practical change is that the open community is much large and better-funded than it was in the 70s or 80s. Bruce has suggested that NSA’s edge over the public crypto community is probably much less than it used to be.

The bad news is, DUAL_EC_DRBG made it through a standards process (and yes, these processes are notoriously rotten).

The good news is, Daniel R. L. Brown discovered the backdoor vulnerability the same year DUAL_EC_DBRG was published (I don’t know when Brown’s analysis was published), and then Shumow and Ferguson independently discovered and published this vulnerability the next year.

So, even though the standards process failed, the academic community promptly red-flagged DUAL_EC_DBRG as unsafe. As I see it, the system worked: not to perfection, but enough to inform the prudent.

Yes, NSA is powerful. Yes, resistance to them can be effective.

Keccak • September 26, 2013 3:23 PM

@Dirk Praet

Interesting slides. Did they explain why they changed Keccak’s padding scheme? This seems to be the most “suspicious” thing about the slides. (The fact they plan to only standardize Keccak-256 and 512 doesn’t sound too suspicious).

Also, at the end of the slide he made mention how the FIPS standardization is out of NIST’s control. I think we all know what that means and who is ultimately calling the shots.

Also I find it interesting that Joan Daemen was a co-designer of both Rijndael and Keccak. NSA really likes his work. 😉

name.withheld.for.obvious.reasons • September 26, 2013 4:51 PM

@Dirk Praet

I think I have read enough to conclude that even absent probable cause there is “reasonable articulable suspicion” to believe there is something wrong with Dual_EC_DRBG and that ditching it would be the cautious thing to do.

Thanks Dirk, I needed a good laugh. I believe we could all use some comic relief at this point.

z • September 26, 2013 5:05 PM

@MarkH

Good points, especially about the civilian crypto community catching the backdoor. But that does bring up an interesting issue about NIST standards for cryptography–the backdoor was promptly discovered and yet the thing was implemented anyway.

The whole point about open source cryptography is that we can examine it for backdoors (or just genuine mistakes). In that sense, the process worked fine because the backdoor was found. But we can also see the double edged sword that is a NIST standard. People implemented it anyway, just because it was a standard. This includes people who should know better, such as RSA. It’s maddening to see something properly identified as flawed/backdoored and then used out of a blind adherence to standards.

Dirk Praet • September 26, 2013 6:51 PM

@ MarkH, @ z

So, even though the standards process failed, the academic community promptly red-flagged DUAL_EC_DBRG as unsafe. As I see it, the system worked: not to perfection, but enough to inform the prudent.

I think the system didn’t work at all. It’s only now that everybody is starting to take the issue serious. Pre-Snowden, Brown, Shumow, Ferguson and even Bruce were pretty much considered tin foil hats and the entire industry went along with the new standard anyway. I actually don’t know of any implementation where DUAL_EC_DBRG was explicitly discarded for these reasons, so saying that the system worked seems a bit of an overstatement to me.

@ name.withheld.for.obvious.reasons

Thanks Dirk, I needed a good laugh.

You’re welcome. Sometimes a wee bit of sarcasm makes for a better point than a lengthy technical elaboration.

z • September 26, 2013 7:05 PM

@ Dirk Praet

I agree, and I think we witnessed a rather comical (though disturbing) mental loop when the issues with Dual_EC_DRBG were brought up.

1.) It’s an open standard
2.) Therefore it can be reviewed for backdoors
3.) Therefore there are no backdoors
4.) Therefore anyone who reviews it and says they found one must be paranoid.

I’ve said before that I think it’s stupid to blindly trust open source cryptography just because it’s open source, assuming assume that competent, thorough reviews have been done. This is even worse. In this case, people found something wrong with it, publicized it, and the community mostly ignored it.

Bauke Jan Douma • September 26, 2013 7:40 PM

@ Dirk Praet, @z

The whole story can be spelled only one way: EPIC FAIL. Epic fail in trust — of corporations,
of standards bodies, of government w.r.t. ‘their’ own citizens, of one government w.r.t. an
other government, even so-called friendly ones, of one cryptographer against another, of…
need I go on.

And this is no bug, this is a feature. I’m going to say it again, after 9/11 the US Government
was a provider FEAR; over ten years later we find it’s become a provider of Fear, Uncertainty
and Doubt.

And to repeat myself: not a bug, but a feature. Under the terrorizing doom of FUD, privileged
and powerrful find opportunitieS. I for one wasn’t the least surprised that economic espionage
is part of the NSA’s activities. Come to think of it: spying on partners, includieng the ex and
prospected varieties, I am certain will be part and parcel (as we hear the violins swell) of life
at the NSA.

No, this whole story will have a larger and wider impact on 9/11. The handshake has grown
cold — your friend is your enemy, people and states are counting their fingers, and meanwhile
rethinking the old option of (true) independence. We may be finally witnessing a quick end
to the pax americana.

bjd

MarkH • September 26, 2013 11:05 PM

For the record, what I mean when I say “the system worked”:

Maybe someday, generally used systems and technologies will provide strong information security. I might live to see this day — it would be a Good Thing — but I don’t count on it. I suspect that the strength of generally used info sec has been compromised by laziness, greed and ignorance, at least as much as by NSA’s subversion.

In the meantime — today, tomorrow, and next year — my concern is that people and groups with extraordinary security needs have access to tools able to provide significant protection. As a starting point, I want it to be possible for security engineers wanting to provide good quality tools, to have a realistic idea of what is dependable, and what is not.

Those of us who worry about info sec were “warned off” about DUAL_EC_DRBG years ago. That millions likely had their privacy compromised by this backdoor is disgusting; that those who were careful to maximize security could determine that this technique was unsafe, is a small but significant victory.

Security never has been, and never can be, all or nothing. I want to make the optimal use of the best available imperfect tools, in this imperfect world.

Wael • September 27, 2013 12:06 AM

@ MarkH

Security never has been, and never can be, all or nothing. I want to make the optimal use of the best available imperfect tools, in this imperfect world.

By us, imperfect humans.

Wael • September 27, 2013 12:25 AM

@ MarkH

For example, it’s trivial to prove that there can be no such algorithm, able to compress any arbitrary input by even a single bit.

You seem to be a fan of Mr. Kolmogorov 🙂
I am aware of that, but my point is not really about the technicality. It’s about the way it’s “conditioned”. The trivial proof:

A key fact about Kolmogorov complexity is that no matter what compression scheme you use, there will always be some bit string that can’t be compressed. This is pretty easy to prove: there are exactly 2^n bit strings of length n, but there are only 2^0 + 2^1 + 2^2 + … + 2^(n-1) = 2^n – 1 bit strings with n or fewer bits. So you can’t pair-up n-length bit strings with shorter bit strings, because there will always be at least one left over. There simply aren’t enough short bit strings to encode all longer bit strings!

I cut and paste this from:
http://c2.com/cgi/wiki?KolmogorovComplexity

There are ways to get around it, But I am not going to tell you how 🙂

Wael • September 27, 2013 12:53 AM

@ MarkH,

Ok, I’ll be nice and give you a hint:
Hashes have collisions, compressions are not supposed to have collisions. There also techniques to factor primitive data out to be used and shared between the sender and receiver of the compressed contents. That’s about all I can tell you!

Mike the goat • September 27, 2013 2:16 AM

Alex: the prng in apple OSX is based on yarrow (hi Bruce!) if you look at prng.c .. I assume iOS uses a similar core. That said the randomize function in iTunes probably doesn’t use /dev/random and probably is just something trivial and importantly fast.

Clive Robinson • September 27, 2013 2:56 AM

@ Alex, Mike the Goat,

The random “play list” algorithm is far from random because as an over generalisation humans grave order, not chaos.

For instance most people would consider getting the same track two or more times in succession as it being “stuck”.

The way it used to be done with CD players was to use a card shuffeling algorithm based on the track numbers so each track would get played once each but out of order.

As MP3 players and their like started getting more and more tracks different algorithms such as dual and tripple sliding window shuffeling algorithms started to be used.

What ever the algorithm it’s a reasonable bet to say the track sellection is NOT independent 😉

MarkH • September 27, 2013 4:12 AM

@Wael:

Lossy compression can have collisions; lossless compression cannot, by definition.

As for “ways to get around” the compression theorem: no, it is not possible to get around it, any more than it possible to find a ratio of two integers, the square of which is 2.

Everyone who claims to “get around it” is either violating the formal definition of a lossless compression algorithm, or clueless about what their precious algorithm actually does. Amusingly, “compression algorithms” are the perpetual motion machines of the algorithm world. It would appear that every year, dozens or even hundreds of nitwits claim to have invented a fantastic new compression algorithm far superior to anything presently known. (We have an exact counterpart to this in cryptography: every few days, some crypto n00b reinvents the concept of a stream cipher, and claims for it the perfect secrecy of an one-time pad. Sigh.)

Violations of the formal definition of a lossless compression algorithm almost always fall into one of two categories:

(1) incompleteness (the system does not always recreate the original file)

(2) requiring the use of one or more “data stores” other than the compressed file

As examples of (2), some geniuses can demonstrate peformance in apparent violation of the compression theorem — but the compressed files are assigned file names that encode some of the content.

Another “cheat” is the use of an external “dictionary” or “code book”, which is not counted as part of the compressed file. That can be a useful technique, but it’s not compression: it’s encoding. A true compression algorithm does not rely on such an external dictionary. To see the absurdity of this cheat, imagine that someone has collected a copy of every file ever created, assigning an ordinal to each unique file. They could then say, “my system can losslessly compress any file in the world to less than 64 bits!” Of course, presented with any new file of randomly generated bits, the system must either immediately update its giant database to include a copy of the new file, or simply fail. Whatever that may be … it’s not compression.

In fact, TRUE compression algorithms typically DO create a dictionary — a custom dictionary, compiled by analysis of the original file. This dictionary becomes part of the compressed file.

True compression algorithms cannot “get around” the compression theorem, because it is simply impossible. As the a billboard for the Natural Law Party used to say, “186,262 miles per second. It’s not just a good idea, it’s the law!”

Clive Robinson • September 27, 2013 6:08 AM

@ Wael,

Compresability (if it’s even a standard dictionary word) is related in a complex way to redundancy.

One conciquence of this is there is no compression algorithm that is optimal for all input types.

In all cases of no loss compression you have to record the changes you make in a reversable way. This means every change involves increasing the information content, it cannot be avoided, what you hope is that added change information takes less space than the space saved by the compression method. There is no way around this plain and simple.

Thus the question falls to two parts,

1, The efficiency of the “coding” of the changes.
2, The efficiency of the “method” of the changes.

It takes no great insight to realise that whatever you do over the entire range of possible inputs these two efficiencies are inverses of each other. Infact it can be further realised that in fact of all the possible inputs for the majority of cases no real compression is possible for any given method of compression. Thus each input that is successfully compressed is a special case to that method and may well not compress at all to other methods.

It’s why when you compress an input with two compression methods in series you usually get different results from the order they are applied. Which is a big red flag as to why “compressability” should not be used as an estimate let alone a measure of entropy (take note all who are designing TRNGs).

As with “testing for randomnes” there are definate time and resource limits to finding optimal ways of applying lossless compression methods in series.

It’s actually a point of note against uniform probability being normal in the human world as to just how much redundancy there realy is in the data/information we routienly have that lossless compression works as often as it does.

Wael • September 27, 2013 6:11 AM

@ MarkH,

Everyone who claims to “get around it” is either violating the formal definition of a lossless compression algorithm, or clueless about what their precious algorithm actually does.

Very classy! I gave you the hint so you don’t go down this path of calling names. Some call it cheating, some call it innovation. Surely you know you that everyone who generalizes is clueless! 😉

MarkH • September 27, 2013 2:20 PM

in·no·va·tion noun \ˌi-nə-ˈvā-shən\

: a new idea, device, or method

: the act or process of introducing new ideas, devices, or methods

Starting in 1846, commercial services sent messages across long distances by means of electric telegraphy. These services usually charged according to the number of words in the message.

In response to the economic incentive for brevity, there promptly arose a vast proliferation of codebooks, by use of which the number of telegram words needed to convey a message could be greatly reduced.

In consequence of changes in communication technology, these systems became obsolete more than a century ago.

A much older usage of codebooks to shorten messages is in naval flag signals, as used (for example) by Britain’s Royal Navy. The famous “England expects that every man will do his duty” was not what Nelson wanted: he had dictated “Nelson confides that every man will do his duty.” But neither his name, nor “confides” were in the Navy’s codebook, and their spelled-out versions would have been too large for a practical signal flag hoist.

I suspect there are likely older examples than that.

Using an external codebook to shorten messages is neither innovation, nor is it a compression algorithm.

PS I agree, everyone who makes generalizations is clueless. Of course, everybody makes generalizations. I never make generalizations 😉

Mike the goat • September 27, 2013 8:29 PM

MarkH: Although when we talk of compression we think of algorithmic methods of conserving bandwidth (e.g. Huffmann Coding, LZW, etc.) you could consider shorthand and other abbreviated language systems as being compressed. Both methods rely on both ends having possession of the “cookbook” to compress/decompress the data (whether that be via an algorithm or a simple codebook of the substitutions) and significantly reduce the number of bits that require transmission. I believe that Western Union used such a system during the days of their teleprinter (and prior to that CW) network.

To be fair though this boils down to semantics. For the purposes of my argument I define data compression as “condensing information using a predefined method to occupy less space (fewer bits) than its plain text representation.” Of course that’s just my opinion. My 2c.

mort • September 28, 2013 12:14 PM

The big losers in this case are RSA.

The reason people described the backdoor as “ham-fisted” is that the algorithm turned out so bad that no one in their right mind would use it. It was assumed that even though it made it into the standard, it would languish unused, and the NSA would have little to show for it.

But RSA went ahead and used it as a default algorithm. Sam Curry’s attempts to plead incompetence are not too convincing considering their expertise in the field.

Despite the apparent technical issues, the NSA got a lot of mileage out of the backdoor because they have non-technical ways to convince people to use it, and because the inclusion in a standard gives vendors a lot of plausible deniability.

What other standards include known weak configurations, and who is using them regardless?

One that springs to mind is SSL/TLS. There has been a lot of foot-dragging in getting support for secure protocols and ciphers in popular implementations.

Andrew neumann • September 28, 2013 3:49 PM

@ all
Why would NSA push deliberately weak standards (e.g. DES 40/56) on Americans to allow an effective backdoor? Would not the weak standards be exploited by other non-US entities or sneakers.

Corman • September 28, 2013 4:11 PM

@Andrew neumann
I am not sure but since exploiting the weak standards still required specific information, perhaps they assumed that no one would find out.

Admittedly though I think that is a good question as it weakened American citizen’s own defenses.

Hopefully someone else has better insight on the motivation.

Thanks

Corman • September 28, 2013 4:15 PM

So maybe this thing that NSA is being accused of (here referring mainly to the weakening of standards, pushing for backdoors, and things like that) is not something that America was doing but something larger that America was doing together with their allies?

Clive Robinson • September 28, 2013 6:12 PM

@

True Compression is otherwise known as “lossless compression” or “no loss compresion and is not tailored to work with only a subset of the available input.

That is any reduction in the size of the input is reversable because no information is lost, and unlike a Telegraph Code Book does not constrain the input to fixed “messages”.

There is an old joke about Navy signal flags and the code books that go with them that explains the constrained input issue.

“A young rating was getting serious about a girle and gave her a broach with three flags on it. She asked what the message was and the rating said “I Love You” any way she was mightily pleased with the gift and the giver untill her elder brother who was a 2ndLte told her the broach realy said “permission to lie alongside”…

Mike the goat • September 29, 2013 12:17 AM

Clive: indeed but in the case of telegraph shorthand in the instance that there was no abbreviation they would send the original text. Thus the input isn’t constrained – it’s just selectively compressed. Todd isn’t that different to some modern compression tools that will just zip -0 a file if there is so little a gain to be made rather than burden the receiving user with a lengthy decompression delay for no real benefit. Semaphore flags, well I guess that’s a different story. 🙂 (although I guess you could spell out each word individually)

Andrew neumann • September 29, 2013 10:38 AM

@Corman
“is not something that America was doing but something larger that America was doing together with their allies?”

This is worth exploring: If that is the case, then “strong” allies should be available within any given boarder.

Andrew neumann • September 29, 2013 10:53 AM

@Clive Robinson

Thank you, It has been sometime since I engaged in this topic. I am trying to see if in practice one could live with “almost” lossless compression algorithm when the restricted subset tailored to work with is a set of measure “1”.

Clive Robinson • September 29, 2013 1:54 PM

@ Wael, Andrew,

Firstly “I hope the mint looks good” 😉

Andrew,

You have now made me curious as to why…

Wael • September 29, 2013 4:26 PM

@ Clive Robinson,

Mints look good. But Andrew and I are about 2300 miles apart at the moment. By the way, Andrew and I worked on that compression problem on and off a few years ago.

TidBit • October 1, 2013 9:45 AM

There is a logical discrepancy: You say that the EC random number generator was the worst of the 4 in the standard. RSA says (one of the links in the article) that it was the best and used it as default in many of its programs. Which is true? Isn’t it more likely that RSA was forced by NSA to use the algorithm as default – and lying now?

Dirk Praet • October 1, 2013 10:02 AM

@ TidBit

Isn’t it more likely that RSA was forced by NSA to use the algorithm as default – and lying now?

From Kim Zetter’s article: “On Thursday, corporate giant RSA Security publicly renounced Dual_EC_DRBG, while also conceding that its commercial suite of cryptographic libraries had been using the bad algorithm as its default algorithm for years”.

If they had received an NSL to do so, such statement IMHO would be a serious violation of it, so I think the chance of coercion by the NSA is rather limited in this specific case. But their reputation is pretty much in tatters. First, they get bttfcked by the Chinese, and now it would appear the NSA did the same. Little reason to be cheerful, and plenty to be cautious.

Leave a comment

Login

Allowed HTML <a href="URL"> • <em> <cite> <i> • <strong> <b> • <sub> <sup> • <ul> <ol> <li> • <blockquote> <pre> Markdown Extra syntax via https://michelf.ca/projects/php-markdown/extra/

Sidebar photo of Bruce Schneier by Joe MacInnis.