Until now, cryptographers thought factoring was the only way to break RSA. Not anymore.
  • rockSlayer@lemmy.blahaj.zoneEnglish
    114·
    1 month ago

    There are tradeoffs with encryption. RSA is so secure, that the US government has tried to insert a mathematic backdoor into the key selection because that’s the easiest method to attack the encryption. RSA uses thousands of bits for their encryption, making it inefficient for most attacks. The attack detailed in this article is on one of the weaker RSA algorithms, with only 1024 bits. The high end RSA uses 4096 bits or more, I believe the algorithm has increased the bit length to officially support 8192.

    On the other side of RSA is another secure algorithm called AES. It can go up to 512 bits, but it hashes the key to meet the key length instead of relying on generating huge prime numbers. It makes it more resilient to certain types of attacks, but the bit limitation makes it easier to brute force or use rainbow tables.

    • sik0fewl@piefed.caEnglish
      8·
      1 month ago

      AES is asymmetric encryption and cannot be used for the same things as RSA. EdDSA would be more comparable to RSA.

      • rockSlayer@lemmy.blahaj.zoneEnglish
        53·
        1 month ago

        I know that AES is symmetrical. I was using it to illustrate that symmetrical and asymmetrical encryption have tradeoffs that cannot be worked around.

    • y0kai [he/him]@anarchist.nexusEnglish
      31·
      1 month ago

      Thanks for this answer. The article makes it sound as though even the 4096-bit versions are now more or less trivial to defeat given a bit of money for a capable machine and this new method:

      Even for 2048- and 4096-bit keys, the method reduces the security of RSA to unacceptable levels. The National Security Agency, National Institute of Standards and Technology, and European Union Agency for Network and Information Security require that any cryptosystem should provide a level of no less than 128 or more bits, meaning the operations required must exceed 2^128.

      The forgery attack drops these levels to 2^65, 2^90, and 2^119 for 1024-, 2048-, and 4096-bit keys respectively. These levels may further drop because Heninger’s team did all the coding by hand and used no AI or GPUs in performing the forgeries. The researcher said these tools will “almost certainly” drop the security levels further.

      • prime_number_314159@lemmy.worldEnglish
        4·
        1 month ago

        Just to put a bit of context on those, OpenAI said they used 180,000 GPUs for training their GPT-5 model. As I understand it, each GPU has ~16,000 cores, and each of those cores does a couple billion operations per second. With that cluster, 2^65 operations takes a couple seconds, 2^90 takes many years, and 2^119 is off in “the sun has grown to surround the Earth” territory. The NSA is concerned with protecting their stuff against organizations with hundreds of billions of dollars, and a hundred of years of time to dedicate dozens or hundreds of people to breaking it. “Not good enough” in that context is a very different bar than what most people have to worry about.

        You also need to provide them 2^43 unsalted responses, which is more than a casual few.