While the US and British governments undoubtedly have the resources to obtain the best computers and cryptographers that money can buy, they cannot (at far as I know) break really good encryption systems. This is why they have achieved much of their success the old-fashioned way and resorted to cheating, such as getting computer and chip makers and communication companies to collaborate with them to install back doors. News reports based on leaked documents by (who else?) Edward Snowden show that the NSA may have bribed RSA, one of the most important companies in the security industry, to get them to provide a loophole that the NSA could exploit.
Documents leaked by former NSA contractor Edward Snowden show that the NSA created and promulgated a flawed formula for generating random numbers to create a “back door” in encryption products, the New York Times reported in September. Reuters later reported that RSA became the most important distributor of that formula by rolling it into a software tool called Bsafe that is used to enhance security in personal computers and many other products.
Undisclosed until now was that RSA received $10 million in a deal that set the NSA formula as the preferred, or default, method for number generation in the BSafe software, according to two sources familiar with the contract.
One consequence of revelations such as this is that computer security professionals are being urged to boycott a conference organized by RSA. Another consequence is that companies are being asked to avoid compromised chip makers like Intel and Via Technologies. The cryptographic systems depend on random number generators built into the hardware and these are thought to have also been compromised
The basic problem for the NSA is that the best encryption involves prime numbers and breaking them involves factoring a number into two primes. As a simplified example, a communication may use the number 35 as part of its scrambling process. The NSA and GCHQ can get hold of that number easily but what they really need to unencrypt the message is not just the number 35 but its two prime factors 5 and 7. This factoring problem starts getting incredibly difficult as the number gets larger and it is a game in which the encrypter has the advantage.
In 2009, computer scientists using classical methods were able to discover the primes within a 768-bit number, but it took almost two years and hundreds of computers to factor it. The scientists estimated that it would take 1,000 times longer to break a 1,024-bit encryption key, which is commonly used for online transactions.
As the NSA and its accomplices in other countries get bigger and more powerful computers and its cryptographers develop better algorithms, all that needs to be done to defy them is to use yet larger numbers, requiring yet larger computers.
A huge leap in computer technology would be the development of so-called quantum computers. These are computers that designed based of the idea of ‘quantum superposition’. This is when that what we think of as two distinct states can co-exist simultaneously. It is bascially the Schrodinger Cat problem. Such a computer, if it could be built, would reduce enormously the time taken to solve massive problems, including the ones involving factoring of large numbers into their component primes.
A large-scale quantum computer, however, could theoretically break a 1,024-bit encryption much faster. Some leading Internet companies are moving to 2,048-bit keys, but even those are thought to be vulnerable to rapid decryption with a quantum computer.
Christopher Monroe is one of those scientists who worked on the NSA’s quantum computer program.
The reasons for trying to build a quantum computer are no secret. Most of the world’s computers encrypt their data using very large numbers. To break the code, spy agencies have to divide the numbers by other numbers — prime numbers. Finding the right prime numbers can take a while.
“A thousand-digit number might take a full year of a team of supercomputers,” says Monroe. “You can add another hundred digits, and forget it — you won’t be able to ever do it.”
…That’s where a quantum computer comes in. Most computers work using bits of data — ones and zeros. The bits in quantum computers can be both one and zero at the same time. What’s more, these quantum bits can all be interconnected in a fundamental way. Known as entanglement, this connecting of bits effectively allows the computer to try many numbers at once.
“It can look at them all at the same time and there’s a huge speed-up by doing that,” Monroe says.
A code that was impossible to break could be cracked in weeks, days — maybe even hours.
Naturally, scientists have been working on supercomputers for a long time because it is both an interesting and important problem and it should be no surprise that the Snowden documents reveal that the NSA has also been pouring vast resources into it, although there is no evidence that they have been more successful than other scientists.
The tricky thing about quantum superposition is maintaining that state over time. The superposed states are called ‘coherent’ but they are highly sensitive to interactions, even thermal ones, with the environment. Even the slightest disturbance can cause the states to ‘decohere’ and lose their superpositioning and drop into one or the other states. Creating a large-scale quantum computer and keeping these delicate systems isolated in order to maintain coherence is a huge technological challenge.
I take it the issue with quantum computers isn’t just speed, otherwise one could just use a quantum computer to generate even bigger primes with a bigger product that would defeat the code-breakers’ quantum computers. I’m assuming the issue is that there are faster factoring algorithms that would work under quantum computing but not such faster algorithms for generating the very large primes?
I don’t know much about quantum computing — I guess I’m eventually going to have to look into it.
Does anyone know what else that flawed random-number generator was used in? Or whether the deviations would be sufficient to affect scientific modeling efforts?
IMHO this is one of the very few things we need the government snoops to be pouring megabucks into investigating. If the mechanisms in use to protect the launch codes are compromised by newly-practical computing technologies, I want “our” snoops to know about it before “their” snoops.
The difference is that a quantum computer essentially calculates all possible solutions simultaneously. They don’t just repeat the same process but faster. Rather, they solve every instance of the problem all at once. Sort of. There are engineering problems that slow it down mightily, but I digress.
That’s why you can’t just throw more bits at the problem. The founding assumption of cryptography, that you have to guess and test every possible solution individually until you find the right one, is not true with quantum computing.
@Chiroptera
Look up Shor’s Algorithm, which is how a Quantum Computer would factor numbers (it uses operations that are impossible with a normal computer). We’ve demonstrated the algorithm with some of the small quantum computers that we’ve developed.
We have developed algorithms that are “quantum-safe,” though. Notably, Lattice-Based Cryptography. However, it’s not used because it’s far less efficient than RSA, Discrete Logs, or Elliptic Curve. Until quantum computers actually become a threat (and they aren’t a threat), there’s no real reason to use Lattice stuff.
@Chiroptera
As I understand it, the only way to break the number into its primes is by what they call brute force, aka trial and error. The primes in the case of a 1024 bit encryption key are each 512 digits long. Running through each of them by trial and error will take a very long time. Even with a bank of computers working on it 24/7.
Factoring algorithms for quantum computers can run in what is called “polynomial time”. The factoring time would be reduced on a logarithmic scale. Thus making the number larger and larger doesn’t offer the same returns.
I think the key then is to create a sort of quantum computer code whose wave function collapses and alters the data contained therein if viewed in transit. [OK, OK, I stole that idea from the fourth realm series of books]