2 ms·

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 leng

by djao 13y ago

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.

tptacek 13y ago
16kbit RSA is also silly! Why dignify the suggestion?
YZF 13y ago
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?
- djao 13y ago
  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-data-for-long-term-with.html http://googleonlinesecurity.blogspot.com/2011/11/protecting-... which has a screenshot.
  - YZF 13y ago
    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.

by djao 13y ago

tptacek 13y ago

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

YZF 13y ago

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?

djao 13y ago
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-data-for-long-term-with.html http://googleonlinesecurity.blogspot.com/2011/11/protecting-... which has a screenshot.
- YZF 13y ago
  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.