News for hackers. Stuff that matters.
Re:Math Advances Suggest RSA Encryption Could Fall Within 5 ... by Mithrandir on Saturday August 10, 2013 @11:33AM (#6191390)
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."

Re:Math Advances Suggest RSA Encryption Could Fall Within 5 ... by ColinWright on Saturday August 10, 2013 @11:54AM (#6191485)

  > 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!

Re:Math Advances Suggest RSA Encryption Could Fall Within 5 ... by pbsd on Saturday August 10, 2013 @02:03PM (#6192012)
If you can compute discrete logarithms modulo composite n, you can actually factor n.

Suppose that n = p * q. The order of the multiplicative group of the integers modulo n is (p-1) * (q-1). Suppose that, given a randomly generated a, we can find a nontrivial x such that a^x = 1 (mod n). Then x divides the order of n, i.e. (p-1)*(q-1), and we can quickly extract p and q from there.

Edit: Terminology correction. Thanks xyzzyz!

Re:Math Advances Suggest RSA Encryption Could Fall Within 5 ... by xyzzyz on Saturday August 10, 2013 @02:39PM (#6192157)
The order of the ring of integers modulo n is (p-1)(q-1)

You mean, the order of the multiplicative group. The order of the ring of integers modulo n is always n, regardless of n.

Re:Math Advances Suggest RSA Encryption Could Fall Within 5 ... by djao on Saturday August 10, 2013 @07:24PM (#6193052)
You're assuming unrestricted discrete logarithms over a composite modulus. This is a much stronger assumption than discrete logarithms over prime moduli. Even if someone found a fast way to break discrete logarithms modulo primes, your assumption would still not automatically hold.

Since cryptography uses discrete logarithms over prime moduli, the discrete logarithm problem that cryptographers are working on is not the same problem as the problem that they would need to solve in order to break RSA.

Re:Math Advances Suggest RSA Encryption Could Fall Within 5 ... by ColinWright on Sunday August 11, 2013 @02:30AM (#6194086)
Absolutely, and that's why I say the unrestricted discrete log lets you break RSA. It's certainly not the special case that cryptographers are currently working on, but it's very much related.

And equally, although the completely unrestricted version needed to break general RSA is very much out of reach at the moment, it's possible (although still incredibly unlikely) that a particular choice of parameters may be broken because we happen to find the right discrete log solution. These are not currently viable methods of attack, but speculating on them may lead to useful insights, and certainly discussing them can help non-experts gain insight.

Re:Math Advances Suggest RSA Encryption Could Fall Within 5 ... by djao on Sunday August 11, 2013 @10:49AM (#6195078)
The only relation between the two problems is that they involve the same type of equation. The underlying number systems are totally different. There is no reason to expect the two problems to be of comparable difficulty.

As an illustrative example, the equation for the RSA problem itself can be defined over prime fields, and it is trivially easy to solve in that setting. The same problem over a composite modulus is believed to be hard, and forms the basis for the RSA cryptosystem. Just because an equation can be solved over prime fields does not mean, at all, that it can be solved over composite moduli.

Re:Math Advances Suggest RSA Encryption Could Fall Within 5 ... by ColinWright on Sunday August 11, 2013 @11:03AM (#6195109)
I suspect we are arguing past each other, and if we were to sit down over coffee (or equivalent) in from of a whiteboard (or equivalent) then we would have a really useful and interesting conversation. Everything you say is right, but I believe there are more connections going on at a deeper level. This is my intuition speaking, and as a PhD in Combinatorics and Graph Theory who has dabbled for decades (literally - I started in 1967) in integer factorization and discrete logs, I've learned to listen to my intuition. It's sometimes wrong, and it may well be in this case, but I feel that the deeper structures in Z_{pq} and Z_p have a cross-fertilization that we may eventually find.

I agree that these aren't the obvious things to be working on, and the more direct attacks - factorization for RSA and discrete logs in Z_p for DHMW - are just that, more direct, and will certainly be more fruitful in the short to medium term.

It would be nice to make that real-life conversation happen. Feel free to email me? Details in my profile.

Re:Math Advances Suggest RSA Encryption Could Fall Within 5 ... by djao on Sunday August 11, 2013 @05:21PM (#6196378)
My experience as someone who is active in research in this exact field (mathematical cryptanalysis) is that generic techniques for discrete logarithms, such as Pollard rho or the number field sieve, do transfer well to integer factorization, but more specific techniques such as Joux's latest function field sieve tend to be harder to transfer from one setting to the other.
Re:Math Advances Suggest RSA Encryption Could Fall Within 5 ... by ColinWright on Sunday August 11, 2013 @05:29PM (#6196401)
Right - that's very useful information. Now I really do want to get together with you to talk about these things. You clearly know more than I about the details, and I'd love to learn more.

Alas, I expect it won't happen, but thanks for the information.

A question. You say:

  > ... more specific techniques such as Joux's latest
  > function field sieve tend to be harder to transfer
  > from one setting to the other.
Do you have any sense that perhaps, as we come to understand it in more detail, we may yet come to find that it becomes more widely applicable? Obviously you feel at the moment that it's too specific, but is that perhaps because we don't understand it properly yet? Or do you feel it's genuinely limited in that regard? I'm just thinking about how Wiles' insights and proofs about the (speaking loosely) limited form of the equivalence of specific Elliptic Curves and Modular Forms opened the field for the full proof of the T-S conjecture (now theorem).

Just looking for a deeper insight into your intuition. Feel free to speculate wildly. If you're right you can appear prescient. If wrong, it was just speculation. 8-)

Added in edit: Supersingular Primes for Rational Points on Modular Curves (?)

Just for fun, see also: http://www.solipsys.co.uk/images/JaoAndWright_c.png

Re:Math Advances Suggest RSA Encryption Could Fall Within 5 ... by djao on Monday August 12, 2013 @12:18AM (#6197636)
Generally speaking, attacks which rely on more structure are hard to adapt to situations where there is less structure. Conversely, attacks which require no structure are easy to generalize to a wide variety of situations.

Something like Pollard rho requires no structure. It works in any group. The number field sieve is an intermediate case. It requires a norm (basically you need some elements to be bigger than others). For arbitrary finite fields, the NFS still represents the fastest known attack. The latest attack is a version of the function field sieve. The FFS uses, in an essential way, the algebraic structure of polynomials over a field. Coppersmith pioneered the use of the FFS in the 80s, when he showed that small characteristic fields (which consist primarily of polynomials) admit faster discrete logarithm solutions. The latest work goes far beyond Coppersmith's work, but tends towards increasing specialization, not generalization, since it adds the new requirement that the field contain an intermediate subfield.

Given that the direction of specialization appears, if anything, to be going in the other direction, there would have to be a substantial further breakthrough in order to apply these results more generally. My own opinion and intuition is that these results are not likely to apply to prime field discrete logs, never mind RSA and/or composite moduli.

Re:Math Advances Suggest RSA Encryption Could Fall Within 5 ... by ColinWright on Monday August 12, 2013 @02:41AM (#6197971)
That's an excellent and useful reply, and you've given me much to think about. Thank you.
Re:Math Advances Suggest RSA Encryption Could Fall Within 5 ... by tptacek on Sunday August 11, 2013 @01:35PM (#6195516)
You two are having a useful and interesting conversation.
Re:Math Advances Suggest RSA Encryption Could Fall Within 5 ... by benmmurphy on Saturday August 10, 2013 @12:51PM (#6191714)
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.
Re:Math Advances Suggest RSA Encryption Could Fall Within 5 ... by ColinWright on Saturday August 10, 2013 @01:01PM (#6191759)
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.
Re:Math Advances Suggest RSA Encryption Could Fall Within 5 ... by jaekwon on Saturday August 10, 2013 @02:10PM (#6192038)
https://gist.github.com/jaekwon/6201493

edit: it doesn't work. :P It worked when e or d was set to 1. oops.

you might want to see if there's a bug in the main function.

Re:Math Advances Suggest RSA Encryption Could Fall Within 5 ... by ColinWright on Saturday August 10, 2013 @02:15PM (#6192053)
Indeed, but these are really small numbers. RSA only works with really BIG numbers, which is one reason people are starting to insist that PKC should use ECC.
Re:Math Advances Suggest RSA Encryption Could Fall Within 5 ... by jaekwon on Saturday August 10, 2013 @02:29PM (#6192106)
updated my comment.

The only thing I can think of is that discrete logs don't work that way.

while E^(e.log_E(M)) == E mod n, e.log_E(M) doesn't equal 1. And I'm not sure what /e means in the realm of exponents, besides *d, and I don't know how to find d without knowing M.

Re:Math Advances Suggest RSA Encryption Could Fall Within 5 ... by benmmurphy on Saturday August 10, 2013 @12:02PM (#6191519)
this doesn't look like log to me. i think the function you want is e'th root.
Re:Math Advances Suggest RSA Encryption Could Fall Within 5 ... by barrkel on Saturday August 10, 2013 @12:11PM (#6191547)
n'th root of x = exp(log(x) / n)
Re:Math Advances Suggest RSA Encryption Could Fall Within 5 ... by tptacek on Saturday August 10, 2013 @02:01PM (#6192006)
* 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.

Re:Math Advances Suggest RSA Encryption Could Fall Within 5 ... by ivmi on Saturday August 10, 2013 @06:17PM (#6192886)
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?

Re:Math Advances Suggest RSA Encryption Could Fall Within 5 ... by tptacek on Sunday August 11, 2013 @01:14PM (#6195450)
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.
Re:Math Advances Suggest RSA Encryption Could Fall Within 5 ... by djao on Sunday August 11, 2013 @01:25PM (#6195482)
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.
Re:Math Advances Suggest RSA Encryption Could Fall Within 5 ... by tptacek on Sunday August 11, 2013 @01:34PM (#6195510)
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.

Re:Math Advances Suggest RSA Encryption Could Fall Within 5 ... by djao on Sunday August 11, 2013 @05:08PM (#6196345)
There is a difference between "Here's an example of a cryptosystem that got attacked" and "Here's an example of an attack against RSA."
Re:Math Advances Suggest RSA Encryption Could Fall Within 5 ... by tptacek on Sunday August 11, 2013 @07:28PM (#6196795)
The intent of the talk was also to urge caution and urgency, was the point I was trying to make.
Re:Math Advances Suggest RSA Encryption Could Fall Within 5 ... by djao on Monday August 12, 2013 @12:07AM (#6197612)
The thing is, some people think we're already on a 10-year clock. Quantum computers represent a very real threat, and there are no theoretical obstacles to their implementation. So yes, we should be migrating to something else. These latest breakthroughs add more impetus, but I don't think they're going to get there before quantum computers (just my opinion).
Re:Math Advances Suggest RSA Encryption Could Fall Within 5 ... by Mithrandir on Saturday August 10, 2013 @02:25PM (#6192088)
(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