4
$\begingroup$

I was looking at the LibSodium documentation where it says

[...] and to mitigate subtle attacks due to the fact many $(p, n)$ [public key - secret scalar] 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 \mathbin\| pk1 \mathbin\| pk2)$, with $pk1$ and $pk2$ being the public keys.

My questions are as follows:

  • What is the chance for two $(p, n)$ pairs to produce the same result? (is it for example worse than the chance of two 252-bit random numbers being equal?)
  • What are the subtle attacks mentioned and how does $h(q \mathbin\| pk1 \mathbin\| pk2)$ defend against them?

I noticed that NaCl in crypto_box/curve25519xsalsa20poly1305/ref/before.c simply hashes the secret without the public keys. So I presume that not following said advice can't be that bad.

$\endgroup$
  • $\begingroup$ Possible duplicate of crypto.stackexchange.com/questions/73138/… $\endgroup$ – Frank Denis Nov 27 '19 at 11:54
  • $\begingroup$ Said question asks if there keys that produce the same shared secret, not how many there are and does not mention anything about the "subtle attacks". $\endgroup$ – Bob Semple Nov 27 '19 at 12:32
  • $\begingroup$ There are about $2^{255} - 2^{252}$ points that are not legitimate public keys, and if you rely on the identity of the public key but only hash the shared secret then an adversary might use one of the illegitimate public keys to confuse you. In general, you should always authenticate the complete transcript of a handshake by hashing it all in so there is no leeway for an adversary to modify it. $\endgroup$ – Squeamish Ossifrage Nov 27 '19 at 15:07
  • $\begingroup$ @SqueamishOssifrage Could you please elaborate? How could they confuse me? What do you mean by the "identity of the public key"? A specific example would be appreciated. Thanks in advance. $\endgroup$ – Bob Semple Nov 27 '19 at 23:03
  • $\begingroup$ You get the same shared secret with two different ‘public keys’, which might be surprising. I don't know of a specific example of a protocol that relies on the identity of DH public key this way, but Monero was bitten by a similar mistake a couple years ago, and some Bitcoin systems have been bitten by assuming that one valid signature can't be transformed into another valid signature or ‘transaction malleability’. $\endgroup$ – Squeamish Ossifrage Nov 27 '19 at 23:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.