Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|improve this question
    
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. – SEJPM Sep 21 '15 at 18:39
    
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). – otus Sep 21 '15 at 19:26
    
@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! – Galaxyquest Sep 21 '15 at 19:41
    
@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! – Galaxyquest Sep 21 '15 at 19:46
    
@Galaxyquest, sorry, I meant step 3 indeed. – otus Sep 21 '15 at 20:26

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.

share|improve this answer
    
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. – Galaxyquest Sep 22 '15 at 20:50
    
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. – Galaxyquest Sep 22 '15 at 20:50
    
@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. – otus Sep 23 '15 at 6:02
    
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. – Galaxyquest Sep 23 '15 at 11:58
    
@Galaxyquest, in the TLS triple handshake attack on Diffie–Hellman the attacker needs to be able to choose the group. Here you are doing it on a particular elliptic curve, so unless you allow negotiation of arbitrary curves you should avoid anything similar (the attack also requires other TLS peculiarities). I don't know the reason for the libsodium advice, but maybe I'm missing something. – otus Sep 23 '15 at 13:15

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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