NSA Trying To Build Quantum Computer

New submitter sumoinsanity writes "The Washington Post has disclosed that the NSA is trying to build a quantum computer for use in cracking modern encryption. Their work is part of a research project into tackling the toughest equipment, which received $79.7 million in total funding. Another article makes the case that the NSA's quantum computing efforts are both disturbing and reassuring. The reassuring part is that public key infrastructure is still OK when done properly, since the NSA is still working so hard to defeat it. It's also highly unlikely that the NSA has achieved significant progress without outside awareness or help. More disturbing is that it may simply be a matter of time before it fails, and our private messages are out there for all to see."

Comments

One word

[Anonymous Coward]

Bitcoin mining.

Ok, 2 words.

Re:One word

[Anonymous Coward]

Quantum computing would only give you a modest square root speed up on computing the hash functions. You could however break the elliptic curve signature algorithm and sign all the coins to yourself.

Re: One word

[Anonymous Coward]

You wouldn't use this to mine bitcoins (since that involves finding a hash with specific properties), but you might use it to steal them (the secret part of your wallet is a private key).

Actually...

[i kan reed]

It's a tool to help them justify congress how they can be spying on all Americans and not spying on any Americans at the same time.

Re:Actually...

[i kan reed]

The main joke of my post here is that congress actually cares.

Re:Actually...

[Anonymous Coward]

This explains why there are cats on the internet.

Re:Actually...

[i kan reed]

The elite at the top are actually temporary political positions that come and go with presidents. The worst of the NSA programs have been continuous programs lasting between administrations.

Re:Actually...

[i kan reed]

I think Hanlon's razor is a perfectly adequate tool for this assertion. Why would someone malevolently steer towards terrible waste, when they could be "just trying to do their job" and not doing a great job it?

Government of the peephole

[ciderbrew]

For the peephole by the peephole.

$79.7 million?

[Anonymous Coward]

That figure is so small vs total intelligence+defence budget that it'd be worth setting up a faux research effort just to give the misleading impression that they haven't yet developed something far better.

No shit?

[jasno]

Come on... what's next? "NSA attempts to listen to other nation's communications"? That *is* their job, you know.

They've broken the law in letter and spirit. Let's try to keep the focus on that.

Re:No shit?

[Spectre]

Agreed, breaking encryption systems is one of the two primary reasons the NSA was formed in the first place ... this is the NSA doing what they are supposed to do!

Re:No shit?

[MightyMartian]

And if the NSA could keep its hands off of domestic data, that wouldn't be an issue, but seeing as it uses existing tools to spy without warrant on US citizens on US territory, there is no reason to believe they won't apply new technologies in the same way.

Re:No shit?

[anagama]

And if the NSA could keep its hands off of domestic data

You know what is sad-funny? If you look at the original leaked verizon order, it applies to 3 out 4 categories of phone calls:

1. those that start and end in the US
2. those that start in the US and end in a foreign country.
3. those that start in a foreign country and end in the US.

It expressly excludes calls that start and end in a foreign country. Good job focusing outward NSA.

http://www.theguardian.com/world/interactive/2013/jun/06/verizon-telephone-data-court-order

Which part is most disturbing?

[meustrus]

The disturbing part is not that the NSA might be able to listen to everyone's encryption someday. They are not an engineering organization and they will not be at the forefront of qubit manufacturing. The disturbing part is that they are wasting an enormous amount of taxpayer dollars on an impossible task aimed at ultimately destroying the ability to have security of any kind.

Re:Which part is most disturbing?

[ledow]

Worse than that - they are wasting that money on a possible task that will actually have little overall impact on security whatsoever.

Post-quantum cryptography has existed for the last 30 years, at least. And to get to the point where it's an issue, what you need is an entity to push towards quantum decryption that you DON'T want to have it (i.e. the NSA, for example).

Then all that happens is we adopt those other schemes faster, spot the holes faster, compensate for them faster, and by the time the NSA can buy a quantum machine of size enough to defeat today's encryption in a reasonable time, we'll have an established standard far beyond it's capabilities and tested for (potentially) decades.

All the NSA has done is forced the entire world to up its game. Compare and contrast to, say, GCHQ who formulated public-key-encryption several years before anyone else had done it, and KEPT IT QUIET (like spy-based agencies are supposed to). They enjoyed years of secure comms, and years of advantage decrypting other secure comms when someone else eventually discovered the exact same mathematics and got famous on it (Diffie and Helman).

