The NSA's Cryptographic Capabilities

The latest Snowden document is the US intelligence "black budget." There's a lot of information in the few pages the Washington Post decided to publish, including an introduction by Director of National Intelligence James Clapper. In it, he drops a tantalizing hint: "Also, we are investing in groundbreaking cryptanalytic capabilities to defeat adversarial cryptography and exploit internet traffic."

Honestly, I'm skeptical. Whatever the NSA has up its top-secret sleeves, the mathematics of cryptography will still be the most secure part of any encryption system. I worry a lot more about poorly designed cryptographic products, software bugs, bad passwords, companies that collaborate with the NSA to leak all or part of the keys, and insecure computers and networks. Those are where the real vulnerabilities are, and where the NSA spends the bulk of its efforts.

This isn't the first time we've heard this rumor. In a WIRED article last year, longtime NSA-watcher James Bamford wrote:

According to another top official also involved with the program, the NSA made an enormous breakthrough several years ago in its ability to cryptanalyze, or break, unfathomably complex encryption systems employed by not only governments around the world but also many average computer users in the US.

We have no further information from Clapper, Snowden, or this other source of Bamford's. But we can speculate.

Perhaps the NSA has some new mathematics that breaks one or more of the popular encryption algorithms: AES, Twofish, Serpent, triple-DES, Serpent. It wouldn't be the first time this happened. Back in the 1970s, the NSA knew of a cryptanalytic technique called "differential cryptanalysis" that was unknown in the academic world. That technique broke a variety of other academic and commercial algorithms that we all thought secure. We learned better in the early 1990s, and now design algorithms to be resistant to that technique.

It's very probable that the NSA has newer techniques that remain undiscovered in academia. Even so, such techniques are unlikely to result in a practical attack that can break actual encrypted plaintext.

The naive way to break an encryption algorithm is to brute-force the key. The complexity of that attack is 2n, where n is the key length. All cryptanalytic attacks can be viewed as shortcuts to that method. And since the efficacy of a brute-force attack is a direct function of key length, these attacks effectively shorten the key. So if, for example, the best attack against DES has a complexity of 239, that effectively shortens DES's 56-bit key by 17 bits.

That's a really good attack, by the way.

Right now the upper practical limit on brute force is somewhere under 80 bits. However, using that as a guide gives us some indication as to how good an attack has to be to break any of the modern algorithms. These days, encryption algorithms have, at a minimum, 128-bit keys. That means any NSA cryptanalytic breakthrough has to reduce the effective key length by at least 48 bits in order to be practical.

There's more, though. That DES attack requires an impractical 70 terabytes of known plaintext encrypted with the key we're trying to break. Other mathematical attacks require similar amounts of data. In order to be effective in decrypting actual operational traffic, the NSA needs an attack that can be executed with the known plaintext in a common MS-Word header: much, much less.

So while the NSA certainly has symmetric cryptanalysis capabilities that we in the academic world do not, converting that into practical attacks on the sorts of data it is likely to encounter seems so impossible as to be fanciful.

More likely is that the NSA has some mathematical breakthrough that affects one or more public-key algorithms. There are a lot of mathematical tricks involved in public-key cryptanalysis, and absolutely no theory that provides any limits on how powerful those tricks can be.

Breakthroughs in factoring have occurred regularly over the past several decades, allowing us to break ever-larger public keys. Much of the public-key cryptography we use today involves elliptic curves, something that is even more ripe for mathematical breakthroughs. It is not unreasonable to assume that the NSA has some techniques in this area that we in the academic world do not. Certainly the fact that the NSA is pushing elliptic-curve cryptography is some indication that it can break them more easily.

If we think that's the case, the fix is easy: increase the key lengths.

Assuming the hypothetical NSA breakthroughs don't totally break public-cryptography -- and that's a very reasonable assumption -- it's pretty easy to stay a few steps ahead of the NSA by using ever-longer keys. We're already trying to phase out 1024-bit RSA keys in favor of 2048-bit keys. Perhaps we need to jump even further ahead and consider 3072-bit keys. And maybe we should be even more paranoid about elliptic curves and use key lengths above 500 bits.

One last blue-sky possibility: a quantum computer. Quantum computers are still toys in the academic world, but have the theoretical ability to quickly break common public-key algorithms -- regardless of key length -- and to effectively halve the key length of any symmetric algorithm. I think it extraordinarily unlikely that the NSA has built a quantum computer capable of performing the magnitude of calculation necessary to do this, but it's possible. The defense is easy, if annoying: stick with symmetric cryptography based on shared secrets, and use 256-bit keys.

