Math Advances Suggest RSA Encryption Could Fall Within 5 Years | Hacker News Reader

Math Advances Suggest RSA Encryption Could Fall Within 5 Years

technologyreview.com

112 pointscodesuela81 comments

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

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

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!

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.

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.

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.

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.

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.

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.

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

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.

That's an excellent and useful reply, and you've given me much to think about. Thank you.

You two are having a useful and interesting conversation.

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.

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.

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.

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.

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.

this doesn't look like log to me. i think the function you want is e'th root.

n'th root of x = exp(log(x) / n)

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

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?

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.

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.

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.

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

The intent of the talk was also to urge caution and urgency, was the point I was trying to make.

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

(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

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

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_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/400.pdf

A lot of smart and proven people put together this information and if they're worried, I'm worried.

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.

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.

This is the third time in a short while I've seen (not random) people say RC4 is broken, so I went and looked it up, and I'm glad I did -- I guess you're referring to this:

http://www.isg.rhul.ac.uk/tls/

I wasn't aware of these weaknesses in RC4 - I thought most of the "RC4 is broken"-comments were WEP fallout/hyperbole -- I guess it really wasn't!

On a side note - shouldn't RC4 in TLS be even more vulnerable to CRIME than block ciphers?

RC4 is so broken. It's comically broken. It's amazing that it made it to 2013.

That's an argument from authority, though. There's no direct evidence to suggest that such a thing will happen, just that it hasn't been shown to be impossible.

It's an article about a tangible step forward in solving DL problems.

Will RSA be broken because of this? Of course nobody knows.

But are the recent breakthroughs interesting "hacker news"? Absolutely. Would you have really preferred not to hear about this?

Edit: As per tptacek's comment, changed "breaking RSA" to "solving DL problems"

I wouldn't go so far as to say a tangible step has been made in literally breaking RSA.

I upvoted/liked/approved/upmodded the story; I just don't think it's time for everyone to start acting like chicken littele, is all.

There's no direct evidence to suggest that such a thing will happen

Isn't this another way of saying there's no evidence that the future has been predicted?

No?

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.

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?

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

The NSA gives pretty good reasons for using ECC, and they are not alone in supporting it. The cryptography research community is also very supportive of ECC.

If that does not convince you or if you would prefer systems with security reductions to worst-case NP-hard problems, you should look here:

https://en.wikipedia.org/wiki/Learning_with_errors

There is a lot of theoretical excitement about LWE right now, not only for public key encryption and signing systems but also for exotic things like fully homomorphic encryption and attribute based encryption. Unfortunately, there is are costs that hamper practical deployment. There keys will be larger. There are even more parameters to set, and bad choices can be fatal to security. The security of LWE-based systems is not as well-understood as ECC (making parameter choices even more difficult). Widely used standards like TLS and PGP do not have support for lattice / hidden codes systems. High-performance implementations are still under development.

Aye, aware of LWE, and it's interesting stuff, and understand the theory as to why ECC is secure, and why DH key exchanges are increasingly not so.

I'm just inherently suspicious of anything the NSA are in favour of, as their focus seems to be on breaking crypto, rather than recommending strong crypto - to recommend a key exchange mechanism that they can't snoop on seems to be a counterintuitive step.

Actually, the NSA both breaks crypto and recommends crypto systems for government use. Much of their ability to recommend cryptosystems comes from their expertise in attacking cryptosystems.

This played out in a very interesting way with DES. Most of the theories about an NSA conspiracy to weaken DES have been falsified. The changes to the s-box structure was later discovered to strengthen the cipher against a certain class of attacks. The small key size was later discovered to be right around the actual security level the cipher provides (larger key sizes would not have improved security by much).

In the case of public key crypto, one of the most important things we need is to know what parameter sizes to use. Cryptanalysis is critical to making such estimates, and once again the NSA's expertise comes in handy here. To put it another way, if you knew nothing about factoring integers, 1024 bit RSA keys would appear to be overkill -- the only reason key sizes have become so large is because of GNFS and similar developments.

In general you should avoid assuming that large, sprawling agencies like the NSA have a single goal. Yes the NSA conducts signals intelligence and would prefer that those signals not be encrypted. On the other hand the NSA also wants to ensure that foreign governments cannot spy on American government communications. With the vast reliance on contractors to develop software for sensitive systems there is a need for the NSA to make good recommendations to the public (even at the risk of improving our opponents' security); it is a classic NSA dilemma.

I also believe that the NSA intended to strenghten DES. However, it was later discovered that the changed they made to the s-boxes also made it weak against a different form of cryptanalysis.

The NSA's changes to the DES s-boxes made them stronger against differential cryptanalysis, an observation that betrayed the NSA's prior knowledge of differential cryptanalysis long before it reached the academic literature.

It's been awhile since I've studied DES, but I'm not aware of any sense in which the s-box changes weakened it.

Linear cryptanalysis. Its been awhile since I've studied it as well, but Applied Cryptography sites a successful attack that took only 50 with 12 workstations (the book was published in 1996).

DES resists linear cryptanalysis --- the best linear attack on DES is 2^43 and requires 2^43 known plaintexts. Linear cryptanalysis of FEAL-8 takes just 4000 plaintexts.

According to Don Coppersmith, NSA picked DES's s-boxes by randomly generating them and choosing the ones that best resisted differential cryptanalysis --- again, this is something NSA did fifteen years before differential cryptanalysis was discovered by the public. They modified DES to resist an attack only they knew about.

They weakened DES by reducing key size from 128 to 56 bits. Everything suggests they didn't know about linear cryptanalysis at the time, and in any case their improved sboxes, by being stronger against DC, were also stronger against LC.

64 bits to 56 bits?

>The small key size was later discovered to be right around the actual security level the cipher provides (larger key sizes would not have improved security by much).

Citation?

Here's one, from Bruce Schneier some nine years ago:

> It took the academic community two decades to figure out that the NSA "tweaks" actually improved the security of DES

http://news.cnet.com/Saluting-the-data-encryption-legacy/201...

Yes, the NSA created sboxes that were resistant to differential cryptanalysis. I was asking for a citation in regard to the claim that:

>The small key size was later discovered to be right around the actual security level the cipher provides (larger key sizes would not have improved security by much).

I have never heard this claim before and without any source backing it up I am liable to doubt it.

Fair enough, and you're right - I just have my THF on a bit too tight these days.

Although I must have one final jab :)

>In general you should avoid assuming that large, sprawling agencies like the NSA have a single goal.

I don't think they actually have any goals, per se, other than their own perpetuation.

Not even that. Even a modicum of self-perpetuation would have seen Snowden run into a brick wall of technological access controls.

Nobody in academia likes ECC because the NSA recommends it; ECC's virtues over simple finite field IFP/DLP crypto are obvious. There's no sane conclusion you can reach by letting NSA's approval or disapproval of technology head-fake you; what you're basically saying is that there's a series of stimuli NSA could issue that'd get you to use FEAL and knapsack algorithms.

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.

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.

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.

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

Breaking crypto is the hard way to get information. Way easier to get it at one of the endpoints. (Industry lingo would say: attack data at rest, not data in transit.)

Poison RNGs, get backdoors into the biggest services and software, and you have the majority of what you could need with almost no computing power.

Because the NSA's task is twofold: protect US govt interests by conducting SIGINT on foreign govts, and protect US govt interest by keeping US company trade secrets and infrastructure secure.

Worse than the NSA being unable to break network traffic is foreign govts being able to break US network traffic.

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

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.

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?

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.

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

Well, now you're changing the goalposts. You originally said 64kbit, not 16kbit. Key generation is roughly O(n^4) in the bit size. If you quadruple the key length, the time goes up by a factor of 4^4, or 256. Key generation time is not irrelevant -- waiting ten hours before your SSH server can come online is no one's idea of a good user experience.

At the 64kbit-level (again, BIG BIG difference from 16kbit), even the cost of encryption/decryption alone is easily going to cripple a high-traffic server.

I apologize for changing the goalposts (slightly). I was using ssh-keygen and 16kbit was the maximum RSA key length I could use. Running the numbers, if we assume L(1/4) then 4kbit keys are slightly stronger than 1kbit keys today. 8kbit keys are very slightly stronger than 2kbit keys today. Please verify this, it's possible I made a mistake. L(1/4), 8kbit would be ~5*10^10 harder to factor than 1024 k-bit keys today. I think I now have the goalpost where it should be for a meaningful discussion? Another interesting question is why did Google choose to move to 2kbit rather than to ECC?

Attaching specific numbers to an expression like L(1/4) is meaningless, because L(1/4) is an asymptotic expression. Asymptotic expressions contain implied constants, whose values are not explicit. There's also no particular reason to expect the L(1/4) attack to apply to RSA. For one, I explained in another reply that we currently do not know any direct relationship between RSA and discrete log. In addition, Joux's latest result is not even L(1/4), it's L(epsilon) for any fixed epsilon > 0 (and in this context, the implied constant cannot be ignored, otherwise you get nonsense values).

Google does use ECC, on platforms that support it. See for example http://googleonlinesecurity.blogspot.com/2011/11/protecting-... which has a screenshot.

You're right and I understand that. I was assuming some hypothetical attack that is equivalent to GNFS. That assumption has no theoretical basis, it's just used as a mechanism to question the ideas and get some intuition. I'm using the same line of argument used in the original presentation where they show a progression and make assumptions about what that means about RSA keys. I think that line of reasoning is odd but even under that line of reasoning the results don't make sense to me.

16kbit RSA is also silly! Why dignify the suggestion?

No competent engineer in the world would give a green light to 768 bit RSA keys.

This article was based on a presentation I was marginally involved with, and I'm telling you that the assertions the talk was making were very much key length dependent. An event that forces a migration from 1024 bit RSA keys would be painful and dramatic.

It also bugged me that different classes of attacks were grouped together to build a "case" against RSA.

Looking at the slides again:

"There is a small but real chance that both RSA and non-ECC DH will soon become unusable"

"key sizes may have to up to 16kbit" - "wildly impractical" (WHY???)

L(1/4) isn't quite enough to make RSA unusable with large enough keys. I ran the numbers for 64k but you don't need to go as large.

It's not clear that this sort of linear progression presented is real. Some math problems don't see any progress in a long time and some see big progress rapidly. Seems to me like it's trying to find a pattern where there isn't one necessarily.

To conclude. RSA may fall tomorrow. ECC may fall tomorrow. AES may fall tomorrow. I agree with the principle we need to have some agility built in to cryptosystems (though if it falls we're kind of screwed). Maybe we need to combine cryptosystems such that one breaking won't take us down. Added complexity and changes create attack opportunities (at least current implementations are battle hardened).

Are you asking why a 16384 bit RSA key is considered wildly impractical? I assume you understand that using RSA-16384 is silly given the alternatives.

I was just stating the fact that factoring 768 bit keys is still difficult (though doable given enough time/compute power). I'm not implying you should use 768 bit keys.

I saw the slides and read various articles that followed and none of them seemed to be specifically concerned about 1024 bit RSA keys. Can you point me to where in the presentation slides that is emphasized as the main concern?

It's quite one thing to say we should be concerned that 1024 bit keys can be compromised and or to say DH/RSA is dead. I wasn't at the presentation so I don't know what was presented.

Title of thread is "Math Advances Suggest RSA Encryption Could Fall Within 5 Years (technologyreview.com) "

Not: "Math Advances Suggest 1024 bit RSA keys may be factorable within 5 years"

After doing some more reading on the matter, integer factorization is not known to be NP-complete. So I retract my original statement.

Reply on news.ycombinator.com