In the indictment that led to the expulsion of 10 Russian spies from the U.S. last summer, the FBI said that it had gained access to their encrypted communications after surreptitiously entering one of the spies' homes, where agents found a piece of paper with a 27-character password.

In essence, the FBI found it more productive to burglarize a house than to crack a 216-bit code, despite having the computational resources of the U.S. government behind it. That's because modern cryptography, when used correctly, is very strong. Cracking an encrypted message can take an incredibly long time.

The scale of the encryption-cracking challenge

Today's encryption algorithms can be broken. Their security derives from the wildly impractical lengths of time it can take to do so.

Let's say you're using a 128-bit AES cipher. The number of possible keys with 128 bits is 2 raised to the power of 128, or 3.4x1038, or 340 undecillion. Assuming no information on the nature of the key is available (such as the fact that the owner likes to use his or her children's birthdays), a code-breaking attempt would require testing each possible key until one was found that worked.

Assuming that enough computing power was amassed to test 1 trillion keys per second, testing all possible keys would take 10.79 quintillion years. This is about 785 million times the age of the visible universe (13.75 billion years). On the other hand, you might get lucky in the first 10 minutes.

But using quantum technology with the same throughput, exhausting the possibilities of a 128-bit AES key would take about six months. If a quantum system had to crack a 256-bit key, it would take about as much time as a conventional computer needs to crack a 128-bit key.

A quantum computer could crack a cipher that uses the RSA or EC algorithms almost immediately.

-- Lamont Wood

"The entire commercial world runs off the assumption that encryption is rock-solid and is not breakable," says Joe Moorcones, a vice president at SafeNet, an information security vendor in Belcamp, Md.

That's the case today. But within the foreseeable future, cracking those same codes could become trivial, thanks to quantum computing.

Before learning about the threat of quantum computing, it helps to understand the current state of encryption. There are two kinds of encryption algorithms used in enterprise-level communications security: symmetric and asymmetric, Moorcones explains. Symmetric algorithms are typically used to send the actual information, whereas asymmetric algorithms are used to send both the information and the keys.

Symmetric encryption requires that the sender and receiver both use the same algorithm and the same encryption key. Decryption is simply the reverse of the encryption process -- hence the "symmetric" label.

There are numerous symmetric algorithms, but most enterprises use the Advanced Encryption Standard (AES), published in 2001 by the National Institute of Standards and Technology after five years of testing. It replaced the Data Encryption Standard (DES), which debuted in 1976 and uses a 56-bit key.

AES, which typically uses keys that are either 128 or 256 bits long, has never been broken, while DES can now be broken in a matter of hours, Moorcones says. AES is approved for sensitive U.S. government information that is not classified, he adds.

As for classified information, the algorithms used to protect it are, of course, themselves classified. "They're more of the same -- they put in more bells and whistles to make them harder to crack," says IDC analyst Charles Kolodgy. And they use multiple algorithms, he says.

The genuine weakness of AES -- and any symmetric system -- is that the sender has to get the key to the receiver. If that key is intercepted, transmissions become an open book. That's where asymmetric algorithms come in.

Moorcones explains that asymmetric systems are also called public-key cryptography because they use a public key for encryption -- but they use a different, private key for decryption. "You can post your public key in a directory with your name next to it, and I can use it to encrypt a message to you, but you are the only person with your private key, so you are the only person who can decrypt it."

The most common asymmetric algorithm is RSA (named for inventors Ron Rivest, Adi Shamir and Len Adleman). It is based on the difficulty of factoring large numbers, from which the two keys are derived.

But RSA messages with keys as long as 768 bits have been broken, says Paul Kocher, head of security firm Cryptography Research in San Francisco. "I would guess that in five years, even 1,024 bits will be broken," he says.

Moorcones adds, "You often see 2,048-bit RSA keys used to protect 256-bit AES keys."

Besides creating longer RSA keys, users are also turning to elliptic curve (EC) algorithms, based on the math used to describe curves, with security again increasing with the size of the key. EC can offer the same security with one-fourth the computational complexity of RSA, Moorcones says. However, EC encryption up to 109 bits has been broken, Kocher notes.

RSA remains popular with developers because implementation requires only multiplication routines, leading to simpler programming and higher throughput, Kocher says. Also, all the applicable patents have expired. For its part, EC is better when there are bandwidth or memory constraints, he adds.

The Quantum Leap

But this tidy world of cryptography may be seriously disrupted by the arrival of quantum computers.

"There has been tremendous progress in quantum computer technology during the last few years," says Michele Mosca, deputy director of the Institute for Quantum Computing at the University of Waterloo in Ontario. Mosca notes that in the past 15 years, we have moved from playing with quantum bits to building quantum logic gates. At that rate, he thinks it's likely we will have a quantum computer within 20 years.

"It's a game-changer," Mosca says, explaining that the change comes not from improvements in the computer's clock speed, but from an astronomical reduction in the number of steps needed to perform certain computations.

Basically, Mosca explains, a quantum computer should be able to use the properties of quantum mechanics to probe for patterns within a huge number without having to examine every digit in that number. Cracking both RSA and EC ciphers involves that very task -- finding patterns in huge numbers.

Mosca explains that with a conventional computer, finding a pattern for an EC cipher with N number of bits in the key would take a number of steps equal to 2 raised to one-half N. As an example, for 100 bits (a modest number), it would take 250 (1.125 quadrillion) steps.

With a quantum computer, it should take about 50 steps, he says, which means code-breaking would then be no more computationally demanding than the original encryption process.

With RSA, determining the number of steps needed for a solution through conventional computation is more complicated than with EC encryption, but the scale of the reduction with quantum computation should be similar, Mosca says.

The situation is less dire with symmetric encryption, Mosca explains. Breaking a symmetric code like AES is a matter of searching all possible key combinations for the one that works. With a 128-bit key, there are 2128 possible combinations. But thanks to a quantum computer's ability to probe large numbers, only the square root of the number of combinations needs to be examined -- in this case, 264. This is still a huge number, and AES should remain secure with increased key sizes, Mosca says.

Timing Issues

When will quantum computing threaten the status quo? "We don't know," says Mosca. To many people, 20 years seems a long way off, but in the world of cybersecurity, it's right around the corner. "Is that an acceptable risk? I don't think so. So we need to start figuring out what alternatives to deploy, since it takes many years to change the infrastructure," Mosca says.

SafeNet's Moorcones disagrees. "DES lasted for 30 years, and AES is good for another 20 or 30 years," he says. Increases in computing power can be countered by changing keys more often -- with each new message, if necessary -- since many enterprises currently change their key only once every 90 days, he notes. Every key, of course, requires a fresh cracking effort, as any success with one key isn't applicable to the next.

When it comes to encryption, the rule of thumb is that "you want your messages to provide 20 years or more of security, so you want any encryption that you use to remain strong 20 years from now," says IDC's Kolodgy.

For the time being, "code-breaking today is an end-run game -- it's all about snatching the user's machine," says Kolodgy. "These days, if you pull something out of the air, you can't decrypt it."

But the biggest challenge with encryption is making sure that it's actually used.

"All business-critical data should be encrypted at rest, especially credit card data," says Richard Stiennon at IT-Harvest, an IT security research firm in Birmingham, Mich. "The Payment Card Industry Security Standards Council requires that merchants encrypt it -- or, better yet, not store it at all. And data-breach notification laws don't require you to disclose your lost data if it was encrypted."

And, of course, leaving your encryption keys lying around on slips of paper can also turn out to be a bad idea.

Quantum key distribution technology could be the solution

If quantum technology jeopardizes the methods used to disseminate encryption keys, it also offers technology -- called quantum key distribution, or QKD -- by which such keys can be simultaneously generated and transmitted securely.

QKD has actually been on the market since 2004, with the fiber-based Cerberis system from ID Quantique in Geneva. Grégoire Ribordy, the firm's founder and CEO, explains that the system is based on the fact that the act of measuring quantum properties actually changes them.

At one end of an optical fiber, an emitter sends individual photons to the other end. Normally, the photons will arrive with the expected values and will be used to generate a new encryption key.

But if there is an eavesdropper on the line, the receiver will see an error rate in the photon values and no key will be generated. In the absence of that error rate, the security of the channel is assured, Ribordy says.

However, since security can only be assured after the fact -- when the error rate is measured, which happens immediately -- the channel should be used to send only the keys, not actual messages, he notes.

The other limitation of the system is its range, which currently doesn't exceed 100 kilometers (62 miles), although the company has achieved 250 kilometers in the lab. The theoretical maximum is 400 kilometers, Ribordy says. Going beyond that would require the development of a quantum repeater -- which would presumably use the same technology as a quantum computer.

QKD security isn't cheap: An emitter-receiver pair costs about $97,000, Ribordy says.

Wood is a freelance writer in San Antonio.

This story, "The clock is ticking for encryption" was originally published by Computerworld.