Sadly, the modern GCHQ is but a shadow of its former self.

Re:Which part is most disturbing?

[Antipater]

$80 million isn't that enormous, as far as things go. That's like half of one F-22.

Re:Which part is most disturbing?

[amorsen]

The NSA is but a misunderstood genius, boldly sending their agent Edward Snowden into the arms of the enemy. Their aim is to protect the Western world from the defeat that will come as a result of ignored security vulnerabilities, lousy cryptography, people who are willing to work with corrupt government entities and so on.

See, no one would have listened if they had simply held lectures on proper security. Some might even do the opposite out of suspicion that the NSA is betraying them. The only way to fulfill their duty of keeping America safe was to send out a "whistleblower" to say all the things that they themselves could not get through with. Only then would the mass media react and the story gather enough momentum to cause every software developer to improve their work, every customer to demand better and more open security, every person to think twice when being asked to do things that are not right.

I wish.

Re:Which part is most disturbing?

[thue]

> Then all that happens is we adopt those other schemes faster

But what of all the encrypted old traffic that the NSA has stored?

Re:Which part is most disturbing?

[slew]

They are not an engineering organization and they will not be at the forefront of qubit manufacturing.

How do you know this? The NSA purchased an old abandoned Sony chip fab in San Antonio and started to re-commission it back in 2006, who knows what they are doing with it for the last 6 years? One of the promising target architectures for a large scale qubit is a cryogenically-cooled silicon double quantum-dot scheme. They might have more going on in this area than you might guess...

Re:Which part is most disturbing?

[LeDopore]

What post-quantum assymetric crypto is there?

Wikipedia to the rescue: https://en.wikipedia.org/wiki/Post-quantum_cryptography. My personal favorite is the McEliece cryptosystem, based on error-correcting codes: https://en.wikipedia.org/wiki/McEliece_cryptosystem. They key size is huge (well, under 1 MB still) but computation isn't too bad. I'd still recommend adding RSA plus several post-quantum schemes in an XOR chain as I described.

About increasing key size without a clear need, a lot of crypto algorithms take compute time that grows faster than linearly with key size. Executing several independent algorithms in parallel is better for two reasons: first, the key sizes of each one aren't large so don't suffer the nonlinear slowing, and second, they can be executed on separate cores in parallel.

I'd welcome advice from an expert, but my impression is that the mainstream crypto researchers think that it's more conservative to adopt a single, trusted crypto algorithm and bet the farm on it. My instincts are that this is a bad approach. Composed algorithms like the one I described where all of (say) 5 schemes must be cracked before the attacker gets anywhere are more conservative in my view since they are at least as strong as each of their constituents. However, I'm not a crypto researcher, and there might be a good reason not to shield RSA (which we know is secure to classical but not quantum attacks) with a variety of layers that each provide a good chance of being robust against a quantum attack.

When will we have quantum computers? One reasonable scenario is that by 2020 we'll have a Sputnik moment where somebody will build a quantum computer much better than the sleepy mainstream expects, yet not powerful enough to run Shore's algorithm against 1024-bit RSA. This will shock the world into a bit of a panic that a bigger quantum computer will come soon, and RSA and elliptic curves will be seen as untrustworthy by 2025. We'd be better off adding a layer of protection now, especially since we're sending data now that we wouldn't want to be public for a lot longer than 2025.

Very little reassuring

[rolfwind]

NSA always will try to expand and it's stands to reason that the Chinese and their companies aren't under NSA sway, so the backdoors they build in are not under NSA control so the NSA has to try to crack them the hard way. In no way does it mean they don't have the US population under total surveillance.

'When done properly'

[BobMcD]

"The reassuring part is that public key infrastructure is still OK when done properly, since the NSA is still working so hard to defeat it."

Unfortunately, 'when done properly' must include 'never using an American entity for key generation, storage, or distribution.' We have every reason to believe the NSA has muscled their way into possession of the master keys, Re: Lavabit. So if you're doing business with any type of PKI vendor who might be compelled to comply with a FISA court order, followed by a gag order, you might rethink it.

Remember when every browser in the world switched to the panic pages about a 'non-trusted' key?

Probably just a coincidence.

Some background facts

[hweimer]

These are hardly shocking revelations. The document mentions to achieve control over two semiconductor qubits, whereas factoring 2048 bit numbers requires at least that many qubits, and probably several orders of magnitude more. The current record stands at control of 14 qubits, achieved in 2010 in Rainer Blatt's group at the University of Innsbruck, Austria, using trapped ions.

