Side question: if quantum computers fulfill their promise, won't they break encryption as we know it? Are we ready for that kind of upheaval?
Factoring 2048 RSA integers in 177 days with 13436 qubits and a multimode memory
31–40 of 146 posts
Re: Factoring 2048 RSA integers in 177 days with 13436 qubits and a multimode memory
#32Side question: if quantum computers fulfill their promise, won't they break encryption as we know it? Are we ready for that kind of upheaval?
Yes and kinda yes.
There's a standardization process going on for post quantum cryptography at the US NIST. Results expected before the almighty RSA-breaking quantum computer arrives.
There's still a concern about store-and-encrypt-later (i.e. someone can store encrypted communication today and decrypt it once a QC is available), and how relevant that is depends on some unknowns (how many years to you expect your comms to be secret? how many years till a usable QC is available?).
Re: Factoring 2048 RSA integers in 177 days with 13436 qubits and a multimode memory
#33Earlier quoted context omitted.
I.e. you can solve it by rotating your keys/certificates every 90 days, like the expiry term given by Letsencrypt.
Rotating keys works for authentication, but not for confidentiality, since nothing stops an attacker from recording the ciphertext and decrypting past messages.
In common practice RSA keys/certificates are used for TLS and similar protocols where it does not allow to decrypt past recorded communications, as those are encrypted with an ephemeral session keys that can not be determined from observing the handshake even if you have the keys. Obtaining a private key would allow you to MITM future sessions and decrypt them, but it would not break confidentiality of past messages. Things like PGP-encrypted email files would be vulnerable, but that niche is extremely rare in comparison to other uses of RSA and similar encryption.
Re: Factoring 2048 RSA integers in 177 days with 13436 qubits and a multimode memory
#34Quantum computers of this scale are probably 5-15 years out. Basically this is a warning that if you have secrets that should still be kept secret over that timeframe, you should not be using RSA today.
> you should not be using RSA today Also, always remember that ECC is believed to be just as weak against quantum computers as RCA. So you'll probably want some fusion of pre and post-quantum algorithms. Or, anyway, get your perfect forward secrecy working and don't rely on asymmetric crypto for confidentiality. Yeah, PFS is very hard to get on some use cases, but it's really the best way to solve this problem.
Yes, that's how pqcrypto is done today. Run two key exchanges, one we're pretty sure is solid, and one that might be post-quantum-secure but has some risk of actually not being secure at all, and use a robust combiner on their outputs.
Re: Factoring 2048 RSA integers in 177 days with 13436 qubits and a multimode memory
#35Earlier quoted context omitted.
I.e. you can solve it by rotating your keys/certificates every 90 days, like the expiry term given by Letsencrypt.
Rotating keys works for authentication, but not for confidentiality, since nothing stops an attacker from recording the ciphertext and decrypting past messages.
RSA is rarely actually used for doing the message encryption. Instead it is used for negotiating other keys. Perfect-forward-secrecy enables you to get message confidentiality even if your key is leaked after the message is sent.
Re: Factoring 2048 RSA integers in 177 days with 13436 qubits and a multimode memory
#36Earlier quoted context omitted.
Rotating keys works for authentication, but not for confidentiality, since nothing stops an attacker from recording the ciphertext and decrypting past messages.
In common practice RSA keys/certificates are used for TLS and similar protocols where it does not allow to decrypt past recorded communications, as those are encrypted with an ephemeral session keys that can not be determined from observing the handshake even if you have the keys. Obtaining a private key would allow you to MITM future sessions and decrypt them, but it would not break confidentiality of past messages.…
That's not how this works.
An attacker can record the key exchange. That is not using RSA, today it's usually some variation of elliptic curve diffie hellman. But that is just as vulnerable to quantum attacks as RSA. So you're attacking the key exchange, not the RSA signature.
What you're probably alluding to here is the forward secrecy property of TLS. But that is only true under the assumption that the key exchange is secure. In a quantum attack scenario it is not.
So a store-and-decrypt-later attack is still a very valid concern around TLS and quantum computers.
Re: Factoring 2048 RSA integers in 177 days with 13436 qubits and a multimode memory
#37Earlier quoted context omitted.
I'd be willing to bet a lot that it's not 5 years, and am still quite confident it's not 15. Of course nobody knows, but these things are still very far from anything that is running today.
At this rate, maybe the first commercial Fusion plants will have asymmetric quantum encryption securing their management portal.
no no no, you need high performance enterprise grade http on port 80 listening on all interfaces for a power plant portal
Re: Factoring 2048 RSA integers in 177 days with 13436 qubits and a multimode memory
#38Earlier quoted context omitted.
Rotating keys works for authentication, but not for confidentiality, since nothing stops an attacker from recording the ciphertext and decrypting past messages.
RSA is rarely actually used for doing the message encryption. Instead it is used for negotiating other keys. Perfect-forward-secrecy enables you to get message confidentiality even if your key is leaked after the message is sent.
Diffie-Hellman over finite fields or elliptic curves is just as vulnerable to Shor's algorithm as RSA. I believe ECC might even need fewer qubits to break at the same classical security level, since the numbers are smaller.
There is a small benefit, because now an attacker needs to attack each session separately, instead of attacking a single key to break all sessions with a particular sever. But that's hardly something you want to rely on.
Re: Factoring 2048 RSA integers in 177 days with 13436 qubits and a multimode memory
#39This paper basically explores a hypothetical scenario where scaling quantum memory ends up being cheaper than scaling computational qubits. The title (or abstract) unfortunately does not mention the quantum memory requirements at n=2048 explicitly. For factoring 2048 RSA integers, the technique proposed in the paper would require ~430 million memory qubits (see the table at top of page 16).
I'm trying to make sense of the 'memory qubits' e.g. 'spatial modes' in the paper. Do you know if they are they a sort of...quantum flip flop?
Is this also a hypothetical structure, or have they been built and shown to be able to reliably store and retrieve quantum state in such spatial modes? 430 million is a much, much larger number than their headline 13436 qubits...
Re: Factoring 2048 RSA integers in 177 days with 13436 qubits and a multimode memory
#40Earlier quoted context omitted.
Rotating keys works for authentication, but not for confidentiality, since nothing stops an attacker from recording the ciphertext and decrypting past messages.
In common practice RSA keys/certificates are used for TLS and similar protocols where it does not allow to decrypt past recorded communications, as those are encrypted with an ephemeral session keys that can not be determined from observing the handshake even if you have the keys. Obtaining a private key would allow you to MITM future sessions and decrypt them, but it would not break confidentiality of past messages.…
But those ephemeral session keys can not be determined from observing the handshake because the handshake uses asymmetric cryptographic algorithms which may use exactly the same mathematics as RSA.