10 ms·

Math Advances Suggest RSA Encryption Could Fall Within 5 Years

112 points by codesuela 13y ago

Mithrandir 13y ago
I think this comment from djao has some additional insights: "It would have been nice if TR had asked an academic researcher for comments. After all, if discrete logarithms are ever broken, it'll likely be by academic researchers. Diffie-Hellman is based on discrete logarithms, but RSA is not. RSA is based on integer factorization, not discrete logarithms. Integer factorization and discrete logarithms share some common techniques, but neither is known to be based on the other, and opinion is split as to whether they are truly equivalent. I can't think of a single respectable academic researcher who thinks that the latest results threaten RSA. The new discrete logarithm attacks require the existence of a nontrivial intermediate subfield, and work best in small characteristic. They do not apply to the most common instances of Diffie-Hellman in deployment (no subfields, large characteristic), and we currently have no realistic approaches that could make them apply. A similar story actually played out with ECC some 10-15 years ago, when Weil descent attacks were new. Those attacks on ECC also require an intermediate subfield, and 10 years of follow-on research has been unable to sidestep this requirement. To date, there is no indication that Weil descent can be used on the most common instances of ECC being deployed today, and nobody is going around saying ECC is at risk from new algorithms. (Quantum computers, yes, but not new algorithms.) It is possible that the new discrete logarithm attacks will extend to cases with large characteristic and no intermediate subfields, but I personally think that it is extremely unlikely. I would not put the chances at "small but definite." It would be a major surprise if this happened. Even if it did, RSA may still be safe. I can't speak for others, but my sense of the crypto community is that most experts agree with my assessment."
- ColinWright 13y ago
  > Diffie-Hellman is based on discrete logarithms, > but RSA is not. Well, sort of, but not entirely. Yes, the obvious way to break RSA is to factor the modulus, and then compute the private key from the public key. But that's not the only thing. You encrypt by raising the message M to the power of the public key e modulo the public modulus n. E = M^e (mod n) That means that log_e(E) = M (mod n) [ This is wrong - see below ] If you can compute logarithms base e modulo n then given the public information, you can recover M. So unrestricted discrete logs let you break RSA. Added in edit: Sorry, I mis-spoke myself as I was (and still am) in a hurry. As benmmurphy correctly points out, this is wrong, but not in an unfixable way. In short: (all done mod n) E = M^e (mod n) log(E) = e.log(M) log(E)/e = log(M) exp(log(E)/e) = exp(log(M)) = M Again, unrestricted discrete log lets you break RSA. PS: There's a non-zero chance I screwed up again - feel free to say so!
  - benmmurphy 13y ago
    this doesn't look like log to me. i think the function you want is e'th root.
    - barrkel 13y ago
      n'th root of x = exp(log(x) / n)
    - deleted 13y ago
      [deleted]
  - benmmurphy 13y ago
    what base do you compute the logs when you do this attack? i assume in (mod n) rsa group there is no generator b that generates all of the numbers (mod n). and you could only recover the message M if you have M = b^x (mod n). so how do you choose b? or is this not a problem.
    - ColinWright 13y ago
      Possibly it only works for some bases, and then possibly it only works for some n and e. I don't have time now to work through all the details, but my gut feeling is that for log(n) selection of bases, at least one will work for the calculation you need to perform. But I am not an expert, so my intuition is not to be trusted. But these very simple calculations show that in at least some cases, being able to compute unrestricted discrete logs will break RSA, perhaps just not in general. Perhaps it's another case where the modulus and exponent need to have extra conditions. Added in edit. Again. > ... you could only recover the message M > if you have M = b^x (mod n). We know that that equation has a solution, because M=E^d (mod n) where d is the private key. > ... what base do you compute the logs when you > do this attack? That would suggest we compute logs base E. Reworking the sums, and specifically using logs base E: E = M^e (mod n) log_E(E) = e.log_E(M) log_E(E)/e = log_E(M) 1 / e = log_E(M) E^(1/e) = E^(log_E(M)) = M Still just idly musing, but it seems right.
      - 13y ago
