3 ms·

768-bit RSA cracked, 1024-bit safe (for now)

8 points by raju 17y ago

shin_lao 17y ago
It needs to be noted that RSA as a whole is discouraged in favour of elliptic encryption. RSA is difficult to use correctly, one needs the data to be padded correctly (OAEP), the prime numbers ideally should be Sophie-Germain primes and the keys need to be longer and longer which causes other problems related to prime generation. See: http://en.wikipedia.org/wiki/NSA_Suite_B_Cryptography http://en.wikipedia.org/wiki/NSA_Suite_B_Cryptography
- tptacek 17y ago
  There may not be a single person on Hacker News, including Colin, who knows enough to implement ECC safely. It's got at least as many easy dealbreaker pitfalls as RSA. You don't need OAEP to make RSA work for signing.
  - shin_lao 17y ago
    Well... You rarely implement the algorithm yourself, do you? It's a project by itself.
    - NateLawson 17y ago
      Tarsnap implements its own crypto algorithms, partially on top of the SSL bignum functions. This is scary (yet another critical part that needs review) but also could help it achieve a higher level of assurance because OpenSSL's RSA implementation is a mess and much harder to review. Note I am not saying that it is good to implement your own algorithms, just pointing out the sorry state we're at with existing libraries.
  - cperciva 17y ago
    There may not be a single person on Hacker News, including Colin, who knows enough to implement ECC safely. Yep. ECC is messy. I don't use it, for the very simple reason that I wouldn't trust an ECC implementation that I wrote. I might trust DJB's ECC code; but I'd be really uncomfortable with using it unless I had spent at least a few weeks checking it over. It's got at least as many easy dealbreaker pitfalls as RSA. s/at least as many/many many more/ You don't need OAEP to make RSA work for signing. No, but you do need PSS if you want to do things right; and PSS is basically the "natural" translation of OAEP from encryption to signing.
    - NateLawson 17y ago
      I agree. The randomized RSA modes (OAEP and PSS) are preferable to the old constant ones (PKCS #1 v1.5). They are better from a theoretical perspective and also from the fact that the randomization may protect you against an attack even in the face of some (but not all!) implementation flaws. They offer both better theoretical security and defense-in-depth.
tptacek 17y ago
Nit: most modern crypto does not rely on large numbers that are the product of two primes. Truly number-theoretic algorithms are mostly in the province of public key crypto. For all you read about public key, it's somewhat rare in workhorse production systems. Also, truly modern public key systems aren't the product of very large prime numbers. Elliptic curve systems achieve better security at much lower key sizes, and for that reason and others it's displacing RSA, especially in the cryptosystems you don't regularly read about in Ars Technica. There is probably another 10 years before there's even an academic result against 1024 bit RSA keys.
- cperciva 17y ago
  For all you read about public key, it's somewhat rare in workhorse production systems. I disagree. Sure, most data gets encrypted or signed using shared-key systems; but those shared keys are almost always negotiated using public key crypto. Don't forget that if you can break RSA, you can write yourself an SSL certificate identifying yourself as anything you want. There is probably another 10 years before there's even an academic result against 1024 bit RSA keys. Given the maxim that the NSA is always 10 years ahead of academic cryptographers, I'd say this is a very good reason to not trust 1024-bit RSA any more.
oscardelben 17y ago
I discovered how RSA works only recently, but I wonder how long would it take for NSA to decrypt a RSA cypher. If people can do that in an academic environment, then I think we don't have to worry that NSA can't decrypt messages, because they are probably doing it more quickly.
eli 17y ago
Factored != Cracked 768-bit RSA is no less safe now than it was last week.
- cperciva 17y ago
  768-bit RSA is no less safe now than it was last week. Indeed. It was completely unsafe last week, and it is still completely unsafe. Stunts like this are like terrorist attacks: They don't make you unsafe; they merely remind you that you're unsafe.
chris123 17y ago
Is there not already "CryptoCracker" website? Where, for a fee, you can submit a cracking task to a cluster and have it send you the results when it's done? Price is set according to a matrix: crackable items down the rows and turnaround times down the columns. The harder the crack and the faster you want it completed, the higher the fee.

8 points by raju 17y ago

It needs to be noted that RSA as a whole is discouraged in favour of elliptic encryption. RSA is difficult to use correctly, one needs the data to be padded correctly (OAEP), the prime numbers ideally should be Sophie-Germain primes and the keys need to be longer and longer which causes other problems related to prime generation. See: http://en.wikipedia.org/wiki/NSA_Suite_B_Cryptography http://en.wikipedia.org/wiki/NSA_Suite_B_Cryptography

tptacek 17y ago
There may not be a single person on Hacker News, including Colin, who knows enough to implement ECC safely. It's got at least as many easy dealbreaker pitfalls as RSA. You don't need OAEP to make RSA work for signing.
- shin_lao 17y ago
  Well... You rarely implement the algorithm yourself, do you? It's a project by itself.
  - NateLawson 17y ago
    Tarsnap implements its own crypto algorithms, partially on top of the SSL bignum functions. This is scary (yet another critical part that needs review) but also could help it achieve a higher level of assurance because OpenSSL's RSA implementation is a mess and much harder to review. Note I am not saying that it is good to implement your own algorithms, just pointing out the sorry state we're at with existing libraries.
- cperciva 17y ago
  There may not be a single person on Hacker News, including Colin, who knows enough to implement ECC safely. Yep. ECC is messy. I don't use it, for the very simple reason that I wouldn't trust an ECC implementation that I wrote. I might trust DJB's ECC code; but I'd be really uncomfortable with using it unless I had spent at least a few weeks checking it over. It's got at least as many easy dealbreaker pitfalls as RSA. s/at least as many/many many more/ You don't need OAEP to make RSA work for signing. No, but you do need PSS if you want to do things right; and PSS is basically the "natural" translation of OAEP from encryption to signing.
  - NateLawson 17y ago
    I agree. The randomized RSA modes (OAEP and PSS) are preferable to the old constant ones (PKCS #1 v1.5). They are better from a theoretical perspective and also from the fact that the randomization may protect you against an attack even in the face of some (but not all!) implementation flaws. They offer both better theoretical security and defense-in-depth.

tptacek 17y ago

Nit: most modern crypto does not rely on large numbers that are the product of two primes. Truly number-theoretic algorithms are mostly in the province of public key crypto. For all you read about public key, it's somewhat rare in workhorse production systems. Also, truly modern public key systems aren't the product of very large prime numbers. Elliptic curve systems achieve better security at much lower key sizes, and for that reason and others it's displacing RSA, especially in the cryptosystems you don't regularly read about in Ars Technica. There is probably another 10 years before there's even an academic result against 1024 bit RSA keys.

cperciva 17y ago
For all you read about public key, it's somewhat rare in workhorse production systems. I disagree. Sure, most data gets encrypted or signed using shared-key systems; but those shared keys are almost always negotiated using public key crypto. Don't forget that if you can break RSA, you can write yourself an SSL certificate identifying yourself as anything you want. There is probably another 10 years before there's even an academic result against 1024 bit RSA keys. Given the maxim that the NSA is always 10 years ahead of academic cryptographers, I'd say this is a very good reason to not trust 1024-bit RSA any more.

oscardelben 17y ago

I discovered how RSA works only recently, but I wonder how long would it take for NSA to decrypt a RSA cypher. If people can do that in an academic environment, then I think we don't have to worry that NSA can't decrypt messages, because they are probably doing it more quickly.

eli 17y ago

Factored != Cracked 768-bit RSA is no less safe now than it was last week.

cperciva 17y ago
768-bit RSA is no less safe now than it was last week. Indeed. It was completely unsafe last week, and it is still completely unsafe. Stunts like this are like terrorist attacks: They don't make you unsafe; they merely remind you that you're unsafe.

chris123 17y ago

Is there not already "CryptoCracker" website? Where, for a fee, you can submit a cracking task to a cluster and have it send you the results when it's done? Price is set according to a matrix: crackable items down the rows and turnaround times down the columns. The harder the crack and the faster you want it completed, the higher the fee.