Tracking issue for RFC 685

kim commented 3 years ago

RFC PR: #685

[ ] evaluate stability of quinn-noise / ipfs-embed
[ ] evaluate status of QUIC version negotiation
[ ] protocol changes (TBD)

kim commented 3 years ago

https://github.com/ipfs-rust/quinn-noise/issues/2

kim commented 3 years ago

https://github.com/libp2p/specs/pull/351 https://github.com/libp2p/specs/issues/315

(tld;dr libp2p engineers are terrified :rofl:)

dvc94ch commented 3 years ago

Well, I don't think there is going to be a spec anytime soon, not sure if that is a deal breaker for you. However if you are using rust-libp2p I'd recommend using tcp/noise/yamux as that works with the relay and hole punching that will (hopefully) land soon and swallow the multiple roundtrips required to establish a connection. Let me know if there is anything I can help you with in regards to quinn-noise/ipfs-embed, radicle looks like a very interesting project.

kim commented 3 years ago

Thanks @dvc94ch.

We considered (rust-)libp2p early on, but it didn't pull its weight for what we wanted to do. In that sense it does not matter much whether there is a libp2p spec or not -- although we obviously benefit from whatever libp2p standardises on, if only because that means it received peer review.

However, since crypto is "baked in" to QUIC and not something that's added on top, it is unclear why libp2p / Protocol Labs should be standardising QUIC+Noise and not the IETF / QUIC-WG. I believe @marten-seemann's comment amounts to the same, although I can't infer whether or not he would see value in a QUIC+Noise standard.

I remember @djc mentioning elsewhere that alternatives to TLS were considered in the WG, and now that the base specs are final there might be interest in reviving a Noise specification effort. I don't know, however, how one would get involved in that process when one is not knowledgeable enough to actually write the spec :)

Perhaps the people mentioned would be willing to chime in?

marten-seemann commented 3 years ago

However, since crypto is "baked in" to QUIC and not something that's added on top, it is unclear why libp2p / Protocol Labs should be standardising QUIC+Noise and not the IETF / QUIC-WG. I believe @marten-seemann's comment amounts to the same, although I can't infer whether or not he would see value in a QUIC+Noise standard.

Having been an active member of the IETF QUIC working group since the beginning (late 2016), I'd say having this standardized in the IETF be the ideal situation. For protocol standardization, it's always best to have multiple players with vastly different use cases, if your intention is to specify a protocol that can be applied to a wide range of use cases. The problem here could be that most of the big players (at least those using QUIC on the web) will be quite happy with TLS 1.3. For the record, I'd be quite happy if there was a Noise+QUIC spec.

At the moment I'm not aware of any attempts to standardize Noise+QUIC, currently people are pretty busy building protocols on top of QUIC, for example MASQUE and WebTransport, as well as defining QUIC extensions, for example Version Negotiation, ACK frequency and various others.

I don't know, however, how one would get involved in that process when one is not knowledgeable enough to actually write the spec :)

The easiest way would be join the QUIC working group Slack channel, and ask around there. Most important is to find other people who're interested in putting in the effort to write an implementation (and a spec).

djc commented 3 years ago

See the QUIC WG mailing list thread on Noise: https://mailarchive.ietf.org/arch/msg/quic/iqkxQcb5pTtFA33aS6jwvwUPChY/.

I wonder to what extent having Noise itself specified at the IETF would be a prerequisite to standardizing Noise + QUIC.

However, since crypto is "baked in" to QUIC and not something that's added on top

Not sure I agree with this sentiment. The QUIC tls spec is a separate document for a reason -- as far as I can tell, QUIC has been intended to abstract over the implementation of the confidentiality/integrity protocol for a long time.

kim commented 3 years ago

having Noise itself specified at the IETF would be a prerequisite

Ohhh...

QUIC has been intended to abstract over the implementation of the confidentiality/integrity protocol