- tptacek 13y ago
  * IFP and DLP crypto do appear to be related; we're just not sure how. * There are well-respected cryptographers who do think the Joux/Barbalescu results are worth considering. Example: Dan Boneh. * A 10-year margin for RSA would still be a huge industry fire drill; the media doesn't have a good feel for what "imminent" means. * You should think of RSA the way you do about 3DES --- a compat hack that works today, and may work indefinitely, but something we have better alternatives for. Disclaimer: if 'pbsd disagrees with anything I've said here, he's right and I'm not.
  - deleted 13y ago
    [deleted]
  - ivmi 13y ago
    I can't tell if you are disagreeing with djao or not. "I can't think of a single respectable academic researcher who thinks that the latest results threaten RSA." -- djao Does Dan Boneh think that the latest results threaten RSA? Is there a serious argument in favor of that position?
    - tptacek 13y ago
      You seem to be asking two questions that my comment already answered. Yes, I'm citing Boneh as an example of someone who has suggested that Joux may have practical implications on RSA.
      - djao 13y ago
        You are perhaps referring to Boneh's comments at the RSA conference last February. Boneh cited the new attacks in the context of arguing that we should diversify away from RSA and DH. The implication, to me, was one of general caution and urgency. I did not get any sense of RSA itself being specifically threatened.
        tptacek 13y ago
        I'm having trouble writing a response to this that reconciles your last sentence with the sentence that precedes it. I think that might be because we're on the same page already. I'm not endorsing the article's interpretation of the talk.