Some time ago, I wrote something on the history and possible future of quantum computing. Moreover, one also has to keep in mind that there are public key cryptosystems that most likely cannot be cracked even with quantum computers.

Re:Some background facts

[hweimer]

The key words you used are "most likely" and at least you're honest enough to use them. There is no mathematical proof that any cipher (other than the one-time pad) is resistant to all as-yet-unknown quantum algorithms. That doesn't mean that they are actually vulnerable - only that we cannot know with certainty whether they are.

That's the usual situation in complexity theory and it applies to classical algorithms as well. There is also no proof that quantum computers are actually superior to classical computers when it comes to cryptanalysis. Still, most people believe this to be true.

People seem to under-estimate the NSA's capabilities here when I talk to them. They employ a lot of really smart people, and they have the benefits of reading all the public literature as well as all the classified stuff that their academic peers cannot read.

Remember that we're talking about actual physical devices that need to be built and being really smart only helps you somewhat when you need to solder electronics or align a laser. And so far, the NSA employs hardly any physicists which you can also tell from the fact that they've outsourced the research mentioned in the documents to a public university. This is very different than in mathematics or computer science, where it is well known that the NSA is a large employer. That being said, I still think that the NSA might possess some interesting knowledge on quantum computing. I wouldn't be too surprised if they were sitting on an efficient quantum algorithm breaking AES, for instance.

Re:Comment is not flamebait, it's a physics pun

[i kan reed]

No, see, I have just posted in a global warming thread. Someone went back and modded all my posts(just -1, no biggy), as a perfectly valid commentary on my opinions.

Quantum computers arn't magic

[Viol8]

In *theory* they can match the values of an N bit code in one go where N is the number of quantum bits. In practice it might be another matter but even if not - that simply means you use more bits in your key. Once a quantum computer has used up all its bits it has to revert to working like a standard computer and doing everything serially. So if the quantum computer is N bits and we have a key with N + 32 bits the machine will still have to try 2^32 matches. So as quantum computer registers get larger so will encryption keys. Someone builds a 256 bit quantum computer? Great! So just use a 512 bit key and it'll have to do 2^256 comparisons. ie - it'll be damn slow.

Re:Quantum computers arn't magic

[compro01]

Symmetric key encryption with sufficiently large keys is perfectly safe from a quantum computer.

But current public-key encryption (e.g. RSA) and key exchange (e.g. DHM) isn't.

Unbreakable symmetric key encryption isn't worth a damn if you have no secure means of exchanging keys.

Re:Quantum computers arn't magic

[i kan reed]

I guess the NSA is giving us a choice: user friendly or secure, choose one.

And they called me crazy

[lagomorpha2]

...and my colleagues called me crazy when I gave them 256GB USB drives full of true randomly generated one-time pads to use to decrypt my emails because I didn't trust public key.

Who's crazy now! Muhahaha! (posted from secret volcano lair)

Re:And they called me crazy

[Ckwop]

256GB USB drives full of true randomly generated one-time pads

I know this is a piece of humour but since this is Slashdot why not?

What a lot of people don't understand is that is much harder than it first appears. For example, doing cat /dev/random to a file on disk will not give you bytes suitable for use in a OTP.

The issue is that the many TRNGs hash their entropy pool with a cryptographically secure hash. When you use such a hash there is no guarantee that the input space would be uniformly mapped to the output space.

To illustrate this, suppose we had an entropy pool 1024-bits deep. Suppose before producing the output the pool is hashed with SHA-1. This is an output that 160-bits wide. There is no proof whatsoever that if we cycled a counter from 0 to 2**1024 that the hash of these would distribute evenly of 2**160 possible has outputs. If this were the case, each output hash value would appear exactly 2**864 times. It is highly unlikely that this is the case.

What this means is the the output is distinguishable from a true random source, which completely breaks the security proof for the OTP. Granted, the attacker would likely to have to do an infeasible amount of work to use this distinguisher. However, the OTPs proof gives you security from computationally unbound adversaries. It's the whole point of using the OTP!

So in short, you can't use /dev/random, you can't use pretty much any commercial random number generator. You'd have to roll your own and show that your bias is small enough for no attack to be practical. Like I said, it's harder than it looks.

Re:Comment is not flamebait, it's a physics pun