Yes sure, what I was trying to express was that the way QUIC defines how it can be extended with crypto protocols is on a layer that libp2p should not need to concern itself with -- unless it would want to implement a less general protocol (which I'm not sure why they would want that). I think it's also fair to say that the transport-level primitives cater very much for TLS, which appears to make things more complicated for Noise specifically (by contrast, just layering a Noise state machine over plain TCP streams is almost trivial).

Everytime this topic comes up, I have people expressing interest, but noone has stepped up yet to say that they would be willing the help make it happen. I'm not sure if I just haven't met the right people, or if it's indeed a matter of resources. Otoh, non-web focused organisations exist which could support this: PL, web3, and of course the Radicle Foundation.

I guess I'll try the Slack route (thanks for the suggestion), or ask on the mailing list. It would be a shame if @dvc94ch's initiative would fizzle, like nQUIC did.

dvc94ch commented 3 years ago

just my 2 cents on the topic of security. I've been looking into what is involved in the libp2p quic tls specification again. While maybe it is secure in theory, bugs are proportional to the number of lines of code. adding tls in the libp2p flavor involves pulling in thousands of loc from more or less trusted and maintained sources. also there is the shear complexity of it. so I'm not convinced that the libp2p tls spec results in more security. Implementing my proposal, if you like it or not for whatever reason, is just a few hundred lines of code which can be easily audited.

kim commented 3 years ago

@dvc94ch I tend to agree -- modulo the Xoodyak stuff, which I haven't had the time yet to even read the paper, it is all very straightforward and most likely good enough(tm) for what radicle-link would require.

My concerns are these:

Can we get a cryptographer to confirm that this is sound?
How can we migrate an existing network from TLS to Noise? (answer: probably not, unless we have Version Negotiation)
In case a standard emerges, or quinn-noise changes in some incompatible way, how to we migrate? (answer: probably not, unless we have Version Negotiation)

dvc94ch commented 3 years ago

Can we get a cryptographer to confirm that this is sound?

I did the best I could on that one [0], but I don't have the money to pay for a proper audit. I don't even know what something like that would cost.

How can we migrate an existing network from TLS to Noise?

The current intention would be to support both. Try version a, if that fails, try version b. And at some point deprecate version b. Some work in that area was done here [1], but not sure if it is sufficient for a smooth transition.

modulo the Xoodyak stuff

With a little bit of effort something closer to noise could be designed. But it is not immediately obvious how to derive keys for an external cipher during the handshake (at least in code that is supposed to be generic over the handshake). Once the handshake is complete, you have data keys that can be used with any cipher.

I guess the handshake state could be used as the seed for a csprng to extract some keys.

dvc94ch commented 3 years ago

I did the best I could on that one

I guess that isn't true. I'll ask on the noise mailing list what they think about it and if someone is interested in performing a thorough security audit + what it would cost.

dvc94ch commented 3 years ago

I guess the handshake state could be used as the seed for a csprng to extract some keys. So would be something like this:

csprng(hash(old_state || kdf(new_state)))

If this is what makes people comfortable with it and there is interest in using it, I can implement it.

cloudhead commented 3 years ago

@dvc94ch keep us updated, we'd be open to funding this effort.

djc commented 3 years ago

With a little bit of effort something closer to noise could be designed. But it is not immediately obvious how to derive keys for an external cipher during the handshake (at least in code that is supposed to be generic over the handshake). Once the handshake is complete, you have data keys that can be used with any cipher.

Can you explain again why you think snow doesn't provide what you need? The key derivation on the TLS side does not seem very complex to me, and I didn't quite understand what you wrote in https://github.com/libp2p/specs/pull/351#issuecomment-883077533:

One of them is that snow provides no api for adding associated data to a message which itself would not be that hard to add [1]. Another one is that a quic packet may have multiple frames. To let noise do it's thing you'd need to add the other frames as a payload to the (encrypted) crypto frame. Safely extracting keys from the noise state that could be used for packet protection is indeed something that would require some security analysis beyond what I can do. What I can do is pick something and use it how it was intended to be used. Since xoodyak is being used the way it was designed to I'm pretty confident that this is fine.

Going from the established crypto + protocol in TLS to a completely new implementation using a competition candidate algorithm seems like a big step back in maturity. Since QUIC + Noise is itself fairly novel, I'd recommend sticking with trusted implementations/algorithms as far as possible and seeking minimal extensions where it's not.

dvc94ch commented 3 years ago

Can you explain again why you think snow doesn't provide what you need?

There is an impedance missmatch between the quinn/snow api's. A clear example is that there is no support for providing the header as associated data when encrypting the packet in snow. The rest is a bit more subtle, but it certainly was hammering something that doesn't fit.

The key derivation on the TLS side does not seem very complex to me,

well, tls required quite a bit of contortion to make it fit quic too from what I understand. There is a reason why rustls requires the dangerous-configuration feature to get it working and why rustls contains special "quic" code. Let's be fair here, stuff designed for tcp doesn't quite fit quic, even if it is possible to make it fit.

Going from the established crypto + protocol in TLS to a completely new implementation using a competition candidate algorithm seems like a big step back in maturity.

just pointing out the list of dependencies required to make quic + tls work: barebones-x509, quinn-proto/tls-rustls, rcgen, ring, rustls, untrusted, webpki, yasna

compiling libp2p-quic with the noise feature flag has 243 dependencies while compiling it with the tls feature flag has 250 dependencies, which I must admit is not as dramatic as I expected. But it's still a non-negligable amount of code. it's also worth pointing out that snow hasn't been audited either.

Quoting from the NIST finalist selection report published on the 21 july, maybe we should wait for 12 months and see if NIST decides to standardize it.

Security Analysis. The designers of Xoodoo provide bounds on differential and linear trails, as well as a preliminary security analysis on the permutation. Song and Guo [234] demon- strated a cube-like attack on Xoodoo-AE reduced to six (out of 12) rounds in 289 time and 255 memory. Zhou et al. [235] also presented a conditional cube attack on Xoodyak re- duced to six (out of 12) rounds in a nonce-misuse setting, recovering the 128-bit key in 243.8 time and negligible memory cost. Liu et al. [236] showed a zero-sum distinguisher on the full 12-round Xoodoo, with 233 time complexity and Liu et al. [213] identified a 4-round rotational differential-linear distinguisher with correlation one on Xoodoo with a probability 2−117.81 . Tweak plan. The submitters have indicated that they plan to make a tweak that will improve speed for short messages [28].

No clue what a zero-sum distinguisher is or a 4-round rotational differential-linear distinguisher is.

djc commented 3 years ago

well, tls required quite a bit of contortion to make it fit quic too from what I understand. There is a reason why rustls requires the dangerous-configuration feature to get it working and why rustls contains special "quic" code. Let's be fair here, stuff designed for tcp doesn't quite fit quic, even if it is possible to make it fit.

At the protocol level the QUIC/TLS interaction different is quite different from TCP/TLS, and a bunch of experts spent a good amount of time thinking about how to make that work. This is why there is a separate QUIC API in rustls; the QUIC support does not itself require the use of dangerous_configuration-gated features. But my remark was about the key derivation in particular, for which QUIC pretty much just uses the TLS 1.3 standard's use of HKDF with different labels, which is pretty straightforward.

just pointing out the list of dependencies required to make quic + tls work: barebones-x509, quinn-proto/tls-rustls, rcgen, ring, rustls, untrusted, webpki, yasna

To be fair, the QUIC/TLS interaction just requires quinn-proto, rustls and ring (which in turn pull in webpki and untrusted). All the other stuff is about a different aspect of this implementation, the use of non-PKI certificates, which you would still need if you wanted to do TLS over TCP for libp2p scenarios. (And with snow you might also use ring and untrusted, so the difference is even smaller.)

it's also worth pointing out that snow hasn't been audited either.

Yes, but maturity is not a binary state. And it looks libp2p already has a libp2p-noise implementation, so it seems sensible to reuse that existing code rather than bifurcating efforts across different implementations.

dvc94ch commented 3 years ago

But my remark was about the key derivation in particular, for which QUIC pretty much just uses the TLS 1.3 standard's use of HKDF with different labels, which is pretty straightforward.

Oh is csprng(hash(old_state || kdf(new_state))) what made you think I was talking about tls? I really don't know much about tls. This part hash(old_state || kdf(new_state)) was a summary of what noise does. The new_state would be an e es etc component being added to the session transcript.

dvc94ch commented 3 years ago

looks libp2p already has a libp2p-noise implementation

that one doesn't support 0-rtt encryption. It also doesn't really make sense to add as you have a large amount of roundtrips anyway. tcp handshake then negotiating noise using multistream-select, then the noise handshake, then negotiating the muxer, and then negotiating the application protocol on a substream.

dvc94ch commented 3 years ago

Another change to consider is replacing xoodyak with strobe. That would be almost a 1:1 primitive swap. strobe is used in ed25519-dalek for some advanced features, in bulletproofs and in schnorrkel.

dvc94ch commented 3 years ago

But to be honest, I'd like to just get a reasonable libp2p quic implementation so that I can focus on other problems. Like adding support for the nymtech mixnet to libp2p, testing the relay/hole punching, improving blake-streams which I think is pretty cool.

dvc94ch commented 3 years ago

Anyway, in 2023 quinn-noise (and tls) will be irreparably broken. So I don't think it's worth having a security audit, I'm sure it's good enough till 2023.

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.

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

kim commented 3 years ago

https://github.com/noiseprotocol/noise_wiki/wiki/Post-Quantum-Noise-with-SIDHp751

dvc94ch commented 3 years ago

It's not quite as easy as just replacing ecdh with sidh. One issue is this one which I don't fully understand, quoting from the document you linked and also matching what I've read in other places:

Note: the paper describes an ephemeral Diffie-Hellman key exchange. It is insecure to use it as is with static keys.

and this one:

Because SIDHp751 uses different primitives for Alice and Bob, Noise implementations must generate static keypairs differently depending upon whether the party will be the initiator or the responder. If the party could perform either role then two sets of static keypairs will need to be generated ahead of time, with the specific keypair chosen when the handshake is started.

which I'm not sure if it fixes the first one, but means that quite a few assumptions are broken in libp2p:

that a single peer_id or public key identifies a peer
the assumption of quinn-noise that the peer-id can embed the public key instead of the hash of the key

and probably others

one option to fix that might be using an NN handshake and authenticating the peer via a signing key and a signature. but a post quantum secure signature scheme would need to be selected too. in any case the result would certainly need a version bump of quinn-noise, that's for sure.

dvc94ch commented 3 years ago

if we are serious about PQC we should find a protocol that isn't based on dh but on KEM and signatures, as SIDH, SIKE and other supersingular isogeny based crypto won't be standardized for a while. would need to spend some time consulting the literature, I don't think [0] is exactly what we want, but goes in the right direction. If it has a universal composability proof we should be able to plug in anything that NIST standardizes in 2022.

[0] https://www.researchgate.net/publication/220234877_A_Universally_Composable_Secure_Channel_Based_on_the_KEM-DEM_Framework

dvc94ch commented 3 years ago

Not that hard to construct an AKE using KEM + signatures

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]. This would allow peer-id's to only contain the hash of the public key if the public key is sent with the second message.

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

