LAS VEGAS – Cryptographic breakthroughs have accelerated in the past six months in areas such as discrete logarithm computations that lead experts to believe that breaking the stalwart RSA algorithm may be in the not-too-distant future.
A team of crypto experts today at Black Hat USA 2013 presented their research into the potential impact of these breakthroughs and made a recommendation that browser vendors, certificate authorities and crypto vendors get ahead of the problem and seriously consider elliptic curve cryptography implementations.
“What we’re trying to say is that we don’t know when or if that’s going to happen, but it’s too late at that point because everything’s broken,” said Alex Stamos of Artemis Internet, a division of iSEC Partners. “Nothing’s going to work. You can’t update things securely and you can’t trust any communication on the Internet. So we’ve got to fix it before then. We’ve got the tools, we just need to have the will to finally do something about it.”
The RSA algorithm is closing in on its 40th birthday and remains the standard public key exchange on the Internet today. Yet because of these breakthroughs by scientists such as Antoine Joux who has set world records for discrete logarithm computations, RSA could fall soon.
“There’s a small, but definite chance that RSA and non-ECC Diffie Hellman will not be usable for security purposes within two to five years,” Stamos said. “We’re not saying this is definite; it’s almost certainly going to happen before we retire. It could also happen in the next five years.”
A number of crypto attacks this year such as BEAST, CRIME and Lucky13 have helped shine new focus on the need to enhance crypto schemes. The industry should have been able to predict these types of attacks were coming, Stamos said, but a number of factors are conspiring against progress, namely the lack of agility built into cryptosystems with regard to backwards compatibility and inefficiencies in the crypto ecosystem between PKI vendors, CAs and browser vendors keep things at bay. In addition it’s difficult for cryptographers to keep pace with the rapid innovation and speed at which research is released.
For example, iSEC Partners researcher Tom Ritter explained how attacks on RSA discrete logarithm computations and factoring—which is the underlying math function in RSA that must be broken to attack RSA–follow almost the same steps in terms of polynomial selection, sieving and linear algebra. The fourth step, square-root computations, are very fast for factoring and painful for discrete logarithms.
“These guys have improved all four steps that have a direct influence on the factoring method,” Stamos said. “There are maybe two guys who work on discrete log because it’s been 30 years since there have been any breakthroughs; not a great thing to make your bones on. Now everybody in the discrete math world has dropped whatever they’re doing and that’s why we’ve seen these improvements.”
A move to ECC, Stamos, Ritter and fellow iSEC Partners researcher Javed Samuel, hope comes soon. ECC Suite B, which was released in 2005, is already supported on most operating systems and programming languages. When Suite B was developed, the cryptographers behind it left out RSA and Diffie Hellman, perhaps seeing the writing on the wall for the RSA algorithm.
“You don’t have to understand how they work, you just have to understand how to call them correctly. So we’re not asking developers to go out and do a Master’s degree in discrete math. We’re asking them, instead of calling the function that does RSA, you call the function that does ECC,” Stamos said. “We’re asking the ecosystem, the PKI and certificate authority companies to make it easy to do this. Right now you have to hunt and search. If you go to a site and want a SSL certificate here are the instructions that tell you to use RSA. That needs to change and if they change that, 90 percent of people are just going to follow those instructions. The browsers need to support it too. People aren’t going to move to ECC until there’s major browser support.
“We’ve got a real chicken and egg problem,” Stamos said, “and the egg needs to hatch.”