7 ms·

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 discre

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

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