0

I've watched a lot of videos on Shor's Algorithm and Quantum Computers. Most of these videos say these two things undermine RSA via fast-factoring, but they never really explain how fast-factoring is used to these break things; just very hand-wavy statements.

Basically:

  • I get that with fast factoring, you could(?) reconstruct the private key from a public key. But wouldn't you still need the username/password/server details? I've ssh'd into servers for work and I still have to provide credentials on top of the ssh keys. Various commands on the server are also password protected, so fast-factoring doesn't seem all that dangerous unless I'm missing something here.
  • I get that MITM can use fast-factoring to decrypt the traffic (via the trick above) allowing you to modify the traffic then re-encrypt.

I guess I have not seen/read a complete start-to-finish example story of how fast-factoring would actually undermine the internet.

Sam Z
  • 1
  • 1
  • Consider your second bullet point about MITM'ing the TLS connection between a client and a server. Alice logs into her online banking web site. She sends her credentials through the TLS connection, but Mallory MITM's the connection using fast factoring. Now, Mallory has Alice's credentials, and Mallory can login to Alice's online banking, and withdraw all of Alice's money! – mti2935 Nov 29 '23 at 12:21
  • @mti2935 - understood, what about the first point? creating the private key from public; that seems insufficient to me. – Sam Z Nov 30 '23 at 11:49
  • 1
    Yes. With SSH, it's quite common for admins to login to an SSH server using public key authentication. For this, the admin sends his public key to the server, and proves that he/she is in possession of the corresponding private key. If the public key is in the server's list of authenticated public keys, then the admin is authenticated. Using fast factoring, an attacker could copy the admin's public key, then solve for the private key, then use this to impersonate the admin, and gain access to the server. – mti2935 Nov 30 '23 at 16:03
  • Even if the server uses password authentication instead of (or in addition to) public key authentication, fast factoring can be used to defeat this as well. An attacker who is positioned between the client and the server (such as an ISP or a rogue wifi hotspot operator) can copy the server's public key, then use fast factoring to solve for the server's private key, Then, the attacker can impersonate the server, and use the fake server to capture the admin's login credentials (similar to my first comment above). – mti2935 Nov 30 '23 at 16:06
  • Here's another scenario to consider: An attacker who has figured out how to do fast-factoring could factor a CA's public key to get the corresponding private key. Then, the attacker could use this to impersonate the CA, and sign certificates for any site. These certificates would appear as if they were signed by the CA, and would be trusted to any browser that trusts the CA. – mti2935 Nov 30 '23 at 21:08
  • @mti2935 - impersonating a CA makes sense, but to impersonate an entire website, you would still need to spoof the URL or use MITM to re-route the traffic, correct? These strategies already exist without fast-factoring; I presume FF just makes them better. – Sam Z Dec 01 '23 at 12:20
  • Yes, to impersonate a site, you need an MITM position and you need to get the browser to trust the MITM's certificate. See https://security.stackexchange.com/questions/230689/if-an-adversary-took-over-a-major-certificate-authority-what-bad-things-could-t for more info. An MITM position could be an ISP, a data center, a wifi hotspot operator, a TOR exit node, etc. Or, it could be done with DNS tampering, etc. – mti2935 Dec 01 '23 at 12:27
  • @mti2935 if you known any other approaches, please share. If you post an answer I'll mark it as correct. – Sam Z Dec 04 '23 at 12:17
  • Thanks Sam. I'll write this up as an answer when I get some time. In the meantime, think about the havoc that would be wreaked if someone with an MITM position (such as a state-run ISP) were to use fast-factoring to get Apple's private signing key that it uses to sign iOS updates, or Microsoft's private signing key that it uses to sign Windows updates. – mti2935 Dec 05 '23 at 17:39

0 Answers0