Curious about key exchange construction

[taylortrimble]

I noticed that for the kx construction, both public keys are added to the KDF hash. (source)

I am under the impression that the public keys are already incorporated into the derived key, in a way, by the scalarmult step. (source)

Is adding the public keys to the KDF hash done merely out of an abundance of caution, or does it prevent a concrete attack on the plain scalarmult?

Thank you for writing this package so cleanly that I can link to small pieces of the source to help ask my question. 😄

[jedisct1]

Hi,

scalarmult() does only what the name implies: it multiplies a point by a scalar on an elliptic curve.

The input and output of this function represent points coordinates (in that specific case, only the x coordinate). Even though these coordinates are encoded as 256 bits, the number of points in the group is much smaller (about 2^252).

Furthermore, the distribution of these x coordinates is not uniform. Some bits are "more random" than others. This makes related-key attacks a more serious issue on affected ciphers.

Hashing the output solves the second issue. Including public keys allows the full 2^256 key space to be used, and mitigates subtle attacks leveraging the fact that scalarmult(n, p) produces the same output for many (n, p) pairs.

While the output of the scalar multiplication can be used directly as a shared key, hashing the result is a simple and fast operation, so skipping this step is rarely justified.

crypto_kx() also takes advantage of the hash function to derives two shared keys instead of one.

[taylortrimble]

Thank you for that explanation, @jedisct1. I found this part most surprising:

Including public keys allows the full 2^256 key space to be used, and mitigates subtle attacks leveraging the fact that scalarmult(n, p) produces the same output for many (n, p) pairs.

Since box does not include the public keys in its HSALSA20 key derivation, is its security level affected by the subtle attack you mentioned?

[jedisct1]

Yes. Namely, you can't rely on public keys to ensure that you're talking to the intended recipient. This is not an issue in properly designed protocols.

[taylortrimble]

This is surprising to me. The documentation on the box page of libsodium.org says:

Using Bob's public key, Alice can verify that the encrypted message was actually created by Bob and was not tampered with, before eventually decrypting it.

And also:

This system provides mutual authentication.

So I feel like there is a contradiction. Are we perhaps talking about 2 subtly different guarantees?

Thank you very much for your help in this.

[jedisct1]

That documentation page is terrible and should be rewritten at some point.

Messages sent using crypto_box cannot be tampered with without knowing the shared secret key. And knowing that shared secret key allows to verify that an authentication tag was produced by a party that knows that shared secret key. Which includes the verifier itself. The message is authenticated, not the sender.

[taylortrimble]

I see your point about the wording of that documentation. It can be read to imply box gives non-repudiation when it only gives authentication. That's not quite what I'm wondering, about, however.

It seems kx and box both derive a shared secret (which kx later expands into 2 shared keys, which is useful, but not the point of the question here). However, kx arrives at its shared secret(s) by roughly the process of Hash(scalarmult_result, client_pk, server_pk), whereas box arrives at its shared secret via roughy Hash(scalarmult_result).

So as a table, it would look like:

	Guarantee	Shared Secret Derivation	Hash in use	Authentication security level
kx + secretbox	Authenticated encryption	Hash(scalarmult_result, client_pk, server_pk)	BLAKE2b	128-bit
box	Authenticated encryption	Hash(scalarmult_result)	HChaCha	128-bit?

It seems like here you might be trying to say that box is not sufficient for authentication at a high security level, due to pitfalls of scalarmult, and that kx + secretbox is constructed in such a way to avoid this pitfall by including the public keys in the hash.

What I'm struggling to understand is how that can be true without undermining the authenticated encryption guarantees of box.

Hopefully I finally get it this time. :) Thank you much for your patience.

[jedisct1]

x25519 security is < 126 bits since the order of the main subgroup is ~ 2^252. H(skb.pka) doesn't improve this. H(skb.pka || pka || pkb) does.

It doesn't make any practical difference.

Given pka, one can compute pkc so that H(skb.pkc) = H(skb.pka). One cannot compute pkc so that H(pka || skb.pkc) = H(pka || skb.pka). For virtually all protocols, this is not a big deal. But it's not far fetched to think that there are some for which this is a concern. Which could have been trivially addressed by adding the peer's public key to the input of the hash function.

Not including that key, as in box is fine. If your application is currently using box, this is fine.

[taylortrimble]

Whoa, I finally get it! 🎉

Thank you!

I was even able to take your example and find reference to it in RFC 7748 Section 7. Very cool. I'll have some fun coming up with an example system that is vulnerable like this.

Thanks again! Keep up the great work!