post quantum security for 2023

[dvc94ch]

So did some research on this yesterday and this is what I came up with:

Breaking elliptic curves requires (pdf, see 6.2) roughly 6n qubits where n is the order or key size of the curve, which for Curve25519 would be 6∗255=1530. Less than secure RSA sizes require, but much more than has been accomplished. [0]

Bob Sutor, vice president of IBM Quantum Strategy and Ecosystem, said the company made a 65-qubit quantum computing system available on the cloud in September and released its quantum hardware roadmap, calling for a 127-qubit system in 2021, a 433-qubit system in 2022, and a 1,121-qubit system in 2023. [1]

This will affect especially noise/tls but also signatures in gossipsub and kademlia. There are two kinds of post quantum resistance.

1. existing communication that is stored by a powerful adversary can't be decrypted once a quantum computer becomes available

• proposed solutions include the noise hybrid forward secrecy extension [2]

2. new communications are not interceptable by an online quantum computer

• proposed solutions are being investigated by the NIST PQC competition, a likely candidate for standardization by 2022 is NTRU for key agreement

Are there any concrete plans yet for libp2p? Even if 2023 is a pessimistic target it likely won't buy us more than a year or two.

• [0] https://crypto.stackexchange.com/questions/35137/how-many-qubits-are-required-to-break-rsa-2048-or-4096-with-a-universal-quantum
• [1] https://www.techrepublic.com/article/6-experts-share-quantum-computing-predictions-for-2021/
• [2] https://github.com/noiseprotocol/noise_wiki/wiki/Hybrid-Forward-Secrecy
• [3] https://medium.com/asecuritysite-when-bob-met-alice/building-for-a-secure-future-goodbye-ecc-and-hello-to-saber-kyber-ntru-or-mceliece-or-even-3aa058d1d399

[mxinden]

Meta: As far as I can tell this is not Rust specific, right? Wouldn't https://github.com/libp2p/specs/ be a better place for this discussion?

Are there any concrete plans yet for libp2p?

I am not aware of any, though that definitely does not mean that there aren't any.

[dvc94ch]

someone pointed out to me that I was comparing apples to oranges. IBM is talking about physical qbits while computer scientists talk about logical qbits. apparently for error correction quite a few physical qbits are required to realize a logical qbit.

Wouldn't https://github.com/libp2p/specs/ be a better place for this discussion?

maybe, but I'm interested in rust-libp2p, and how it helps me solve my problems, I really don't have much interest in libp2p as a standards body.

[burdges]

Just copy whatever cipher suite TLS adopts, presumably some lattice plus elliptic curve hybrid, meaning leave arguments over lattice structure, FO under QROM, etc. to the WG's at TLS, NIST, Google, etc.

Almost all libp2p users' products die completely once quantum computers work anyways, so some lag makes no difference.

[dvc94ch]

I guess if projects would start planning for this it would not be that bad? When it comes to assessing the risk, I did the best I could without being an expert, but it may be that these estimates are way off. And predicting the future is hard even for experts I guess.

Obviously I'm not suggesting inventing our own primitives, I'm assuming that a lattice based KEM and some signature is standardized by NIST. So for now we could add those to libp2p using the c implementations submitted to nist and then kill the ones that don't make it.

When it comes to the handshake there also seems to be some hope. It seems that it is not that hard to construct an AKE using KEM + signatures, but you're the expert, just writing this in case other people are trying to follow:

Generate(Kd , Ke)
σ1 = Sig(Ke)
--> Ke, σ1
Ver(Ke, σ1)
(c, k) = Enc(Ke)
σ2 = Sig(c)
<-- c, σ2
Ver(c, σ2)
k = Dec(Kd, c)

There are even optimizations possible to this scheme [0].

• [0] https://eprint.iacr.org/2016/435.pdf

[burdges]

Google did two production experiments using Chrome and their own sites, which one could emulate of course. Ain't clear signatures shall become really viable terribly soon, but key exchanges that provide authentication work. I'm not tracking these so closely myself, but asking the mailing list is harmless.

[DemiMarie]

Google did two production experiments using Chrome and their own sites, which one could emulate of course. Ain't clear signatures shall become really viable terribly soon, but key exchanges that provide authentication work. I'm not tracking these so closely myself, but asking the mailing list is harmless.

Is the problem with SPHINCS purely that it is slow and has large signatures?

[burdges]

I think SPHINCS runs acceptably fast actually, but the signatures turn out way too large, like 40kb.

[dvc94ch]

falcon 512 has a 666 byte signature [0] and some consider it a favorite for standardization [1]

• [0] https://falcon-sign.info/
• [1] https://medium.com/asecuritysite-when-bob-met-alice/under-starters-orders-its-a-three-horse-race-dilithium-rainbow-and-falcon-but-who-will-win-530b78279b1c

[DemiMarie]

I think SPHINCS runs acceptably fast actually, but the signatures turn out way too large, like 40kb.

That they do. The reason I suggested it is because it has a proof of security under extremely conservative assumptions, and for some applications (like repository metadata signing) the large signature size is actually okay.

[DemiMarie]

falcon 512 has a 666 byte signature [0] and some consider it a favorite for standardization [1]

• [0] https://falcon-sign.info/
• [1] https://medium.com/asecuritysite-when-bob-met-alice/under-starters-orders-its-a-three-horse-race-dilithium-rainbow-and-falcon-but-who-will-win-530b78279b1c

I am not a fan of FALCON, as it is extremely tricky to implement securely.

[dvc94ch]

I am not a fan of FALCON, as it is extremely tricky to implement securely.

Because of side channels? I guess aes-gcm is hard to implement too, and the way to solve it is by implementing it in hardware. But first generation PQ crypto will certainly require some cutbacks somewhere.

[DemiMarie]

I am not a fan of FALCON, as it is extremely tricky to implement securely.

Because of side channels? I guess aes-gcm is hard to implement too, and the way to solve it is by implementing it in hardware. But first generation PQ crypto will certainly require some cutbacks somewhere.

No, because it is an inherently incredibly complex algorithm, far worse than AES-GCM. The hardest part is constant-time sampling from a discrete Gaussian distribution with a variable center. I recommend reading the FALCON paper to get an idea of how tricky this is; it is so difficult that the first version submitted by the authors was buggy.

[dvc94ch]

The hardest part is constant-time sampling

So it is a side channel problem where timing is leaked. Not sure if this particular algorithm can be implemented in hardware (that usually depends on how memory hard it is). But if it can be, it's much easier to implement it in constant-time due to hardware being inherently parallel, all paths being computed and some computation paths just being discarded. You can build fancy hardware that tries to save energy by disabling some logic circuits (clock gating) which would leak other stuff like power usage and EM radiation.

But then again I'm probably just talking out of my ass, my fpga experience is limited to implementing an RV32I.

[burdges]

I've no idea if anyone seriously proposed SPHINCS for authenticating connections in TLS. I've only really seen SPHINCS proposed for signing binary software during distribution.

[thomaseizinger]

Closing as stale and not immediately actionable.