[nobuddy]

Not today. He was caught mass-modding people who disagree with him last night. All associated accounts were stripped of mod ability forever.

He will just make more, but he's dead in the water for a bit.

This is what they should be working on

[wcrowe]

The NSA deserves a lot of criticism for some of the things they've been doing. However, this is the kind of thing they should be working on. It's not the tools they have that bothers me. It is how they use them that is the problem.

Good

[jgotts]

The NSA is supposed to be working on cryptography technology.

The NSA needs to get back to doing its job, and stop spying on Americans. We already have several branches of government that are responsible for domestic criminal investigations, and they're subject (in theory anyway) to the robust safeguards in the Constitution.

The NSA helps everyone with robust cryptography. It's in nobody's best interest when one government can decipher everyone else's communications, except maybe for that handful of codebreakers.

Regardless of what they say, terrorists are low tech. They do not have access to a large pool of cryptography talent, nor will they ever.

NSA has a long history in this area

[Animats]

One NSA director in the 1960s said "I want a thousand-megacycle machine. I'll get you the money!" There's a book, "IBM's Early Computers", which shows much of NSA's exotic hardware from the 1950s through the early 1970s. High-density tape drives, the first automatic-changing tape library (TRACTOR), the first superscalar machine (STRETCH, which, for NSA, had a special crypto processor instead of an FPU), and a number of cyrogenic machines.

NSA tried hard to get cyrogenic computing to work, from the 1960s onward. They had some successes with getting devices to work fast in the 1960s, but the early superconducting devices were gated magnetically, which meant coils and discrite devices, not ICs. So they could be made fast, but not small, which means speed of light lag within the processor becomes a bottleneck. Mainstream CMOS IC technology eventually beat out the superconducting Josephson junction stuff on both price and speed. Some time in the 1980s, IBM and NSA gave up on that. It just wasn't a win over Moore's Law.

Quantum computing, though... Just maybe.

That's not reassuring

[davecb]

If I have a crack for a current cryptosystem, I'd still need to build a machine to address the next cryptosystem.

Remember the panic in Britain when the (WW2) German submarine service switched from 3-rotor to 4-rotor Enigma machines! They hadn't finished a "bombe" got 4-rotor machines, and only broke the 4-rotor code when they captured an undamaged 4-rotor machine.

That failure was one of the reasons behind building "Colossus", the first electromechanical computer. Colossus was eventually able to decrypt message from the Lorenz SZ40/42 12-wheel machines, which were much harder than the 4-wheel enigma.

Re:That's not reassuring

[davecb]

Actually they only did that for a few individual messages where the operators messed up, although they did describe it as an approach, until it was safe to admit they'd captured a 4-rotor machine from a sub. It was just declassified last year that they were so very badly stuck that they laid on the Dieppe raid in hopes they could "pinch" at least one machine from either the naval headquarters building or one of all the trawlers and e-boats based there. They failed miserably.

My wife bought me the book on it for Christmas (One Day in August: The Untold Story Behind Canada's Tragedy at Dieppe, by David O'Keefe) , as she knew the Essex Scottish was my regiment, and that I was interested in crypto.

Re:Solution

[slew]

Has it actually been proven that it is mathematically impossible for a quantum algorithm to exist capable of defeating this system? I'm sure you could prove that any particular known algorithm wouldn't work, but the only system resistant to unknown algorithms that I'm aware of is the one-time pad.

If this has been proven I'm genuinely interested. I will confess I'm not a cryptographer.

I don't know about ring-learning-with-errors, but if it indeed reduces to an integer lattice problem, I suspect it would eventually prove to be vulnerable to some sort of attack that could be executed by a quantum computer.

As a silly example, here's a proposed attack on lattices that employs a quantum computer implementing a partial Grover's algorithm to speed up looking for solutions...

http://www.cdc.informatik.tu-darmstadt.de/reports/TR/TI-03-03.QSamplingPaper.pdf

As with many things, I doubt there is a negative proof. There's much about quantum computability that we do not understand yet (of course there is much about regular computability that we don't understand either, starting with P ?= NP). When people usually say it's resistant to quantum computers, they actually are implying that it's resistant to a quantum computer employing Shor's algorithm (and similar quantum fourier transform techiques) to factor large numbers and compute discrete logarithms (the basis behind the RSA and DH public key cryptosystems). There are other algorithms that quantum computer can run, most of which people have not even discovered yet.