News for hackers. Stuff that matters.
Re:Willow, Our Quantum Chip by kortilla on Monday December 09, 2024 @07:57PM (#42372458)
> quantum computers would be able to retroactively break any public keys that were stored

Use a key exchange that offers perfect forward secrecy (e.g. diffie Hellman) and you don’t need to worry about your RSA private key eventually being discovered.

Re:Willow, Our Quantum Chip by HeatrayEnjoyer on Monday December 09, 2024 @08:04PM (#42372507)
Not exactly, they can just reverse the entire chain.
Re:Willow, Our Quantum Chip by kortilla on Tuesday December 10, 2024 @02:47AM (#42374743)
What chain are you talking about?
Re:Willow, Our Quantum Chip by ReptileMan on Monday December 09, 2024 @08:07PM (#42372522)
Perfect forward secrecy doesn't work that well when NSA motto is - store everything now decrypt later. If they intercept the ephemeral key exchange now they can decrypt the message 10 or 50 years later.
Re:Willow, Our Quantum Chip by JKCalhoun on Monday December 09, 2024 @10:00PM (#42373283)
Something tells me that by the end of the century only the one-time pads will still be holding their secrets.
Re:Willow, Our Quantum Chip by FredPret on Monday December 09, 2024 @10:44PM (#42373513)
Even for that to work you need a good random number generator
Re:Willow, Our Quantum Chip by adgjlsfhk1 on Monday December 09, 2024 @11:41PM (#42373825)
That's pretty trivial. xor a video camera with AES and no one is decrypting that ever.
Re:Willow, Our Quantum Chip by JKCalhoun on Tuesday December 10, 2024 @08:15AM (#42376522)
And, famously, the camera is pointing at a lava lamp, ha ha.
Re:Willow, Our Quantum Chip by JKCalhoun on Tuesday December 10, 2024 @08:14AM (#42376516)
Honestly not sure how they created one-time pads 100 years ago.
Re:Willow, Our Quantum Chip by rdtsc on Tuesday December 10, 2024 @08:54AM (#42376805)
In one case it was people just banging on typewriters randomly.
Re:Willow, Our Quantum Chip by kortilla on Tuesday December 10, 2024 @02:54AM (#42374791)
Diffie Hellman doesn’t ever send the key over the wire, that’s the point. There is nothing to decrypt in the packets that tells you the key both sides derived.

Unless they break ECDHE, it doesn’t matter if RSA gets popped.

Re:Willow, Our Quantum Chip by bsaul on Tuesday December 10, 2024 @03:55AM (#42375083)
wouldn't be surprised if ecdhe isn't quantum resistant.
Re:Willow, Our Quantum Chip by ReptileMan on Tuesday December 10, 2024 @04:47AM (#42375315)
Diffie Hellman to the best of my understanding also relies on the same hard problems that make the public key cryptography possible. If you trivialize factoring of big numbers, you break both RSA and the original DHE. Not sure how it will work for elliptic curves, but my instinct tells me that if you make the fundamental ECC problem easy, the exchange will also go down.
Re:Willow, Our Quantum Chip by Thorrez on Tuesday December 10, 2024 @09:11AM (#42376973)
According to the top image on the Wikipedia page, Diffie Hellman does send the public key over the wire.

https://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exc...

Re:Willow, Our Quantum Chip by dathery on Monday December 09, 2024 @09:06PM (#42372931)
Diffie-Hellman isn't considered to be post-quantum safe: https://en.wikipedia.org/wiki/Shor%27s_algorithm#Feasibility...
Re:Willow, Our Quantum Chip by lxgr on Monday December 09, 2024 @10:43PM (#42373507)
Forward secrecy is orthogonal to post-quantum safety.
Re:Willow, Our Quantum Chip by ramchip on Tuesday December 10, 2024 @12:34AM (#42374080)
> Forward secrecy is designed to prevent the compromise of a long-term secret key from affecting the confidentiality of past conversations. However, forward secrecy cannot defend against a successful cryptanalysis of the underlying ciphers being used, since a cryptanalysis consists of finding a way to decrypt an encrypted message without the key, and forward secrecy only protects keys, not the ciphers themselves.[8] A patient attacker can capture a conversation whose confidentiality is protected through the use of public-key cryptography and wait until the underlying cipher is broken (e.g. large quantum computers could be created which allow the discrete logarithm problem to be computed quickly). This would allow the recovery of old plaintexts even in a system employing forward secrecy.

https://en.wikipedia.org/wiki/Forward_secrecy#Attacks

Re:Willow, Our Quantum Chip by kortilla on Tuesday December 10, 2024 @02:51AM (#42374776)
I’m talking specifically about RSA being eventually broken. If just RSA is broken and you were using ECDHE for symmetric keying, then you’re fine.

The point is that you can build stuff on top of RSA today even if you expect it to be broken eventually if RSA is only for identity verification.

Re:Willow, Our Quantum Chip by minitech on Tuesday December 10, 2024 @03:20AM (#42374903)
The relevant RSA break is sufficiently powerful quantum computers, which also break ECDH (actually, ECDH is easier than classically equivalent-strength RSA for quantum computers[1]), so no, you’re not fine.

[1] https://security.stackexchange.com/questions/33069/why-is-ec...

Re:Willow, Our Quantum Chip by coppsilgold on Tuesday December 10, 2024 @04:20AM (#42375193)
I would actually expect RSA to see a resurgence due to this. Especially because you can technically scale RSA to very high levels potentially pushing the crack date to decades later than any ECC construction. With the potential that such a large quantum computer may never even arrive.

There are several choices with scaling RSA too, you can push the primes which slows generation time considerably. Or the more reasonable approach is to settle on a prime size but use multiple of them (MP-RSA). The second approach scales indefinitely. Though it would only serve a purpose if you are determined to hedge against the accepted PQC algorithms (Kyber/MLKEM, McEliece) being broken at some point.

Re:Willow, Our Quantum Chip by bwesterb on Tuesday December 10, 2024 @09:59AM (#42377465)
If you don't mind a one terabyte public key. https://eprint.iacr.org/2017/351.pdf
Re:Willow, Our Quantum Chip by adgjlsfhk1 on Tuesday December 10, 2024 @10:30AM (#42377748)
also that paper (IMO) is ridiculously conservative. Just using 1GB keys is plenty sufficient since it would require a quantum computer with a billion bits to decrypt.
Re:Willow, Our Quantum Chip by Vecr on Tuesday December 10, 2024 @12:00PM (#42378659)
How long does it take to generate a key that big? What probabilities do you need to put on generating a composite number and not a prime? Does the prime need extra properties?
Re:Willow, Our Quantum Chip by adgjlsfhk1 on Tuesday December 10, 2024 @08:59PM (#42383905)
Based on https://eprint.iacr.org/2017/351.pdf it would be about 1900 core hours (but I'm pretty sure optimized implementations could bring it down a bunch). No extra properties needed and moderate probability is sufficient.
Re:Willow, Our Quantum Chip by trogdor on Tuesday December 10, 2024 @11:28AM (#42378355)
Although I know it’s an apocryphal quote, I am reminded of “640K should be enough for anybody.”

The Intel 4004, in 1971, had only 2,250 transistors.

A handful of qubits today might become a billion sooner than you think.

Re:Willow, Our Quantum Chip by adgjlsfhk1 on Tuesday December 10, 2024 @09:18PM (#42384012)
it took until 2011 before Sandy bridge cracked 2 billion. If we get 40 years of quantum resistance from 1GB RSA, that would be pretty great.
Re:Willow, Our Quantum Chip by coppsilgold on Tuesday December 10, 2024 @04:02AM (#42375103)
Perfect forward secrecy requires the exchange of ephemeral keys. If you use either ECC or RSA for this and the traffic is captured a quantum computer will break it.

All perfect forward secrecy means is that you delete your own ephemeral private keys, the public keys stay in the record. And a quantum computer will recover the deleted private keys.

Also, none of the currently accepted post-quantum cryptographic algorithms offer a Diffie-Hellman construction. They use KEM (Key Encapsulation Mechanism).