126
There's a new way to break RSA that's faster than anything we've seen before (arstechnica.com)
submitted 1 month ago by to c/technology@lemmy.world
54 comments fedilink hide all child comments
you are viewing a single comment's thread
view the rest of the comments
[–] 6 points 1 month ago (20 children)

RSA is secure because it relies on P vs NP. Very basically, RSA multiplies 2 very large prime numbers together to encrypt things. We rely on something similar for secure Internet connections

  • permalink
  • fedilink
  • source
  • parent
  • hideshow 20 child comments
    •
  • [–] 7 points 1 month ago (4 children)

    it relies on P vs NP

    That is incorrect. It relies on perceived difficulty of factoring large semi-prime. P equals NP is related, of course, if it happens to be an NP-intermediate problem, but the difficulty of factoring is not because it's NP-complete.

    There are already classical algorithms that are sub-exponential to solve the problem. If it were the case that the problem was NP-complete, then we would have had a big advance in our theory and practice based on it.

  • permalink
  • fedilink
  • source
  • parent
  • hideshow 4 child comments
    •
  • [–] -5 points 1 month ago (3 children)

    I'm not about to get into the weeds about P vs NP to explain a concept to someone that doesn't know much about encryption in the first place. I'm aware that factoring isn't really NP complete, but P vs NP is about solving vs verifying solutions for something in Polynomial time, which can't be done via brute force for RSA keys.

  • permalink
  • fedilink
  • source
  • parent
  • hideshow 3 child comments
    •
  • [–] 6 points 1 month ago (2 children)

    really NP complete

    I don't care who you want to get in the weeds with or what you wish to spar about, you're just not correct.

    There is no almost NP complete. There are strong and weak variants, sure, and those have particular implications.

    But you're drawing conclusions that don't exist from definitions that you clearly don't understand.

    Signed: Somebody who has taught theory of computation for over a decade.

  • permalink
  • fedilink
  • source
  • parent
  • hideshow 2 child comments
    •
  • [–] -2 points 1 month ago (1 child)

    If you want to be pedantic, fine. Integer factoring is not in P. Therefore the math used to encrypt RSA is not in P. The usage of integer factoring to encrypt therefore means it can't be decrypted in P using brute force. That's the point I'm making.

  • permalink
  • fedilink
  • source
  • parent
  • hideshow 1 child comment
    •
  • [–] 5 points 1 month ago

    We actually don't know if integer factorization is not in P, though.

    Right now, I think most of us would guess that it is a prime candidate for NP Intermediate. Hence why I mentioned it earlier.

    And you absolutely can solve it in polynomial time just not with classical architectures.

  • permalink
  • fedilink
  • source
  • parent
  • [–] 4 points 1 month ago (14 children)

    but do we not have other, much more secure encryption that is just as easy to employ?

  • permalink
  • fedilink
  • source
  • parent
  • hideshow 14 child comments
    •
  • [–] 6 points 1 month ago (7 children)

    Yes it's becoming more common to have Elliptic Curve keys. But many still use RSA.

  • permalink
  • fedilink
  • source
  • parent
  • hideshow 7 child comments
    •
  • [–] 1 point 1 month ago* (6 children)

    Elliptical curve for RSA was immediately phased out as soon as it was proven that the NIST was influenced by the NSA to implement it

  • permalink
  • fedilink
  • source
  • parent
  • hideshow 6 child comments
    •
  • [–] 7 points 1 month ago (4 children)

    And if I remember correctly, I believe it has more weaknesses (especially potential unknown ones) than RSA.

    But it's definitely more efficient on embedded hardware, and for sure still gets used in that space. Not that I'd know cough cough

  • permalink
  • fedilink
  • source
  • parent
  • hideshow 4 child comments
    •
  • [–] 2 points 1 month ago (1 child)

    And if I remember correctly, I believe it has more weaknesses (especially potential unknown ones) than RSA.

    what are those weaknesses? so far I have only read for users that ECC is more secure than RSA

    But it's definitely more efficient on embedded hardware,

    not only on embedded hardware, but everywhere and also in network transfer because of the smaller keys

  • permalink
  • fedilink
  • source
  • parent
  • hideshow 1 child comment
    •
  • [–] 2 points 1 month ago* (last edited 1 month ago)

    Tl;dr - Choosing parameters for ECC is very important but also very difficult. Also, ECC is more resistant to quantum algorithms than RSA.

    I didn't know about the PQC readiness of ECC so thank you!

    To my understanding, picking the right ECC parameters is critical to ensuring large enough entropy that it can't be brute forced. There are a lot of weak and easy to compromise parameters, and a lot of trust has to be put in the standards organizations declaring which ones are "safe" like the NIST curves. Or you can choose your own, with a lot of risk associated.

    There's also the fact that I believe there's more potential to leak info/expose side channels on the embedded devices running these protocols (I've personally had to worry at work!)

    interesting about the security, it looks like ECC is arguably more secure against quantum algorithms? I first learned about all of this stuff about 10 years ago, and I only vaguely remember reading about the pqc resistance. Thanks for the update on that!

    Edit: But I want to be clear I'm not a security expert, just some lady whose had to deal with embedded cryptography from time to time.

  • permalink
  • fedilink
  • source
  • parent
  • [–] 1 point 1 month ago

    Elliptical curve for RSA was immediately phased out

    what? when did RSA want to use elliptical curves? its a completely different technology. and ECC itself was not phased out of anywhere. certain curves were, not ECC as a whole.

  • permalink
  • fedilink
  • source
  • parent
  • [–] 8 points 1 month ago* (4 children)

    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.

  • permalink
  • fedilink
  • source
  • parent
  • hideshow 4 child comments
    •
  • [–] 2 points 1 month ago (1 child)

    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.

  • permalink
  • fedilink
  • source
  • parent
  • hideshow 1 child comment
    •
  • [–] 4 points 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.

  • permalink
  • fedilink
  • source
  • parent