kim commented 3 years ago

Yeah afaik KEMs have also been proposed for WireGuard, which afaiu requires a PSK and/or out-of-band exchange of static keys.

I can not, however, see the urgency of a PQ resistant handshake in open ("permissionless") peer-to-peer networks: identities are not effectively hidden, nor are they trusted. I would think that there are cheaper attacks. More impactful would be to ensure PQ data integrity, ie. a suitable signature scheme. I believe the NIST winner is due to be announced later this year.

dvc94ch commented 3 years ago

identities are not effectively hidden, nor are they trusted

That's a good point that in some cases it won't matter. However let's say you configure some bootstrap nodes in a dht, you probably don't want anyone to be able to claim they're the node you're trying to contact. It's also not a good idea to provide the user with an abstraction that puts the burden on the user.

Let's forget online attacks for now. The question is can someone record an encrypted communication and in 2023 rent an IBM cloud QC to find the shared secret and decrypt it, which at the moment is yes.

alexjg commented 3 years ago

One note on the IBM quantum roadmap. I'm pretty sure the number of qubits they are referring to are physical qubits, they'll still be several orders of magnitude away from 1500 logical qubits.

dvc94ch commented 3 years ago

that does sound reassuring, didn't realize I was comparing apples to oranges. so I guess we can wait a few years. thanks!

dignifiedquire commented 1 year ago

Fyi it is 2023, and I believe we are still fine 😅 Though I still could use a security audit for quic + noise

radicle-dev / radicle-link

Tracking issue for RFC 685 #701