6
$\begingroup$

The question is whether the following simple key agreement protocol design has good security properties, and how it can or should be improved.

Assumptions

  1. Alice is a persistent entity with a static and well-known public key.

  2. Bob is a transient anonymous party who would like to exchange some private information with Alice over the public Internet in a session of short duration (less than an hour), in a way that is forward-secure (has the forward secrecy or PFS property).

  3. Bob has a good copy of Alice's static public key.

  4. Bob must authenticate Alice, but Alice need not authenticate Bob.

  5. All key and ECDH operations use Curve25519 or another SafeCurve.

  6. The final shared secret that is the outcome of the protocol will be used to secure the data transfer between Alice and Bob (which takes place with a separate protocol) by serving as the key to an Encrypt-then-MAC authenticated encryption (AE) procedure (for example, XSalsa20/Poly1305) that also requires a unique-per-(key, message) nonce as input.

  7. The transport protocol is message-based (not TCP), and protocols such as TLS and DTLS are not applicable.

It is well known that using mature and battle-tested key exchange protocols is usually the right answer, so pointing this out is unnecessary. Useful answers will provide specifics as to any problems with this protocol and, especially, how they can be corrected.

Protocol

  1. Bob generates an ephemeral (private, public) keypair (b, B).

  2. Bob computes the DH shared secret X using his private key and Alice's static public key A, and then K(X), the result of applying an appropriate key derivation function (KDF) to the combination of A, B, and X.

  3. Bob initiates communication with Alice by sending her a (cleartext) message that contains some fixed protocol information such as a magic number and version, and a copy of Bob's public key B.

  4. Alice receives the message and computes the DH shared secret X using her static private key a and the public key B that Bob sent. She then computes K(X) as Bob did.

  5. Alice generates an ephemeral (private, public) keypair (e, E).

  6. Alice generates a unique nonce N0 and the ciphertext C that results from applying AE with nonce N0 and key K(X) to her ephemeral public key E. She then sends N0 and C to Bob.

  7. Bob receives the message and authenticates/decrypts it with AE using the nonce N0 sent in the message and key K(X).

  8. Both Alice and Bob compute the DH shared secret Y using their ephemeral keys (e, E) and (b, B), and then K(Y), the result of applying the KDF to the combination of E, K(X), and Y. The values X, K(X), and Y are discarded.

  9. At this point the protocol is complete, and data transfer is carried out separately using AE with key K(Y) and a unique nonce sent in the clear with each message. When the session is finished, the ephemeral keys (b, B), (e, E), and K(Y) are discarded.

Improve this question
$\endgroup$
8
  • $\begingroup$ In 2): Don't use a straight hash, use a function specifically made for this task: a key-based key derivation function such as HKDF. $\endgroup$
    – SEJPM
    Sep 21, 2015 at 18:39
  • $\begingroup$ Is the message in step 2. sent in the clear? This all seems needlessly complicated if you are using NaCl (with your choice of primitives you probably should). $\endgroup$
    – otus
    Sep 21, 2015 at 19:26
  • $\begingroup$ @SEJPM Thanks, edited to specify the use of a KDF instead of a generic hash function. If you have recommendations on a particularly suitable KDF and how to use it in this step, that would be helpful! $\endgroup$
    – Galaxyquest
    Sep 21, 2015 at 19:41
  • $\begingroup$ @otus Step 2 is a computation step. The message in Step 3 is sent in the clear. I don't see why the procedure is "needlessly complicated" - if you can suggest specific simplifications that are applicable to this scenario and that wouldn't harm security, that would be helpful! $\endgroup$
    – Galaxyquest
    Sep 21, 2015 at 19:46
  • $\begingroup$ @Galaxyquest, sorry, I meant step 3 indeed. $\endgroup$
    – otus
    Sep 21, 2015 at 20:26

1 Answer 1

Reset to default
3
$\begingroup$

The protocol seems secure. Some comments below.

  1. Bob computes the DH shared secret X using his private key and Alice's static public key, and then K(X), the result of applying an appropriate key derivation function (KDF) to the combination of A, B, and X.

The DH secret X already depends on both key-pairs. Including the public keys in key derivation does not seem to add security.

(Also, in practice Bob should calculate X after sending the ephemeral key to Alice, while waiting for reply, so it is not part of the critical path.)

  1. Both Alice and Bob compute the DH shared secret Y using their ephemeral keys (e, E) and (b, B), and K(Y), the result of applying the KDF to the combination of E, K(X), and Y. The values X, K(X), and Y are discarded.

Again, the inclusion of anything but Y in key derivation seems unnecessary.

  1. [...] When the session is finished, the ephemeral keys (b, B), (e, E), and K(Y) are discarded.

The ephemeral key-pairs (b, B) and (e, E) can be discarded already in step 8 after Y is calculated. Unless you use them for something else, in which case you need to look at how that might interact with the protocol.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Thanks for your answer! I believe your statement that including additional contextual data, such as the public keys, in the KDF input is not correct. Apparently there are known attacks that can be carried out if this is not done (in which an attacker with a different key can end up with the same shared secret as the genuine parties), and so the recommended practice these days seems to be to include at least the public keys in the KDF computation, and perhaps also additional context information such as protocol parameters and nonce values. $\endgroup$
    – Galaxyquest
    Sep 22, 2015 at 20:50
  • $\begingroup$ For example, the Diffie-Hellman chapter of the libsodium documentation explicitly advises hashing the DH shared secret with the public keys rather than using it directly. $\endgroup$
    – Galaxyquest
    Sep 22, 2015 at 20:50
  • $\begingroup$ @Galaxyquest, if you know of any such attacks, please link. Including context information is a good idea if you need to derive several different keys from it. If someone could end up with the same shared secret, they could just derive the same key even if you include the public keys (which are, after all, public). If you look at how libsodium crypto_box works, the key derivation does not include public keys or nonces, just the shared secret and some constants. $\endgroup$
    – otus
    Sep 23, 2015 at 6:02
  • $\begingroup$ The only such attack I've been able to find details of is TLS Triple Handshake. It seems that can compromise DH, but I'm unsure whether it (or something similar) would affect a protocol like the one in this question. In surveying other protocols, implementations and commentary I almost always see additional material included in the KDF. Do you know why the libsodium docs state: Instead of directly using the output of the multiplication q as a shared key, it is recommended to use h(q || pk1 || pk2), with pk1 and pk2 being the public keys. $\endgroup$
    – Galaxyquest
    Sep 23, 2015 at 11:58
  • 1
    $\begingroup$ Adding to what @mlpo said, if you had a system where public keys were used as identifiers, and knowledge of the shared secret was used to prove ownership of that identity, then (if you do not include the public keys in the KDF) an attacker can take your proof of identity and swap the public key identifier for a different (computable) one that would produce the same shared secret (same x-value, different y): same proof, different identifiers. It's an obscure case (bad protocol), but easy to avoid this ambiguity in the first place by include the public keys in the key derivation. $\endgroup$
    – Neil Madden
    May 10, 2017 at 15:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.