NSA Trying To Build Quantum Computer 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."
Which part is most disturbing? (Score:5, Interesting)
'When done properly' (Score:3, Interesting)
"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:Comment is not flamebait, it's a physics pun (Score:3, Interesting)
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 (Score:5, Interesting)
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:Which part is most disturbing? (Score:5, Interesting)
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:And they called me crazy (Score:4, Interesting)
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.