There's a saying inside the NSA: "Cryptanalysis always gets better. It never gets worse." It's naive to assume that, in 2013, we have discovered all the mathematical breakthroughs in cryptography that can ever be discovered. There's a lot more out there, and there will be for centuries.

And the NSA is in a privileged position: It can make use of everything discovered and openly published by the academic world, as well as everything discovered by it in secret.

The NSA has a lot of people thinking about this problem full-time. According to the black budget summary, 35,000 people and $11 billion annually are part of the Department of Defense-wide Consolidated Cryptologic Program. Of that, 4 percent -- or $440 million -- goes to "Research and Technology."

That's an enormous amount of money; probably more than everyone else on the planet spends on cryptography research put together. I'm sure that results in a lot of interesting -- and occasionally groundbreaking -- cryptanalytic research results, maybe some of it even practical.

Still, I trust the mathematics.

This essay originally appeared on Wired.com.

EDITED TO ADD: That was written before I could talk about this.

EDITED TO ADD: The Economist expresses a similar sentiment.

Posted on September 6, 2013 at 6:30 AM • 55 Comments

Comments

dot tilde dotSeptember 6, 2013 6:49 AM

bruce, I am sure you have watched jacob applebaum's keynote to last years 29c3 in hamburg. If not, it's on youtube. jesselyn radack, thomas drake and bill binney also gave a talk there and it was all well before snowden is said to have contacted glenn greenwald.

can you please come to 30c3? people need your voice and your ability to communicate these urgent matters.


the cfp is here:

http://events.ccc.de/2013/07/18/30c3-call-for-participation-en/


thank you for your effort,

.~.

rdmSeptember 6, 2013 7:30 AM

I rather doubt it's just one thing:

(1) if they've managed to build an optical computing infrastructure, I rather doubt that the 80 bit key length thing is a real limit.

(2) If they've managed to do any significant mathematical analysis in elliptical curves (or whatever other mathematical domains), we may not even have a linear relation between physical bits and significant bits.

(3) If they're not going for complete coverage, the worst case limits are irrelevant - they mean some information loss, but so what?

(4) If we look at physics, we can see that our current computing infrastructure offers almost no security against listening devices placed close enough to the system. All encryption does is underline and emphasize certain kinds of information.

There's more, also, but thinking about these problems like a specialist instead of like a generalist can get you into some really misleading territory.

lecSeptember 6, 2013 7:57 AM

Hi
Have you considered ASIC for brute forcing? The progress in iteration power observed in the Bitcoin mining industry is quite spectacular. Due to this new hardware Mega hash/sec became Terra hash/s. Imagine what sort of dedicated chip could come out of an agency with no need to create a commercialy expoiltable product and infinite budget.
M.

NobodySpecialSeptember 6, 2013 8:02 AM

Wouldn't the first indiciation of a breakthrough in crypto be an instruction from the NSA to other branches of government to stop using that algorithm?

Or do they assume they are the only ones who could discover and exploit it? I mean - when did you last hear of a Russian mathematician and how could the chinese possibly build their own supercomputers?

Or are they now so out of control that they see spying on American's twitter accounts more important than securing the army's communications

jddjSeptember 6, 2013 8:10 AM

What about D-wave's "adiabatic" quantum computer? I understand it's not the same thing people usually think of when discussing quantum computing, but could this approach have traction against public key cryptography?

MarcosSeptember 6, 2013 8:25 AM

Nope, quantum computers have a hard limit on the size of the keys they can deal with. That limit is given by physics, not by the complexity of the algorithm, and it is the size of the computer's registry.

Last time I saw it, the biggest quantum computer built (and public) was limited to 11 bits, but there are probably bigger ones now.

xyzzySeptember 6, 2013 8:29 AM

It's worth noting that AES is not accredited for TOP SECRET with 128 bits, but is accredited with 192 bits. If you assume that 80 bits are tractable, one interpretation of that ruling would be that the NSA have something like 48 bits of leverage on AES. It's not totally implausible: if the leverage scaled linearly with keylength (who knows?) then 17 bits of leverage on DES might be equivalent to 40 bits on AES, which would be in the ball park.

tinfoilSeptember 6, 2013 8:38 AM

There is also speculation of a possible backdoor in AMD/Intel to mess with RNGs and NXbit. Lots of microcode there nobody can brute force to figure out what its doing. NSA seems to like the RNG skeleton key approach, and they could protect themselves from it by patching their own systems and forcing us to buy backdoored chips. Open and trusted hardware becoming a necessity

Nick PSeptember 6, 2013 9:08 AM

@ xyzzy

"It's worth noting that AES is not accredited for TOP SECRET with 128 bits, but is accredited with 192 bits. If you assume that 80 bits are tractable, one interpretation of that ruling would be that the NSA have something like 48 bits of leverage on AES."

