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.”

Categories: Cryptography

Comments (7)

  1. Bob

    I’m no mathematician, but I am sceptical of any “new” crypto algorithms. In light of recent NSA scandals, one can only hope any new crypto has been vetted by honest, principled crytographers. Bruce Schneier’s Nov 2007 securitymatters commentary on regarding the alleged skeleton key for Dual_EC_DRBG should make us reconsider being early adopters.

  2. DDT

    To make some stuff clear:
    - BEAST attack has nothing to do with RSA, but the underlying symmetric cipher of SSL and TLS.
    - CRIME is an attack on the compression algorithm and again nothing to do with RSA.
    - Lucky 13 is a padding oracle attack and again not realy anything to do with RSA algorithm.
    The 3 above attacks are related to the protocol of the usage of RSA and not on the RSA algorithm itself. These problems can happen to ECC also.
    Will one day the RSA be broken? Yes, when the Riemann hypothesesis is proved.
    I would like to ask to scare people about the presumed weaknesses of the RSA algorithm, until you have real prove (mathematical) about its weaknesses. I know ECC has its advantages, but a bad designed protocol with the ECC algorithm put it in the same position as the RSA algorithm.

  3. Conrad

    Bob has a point, however ensuring the implementation of any new crypto mechanism has to be done in the light of Open Source Markets so that the code can be vetted by everyone that is able to do so. Even hackers want to be sure that they can do banking and purchases in a secure manner.

  4. Dennis Farr

    Discrete log is a problem which, if it turns out to be easy to solve, leads to breakage of ECC. RSA is not technically based on discrete log, but there has been an unexplained correlation between advances in discrete log and advances in factoring large numbers (on which the hardness of RSA is based.)

  5. Morty

    @DDT: You’re right in pointing out that BEAST, CRIME etc. are not at all related to RSA and would be equally possible with ECC-based cipher suites. I was very much discouraged when the article brought up this point, since it indicates the authors doesn’t really understand what problems (if any) there might be with RSA.

    But another correction: The Riemann hypothesis is not related to RSA security. If we wake up tomorrow and learn someone has proved/disproved the Riemann hypothesis, this doesn’t imply that RSA is suddenly broken (or secure). I have never heard of such a connection.

    Of course one cannot exclude that such a proof might contain elements or techniques that would have bearing on the security of RSA, but there’s absolutely no reason to think that is the case with the current knowledge and it is not particular to the Riemann problem.

    What might have an important bearing on the security of RSA would be the P vs NP question especially in the case where P=NP it would raise questions about RSA security (the only saving grace might be if the associated constants/exponents were so high as to make an attack impractical despite them being polynomial).

  6. Morty

    By the way, I would like to add that I don’t disagree with the suggestion of pursuing other crypto systems than RSA. After all, any cryptosystem of unproven security could be broken at any time, so it is only prudent to have something to replace RSA. I agree the industry is too complacent about this – maybe because it is too painful to think about the ‘unthinkable’, namely the scenario where RSA is completely broken in a zero-day exploit.

    Ideally, one should pursue a strategy of not only agility with respect to switching algorithms, but also using multiple systems at the same time. For instance, a certificate could contain both an ECC and an RSA public key. Signatures would be done with both keys so a signature would effectively contain both an ECC and an RSA signature which would both need to be verified by the recipient. Likewise, when sending a key encrypted under RSA (as in SSL, S/MIME etc) the sender would generate two key parts and XOR them to form the effective key. The two key parts would be encrypted with the two systems, respectively. The recipient (or an adversary) would only be able to recover the effective key if he could break both ciphers, and so on and so forth.

    But given that there has never been any widespread of RSA during its existence (disregarding the fact that the initial security estimates were too optimistic, and hence the keys initially used were too small, and thus amenable to breaking with today’s technology), and the general lack of interest from both the public and business outside IT in encrypted mail, it is unlikely that we would see the investment required for such a transition to multi-layer technology. It would require the zero-day scenario or something close with everyone scrambling to reestablish trust, before this would be perceived as a risk worth mitigating.

  7. Michael Hunt

    The only reason ECC is viewed as “more secure” than RSA is that ECC is a newer, more abstruse framework that requires deeper knowledge of number theory and abstract algebra to grasp fully. Who in his right mind has ever heard of Jacobians, Noetherian rings, Etale cohomology, Grassmannians, and Lord only knows what else? You can bet that if ECC ever replaces RSA as the norm, all sorts of math and crypto boffins will attack it, and I doubt it will prove more robust. Obscurity leads to security only as long as things stay truly obscure.

Comments are closed.