Beta

Slashdot: News for Nerds

×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

NSA Trying To Build Quantum Computer

Soulskill posted about 7 months ago | from the looking-forward-to-quantum-leaks dept.

Encryption 221

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."

cancel ×

221 comments

One word (5, Funny)

Anonymous Coward | about 7 months ago | (#45856683)

Bitcoin mining.

Ok, 2 words.

Re:One word (0)

ninlilizi (2759613) | about 7 months ago | (#45856907)

Exactly,
For all the unknowns in bitcoins history. Such a thing could as easily be a clever way of crowd sourcing the generation of massive rainbow tables.

durrrrr (1)

Anonymous Coward | about 7 months ago | (#45857705)

you don't know what you're talking about

Re:durrrrr (0)

Anonymous Coward | about 7 months ago | (#45857933)

To be fair, rainbow tables are becoming more useful thanks to the growing desire of people to store bitcoins in low-entropy brain wallets.

Re:One word (1)

pla (258480) | about 7 months ago | (#45857945)

For all the unknowns in bitcoins history. Such a thing could as easily be a clever way of crowd sourcing the generation of massive rainbow tables.

First, that doesn't in any way count as an unknown. You can actually step through the entire blockchain and see every single input and output that led to the acceptance of that particular block.

Second, BitCoin mining has the "goal" of coming up with the lowest hash. For the same reason it currently takes 10-20 times the total processing power of the entire TOP500 supercomputer list, to crank out one BTC block every 10 minutes or so, you will virtually never see a hash with anywhere near that many leading zeros in a real world situation.

And finally, I think you underestimate the size of the problem space involved here - Yes, you could conceivably use the blockchain as a sort of rainbow table, but one so sparsely populated and with low-probability hashes (as mentioned above), that it only works as the "reverse" of exactly one thing: The dual-SHA256 hash of a given Bitcoin block.

Re:One word (2, Informative)

Anonymous Coward | about 7 months ago | (#45857735)

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 (2, Informative)

Anonymous Coward | about 7 months ago | (#45857757)

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).

What They Need ... (0)

Anonymous Coward | about 7 months ago | (#45856709)

What they need is a bigger Faraday cage to keep the non-NSA snoops from disrupting their cubits.

Re:What They Need ... (0)

Anonymous Coward | about 7 months ago | (#45857721)

It's qubits. A cubit is a unit of measurement from a man's elbow to the tip of his middle finger.

Actually... (5, Funny)

i kan reed (749298) | about 7 months ago | (#45856713)

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... (5, Funny)

i kan reed (749298) | about 7 months ago | (#45856739)

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

Re:Actually... (0)

Anonymous Coward | about 7 months ago | (#45856791)

I see you've picked up on the NSA's new definition of the Uncertainty Principle.

Comment is not flamebait, it's a physics pun (1)

blach (25515) | about 7 months ago | (#45856887)

Moderators asleep at the wheel. Moderated flamebait? It's clearly a pun about quantum states. *sigh*

Re:Comment is not flamebait, it's a physics pun (2, Interesting)

i kan reed (749298) | about 7 months ago | (#45856905)

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.

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

Anonymous Coward | about 7 months ago | (#45856937)

Cold fjord must have mod points today.

Re:Comment is not flamebait, it's a physics pun (4, Funny)

nobuddy (952985) | about 7 months ago | (#45856983)

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.

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

Anonymous Coward | about 7 months ago | (#45857293)

Pretty please tell me you're not joking. Source?

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

tolkienfan (892463) | about 7 months ago | (#45857517)

Supposing that happened to me. Hypothetically, of course. Is there a way to appeal?

Re:Actually... (0)

Anonymous Coward | about 7 months ago | (#45856993)

It's a tool to justify spending. After all, even if they end up junking it, the elite at the top of the NSA pyramid still get to leverage that $80 million cash flow for personal gain.

Re:Actually... (3, Informative)

i kan reed (749298) | about 7 months ago | (#45857065)

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... (0)

Anonymous Coward | about 7 months ago | (#45857385)

That's great, but in the end, that $80 million cash flow will be leveraged by somebody in government, somewhere upstream on the hierarchy, for personal gain -- and this is the primary reason they want the money in the first place. They don't give a damn whether the project "succeeds" or "fails". More often than not, in government failure is rewarded with yet even more funding. That only happens when the ultimate objective is simply to get the money.

Re:Actually... (2)

i kan reed (749298) | about 7 months ago | (#45857543)

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?

Re:Actually... (3, Funny)

Anonymous Coward | about 7 months ago | (#45857043)

This explains why there are cats on the internet.

Re:Actually... (0)

Anonymous Coward | about 7 months ago | (#45857621)

This explains why there are cats on the internet.

Yeah but most of them are alive.

This is news? (0)

Anonymous Coward | about 7 months ago | (#45856735)

Gee, I'm shocked.

Government of the peephole (5, Funny)

ciderbrew (1860166) | about 7 months ago | (#45856745)

For the peephole by the peephole.

Re:Government of the peephole (0)

Anonymous Coward | about 7 months ago | (#45857677)

It's government in your bunghole...

$79.7 million? (4, Insightful)

Anonymous Coward | about 7 months ago | (#45856753)

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.

Re:$79.7 million? (0)

Anonymous Coward | about 7 months ago | (#45856841)

I think the article got it wrong. The $79.7 million is their PR budget for this project.

No shit? (2)

jasno (124830) | about 7 months ago | (#45856761)

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? (5, Insightful)

Spectre (1685) | about 7 months ago | (#45857257)

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? (4, Insightful)

MightyMartian (840721) | about 7 months ago | (#45857837)

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.

Which part is most disturbing? (4, Interesting)

meustrus (1588597) | about 7 months ago | (#45856807)

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? (5, Interesting)

ledow (319597) | about 7 months ago | (#45856997)

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? (1)

Anonymous Coward | about 7 months ago | (#45857211)

> 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).

My understanding is that they did not use it much, if at all, because computers at the time were not sufficiently powerful to deal with anything other than toy examples. When the hardware caught up, civilian research was already there.

Re:Which part is most disturbing? (5, Funny)

amorsen (7485) | about 7 months ago | (#45857383)

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? (4, Insightful)

Antipater (2053064) | about 7 months ago | (#45857051)

$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? (1)

Anonymous Coward | about 7 months ago | (#45857497)

which half though?

Re:Which part is most disturbing? (1)

Anonymous Coward | about 7 months ago | (#45857785)

which half though?

The one that asphyxiates the pilots.

Re:Which part is most disturbing? (0)

Anonymous Coward | about 7 months ago | (#45857089)

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 classical security of any kind.

FTFY

Re:Which part is most disturbing? (0)

Anonymous Coward | about 7 months ago | (#45857487)

It's not a lot of money and it's towards more research. I would prefer the money be spent the more normal open way as I doubt NSA would show their findings in a timely fashion. If $80mil is enough to "break encryption for everyone", I would rather us be leading that. It would mean any big player could do it.

Very little reassuring (2)

rolfwind (528248) | about 7 months ago | (#45856853)

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.

They didn't pay enough (0)

Anonymous Coward | about 7 months ago | (#45856855)

Obviously, the NSA is having a hard time cracking the encryption because they haven't paid the creators enough dough to spill the beans.

'When done properly' (2, Interesting)

BobMcD (601576) | about 7 months ago | (#45856877)

"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.

Re:'When done properly' (1)

amorsen (7485) | about 7 months ago | (#45857631)

The "since the NSA is still working so hard to defeat it" part is wrong, sadly.

Imagine if you were in charge of NSA. Your agents have broken every encryption protocol and algorithm, they can tap into data anywhere in the world at any time, nothing is safe from them. Now, completely victorious, would you fund research into quantum computing? Of course you would. Why not? It is obviously within scope of the NSA mission, and you can never be sure that the "happy" state of complete unfettered access will continue forever. Besides, the NSA has a reputation to maintain.

Some background facts (4, Informative)

hweimer (709734) | about 7 months ago | (#45856889)

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 [quantenblog.net] . Moreover, one also has to keep in mind that there are public key cryptosystems [wikipedia.org] that most likely cannot be cracked even with quantum computers.

Re:Some background facts (1)

Rich0 (548339) | about 7 months ago | (#45857199)

Moreover, one also has to keep in mind that there are public key cryptosystems [wikipedia.org] that most likely cannot be cracked even with quantum computers.

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.

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. They obviously don't have high citation rates so the academics tend to look down on them. However, the story of differential cryptanalysis proves that academics aren't always the ones in the lead. Apparently IBM was aware of the technique at least 10 years before it was published, and the NSA was aware of it much longer than that (though nobody knows how long) - this is why DES lasted as long as it did (indeed, the gimped key size is its biggest flaw and 3DES is still reasonably secure though it isn't really future-proof).

For all we know the NSA has a bunch of quantum algorithms just waiting for hardware to run it on. They certainly have a long history of bright cryptographers. Where they might struggle is the physics side, but they certainly could hire promising scientists and give them lots of money. The thing I've found interesting about quantum computing is that there are many different measurement technologies that can be brought to bear that all are fairly well-developed. You have everything from SQUID to NMR, various states of matter for the qubits, nanotechnology, and so on. If the NSA has the budget to pursue many different technologies seriously they could potentially stumble on something that everybody else misses.

Re:Some background facts (2)

hweimer (709734) | about 7 months ago | (#45857565)

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:Some background facts (1)

FrangoAssado (561740) | about 7 months ago | (#45857885)

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 anything; the same is true for classical algorithms.

That's hardly surprising if you understand what proving anything like that would entail. Hell, to prove you can't break ECC or RSA with a classical computer you'd have to prove P!=NP, since discrete log and factoring are in NP. (To see why, just note that fast factoring would break RSA, so to prove you can't break RSA you have to prove that fast factoring is impossible, which means that you have to prove that factoring is not in P -- but since factoring is in NP, you'd also be proving P!=NP).

Note, however, that proving that ECC or RSA are breakable does not require a proof of P=NP or P!=NP -- for example, you don't need fast factoring to break RSA.

Quantum computers arn't magic (5, Interesting)

Viol8 (599362) | about 7 months ago | (#45856909)

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 (3, Informative)

compro01 (777531) | about 7 months ago | (#45857125)

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 (1)

i kan reed (749298) | about 7 months ago | (#45857351)

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

"Hey, Alice"
"Hey, Bob"
"See anyone around, Alice?"
"Nope, you?"
"Nope"
"Here, take this thumb drive with my pictures, the 6th of which totally doens't hide my encryption key"
"Sure thing, Alice"

Re:Quantum computers arn't magic (1)

Kielistic (1273232) | about 7 months ago | (#45857659)

That isn't terribly useful on the Internet. You also need to keep track of a lot of keys that way. Public-key systems are just so much more user-friendly.

Re:Quantum computers arn't magic (2)

i kan reed (749298) | about 7 months ago | (#45857731)

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

Re:Quantum computers arn't magic (1)

Kielistic (1273232) | about 7 months ago | (#45857791)

Currently I can still choose both (theoretically).

Re:Quantum computers arn't magic (1)

Rich0 (548339) | about 7 months ago | (#45857243)

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.

Well, nobody would even use a quantum computer to implement a non-quantum algorithm. Since we don't know how to build a practical quantum computer at all it is hard to tell whether it will be harder for the NSA to add more qubits to their designs than it will be for everybody else to use RSA with a 2 gigabit key and a 32-core system to serve an SSL website to 3 users at a time. Adding bits to an encryption algorithm has its costs as well. Quantum computing is remarkably efficient so the NSA might just need one machine, and if the design is sure to work you can bet they'll have the budget to build it.

Security through Obscurity. (0)

Anonymous Coward | about 7 months ago | (#45856921)

Hey, no worries, hide messages in plain sight with no encryption!
They'd never think to look there!

Re:Security through Obscurity. (1)

nobuddy (952985) | about 7 months ago | (#45857075)

We will be doing old school cyphers soon.

Anyone else have a copy of "Where The Red Fern Grows"?
First word: P7,line7, word 3.
Second word....

Wasn't this news 20 years ago? (0)

hubie (108345) | about 7 months ago | (#45856953)

Google is mainly returning all links to this story, but I seem to recall from at least 15 to 20 years ago when quantum computing became a popular issue, that cracking encryption keys was exactly the thing you'd use a quantum computer for. There was all this discussion of how many bits you should use for key generation, and how safe it would be ("It would take you the age of the Universe to crack 256 bits, even when harnessing all the computers on Earth, but a quantum computer could crack it in an hour" and stuff like that). It was no secret that the NSA was working on quantum computer technology then as well.

The NSA does all sorts of cutting-edge research in mathematics and computer sciences, so you can pretty much write a story that says "The NSA is working on a program to [insert futuristic computer-related topic]". Other than making for breathless headlines, is ANYONE surprised that they have a quantum computing program?

Re:Wasn't this news 20 years ago? (1)

wile_e_wonka (934864) | about 7 months ago | (#45857379)

It was no secret that the NSA was working on quantum computer technology then as well.

Speaking of it being "no secret," here is the public website for the quantum computing initiative at the Los Alamos National Laboratory:
http://quantum.lanl.gov/ [lanl.gov]
That page says:

Quantum information science and technology research is conducted at several outstanding universities and laboratories around the world, including LANL. At Los Alamos, however, even the most basic quantum research often has national security implications or connections.

Although the Quantum Initiative's national security mission at Los Alamos is manifest in many areas, it is perhaps most evident in two of the Laboratory's most successful quantum technology initiatives— quantum cryptography and the race for a quantum computer.

Los Alamos National Laboratory, of course, is owned and operated by the U.S. Federal Government. The fact that the Government has been working on this for some time (since the 90s) has not been a secret.

The Laboratory also revealed recently, as was reported on /. [slashdot.org] that it has been operating a quantum network for 2 1/2 years. Though I feel certain I read about that in Technology Review or the like a couple years ago, but cannot find any such article now.

And they called me crazy (3, Funny)

lagomorpha2 (1376475) | about 7 months ago | (#45856957)

...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 (0)

Anonymous Coward | about 7 months ago | (#45857477)

Hawk??

Re:And they called me crazy (0)

Anonymous Coward | about 7 months ago | (#45857629)

My boss called me crazy years ago for suggesting that I would put electrical tape over my computer's webcam.

Re:And they called me crazy (0)

Anonymous Coward | about 7 months ago | (#45857647)

Your memory sticks were the fraudulent 256MB type. You are reading zeroes from the key material now. Proof: I can read your post without difficulty despite not having one of the drives.

Of course they call you crazy (1)

davidwr (791652) | about 7 months ago | (#45857707)

Why should they trust those memory sticks you are giving them? After all, you might have gotten them from a manufacturer whose factory was hacked and the USB drives are silently corrupting data in random ways.

posted from secret volcano lair

Now I know you are either crazy or crazy like a fox. Since only a relatively small part of the Earth's surface has placed where you could put a volcano lair, I'm a lot closer to knowing where you are. Or maybe you are lying and crazy like a fox, in which case I say "well played, sir, well played."

If by chance you aren't on the Earth yet you still managed to pot to Slashdot, I say "VERY well played, sir, VERY well played."

Don't hold you breath (0)

Anonymous Coward | about 7 months ago | (#45856961)

It will be interesting when someone shows that they can factor 15 with a scalable algorithm.

Until then it's just a toy.

huh? (1)

DriveDog (822962) | about 7 months ago | (#45856989)

Surely it wouldn't be so easy for the NSA to get people to trust current systems as to just say they're building a quantum computer to crack those (because they can't otherwise)? Come on, that's an old trick. CIA pulled it on the Soviets, stealing a cypher machine to cover an agent who'd already provided the means of decrypting their messages, hoping the Soviets would stop investigating the agent. So the Soviets appeared to stop investigating.

Maybe the NSA can't crack some current codes, and is building a quantum computer to do so. But the converse isn't necessarily true. Maybe the US really couldn't read Soviet messages until CIA stole the machine (known as a "smoking bolt" operation, according to Tony Mendez). But I have trouble believing everyone in the KGB really bought that. James Jesus Angleton would not have.

Solution (1)

IamTheRealMike (537420) | about 7 months ago | (#45857003)

Switch to ring learning-with-errors [iacr.org] , which was proven by Regev to reduce in the average case to the hardness of some worst case integer lattice problems. Crypto systems built in this way are believed to not be affected by quantum computers and research is proceeding fast as a result. The fact that the NSA is no further ahead than anyone else is reassuring - we know how to build post-quantum crypto systems, the work that remains is largely in the "maturing" phase rather than the "wtf do we do now" phase.

Re:Solution (1)

Rich0 (548339) | about 7 months ago | (#45857335)

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.

A few important points (1)

Anonymous Coward | about 7 months ago | (#45857053)

Classic* public-key crypto (SSL, TLS, GPG, PGP) would be dead except, and this is quite interesting, except the one based on elliptic curves, which NSA has been advocating for for a long time.

Symmetric crypto (data at rest, file/disk encryption) would be affected, but not so badly. The key size would be halved. So Twofish with a 256-bit key would be as strong as Twofish with a 128-bit key (note that this means it would be 2^128 times easier to brute force, NOT twice as easy).

* By classic I mean DH and RSA-based.

They'll botch it. (1)

vikingpower (768921) | about 7 months ago | (#45857057)

They are a dinosaurian government agency, that has a habit of gobbling up money by the truckload. They have no reputation for technical or scientific excellence whatsoever. Neither do they have a track record in building first-rate equipment or software. Moreover, they have been proved, over and over again, to be pathological liars. In other words: who gives a shit ??

Re:They'll botch it. (0)

Anonymous Coward | about 7 months ago | (#45857357)

This [slashdot.org] doesn't seem trivial to me, and everything I've heard about the NSA from folks who've worked there suggests their technical skills are incredibly high, just wasted by management.

Least interesting relevation so far (0)

Anonymous Coward | about 7 months ago | (#45857061)

I feel like the NSA would be remiss if they weren't investigating Quantum Computing. Breaking other people's encryption is completely in their remit. They could (and probably will) abuse the part about when & when it's *used*, but the simple fact that they're looking into it is not problematic to me.

Fact is, the NSA doesn't have a technology problem. They have a massive *targeting* problem. If they were using the technology they have *and* following the constitution, there would be no problems. But, blanket spying on everyone is not okay. That's the problem. Investigating quantum computing is totally fine for them to be doing. Using quantum computing to break everyone's keys in the entire world is not fine.

Re:Least interesting relevation so far (0)

Anonymous Coward | about 7 months ago | (#45858053)

Fact is, the NSA doesn't have a technology problem. They have a massive *targeting* problem. If they were using the technology they have *and* following the constitution, there would be no problems. But, blanket spying on everyone is not okay. That's the problem. Investigating quantum computing is totally fine for them to be doing. Using quantum computing to break everyone's keys in the entire world is not fine.

This.

But that catalog of persistent exploits that could be placed on single targeted machines and/or network hardware? Fascinating reading, I didn't need to know that, (and since I have no clearance to lose by knowing it) cool beans. Quantum computer? A lot of stuff was redacted from those pages, but from what was there, I'm either kinda disappointed they hadn't made further progress, or reassured that if they had, it was sufficiently compartmentalized that it wasn't part of the leak.

If NSA would just stop with the parallel construction BS and dragnet surveillance (give me every word ever written by every American, and even I could find six upon which to hang each of them in court, which is precisely the problem), they wouldn't feel the need to compromise US corporations or backdoor NIST's crypto standards, and they might just re-earn their once-white-hat reputation in about 20 years.

Ha ha. I wouldn't worry too much... (1)

cyn1c77 (928549) | about 7 months ago | (#45857091)

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.

There is quite a bit of fearmongering here...

Given that they couldn't even secure their internal network properly, it would seem highly unlikely that the NSA has the commitment, expertise, or efficiency to secretly develop cutting edge technology far in excess of what the best academics in the world can do.

That said, instead of everyone standing around and wringing their hands, maybe now would be a good time to start developing more secure encryption algorithms that are more robust to brute force attacks. The encryption community has been resting on their laurels for quite a while now.

This is what they should be working on (4, Insightful)

wcrowe (94389) | about 7 months ago | (#45857099)

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.

Re:This is what they should be working on (1)

asylumx (881307) | about 7 months ago | (#45857291)

I've said similar before -- the same goes for their data mining techniques. Sure it's being used inappropriately, but the fact they are able to collect, store, and analyze such an humongous data set is really a marvel of computer science.

Remember, rockets were used to kill people before they were used to take people to space. Lots of inventions are created for the wrong purpose and then later used for good.

Mod parent up (1)

davidwr (791652) | about 7 months ago | (#45857723)

Yes, yes, yes. If they'd spend their money on this instead of invading American's privacy, maybe they'd be a few months further down the road than they are.

Who would be surprised by this? (0)

daveschroeder (516195) | about 7 months ago | (#45857111)

One of NSA's chief missions is breaking encryption. So (for the US folks among us) it's okay when it's the German or Japanese codes in WWII, but somehow sinister when the reality is that much of the world now shares the same tools, systems, services, networks, encryption standards, etc.?

In a free society governed by the rule of law, it is not the capability, but the law, that is paramount. And for all of the carping and hand-wringing about what NSA is doing because its capabilities continue to be laid bare, where is the worry about what states like China and Russia are doing?

Re: Who would be surprised by this? (0)

Anonymous Coward | about 7 months ago | (#45857505)

The worry is there for China et al, but people on the U.S. and other five-eyes states don't have any way to influence their politicians to make the Chinese NSA equivalent behave.

The problem is that we can't even make our OWN agencies behave, because the oversight process is BROKEN.

Re:Who would be surprised by this? (0)

Anonymous Coward | about 7 months ago | (#45857603)

it's okay when it's the German or Japanese codes in WWII, but somehow sinister when it's used on Americans

FTFY. And yes, it is sinister. I bet even the jackboot lickers like you and cold fjord would absolutely agree if I said "it's ok when its our soldiers shooting up German or Japanese soldiers in WWII but somehow sinister when they shoot up Americans".

Espionage is an act of war. Americans committing acts of war against their fellow Americans is treason. It's right there in the Constitution.

Re:Who would be surprised by this? (0)

Anonymous Coward | about 7 months ago | (#45858109)

In a free society governed by the rule of law, it is not the capability, but the law, that is paramount. And for all of the carping and hand-wringing about what NSA is doing because its capabilities continue to be laid bare, where is the worry about what states like China and Russia are doing?

I'm neither Russian nor Chinese. They can worry about the loss of the rule of law in Russia and China.

I live in America, and I am worried about the end of the rule of law in America. When you eliminate the Fourth (and harm the Third, for is not giving NSA carte-blance access to one's business records the electronic quivalent of quartering troops), you also harm the First. Clapper is free to lie to Congress. Americans self-censor when they think about searching for something they read in the news. "Careful, you don't wanna google that, you might end up on a watch list..."

That's not entirely the end of the rule of law, but it's a damn big warning sign.

Good (2)

jgotts (2785) | about 7 months ago | (#45857227)

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.

Post-Quantum Cryptography (0)

Anonymous Coward | about 7 months ago | (#45857265)

This is why we need research into post-quantum cryptography.

http://en.wikipedia.org/wiki/Post-quantum_cryptography

But... (0)

Anonymous Coward | about 7 months ago | (#45857401)

Information wants to be free!

I thought the disclosure of private information is to be lauded?

Never happen. (1)

RightSaidFred99 (874576) | about 7 months ago | (#45857431)

"Quantum Computing" is hogwash. I'll eat my shoe when they can crack even a tiny RSA key, say the smallest possible, faster than a conventional chip.

Re:Never happen. (0)

Anonymous Coward | about 7 months ago | (#45857741)

That must be why there is a whole field of study around finding encryption systems that are not crackable even with quantum computers.

http://en.wikipedia.org/wiki/Post-quantum_cryptography

Re:Never happen. (0)

RightSaidFred99 (874576) | about 7 months ago | (#45858003)

True, good point. On an unrelated topic, horoscopes work. I mean, there is a whole field of study around it. http://en.wikipedia.org/wiki/Astrology [wikipedia.org]

Re:Never happen. (0)

Anonymous Coward | about 7 months ago | (#45857747)

They did crack the smallest possible RSA key, didn't they? The public key was n=15, the private key was p=3, q=5.

Re:Never happen. (1)

r2kordmaa (1163933) | about 7 months ago | (#45857931)

Oh it'll happen sooner or later, science behind it is sound, you can practically build quantum computers and they work. The problem is that while there are plenty of prototype computers out there, they can still only do operations with few qbits and thats no good for practical applications. While developing computers with more qbits is not exactly easy, it is very much doable, its an engieneering problem now, not something that would require a novel scientific breakthrough.

this reminds me of a horrible dan brown book (1)

netsavior (627338) | about 7 months ago | (#45857445)

"Digital Fortress" wherein a rogue NSA cryptographer out to save and or destroy a 12-ton NSA codebreaking (quantum?) computer gets chased by a blind assassin for some reason... and a 64 BIT encryption key was pressed into a gold ring, but was somehow made up of 64 ascii characters.

Don't worry because (spoiler) the "enigma" or whatever melted down when a virus caused it to something something, not even the fat IT guy named Jabba was able to stop the awesome power of something something. I am not even joking.

Although since it is written from the point of view of an NSA "genius," I suppose the glaring errors make it a lot more realistic.

Don't worry (1)

Virtucon (127420) | about 7 months ago | (#45857617)

It's a government project. Eventually the contractors involved will screw the project up and they'll have to announce it in a secret meeting on the black budget. They'll then ask for billions more to develop a solution to a so-called quantum computer gap that exists with the Chinese and Russians. The Cold War with the Soviets may be over but we're in a new Cold War with BRIC [wikipedia.org] and the stakes are more along the lines of economic vs. military.

Re:Don't worry (1)

jasper160 (2642717) | about 7 months ago | (#45857699)

And which politician's family member will be sitting on the board of the contracting companies?

Re:Don't worry (1)

Virtucon (127420) | about 7 months ago | (#45857927)

You have that wrong, it'll be an ex-congressman on the board not a family member.

Re:Don't worry (1)

jasper160 (2642717) | about 7 months ago | (#45858129)

Also true, both can happen. Here in Minnesota all the license plates had to be changed a few years ago; later it was found the state senatewhore who pushed for the bill failed to mention his brother in-law owned the company making them.

Quantum encryption (1)

Conspiracy_Of_Doves (236787) | about 7 months ago | (#45857899)

Once such a thing is achieved, can't it be duplicated and used for quantum encryption for everyone?

operative term "trying" (1)

r2kordmaa (1163933) | about 7 months ago | (#45857937)

Theres a world of difference between trying and succeeding. Still its not bad that money is pumped into quant computing research, someone is going to crack the problem sooner or later anyway, and it will cause problems for cryptography and security anyway. But cracking crypto is hardly the only thing you can do with practical quant computer, having one would literally mean quantum jump in engineering and science research. The boost it would give world of science greatly outweighs the risk of NSA cracking your porn archive open.

How far away is it? (1)

Soluzar (1957050) | about 7 months ago | (#45857973)

Has anything practical actually been demonstrated in the field of quantum computing yet? I understand that a lot of exciting and complex (if you're into that) math has gone into describing a model for how quantum computing should function, but as far as I'm aware nobody has actually managed to build any prototype devices yet.

When I first heard the term "quantum computing", I believed it to be a meaningless buzzword. I think at that time it may have been so. Now it is obviously a real concept, but unless I may be better informed, I think it is still a very long way off.

I wonder if programming for a quantum computer will be anything like programming for the digital (is that the proper term to use in contrast?) computers we have now. I can't help but feel that it would be both very different and rather more difficult.

Great (1)

PPH (736903) | about 7 months ago | (#45858137)

And when they drag me into court for some conspiracy, I'll just cite Heisenberg's Uncertainty Principle and SchrÃdinger's cat as basis for reasonable doubt and get off scott free.

Are there no terrorists (1)

future assassin (639396) | about 7 months ago | (#45858149)

out there to save us from the NSA?

Load More Comments
Slashdot Account

Need an Account?

Forgot your password?

Don't worry, we never post anything without your permission.

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>
Create a Slashdot Account

Loading...