The most likely reason for that has to do with classification periods. Top Secret documents will typically stay classified for decades unless manually downgraded or released. So, a given cipher protecting Top Secret data must be strong both now and THEN. NSA assumes that certain key sizes will get easier to attack over time. And then there's the possibility of enemy advances in things like quantum computers.

Put it together, you get the NSA mandating a bit higher key lengths for standardized algorithms used for classified information. They also have secret algorithms (Type 1) and dedicated networks for highly classified data as another just in case security measure.

CHFSeptember 6, 2013 9:14 AM

"More likely is that the NSA has some mathematical breakthrough that affects one or more public-key algorithms."

That would be consistent with a statement I heard at a Grid security conference 7 or 8 years ago to the effect that public-key systems were not authorised in the UK for military classified material or systems, but the reason for that was itself classified. I assumed at the time that probably meant they knew an unpublished weakness.

AlbertSeptember 6, 2013 9:23 AM

jddj, In the Crypto I course on Coursera the lecturer (Dan Boneh) says that a hypothetical future quantum computer would need the square root of the keysize number of iterations for symmetrical ciphers. So AES-128 would take 2^64 iterations and AES-256 would take 2^128 iterations to break (I think it was using Grover's algorithm). So symmetrical ciphers would still be "pretty safe" while public key systems would be completely broken (because of Shor's algorithm).

GSeptember 6, 2013 9:47 AM

Increasing key size in GnuPG:

"Although it is technicaly possible to work with 8192 bit GPG keys the creators of Gnupgp ship the sources with a hard coded limit of 4096 bit. If you want a larger GPG key than 4096 bit your are supposed to change the given limit yourself by changing one line of code in the file g10/keygen.c. That's it. After that you can create 8192 bit GPG keys."

AndrewSeptember 6, 2013 9:49 AM

Perhaps the reason the NSA is pushing ECC isn't to lull people in to using crypto that they can punch a hole in, but because they have made a breakthrough that weakens RSA and are afraid it will become public sooner or later.

A *lot* of websites, schneier.com amongst them, still seem to be using 2048 bit RSA keys. Wikipedia currently states 2048-bit RSA is believed to be as hard as 112-bit symmetric keys. What if the big secret is they've got an algorithm to get that down to ~80-90 bits? Is that feasible?

Man of Chai TeaSeptember 6, 2013 10:12 AM

I think Clapper was overplaying an executive summary that was written to persuade whoever oversees the budget allocation that the NSA was doing excitingly cutting-edge stuff.

As you say, the maths are good but it will take serious collaborative effort from respected cryptographers to sign-off and lock-down trusted implementations for everyone else. How you prevent that process from being subverted I don't know. If the powers choose to pass legislation outlawing strong encryption (as the NSA v. Phil Zimmerman) without submitting keys as RIPA in the UK requires, I'm not sure there's much to be done about it.

He who hath a secret must first keep it secret that he hath a secret to keep -- Sir Humphrey Appleby

If you would keep a secret from an enemy, tell it not to a friend -- Benjamin Franklin

bf skinnerSeptember 6, 2013 10:51 AM

We've been discussing witting friendly companies.

It occurs to me that NSLs and FISA orders compel behavior while gagging the compelee.

Of course there are company's that would willing aid and abet (I'm thinking Oracle here) but others that wouldn't (and here I'm thinking Qwest)

Could they be use to force (should it be needed) the installation of backdoors and other weaknesses.

SethSeptember 6, 2013 10:59 AM

"That's an enormous amount of money; probably more than everyone else on the planet spends on cryptography research put together"

Really made me smile. The government is really good at spending more money than anyone else on a lot of things and not getting anything done.

CarpeSeptember 6, 2013 11:03 AM

@Bruce

Of course you are correct, it is likely that the advances by the NSA have primarily been side-channel style attacks and not full on brute forcing. Here is the dilemma though, say people do start using stronger keys, the NSA is just going to respond by amping up it's side-channel/political attack vectors. National security letters, gag orders, secret taps, black bag operations, covert infiltration/manipulation of devs (There is more to the OpenBSD accusations than most realize, let's not even get started on MS).

So what I propose is this, we need a combined approach that closes up some of the low hanging fruit (evil maid attacks for example) and at the same time increases key strength.

Just doing one at a time will likely result in a weakening of the other. Doing one too soon would also do the same.

In my mind this primarily involves complete protocol re-designs as well. A tall order to say the least.

Clive RobinsonSeptember 6, 2013 11:05 AM

@ CHF,

    ... to the effect that public-key systems were not authorised in the UK for military classified material or systems, but the reason for that was itself classified. I assumed at the time that probably meant they knew an unpublished weakness.

