Using the shared secret directly

[samuel-lucas6]

Hi @LoupVaillant,

In reference to Curve25519 and Curve448, RFC 7748 says:

Designers using these curves should be aware that for each public key, there are several publicly computable public keys that are equivalent to it, i.e., they produce the same shared secrets. Thus using a public key as an identifier and knowledge of a shared secret as proof of ownership (without including the public keys in the key derivation) might lead to subtle vulnerabilities.

Similarly, on the Point*scalar multiplication page of the libsodium documentation, Frank notes the following:

q represents the X coordinate of a point on the curve. As a result, the number of possible keys is limited to the group size (≈2^252), which is smaller than the key space.

For this reason, and to mitigate subtle attacks due to the fact many (p, n) pairs produce the same result, using the output of the multiplication q directly as a shared key is not recommended.

A better way to compute a shared key is h(q ‖ pk1 ‖ pk2), with pk1 and pk2 being the public keys.

By doing so, each party can prove what exact public key they intended to perform a key exchange with (for a given public key, 11 other public keys producing the same shared secret can be trivially computed).

This suggests it would be safest to have crypto_key_exchange() use BLAKE2b instead of HChaCha20 and include both public keys in the calculation of the shared key, a bit like the crypto_kx() API in libsodium. At the very least, I think it should be noted in the documentation. I will be mentioning it in my guidelines document as it's definitely something people overlook. It's something I need to change in Kryptor for v4 as well.

[LoupVaillant]

Hi,

Unfortunately, backward compatibility will prevent me from changing this. Also, I think the issues is not serious enough to warrant any bug fix. I vote for a small warning in the documentation.

Frank is right, there are many (p, n) that have the same shared secret. But each party will be using their own secret key, which leaves only one valid prime order key on the other end. That is, 8 keys total in the case of X25519, all of which matches the actual private key of the other party.

In addition, parties are supposed to authenticate the other key by simply comparing it with a list of known keys. Adding a low order component will just cause that check to fail. And that’s in cases where the key is transmitted, if the public key is known in advanced there’s no opportunity for the attacker to change it.

As far as I know, attacks on this will be extremely limited. The lack of forward secrecy is orders of magnitude more serious, though to address this properly you need something like Noise.

[samuel-lucas6]

I agree that it's not a problem in all cases, but it's definitely a sensible default step. It improves the entropy of the derived key and ensures sender authentication. It's unfortunate that the crypto_box() libsodium documentation was actually incorrect for a long time, as noted here.

Also, it sounds like it can be quite a serious issue in some cases. For example, it affected the Matrix protocol, as noted in Real-World Cryptography:

Interestingly, as I was writing chapter 10 on end-to-end encryption, I started looking into how users of the Matrix end-to-end encrypted chat protocol authenticated their communications. In order to make the verification more user-friendly, Matrix created their own variant of a SAS-based protocol. Unfortunately, it hashed the shared secret of an X25519 key exchange and did not include the public keys being exchanged in the hash.

In chapter 5, I mentioned that it is important to validate X25519 public keys. Matrix did not, and this allowed a MITM attacker to send incorrect public keys to users, forcing them to end up with the same predictable shared secret and, in turn, the same SAS. This completely broke the end-to-end encryption claim of the protocol and ended up being quickly fixed by Matrix.

[LoupVaillant]

Whoa, the Matrix bug was pretty bad, I had no idea. That said, I'm not sure how hashing the public keys could have prevented the bug: what I guess must have happened is that the MITM attacker replaced the true public key by a low order point, resulting in a shared secret of zero. If we hashed the public keys instead of just the shared secret, we get a hash of a known shared secret and… two known public keys (the recipient's and either the sender's or the MITM's, depending on how the code is written). The only way to stop this attack is to compare the public key you get against your list of contacts, and make the screen blink red if there's a mismatch. And if you do that, hashing the shared secret ought to be enough.

Still, when I design a protocol, I try to make sure that flipping a single bit anywhere causes the protocol to abort. Much easier to test that way, and it is indeed good hygiene to authenticate everything indiscriminately. Thus, your proposal of using Blake2b(shared_secret || PKa || PKb) is indeed a good idea, and we should document that option. I'm not closing this bug until we do. (Another option is to authenticate the public keys as additional data of the first AEAD message.)

I don't believe adding the public keys increases the entropy of the hash in any way: those keys are public information, presumably available to the attacker. And as long as they don't break the curve (a more or less 2^126 operation), the symmetric key has 255 bits of entropy, which is plenty. And as I've speculated above, if the shared secret is known because of attacker shenanigans, hashing the public keys won't help, the symmetric key will still end up being predictable.

[samuel-lucas6]

Yeah I haven't come across any other mention of that vulnerability, but that sounds like it could be right.

Didn't think about including them in the additional data. Would you like me to do a PR? I'm sorry for not doing one for the spelling/grammar suggestions.

That's what I thought, but Frank and a Cryptography Stack Exchange user suggest it improves the key space. It's not significant anyway if it does, as you say.

[LoupVaillant]

Would you like me to do a PR?

To update the documentation? sure! Just don't forget to add your name to the copyright information of the affected files. (And don't worry about spelling, being forced to double check was a good thing).