The clock is ticking on encryption
Today's secure cipher-text may be tomorrow's open book
Lamont Wood
December 17, 2010 (Computerworld)
In the indictment that led to the expulsion of ten Russian spies from the U.S. in the summer of 2010, the FBI said that it gained access to their communications after surreptitiously entering one of the spies' homes, during which agents found a piece of paper with a 27-character password.
In other words, 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 rock solid. Cracking an encrypted message can require time frames that dwarf the age of the universe. That's the case today. But within the foreseeable future, cracking those same codes could become trivial, thanks to quantum computing.
The encryption landscape
"The entire commercial world runs off the assumption that encryption is rock solid and is not breakable" says Joe Moorcones, vice president at SafeNet Inc., an information security firm in Belcamp, Md.
There are two kinds of encryption algorithms used in enterprise-level communications security -- symmetric and asymmetric (also called public-key encryption), he explains. Symmetric algorithms are typically used to send the actual information, where asymmetric algorithms are used to send both the information and the keys.
Symmetric encryption requires that the sender and receiver both employ the same algorithm and the same encryption key. Decryption is simply the reverse of the encryption process -- hence the "symmetric" name.
The scale of the problem
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.4x10^38, or 340 undecillion. Assuming no information on the nature of the key (such as that the owner likes to use his or her children's birthdays) a code-breaking attempt would require the testing of each possible key until one is found that works.
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.
Using quantum technology with the same throughput, exhausting the possibilities of a 128-bit AES key would take about six months. However, moving to 256 bits would give the system a level of security equivalent to 128 bits with a conventional computer.
Cracking an RSA or EC cipher with a quantum machine would be essentially immediate.
There are numerous symmetric algorithms available, but Moorcones says that, at the enterprise level, nearly everyone uses 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.
Typically using keys that are either 128 or 256 bits long, AES 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 Charles Kolodgy, analyst at IDC, a market research firm in Framingham, Mass. And they use multiple algorithms, he says.
Though rumors have long swirled around the idea, well-respected sources universally reject the idea that AES has a "back door" that allows the government to read messages encrypted with it. "It's been too heavily scrutinized," says Paul Kocher, head of Cryptography Research Inc., in San Francisco. "They would have to put in a back door that no one else could see, and to be able to do that they would have to be years ahead of everyone else, and that is unlikely."
The beauty of public-key cryptography
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, as a method for disseminating symmetric keys.
Moorcones explains that asymmetric systems are also called public key cryptography because they use a public key for encryption and 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 (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, notes Kocher. "I would guess that in five years even 1,024 bits will be broken." Moorcones adds: "You often see 2,048-bit RSA keys used to protect 256-bit AES keys."
Other kinds of algorithms
Besides responding with 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, Moocones says. However, EC encryption up to 109 bits has been broken, Kocher explains.
Anna Chapman and nine other accused Russian spies were rooted out earlier this year when the FBI filched a 27-character password that revealed data that the spy ring had hidden. Photo courtesy of the U.S. Marshals Service.
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.
As for private individuals, IDC's Kolodgy says that many turn to freeware implementations of PGP (Pretty Good Privacy), published in 1991 by Phil Zimmermann. PGP traffic can be readily identified, inviting attempts to intercept key transfers.
For those who want to hide the fact that they are receiving messages, there's steganography, which involves hiding text, encrypted or not, typically within the pixels of photos posted on the Web. Anyone can download the picture and extract the message, assuming he has the right software. In fact, the previously cited 27-character code used by the Russian spies was for the password protection of a steganography software disk.
"The problem with steganography is that is not encryption, it's hiding, like putting drugs in a secret compartment of your suitcase," says Zimmermann, now a security consultant in Santa Cruz, Calif. "If your opponent knows about it they can intercept the message."
The quantum danger
This mostly tidy world of cryptography may be seriously disrupted by the expected 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 Waterloo, Ontario, Canada. 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 is likely we will have a quantum computer within 20 years.
"It's a game changer," Mosca says, explaining that the change comes not from a speed-up 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 depends on this very issue -- 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 2^50 (1.125 quadrillion) steps.
Michele Mosca, deputy director of the Institute for Quantum Computing at the University of Waterloo, calls quantum computing a "game changer" for cryptography and says it could happen within 20 years.
With a quantum computer it should take about 50 steps, he says, and 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 2^128 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 2^64. This is still a huge number, and AES should remain secure with increased key sizes, he says.
Timing issues
When will all this happen?
"We don't know," says Mosca. To mere mortals, 20 years is a long way off, but in the world of cyber-security, 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."
Moorcones at SafeNet 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 -- one per message if necessary -- he adds, as many enterprises currently change their key only once every 90 days. Every key, of course, requires a fresh cracking effort, as any success with one key is inapplicable with the next.
The rule of thumb, when it comes to encryption, 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 Kolodgy.
The other quantum technology
If quantum technology calls into question 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. This works in at least in some situations.
QKD has actually been on the market since 2004, with the fiber-based Cerberis system from ID Quantique SA in Geneva, Switzerland. Grégoire Ribordy, the firm's founder and CEO, explains that the system is based on the fact that measuring quantum properties changes them.
At one end of an optical fiber, an emitter sends individual photons to the other end. The phase of some the photons are measured as they are transmitted and thereby acquire a value, and the receiver is informed of the value through a separate channel. 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, that third party will have reassigned values to the photons through the act of measuring them. In that case, 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. "It's like a fountain of random bits," he says of the system. "You can store the bits in a buffer and use them different ways, and with standard applications we use them to make 256-bit AES keys, and then replace the key every minute."
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, and not actual messages, he notes.
The other limitation of the system is range, which currently doesn't exceed 100 kilometers (62 miles), although they have achieved 250 kilometers in the lab. However, due to the rate that photons get lost in the fiber, the theoretical maximum is 400 kilometers, Ribordy says. Going beyond that must await the development of a quantum repeater -- which would presumably use the same technology as a quantum computer, he adds.
QKD security, like all security, is not cheap, with an emitter-receiver pair costing about 100,000 Swiss francs (about $97,000), he says.
Safe, at least for now
For the time being, "code-breaking today is an end-run game -- it's all about snatching the user's machine," says Kolodgy at IDC."These days, if you pull something out of the air, you can't decrypt it."
But the biggest problem with encryption, typically, is the lack of any. "All business-critical data should be encrypted at rest, especially credit card data," says Richard Stiennon at IT-Harvest, a security analyst 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 also turns out to be a bad idea.
Lamont Wood is a freelance writer in San Antonio.
http://www.computerworld.com/s/article/9201281/The_clock_is_ticking_on_encryption?source=CTWNLE_nlt_dailyam_2010-12-17
Lamont Wood
December 17, 2010 (Computerworld)
In the indictment that led to the expulsion of ten Russian spies from the U.S. in the summer of 2010, the FBI said that it gained access to their communications after surreptitiously entering one of the spies' homes, during which agents found a piece of paper with a 27-character password.
In other words, 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 rock solid. Cracking an encrypted message can require time frames that dwarf the age of the universe. That's the case today. But within the foreseeable future, cracking those same codes could become trivial, thanks to quantum computing.
The encryption landscape
"The entire commercial world runs off the assumption that encryption is rock solid and is not breakable" says Joe Moorcones, vice president at SafeNet Inc., an information security firm in Belcamp, Md.
There are two kinds of encryption algorithms used in enterprise-level communications security -- symmetric and asymmetric (also called public-key encryption), he explains. Symmetric algorithms are typically used to send the actual information, where asymmetric algorithms are used to send both the information and the keys.
Symmetric encryption requires that the sender and receiver both employ the same algorithm and the same encryption key. Decryption is simply the reverse of the encryption process -- hence the "symmetric" name.
The scale of the problem
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.4x10^38, or 340 undecillion. Assuming no information on the nature of the key (such as that the owner likes to use his or her children's birthdays) a code-breaking attempt would require the testing of each possible key until one is found that works.
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.
Using quantum technology with the same throughput, exhausting the possibilities of a 128-bit AES key would take about six months. However, moving to 256 bits would give the system a level of security equivalent to 128 bits with a conventional computer.
Cracking an RSA or EC cipher with a quantum machine would be essentially immediate.
There are numerous symmetric algorithms available, but Moorcones says that, at the enterprise level, nearly everyone uses 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.
Typically using keys that are either 128 or 256 bits long, AES 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 Charles Kolodgy, analyst at IDC, a market research firm in Framingham, Mass. And they use multiple algorithms, he says.
Though rumors have long swirled around the idea, well-respected sources universally reject the idea that AES has a "back door" that allows the government to read messages encrypted with it. "It's been too heavily scrutinized," says Paul Kocher, head of Cryptography Research Inc., in San Francisco. "They would have to put in a back door that no one else could see, and to be able to do that they would have to be years ahead of everyone else, and that is unlikely."
The beauty of public-key cryptography
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, as a method for disseminating symmetric keys.
Moorcones explains that asymmetric systems are also called public key cryptography because they use a public key for encryption and 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 (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, notes Kocher. "I would guess that in five years even 1,024 bits will be broken." Moorcones adds: "You often see 2,048-bit RSA keys used to protect 256-bit AES keys."
Other kinds of algorithms
Besides responding with 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, Moocones says. However, EC encryption up to 109 bits has been broken, Kocher explains.
Anna Chapman and nine other accused Russian spies were rooted out earlier this year when the FBI filched a 27-character password that revealed data that the spy ring had hidden. Photo courtesy of the U.S. Marshals Service.
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.
As for private individuals, IDC's Kolodgy says that many turn to freeware implementations of PGP (Pretty Good Privacy), published in 1991 by Phil Zimmermann. PGP traffic can be readily identified, inviting attempts to intercept key transfers.
For those who want to hide the fact that they are receiving messages, there's steganography, which involves hiding text, encrypted or not, typically within the pixels of photos posted on the Web. Anyone can download the picture and extract the message, assuming he has the right software. In fact, the previously cited 27-character code used by the Russian spies was for the password protection of a steganography software disk.
"The problem with steganography is that is not encryption, it's hiding, like putting drugs in a secret compartment of your suitcase," says Zimmermann, now a security consultant in Santa Cruz, Calif. "If your opponent knows about it they can intercept the message."
The quantum danger
This mostly tidy world of cryptography may be seriously disrupted by the expected 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 Waterloo, Ontario, Canada. 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 is likely we will have a quantum computer within 20 years.
"It's a game changer," Mosca says, explaining that the change comes not from a speed-up 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 depends on this very issue -- 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 2^50 (1.125 quadrillion) steps.
Michele Mosca, deputy director of the Institute for Quantum Computing at the University of Waterloo, calls quantum computing a "game changer" for cryptography and says it could happen within 20 years.
With a quantum computer it should take about 50 steps, he says, and 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 2^128 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 2^64. This is still a huge number, and AES should remain secure with increased key sizes, he says.
Timing issues
When will all this happen?
"We don't know," says Mosca. To mere mortals, 20 years is a long way off, but in the world of cyber-security, 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."
Moorcones at SafeNet 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 -- one per message if necessary -- he adds, as many enterprises currently change their key only once every 90 days. Every key, of course, requires a fresh cracking effort, as any success with one key is inapplicable with the next.
The rule of thumb, when it comes to encryption, 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 Kolodgy.
The other quantum technology
If quantum technology calls into question 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. This works in at least in some situations.
QKD has actually been on the market since 2004, with the fiber-based Cerberis system from ID Quantique SA in Geneva, Switzerland. Grégoire Ribordy, the firm's founder and CEO, explains that the system is based on the fact that measuring quantum properties changes them.
At one end of an optical fiber, an emitter sends individual photons to the other end. The phase of some the photons are measured as they are transmitted and thereby acquire a value, and the receiver is informed of the value through a separate channel. 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, that third party will have reassigned values to the photons through the act of measuring them. In that case, 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. "It's like a fountain of random bits," he says of the system. "You can store the bits in a buffer and use them different ways, and with standard applications we use them to make 256-bit AES keys, and then replace the key every minute."
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, and not actual messages, he notes.
The other limitation of the system is range, which currently doesn't exceed 100 kilometers (62 miles), although they have achieved 250 kilometers in the lab. However, due to the rate that photons get lost in the fiber, the theoretical maximum is 400 kilometers, Ribordy says. Going beyond that must await the development of a quantum repeater -- which would presumably use the same technology as a quantum computer, he adds.
QKD security, like all security, is not cheap, with an emitter-receiver pair costing about 100,000 Swiss francs (about $97,000), he says.
Safe, at least for now
For the time being, "code-breaking today is an end-run game -- it's all about snatching the user's machine," says Kolodgy at IDC."These days, if you pull something out of the air, you can't decrypt it."
But the biggest problem with encryption, typically, is the lack of any. "All business-critical data should be encrypted at rest, especially credit card data," says Richard Stiennon at IT-Harvest, a security analyst 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 also turns out to be a bad idea.
Lamont Wood is a freelance writer in San Antonio.
http://www.computerworld.com/s/article/9201281/The_clock_is_ticking_on_encryption?source=CTWNLE_nlt_dailyam_2010-12-17
Comments
Post a Comment