Probably not. In the UK the major reason for not using something was "unknown strength".

Basicaly if they could break a system then they knew how strong it was and could factor a "secure for time" and rate its usage appropriatly.

The fact that other equaly as "security concious" entites do use various forms of asymetric crypto sugests it is acceptable (or was a few years ago).

antimatterSeptember 6, 2013 11:12 AM

tinfoil • September 6, 2013 8:38 AM


There is also speculation of a possible backdoor in AMD/Intel to mess with RNGs and NXbit. Lots of microcode there nobody can brute force to figure out what its doing.

You are right about that. For example Steve Blank discusses this in his article at Forbes.

Your Computer May Already be Hacked -- NSA Inside?
http://www.forbes.com/sites/steveblank/2013/07/15/your-computer-may-already-be-hacked-nsa-inside/

Steve writes that:


Starting in 1996 with the Intel P6 (Pentium Pro) to today’s P7 chips (Core i7) these processors contain instructions that are reprogrammable in what is called microcode. Intel can fix bugs on the chips by reprogramming a microprocessors microcode with a patch. This patch, called a microcode update, can be loaded into a processor by using special CPU instructions reserved for this purpose.
...
Since 2000, Intel has put out 29 microcode updates to their processors. The microcode is distributed by 1) Intel or by 2) Microsoft integrated into a BIOS or 3) as part of aWindows update. Unfortunately, the microcode update format is undocumented and the code is encrypted.

Later in the article he refers to the "Cloaker" proof of concept rootkit as an example of a backdoor that would not be detected by antivirus software.

Now of course the industry is moving from BIOS to UEFI so who knows what could be lurking inside that...

easSeptember 6, 2013 11:45 AM

I feel like this post has too much scare-mongering.

If anyone else were to recommend ECC over RSA, you'd say, "Duh." But if the NSA does it, it must be due to some backdoor? I think that the NSA is just trying to protect citizens in this case.

I don't believe that the NSA has a quantum computer of any appreciable use. There's no reason to believe that they have a jump on what's publicly available. There's also no reason to yet beleive that it's even possible to build a quantum computer of any use: The current, best, fastest quantum computer can't factor anywhere near RSA-sized numbers.

This post is a little over-the-top for what I've come to expect here.

PaulMSeptember 6, 2013 12:44 PM

Sorry if this is a bit naive but wouldn't it be fairly trivial to check if your RNG has been nobbled? Just generate random numbers until you have a statistically significant number and make sure the distribution is as expected?

Or is this something within e.g. the Windows key generating algorithm that might switch on the "restricted" RNG?

NobodySpecialSeptember 6, 2013 1:05 PM

@PaulM - the PRNG could produce perfectly randomly distributed numbers and pass all the tests. But if the NSA built your PRNG and knows sequence it is producing all bets are off!


tinfoilSeptember 6, 2013 1:32 PM

Of course you could always make or use a RN/PRN extractor to defeat this, and run a periodic test that tries to write and execute memory to determine if NX bit is flipped. Extreme paranoia but if handling something the NSA wants like foreign gov databases or stolen secrets it would be well worth your time to make sure

SniffnoySeptember 6, 2013 1:38 PM

There are asymmetric ciphers that are not known to be easily breakable by quantum computers; see lattice-based crypto. Whether there are good implementations of this out there, I don't know...

Bill ColeSeptember 6, 2013 1:41 PM

The detailed tables for the Black Budget split up costs in a different way than the summary, following DoD standards. It shows $2.5 billion this budget year for "Research, Development, Test, & Evaluation, Defense-Wide" from the CCP's $10.8 billion total (23%) rather than the 4% shown as "Research & Technology" in the summary pie chart.

So, depending on how you look at it they may be spending "more than everyone else on the planet spends on cryptography research put together" or maybe it's over 5 times that.

Frank SchmalzSeptember 6, 2013 3:28 PM

Certainly the fact that the NSA is pushing elliptic-curve cryptography is some indication that it can break them more easily.

- The NSA made DES resistant to differential cryptoanalysis at a time no one else was aware of the attack.
- The NSA is recommending ECC for classified information of secret and top secret level for US agencies.

I think there are more reasons to believe they are promoting it because they found new methods to attack vintage asymmetric algorithms.
To my knowledge the NSA has 2 major tasks (simplified):
1. aquiring information
2. protecting information
Today everyone seems to assume they are caring only for task 1. I think they are doing their job as good as they can without any morale considerations. They are not the evil empire trying to enslave the world. That might be the intention of the guy who gives the money and gets the information.

PaulGSeptember 6, 2013 4:04 PM

>The defense is easy, if annoying: stick with symmetric cryptography based on shared secrets, and use 256-bit keys.