- Mithrandir 13y ago
  (I can't edit my original comment anymore.) In case anyone here is interested, there was a discussion about the presentation last week on HN: https://news.ycombinator.com/item?id=6155502 https://news.ycombinator.com/item?id=6155502
madaxe 13y ago
I'd say "switch to ECC", but the fact that the NSA are strong proponents of it rather makes one wonder why.
- jloughry 13y ago
  NSA is really two organizations in one. One side of the house is tasked with Information Assurance (IA), i.e., protecting the U.S. government's information. The other side of the house is tasked with interception. Cryptanalysis folks at NSA straddle both activities, necessarily.
  - madaxe 13y ago
    Sure, but I just can't understand why they would be recommending to the general public that they improve their crypto, as it goes directly against the NSA's interests.
    - LoganCale 13y ago
      Now that they are in the domestic surveillance game, they have contradictory interests. They were originally intended to jointly ensure the security of U.S. interests while breaking the security of everyone else. So it made sense to advocate improved crypto for, say, U.S. businesses, because that would benefit the U.S. in general by preventing the intelligence agencies of other countries from stealing U.S. corporate secrets.
      - devcpp 13y ago
        To take it further, I suppose they want to protect US citizens, companies and government from crypto attacks while using US laws to snoop on them easily. That way, they prevent foreign threats by making it very hard for everyone to break any system in the US. And on the other hand, they can still read everything by issuing subpoenas to any company and ISP they feel like (with borderline constitutional legality in some cases).
    - Locke1689 13y ago
deleted 13y ago
[deleted]
ceautery 13y ago
Isn't there an article like this every year, always long on FUD and short on math?
- tptacek 13y ago
  No?
- IvyMike 13y ago
  C'mon man, you're better than that. I'm sure you know how to use google to find the black hat presentation: https://www.isecpartners.com/media/105564/ritter_samuel_stamos_bh_2013_cryptopocalypse.pdf https://www.isecpartners.com/media/105564/ritter_samuel_stam... Which you then know how to use to find the papers by Joux. http://eprint.iacr.org/2013/095.pdf http://eprint.iacr.org/2013/095.pdf http://eprint.iacr.org/2013/400.pdf http://eprint.iacr.org/2013/400.pdf A lot of smart and proven people put together this information and if they're worried, I'm worried.
  - ceautery 13y ago
    Thanks for the vote of confidence. I didn't search for the specifics based on the language of the article; it seemed to boil down to "some future math breakthrough based on current work is possible"... which is always the case. If I'm good enough to do something, it's to be able to switch out the encryption tools the enterprise I support uses at the drop of a hat, but despite similar fears voiced in tech forums over the last decade, I haven't yet needed to. I think it's more likely our security breach will come from someone trying to buy cheap drugs from Canada over email, or by a good old-fashioned mole.
    - tptacek 13y ago
      That's cryptography at its frontiers: you look at progress and try to get a sense of where it's going to take you. It's why Schneier keeps pounding on "attacks only get better". Also, as layperson, you should be wary of the lesson the last two decades have taught people like you on responding to far-out attacks on algorithms. RC4 was known to be broken almost immediately after it was published, but it wasn't until a few months ago(!) that someone bothered to refine the attack to the point where it could break TLS. The industry's intuition about how likely it is that a "theoretical" flaw will be weaponized is probably wrong. Crypto as a discipline only came into its own within the last ~10 years, and it's safe to assume offensive crypto research has lagged behind it.
kenster07 13y ago
This isn't very different from saying P = NP will be proven within 5 years. Sounds like linkbait.
- tptacek 13y ago
  This is very different from saying P=NP. It would instead be to say that the integer factorization or discrete log problems in the specific parameters used by cryptosystems simply aren't as hard as we once thought they were. RSA-128 is trivially breakable. Being able to break RSA-128 isn't a demonstration that P=NP, either.
  - YZF 13y ago
    For RSA to be completely broken the attacker must be able to retrieve the private key for any practical key length. Some of what people are writing seems to imply more than attacks against specific parameters but rather some theoretical breakthrough that would render the scheme completely unusable. (e.g. factoring in polynomial time to key length) People have been moving to longer keys over time and thus simply being able to attack a given key length isn't the same as saying the entire scheme is broken. Today a 768 bit key is very difficult to attack. Is RSA with 64k-bit keys likely to be broken within 5 years? I guess in one sense our ability to work with much larger RSA keys has progressed faster than the theoretical advances in factoring. Until the time someone has some practical and provably strong cryptosystem we're kind of always at risk. ECC could also be broken so why should I feel more comfortable using ECC over RSA with 64k bit keys?
    - djao 13y ago
      RSA with 65536-bit keys is quite secure, but it's hugely impractical. Try it in OpenSSL. Key generation alone will take you several hours on a fast, current-generation machine.
      - YZF 13y ago
        You only need to generate your key pair once. I just generated a 16kbit key in 10 minutes. Why is this impractical? The cost of encrypt/decrypt would be modular exponentiation which isn't that bad. My point is though that as long as there is some number of bits where RSA is secure and it's use is practical then RSA isn't dead. A lot of the discussion seems to imply RSA will be dead soon as a result of recent work. Maybe it will or maybe it won't but it seems the claims are a bit overblown. I agree with the idea that we need to design to the possibility of RSA falling (or ECC falling) within reason but RSA could have fallen 5 years ago and it could fall tomorrow (and so can ECC).
beagle3 13y ago
Anyone know if DLP for a group generated by a primitive polynomial over GF(2) has had any advances in the last few years? I haven't seen it referenced anywhere in the last 10 years, but it's a version of DH that is much easier to implement in hardware than over integers, and the DLP was (last I checked) believed to be at least as hard, and probably harder, then the equivalent integer problem.
- pbsd 13y ago
  Yes, that's the kind of logarithm where the breakthroughs have happened, and the source of all this fuss. Not all logarithms over these fields are affected equally, though. Do you know of any actual thing using Diffie-Hellman (or anything else) over such fields?
  - deleted 13y ago
    [deleted]

112 points by codesuela 13y ago

I think this comment from djao has some additional insights: "It would have been nice if TR had asked an academic researcher for comments. After all, if discrete logarithms are ever broken, it'll likely be by academic researchers. Diffie-Hellman is based on discrete logarithms, but RSA is not. RSA is based on integer factorization, not discrete logarithms. Integer factorization and discrete logarithms share some common techniques, but neither is known to be based on the other, and opinion is split as to whether they are truly equivalent. I can't think of a single respectable academic researcher who thinks that the latest results threaten RSA. The new discrete logarithm attacks require the existence of a nontrivial intermediate subfield, and work best in small characteristic. They do not apply to the most common instances of Diffie-Hellman in deployment (no subfields, large characteristic), and we currently have no realistic approaches that could make them apply. A similar story actually played out with ECC some 10-15 years ago, when Weil descent attacks were new. Those attacks on ECC also require an intermediate subfield, and 10 years of follow-on research has been unable to sidestep this requirement. To date, there is no indication that Weil descent can be used on the most common instances of ECC being deployed today, and nobody is going around saying ECC is at risk from new algorithms. (Quantum computers, yes, but not new algorithms.) It is possible that the new discrete logarithm attacks will extend to cases with large characteristic and no intermediate subfields, but I personally think that it is extremely unlikely. I would not put the chances at "small but definite." It would be a major surprise if this happened. Even if it did, RSA may still be safe. I can't speak for others, but my sense of the crypto community is that most experts agree with my assessment."

ColinWright 13y ago
> Diffie-Hellman is based on discrete logarithms, > but RSA is not. Well, sort of, but not entirely. Yes, the obvious way to break RSA is to factor the modulus, and then compute the private key from the public key. But that's not the only thing. You encrypt by raising the message M to the power of the public key e modulo the public modulus n. E = M^e (mod n) That means that log_e(E) = M (mod n) [ This is wrong - see below ] If you can compute logarithms base e modulo n then given the public information, you can recover M. So unrestricted discrete logs let you break RSA. Added in edit: Sorry, I mis-spoke myself as I was (and still am) in a hurry. As benmmurphy correctly points out, this is wrong, but not in an unfixable way. In short: (all done mod n) E = M^e (mod n) log(E) = e.log(M) log(E)/e = log(M) exp(log(E)/e) = exp(log(M)) = M Again, unrestricted discrete log lets you break RSA. PS: There's a non-zero chance I screwed up again - feel free to say so!
- benmmurphy 13y ago
  this doesn't look like log to me. i think the function you want is e'th root.
  - barrkel 13y ago
    n'th root of x = exp(log(x) / n)
  - deleted 13y ago
    [deleted]
- benmmurphy 13y ago
  what base do you compute the logs when you do this attack? i assume in (mod n) rsa group there is no generator b that generates all of the numbers (mod n). and you could only recover the message M if you have M = b^x (mod n). so how do you choose b? or is this not a problem.
  - ColinWright 13y ago
    Possibly it only works for some bases, and then possibly it only works for some n and e. I don't have time now to work through all the details, but my gut feeling is that for log(n) selection of bases, at least one will work for the calculation you need to perform. But I am not an expert, so my intuition is not to be trusted. But these very simple calculations show that in at least some cases, being able to compute unrestricted discrete logs will break RSA, perhaps just not in general. Perhaps it's another case where the modulus and exponent need to have extra conditions. Added in edit. Again. > ... you could only recover the message M > if you have M = b^x (mod n). We know that that equation has a solution, because M=E^d (mod n) where d is the private key. > ... what base do you compute the logs when you > do this attack? That would suggest we compute logs base E. Reworking the sums, and specifically using logs base E: E = M^e (mod n) log_E(E) = e.log_E(M) log_E(E)/e = log_E(M) 1 / e = log_E(M) E^(1/e) = E^(log_E(M)) = M Still just idly musing, but it seems right.
    - 13y ago
tptacek 13y ago
* IFP and DLP crypto do appear to be related; we're just not sure how. * There are well-respected cryptographers who do think the Joux/Barbalescu results are worth considering. Example: Dan Boneh. * A 10-year margin for RSA would still be a huge industry fire drill; the media doesn't have a good feel for what "imminent" means. * You should think of RSA the way you do about 3DES --- a compat hack that works today, and may work indefinitely, but something we have better alternatives for. Disclaimer: if 'pbsd disagrees with anything I've said here, he's right and I'm not.
- deleted 13y ago
  [deleted]
- ivmi 13y ago
  I can't tell if you are disagreeing with djao or not. "I can't think of a single respectable academic researcher who thinks that the latest results threaten RSA." -- djao Does Dan Boneh think that the latest results threaten RSA? Is there a serious argument in favor of that position?
  - tptacek 13y ago
    You seem to be asking two questions that my comment already answered. Yes, I'm citing Boneh as an example of someone who has suggested that Joux may have practical implications on RSA.
    - djao 13y ago
      You are perhaps referring to Boneh's comments at the RSA conference last February. Boneh cited the new attacks in the context of arguing that we should diversify away from RSA and DH. The implication, to me, was one of general caution and urgency. I did not get any sense of RSA itself being specifically threatened.
      - tptacek 13y ago
        I'm having trouble writing a response to this that reconciles your last sentence with the sentence that precedes it. I think that might be because we're on the same page already. I'm not endorsing the article's interpretation of the talk.
Mithrandir 13y ago
(I can't edit my original comment anymore.) In case anyone here is interested, there was a discussion about the presentation last week on HN: https://news.ycombinator.com/item?id=6155502 https://news.ycombinator.com/item?id=6155502

madaxe 13y ago

I'd say "switch to ECC", but the fact that the NSA are strong proponents of it rather makes one wonder why.

jloughry 13y ago
NSA is really two organizations in one. One side of the house is tasked with Information Assurance (IA), i.e., protecting the U.S. government's information. The other side of the house is tasked with interception. Cryptanalysis folks at NSA straddle both activities, necessarily.
- madaxe 13y ago
  Sure, but I just can't understand why they would be recommending to the general public that they improve their crypto, as it goes directly against the NSA's interests.
  - LoganCale 13y ago
    Now that they are in the domestic surveillance game, they have contradictory interests. They were originally intended to jointly ensure the security of U.S. interests while breaking the security of everyone else. So it made sense to advocate improved crypto for, say, U.S. businesses, because that would benefit the U.S. in general by preventing the intelligence agencies of other countries from stealing U.S. corporate secrets.
    - devcpp 13y ago
      To take it further, I suppose they want to protect US citizens, companies and government from crypto attacks while using US laws to snoop on them easily. That way, they prevent foreign threats by making it very hard for everyone to break any system in the US. And on the other hand, they can still read everything by issuing subpoenas to any company and ISP they feel like (with borderline constitutional legality in some cases).
  - Locke1689 13y ago

deleted 13y ago

[deleted]

ceautery 13y ago

Isn't there an article like this every year, always long on FUD and short on math?

tptacek 13y ago
No?
IvyMike 13y ago
C'mon man, you're better than that. I'm sure you know how to use google to find the black hat presentation: https://www.isecpartners.com/media/105564/ritter_samuel_stamos_bh_2013_cryptopocalypse.pdf https://www.isecpartners.com/media/105564/ritter_samuel_stam... Which you then know how to use to find the papers by Joux. http://eprint.iacr.org/2013/095.pdf http://eprint.iacr.org/2013/095.pdf http://eprint.iacr.org/2013/400.pdf http://eprint.iacr.org/2013/400.pdf A lot of smart and proven people put together this information and if they're worried, I'm worried.
- ceautery 13y ago
  Thanks for the vote of confidence. I didn't search for the specifics based on the language of the article; it seemed to boil down to "some future math breakthrough based on current work is possible"... which is always the case. If I'm good enough to do something, it's to be able to switch out the encryption tools the enterprise I support uses at the drop of a hat, but despite similar fears voiced in tech forums over the last decade, I haven't yet needed to. I think it's more likely our security breach will come from someone trying to buy cheap drugs from Canada over email, or by a good old-fashioned mole.
  - tptacek 13y ago
    That's cryptography at its frontiers: you look at progress and try to get a sense of where it's going to take you. It's why Schneier keeps pounding on "attacks only get better". Also, as layperson, you should be wary of the lesson the last two decades have taught people like you on responding to far-out attacks on algorithms. RC4 was known to be broken almost immediately after it was published, but it wasn't until a few months ago(!) that someone bothered to refine the attack to the point where it could break TLS. The industry's intuition about how likely it is that a "theoretical" flaw will be weaponized is probably wrong. Crypto as a discipline only came into its own within the last ~10 years, and it's safe to assume offensive crypto research has lagged behind it.

kenster07 13y ago

This isn't very different from saying P = NP will be proven within 5 years. Sounds like linkbait.

tptacek 13y ago
This is very different from saying P=NP. It would instead be to say that the integer factorization or discrete log problems in the specific parameters used by cryptosystems simply aren't as hard as we once thought they were. RSA-128 is trivially breakable. Being able to break RSA-128 isn't a demonstration that P=NP, either.
- YZF 13y ago
  For RSA to be completely broken the attacker must be able to retrieve the private key for any practical key length. Some of what people are writing seems to imply more than attacks against specific parameters but rather some theoretical breakthrough that would render the scheme completely unusable. (e.g. factoring in polynomial time to key length) People have been moving to longer keys over time and thus simply being able to attack a given key length isn't the same as saying the entire scheme is broken. Today a 768 bit key is very difficult to attack. Is RSA with 64k-bit keys likely to be broken within 5 years? I guess in one sense our ability to work with much larger RSA keys has progressed faster than the theoretical advances in factoring. Until the time someone has some practical and provably strong cryptosystem we're kind of always at risk. ECC could also be broken so why should I feel more comfortable using ECC over RSA with 64k bit keys?
  - djao 13y ago
    RSA with 65536-bit keys is quite secure, but it's hugely impractical. Try it in OpenSSL. Key generation alone will take you several hours on a fast, current-generation machine.
    - YZF 13y ago
      You only need to generate your key pair once. I just generated a 16kbit key in 10 minutes. Why is this impractical? The cost of encrypt/decrypt would be modular exponentiation which isn't that bad. My point is though that as long as there is some number of bits where RSA is secure and it's use is practical then RSA isn't dead. A lot of the discussion seems to imply RSA will be dead soon as a result of recent work. Maybe it will or maybe it won't but it seems the claims are a bit overblown. I agree with the idea that we need to design to the possibility of RSA falling (or ECC falling) within reason but RSA could have fallen 5 years ago and it could fall tomorrow (and so can ECC).

beagle3 13y ago

Anyone know if DLP for a group generated by a primitive polynomial over GF(2) has had any advances in the last few years? I haven't seen it referenced anywhere in the last 10 years, but it's a version of DH that is much easier to implement in hardware than over integers, and the DLP was (last I checked) believed to be at least as hard, and probably harder, then the equivalent integer problem.

pbsd 13y ago
Yes, that's the kind of logarithm where the breakthroughs have happened, and the source of all this fuss. Not all logarithms over these fields are affected equally, though. Do you know of any actual thing using Diffie-Hellman (or anything else) over such fields?
- deleted 13y ago
  [deleted]