libsodium's Curve25519 point validation conflicts with Noise's approach

[mcginty]

This is a continuation of the conversation started on #75.

Summary

libsodium has made the decision to try to prevent accidental foot-shooting by refusing to do DH operations on points that are clearly not securely randomly generated.

Noise has taken the approach of not validating keys at all, since it's impossible to definitively say that a point is safe, so it creates a false sense of security.

libsodium has a blacklist it maintains for low-order GroupElement points, and returns an error if encountered.

Workarounds

For snow, the two options are either to:

1. Respect libsodium's decisions and document its divergent behavior and its effects on compatibility with Noise.
2. Workaround their limitations by copying their blacklist and evading the failure by simply returning all-zero results in those cases. This may be kind of flimsy if libsodium ever decides to get more adventurous with their blacklist and we're forced to play that game.

[tarcieri]

Is it currently panicking here?

https://github.com/mcginty/snow/blob/1408112/src/resolvers/libsodium.rs#L110

let pubkey = sodium_curve25519::GroupElement::from_slice(&pubkey[0..32])
            .expect("Can't construct public key for Dh25519");

Looking at the Dh trait, it seems it’s already equipped to return a Result, so I think the most straightforward thing to do is your proposed option 1: propagate this error from libsodium by changing that expect to a ?.

You could implement option 2 without copying the blacklist from libsodium by returning Ok([0u8; 32]) in the event of a point validation error, which would per the current libsodium blacklist provide the same behavior as X25519 without point validation (i.e. multiplying any of the blacklisted points by any scalar value results in 0).

It’s a six of one, half dozen of another to me: there’s no legitimate reason for these points to ever be a used as a public key and doing so is a sort of self-inflicted plaintext recovery attack. Noise would catch an attacker swapping a legitimate public key for one of these as a MAC verification failure, although given the current use of expect it seems this might presently be a DoS attack vector (via a panic) until fixed?

[mcginty]

@tarcieri it errors at the DH calculation which does properly return an Err, not the GroupElement construction. That said, this should return a Result too, so I'll fix that. I don't think this expect() is a DoS attack vector, since snow checks the provided public key lengths earlier in the process of doing the handshake.

[mcginty]

My concern about the workaround of always returning a [0u8; 32] on libsodium failure is if the library ever introduced another failure case that's not related to providing a low-order point, then we'll fail-open instead of fail-safe, which seems flimsy. I also have no interest in maintaining a copy of libsodium's blacklisted points, so I feel like the safest choice with very little practical side-effect is to add a caveat about libsodium's compatibility issue and keep it at that.

[tarcieri]

I don't think this expect() is a DoS attack vector, since snow checks the provided public key lengths earlier in the process of doing the handshake.

Where does point validation occur in sodiumoxide? If it fails during scalar mult, then I think the current implementation is fine.

My concern about the workaround of always returning a [0u8; 32] on libsodium failure is if the library ever introduced another failure case that's not related to providing a low-order point, then we'll fail-open instead of fail-safe, which seems flimsy.

Since the Noise handshake cryptographically binds all parameters ala a transcript hash, any discrepancies on either side will result in a MAC verification failure, so getting anything wrong will automatically fail closed.

That said, I'd agree failing closed early on a point validation failure feels safer to me.

[mcginty]

Where does point validation occur in sodiumoxide? If it fails during scalar mult, then I think the current implementation is fine.

I agree that it's kind of... counterintuitive, but libsodium (and sodiumoxide) do the low-order check in the scalarmult function.

So, it sounds like the safe option here is to fail closed. I'll keep it this way unless there's a compelling real-world issue that justifies a more sketchy workaround.