There are asymmetric schemes proven secure against quantum attack. Lattice-based cryptography and McEliece are examples. We'd just have to modify existing key exchange to use these primitives and we could keep using the same PKI.

jonesSeptember 6, 2013 4:43 PM

What if they're using novel computational techniques, such as with their HTMT (Hybrid Technology Multi-Threaded Architecture) or something built on AND Corporation's HNeT platform.

I know Mr. Schenier was skeptical in the past about the NSA's ability to move so much data. The NSA has repeatedly expressed interest in holographic data storage, and, specifically, in massively parallel implementations.

http://en.wikipedia.org/wiki/Holography#Data_storage

Perhaps, moreover, for purposes of "feature extraction" the variable resolution of holographic data retrieval offers some novel computational "shortcuts," since each part essentially contains a low-resolution version of the whole.

i.e.,

"When a photograph is cut in half, each piece shows half of the scene. When a hologram is cut in half, the whole scene can still be seen in each piece. This is because, whereas each point in a photograph only represents light scattered from a single point in the scene, each point on a holographic recording includes information about light scattered from every point in the scene."

http://en.wikipedia.org/wiki/Holography#Holography_vs._photography

travisSeptember 6, 2013 6:08 PM

lec, people have indeed considered the NSA using ASICs to break encryption. Search for "NSA fabrication plant". They exist in Ft. Meade and San Antonio at least (that's not a secret, but little is known about what they do—it seems they may have been cracking garage door opener codes at the latter plant...).

Wesley ParishSeptember 6, 2013 7:39 PM

As far as backdoors in code and chips goes, there was a brilliant example of backdooring the c compiler done by Ken Thompson.

There is a pile of good source code of compilers from assembly to (I don't know) Pascal and so on. Free and Open Source.

The backdoor is still a risk. You have to read and compile the code yourself to be absolutely sure of it - and make sure the compiler's not inserting the backdoor while doing so. Decompile, disassemble the compiler first in such a situation.

There is also a growing pile of good source code for chips - VHDL and Verilog. You can find a good lot of it at OpenCores and the tools at Open Circuit Design.

The major problem with Open Hardware is that to write and publish the hardware designs is all very well: to make the chips on anything but an FPGA, you need the postprocessor, and the postprocessor comes with the foundry hardware, or is licensed by them to the EDA publishers. Ego closed source. So it is perfectly possible for it to be including a set of backdoors for any chip designs.

And it seems like only yesterday that there were rumors about the Chinese chip foundries including backdoors in their chips, and everybody and his dog was panicking about that. (It was only yesterday! OMIGAWD!)

How the mighty have fallen, in the midst of battle. (Letting them tie their own shoelaces was a bad thing. How were we to know they'd tie them together? Because it seemed like such a good idea at the time?)

undisclosedSeptember 6, 2013 9:58 PM

Mmmm-hmmm... I love the smell of home-baked crypto in the morning...

1 Chop the data into small pieces.

2 Sprinkle various off-the-shelf crypto liberally in an order derived from the pass phrase.

3 Pour into a container and wait for the CPU to cool off.

Tasty!

(Be sure to store it in slices in different places so that the whole pie won't get eaten at once.)

Bon appetit, NSA!

Michael WolfSeptember 6, 2013 11:50 PM

Mr. Schneier,

I would like to request you pose a question to Edward Snowden:

Can the NSA products be used by, say, a corrupt federal law enforcement officer (National Park Service) to look up online information about an individual which can then be used to track that individual and surveil him?

I have circumstantial evidence which strongly supports that this is precisely what happened to me last year after I turned in a marijuana grow operation because the principals were all (5) trying to run residents off the treacherous mountain road. I have sufficient evidence, albeit circumstantial at this point (it can be verified through investigation) that the officer was running protection for the operation.


If Mr. Snowden confirms that any Federal officer using dishonest means, can utilize these products, then I would like to request that I be interviewed and my case investigated. I am already attempting to have the matter investigated by Congress through Senator Wyden (I have asked him to retrieve any NSL on me from my ISP which, if dated prior to my arrest PROVES I was set up, and by using NSA products) but do not have any faith in my government or my representatives to it.

As you can imagine, it is vital that Americans know if these programs can be abused, and in what manners they can be abused. You already demonstrated that Kim Dotcom was arrested after evidence was obtained through NSA products; this would provide sufficient evidence to allow Americans to draw the logical conclusion that all of the stories thus far should have led Americans to: that these programs were never intended to route out terrorism - these programs are in fact terrorism, against the American people and others around the world - everyone except terrorists.

And if this conclusion can be drawn validly, it is no difficult step to then conclude that the terrorist attacks of 9/11 and other attacks were in fact "false flags."


Given that our government is effectively run by psychopaths, and given the nature of psychopathy, it is not at all difficult to believe that the US Government has become an evil government hell bent on world conquest vis a vis Hitler's Third Reich; especially considering the same exact methods are being used; though most have been "modernized."

NSADSeptember 6, 2013 11:57 PM

In my opinion the best way for NSA or any other SIGINT agency for breaking encryption or snooping communications is through side channel attacks.
I would spend my budget in that area rather than very specific and unreliable attacks like "truncated differential cryptanalysis" or brute force.

Bob O`BobSeptember 7, 2013 12:34 AM

"Social engineering" seems like a simpler answer to me.

It's pretty obvious to me that they should expect the results of their corruption of the infrastructure would eventually be externally observable. Unless they literally never did anything with the intel gathered, and we know that's a non-starter.

Claims about a "mathematical breakthrough" could simply be massive exaggeration (i.e. lies) as part of a cover story, for when the risk of exposure would have risen just through use, even had there been no whistle-blowers or leaks.

Michael JSeptember 7, 2013 6:57 AM

I thought of a new cryptographic algorithm/protocol using 512 bit cryptographic hashes for encryption and decryption. It may be of interest to you Bruce. In theory as long as finding a pre-image for a HMAC is hard it should be NSA/quantum/supercomputer/secure.

The thread is here:
crypto.stackexchange.com/questions/10204/using-hashes-for-encryption-decryption-v2-with-modifications

I posted on the crypto.stackexchange forum but the power users seem to have frozen the thread due to it not being in the "right" question format. Be sure to review the edit history in case they edited something. Otherwise the full algorithm is listed here as well:
pastebin.com/LCGfATXT

Would be interested to hear what you (or other commenters) think or if there are could be improvements made for it.

Thomas_HSeptember 7, 2013 8:11 AM

If many NSA backdoors exist on both soft- and hardware levels, could the machines involved be exploited as a massive distributed computing system used to crack the more complicated systems?

Doubtfully AnonymousSeptember 8, 2013 5:41 AM

Mr. Schneier,

I am not really security savvy, in fact I have lost my wallet quite a few times. And before the NSA or other asks, I think the worst thing I have done is forget to buy a train ticket.

It's funny how betrayed i feel by this business with the NSA, and I'm not even a US citizen, I can only imagine how some of you feel.

Now I might be reading too far into this and if so feel free to correct me.

It seems we cant trust closed source programs, or US hardware due to the NSA having the rights to apply screws to business'. And I understand while the NSA may have no reason to go all 'CLU' on my privacy how can we tell they aren't leaving the doors open for more nefarious characters?

Does this business not scarily enough give the great firewall of China a measure of legitimacy?

How bad could the economy and employment rate of the US be affected, if the world started boycotting big name US brands and startup's coming out of Silicon Valley? This could mean big losses for Windows/Intel/Apple and I'm sure a plethora of others.

I have started to close the doors my end, and while I may not be able to keep anyone determined out forever, I want to make sure it's damn costly to make my displeasure known.

Here is how I have started with my amateur ability to understand some security suggestions.

Make master type passwords with a code consisting of upwards of 20 characters using all of the below in a modified and abbreviated pass-phrase.

*lower
*uppercase
*special
*numbers

I put a True Crypt Volume using AES-TWOFISH-SERPENT (Whirlpool) on my computer and store a TOR Browser and Password Safe within.

Where do I go from here is what i have done secure?

*Securing my email/mobile?
*vetting any endpoint software I might have?
*Open source only?
*Buy a Linux?

How fares my yubikey, did it come out of the US factory?
Is last pass still safe?

The NSA was outed, it would be foolish to believe they are the only ones, are we looking at a CAR (Cryptographic Arms Race) or were we already in one and I just needed to get my head out of the clouds?

Steve TSeptember 8, 2013 9:43 AM

I've been thinking about this a bit, and I see a few contradictory things that just make me more curious what the "real story" is. I suspect it's not as bad as my first "Oh my God!" reaction, and my view of the situation has tempered a bit over the past couple of days. First off, the threat model most people are worried about seems to be the NSA Hoovering up ciphertext and then breaking it all for data mining at their new, big Utah data center (or something similar). Based on that threat model, people are suggesting that protocols all use schemes that provide forward security, so post-capture processing wouldn't be effective.

However, the latest documents (specifically the GCHQ briefing) suggest that SSH has on the list of compromised technologies - and SSH has always used a forward secure key establishment protocol, so there must be something more to this than just post-processing captured ciphertext.

Could the "something more" be the "groundbreaking cryptanalytic capabilities" mentioned in the funding request? And is the advice to avoid elliptic curve crypto sensible? My first gut reaction is the same as Bruce's advice: we don't understand the math behind elliptic curves as well as the centuries-old number theory problems behind things like RSA, but this "gut reaction" doesn't pan out for reasons that Frank Schmalz points out above. NSA's Suite B includes ECDH with approval for use with top secret / SCI when used with the appropriate key lengths (a specific, publicly-known 384-bit prime modulus curve). I simply do not believe that NSA would put US national security information at risk by using a technique that either has a mathematical weakness or a trapdoor in curve parameters that could be discovered and exploited by someone else. A leaked trapdoor in the fixed parameters would not just expose one communication, but would potentially expose a huge amount of ciphertext that is collected by, say, the Russians (and you know they're grabbing everything they can, just like we are). Based on just that observation, my faith in elliptic curve crypto - at least with respect to what the NSA knows - remains high.

CA compromise is a real possibility, but requires an active attack, changing the threat model. They're not doing wide-scale MitM attacks (which would be quickly detected), so post-processing large collections isn't an issue there.

I'm left with "engineering-introduced vulnerabilities" as the remaining serious threat. For example, how does the timing of the GCHQ briefing (there's no date on the document) compare to the discovery and patching of the ssh entropy bug (2008 - could the briefing be that old?). If this is the type of threat we're looking at, then we have more power, at least for software-implemented crypto - thorough audits of software and the tool chains that are used. A lot of work, sure, but at least we're not battling some unknown mathematical breakthrough. That's why I'm a little more optimistic today than I was two days ago.

Carl 'SAI' MitchellSeptember 8, 2013 5:19 PM

I wonder why we don't see much about lattice-based cryptography. We need new cryptosystems that are more trustworthy, so we need cryptographers to analyze new systems in detail. NTRUEncrypt is patented, which is a downside, but we certainly need options other than discreet log and elliptic curve types.

mcjtomSeptember 9, 2013 4:24 AM

The article states: "...The defense is easy, if annoying: stick with symmetric cryptography based on shared secrets, and use 256-bit keys."

Why shared secrets? And how?

Clive RobinsonSeptember 9, 2013 5:22 AM

@ mcjtom,

The expression "shared secrets" has a number of meanings depending on the context it is used in.

Keying material (KeyMat) handeling is a very much more complicated issue than basic crypto usage, which various forms of aysmetric crypto were supposed to simplify...

In this case where their may be a question over the maths / security of aysmetric crypto I would assume that all math theoretical systems are likewise "suspect untill indicated otherwise".

Thus what is ment by "shared secrets" is in effect a piece of paper with the 256bit symetric cipher key written down which you hand over personaly to the person you wish to communicate with.

If it was me it would not be a piece of paper but a write once DVD or credit card card shaped CD with enough "Truely Random" KeyMat on it to last a while as "One Time Keys". That said you only need two 256 truely random numbers to generate keys that are as secure as the crypto algorithm (ie AES) you are using. Basicaly you use AES-256-CTR with one number as the AES key and the other as the seed / start point of the counter. It lacks certain security advantages over truely random keymat but as it is good for 2^64 keys it's going to last you a life time...

JeffSeptember 9, 2013 8:34 AM

Is much chance the NSA's breakthroughs related to the Green–Tao theorem? We'd rumors and gossip about that in the mathematical world a couple years ago. Any idea if Green or Tao are connected to the NSA via IDA-CCR?

Clive RobinsonSeptember 9, 2013 9:40 AM

@ Jeff

Contrary to what people generaly think primes are actually very repeatably placed along the number line and you can see this fairly easily with a few moments thought.

Twin primes are primes that are seperated by an even number, and finding candidates is very very easy, in that you will find them sitting astride the result of multiply primes together just like intigers and factorials.

So,

1.2 = 2 giving 1,3
1.2.3.5 = 30 giving 29,31

And so on.

What is less clear is the pattern the primes fall in reflects around these primes, with the exception of those struck out by later primes.

One way to imagine it is like waves that are harmonics of the central even number they all start in phase at zero and cross at the respective lower central even numbers (multiples of six in the case of 30).

In a way it's the inverse of the Sieve of Eratosthenese, and a lot faster way of finding prime candidates than either the sieve or randomly selecting an odd number and doing a two step walk up or down the line.

jackSeptember 9, 2013 12:20 PM

simple- We are not allowed to export anything stronger than 128 bit - this means that 128bits is an open book for NSA. Minimum commercial standard should be 256 or even 512 and a minimum of 2048

Whiskers in MenloSeptember 9, 2013 3:21 PM

This is interesting -- I would take this announcement
and apply it to the collection of data retained in some
massive storage resource. I would not take it
and apply it to a single random message.

i.e. if a communication could be compromised
perhaps with a man in the middle attack the keys
discovered could be applied to retained data. Thus
opening up messages (plural) in the past and future.

This is perhaps foiled should we exchange keys via USB stick
at a coffee shop but as long as the data exchanges can be
captured the "history" has the potential of being undone. Especially
if I store your data encoded with your key should the key
to a key ring with the key be cracked.

Public+Private key pairs are not very secure long term
because of the one to many use of the method and also
the short key length of most key ring tools.

Wolf BaginskiSeptember 11, 2013 1:30 AM

$440 million would pay for a lot of "social engineering".

Think of the basic "Breaking Bad" scenario, and apply the prospect of huge medical bills to somebody inside a software company. How reliable is the medical insurance a Silicon Valley startup can supply? Yes, it's fiction, but could it also be movie-plat cryptography, making your targets aware of how precarious their circumstances might be, and so open to bribery?

Do the healthcare systems of us dreadful socialist Europeans give us better security?

btSeptember 26, 2013 12:56 PM

At the end of the day the trustworthiness of the mathematics is moot. All non-government and most government entities must rely on commercial (and therefore vulnerable) implementations of cryptography.

Until a newbie programmer can effectively build a perfect implementation of a sound mathematical cryptographic algorithm that is invulnerable to tainted hardware/firmware/software, we are just doing the best we can and operating on faith.

Cl!ch3March 2, 2014 7:06 AM

Great article, Bruce. That quote really makes you think. "According to another top official also involved with the program, the NSA made an enormous breakthrough several years ago in its ability to cryptanalyze, or break, unfathomably complex encryption systems employed by not only governments around the world but also many average computer users in the US."

The best way to ensure access to all the encrypted information in the world is to supply the encryption. Since most of the algorithms are mathematically sound, as you point out, the implementation of these methods is the weakest link. I honestly believe this quote is referring to the total subversion, by the NSA, of our ubiquitous TrueCrypt.

What are the chances of the best "Open Source" encryption software, written by 2 anonymous people, implementing stronger encryption (triple cascading/ full drive encryption) than any other commercially available software? If you were the NSA, how would you get weak encryption implementations into everyone's hands? The answer is to provide a supposed "Open and Free" software to the world that exceeds the performance and availability of any other software. They make it seem like using anything else would be ridiculous. The NSA has said that its breakthrough decryption capabilities are "Extremely Sensitive." I believe this refers to the fact that if this becomes well known, and people start using other encryption systems, they will lose access to a ton of information.

The weak link in TrueCrypt is probably the installer file. You might actually be able to review and build a clean executable from the source code but the windows installer would compress, encrypt and store your key.

Another thing, if anyone can review the source code, why are there tons of people donating money to fund an independent review of TrueCrypt? http://istruecryptauditedyet.com/ This is a great idea, as long as we can trust the auditors. I could see the NSA dropping a bag of money on a couple software auditors, or creating a subsidiary of another company to handle the reviews.

Anyone that mentions anything about the potential weaknesses of this software is shot down immediately by people repeating everything they've heard about "Its Open Source so its better!" Are there really encryption fanboys? Government shills sound more likely.

I'm not sure if TrueCrypt started out as Open Source software, and then through whatever means the NSA took over development and distribution, or if it was an NSA creation from the very beginning. They've already proven their programming prowess and ambition with Stuxnet and Flame.

Look, the NSA obviously had to design their own cryptographic software to secure their own systems- Why not use that same software with an added backdoor to release to the world as the supposed "open-source" software solution to all government, business, and personal cryptographic needs? Its too good to be true! They get to securely encrypt all their own information while gaining access to the bulk of the world's highly guarded secrets. From industrial espionage, political spying, to high priority criminal/terror cases and every average encrypter in the US. Its a Win-Win for the NSA and this is exactly how they work! The story of the Brazilian Banker that evaded prosecution thanks to his TrueCrypt encrypted HDDs is obviously trumpeted around for the "street cred"- not to mention I've only heard of one supposed South American student that was able to build the executable file from the source code.

They pressured their way into Lotus Notes back in the 90's along with Windows 95. The Bit-Locker team recently put up a good fight too. The NSA probably realized that if they're the ones making the software, then they won't have to beg, blackmail, and bribe their way into the backdoor, they can just design a perfect side entrance. The only way to get everyone to use it would be to make it open-source and written by anonymous developers.

Leave a comment

Allowed HTML: <a href="URL"> • <em> <cite> <i> • <strong> <b> • <sub> <sup> • <ul> <ol> <li> • <blockquote> <pre>

Photo of Bruce Schneier by Per Ervland.

Schneier on Security is a personal website. Opinions expressed are not necessarily those of Co3 Systems, Inc..