@ Loup's

Impossible? Like that would stop me.

XCKDF: X25519 Chacha20 Key Derivation Function

We describe here a way to derive keys from X25519 shared secrets, using nothing but the Chacha20 stream cipher (and its related hash HChacha20).

This is a cascading scheme, intended to be used with up to 4 levels (we could go beyond, but the protocols I intend to use it for don't go beyond 4 key exchanges).

   DH1       DH2       DH3       DH4
  ┌─┴─┐     ┌─┴─┐     ┌─┴─┐     ┌─┴─┐
0╶┤ H │   0╶┤ H │   0╶┤ H │   0╶┤ H │
  └─┬─┘     └─┬─┘     └─┬─┘     └─┬─┘
    │   ┌────╴+   ┌────╴+   ┌────╴+
  ┌─┴─┐ │   ┌─┴─┐ │   ┌─┴─┐ │   ┌─┴─┐
p╶┤ H │ │ p╶┤ H │ │ p╶┤ H │ │ p╶┤ H │
  └─┬─┘ │   └─┬─┘ │   └─┬─┘ │   └─┬─┘
  ┌─┴─┐ │   ┌─┴─┐ │   ┌─┴─┐ │   ┌─┴─┐
1╶┤ C ├─┘ 1╶┤ C ├─┘ 1╶┤ C ├─┘ 1╶┤ C │
  └┬┬┬┘     └┬┬┬┘     └┬┬┬┘     └┬┬┬┘
   ││└╴AK1   ││└╴AK2   ││└╴AK3   ││└╴AK4
   │└╴EK1    │└╴EK2    │└╴EK3    │└╴EK4
   └╴PK1     └╴PK2     └╴PK3     └╴PK4

DH1, DH2, DH3, and DH4, are X25519 shared secrets. "+" means XOR, and p is an arbitrary constant (typically the protocol name, used for domain separation) The boxes mean the following:

input╶┤ H │       out = HChacha20(key, input)

      ┌─┴─┐       out1 = Chacha20(key, nonce)[ 0: 31]
nonce╶┤ C ├╴out1  out2 = Chacha20(key, nonce)[32: 63]
      └┬┬┬┘       out3 = Chacha20(key, nonce)[64: 95]
       ││└╴out2   out4 = Chacha20(key, nonce)[96:127]

Keys span 32 bytes. The HChacha20 input spans 16 bytes. All outputs span 32 bytes. Chacha20 technically outputs a stream, we just divide the first 128 bytes of that stream among the four outputs.

Security Goals

Being a "random string" means being indistinguishable from uniform random string in a feasible amount of computation. Being "secure" for a DH shared secret means the private keys involved in the key exchange are independent random strings, unknown to anyone but their rightful owner.

Analysis of a single stage

A single stage of the cascade looks like this:

         DH      (1) hash_s  = HChacha20(DH, 0)
        ┌─┴─┐    (2) x       = CK_prev XOR hash_s
      0╶┤ H │    (3) hash_x  = HChacha20(x, p)
        └─┬─┘    (4) CK_next = Chacha20(hash_x, 1)[ 0: 31]
CK_prev╶─╴+      (5) AK      = Chacha20(hash_x, 1)[32: 63]
        ┌─┴─┐    (6) EK      = Chacha20(hash_x, 1)[64: 95]
      p╶┤ H │    (7) PK      = Chacha20(hash_x, 1)[96:127]
      1╶┤ C ├╴CK_next

The security goals of a single step are:


Preliminary lemmas

Induction lemmas

Analysis of the whole chain

Notes: CK_prev(0) is zero. CK_next(n) = CK_prev(n+1) for all n > 0.


Design rationale

This key derivation is intended to be used in protocols that already rely on Chacha20 for encryption. Using it instead of an actual hash saves a primitive, allowing implementations to be simpler and smaller.

All output keys are, when secure, independent random strings. This independence is important because:

The intermediate HChacha20 call with p has been added to provide domain separation across protocols, even if users end up reusing keys between protocols. This can happen if users perform an exchanges between their long term keys, or if they (misguidedly) reuse an ephemeral key for several protocols to save key exchanges during a protocol negotiation. Users who don't need such domain separation could arguably remove it, and save a tiny bit of computation in the process. I personally think the flexibility is worth the cost.

The call to Chacha20 has a nonce of 1, to avoid collision with the HChacha20 of the DH key exchanges, even if the attacker controls one an knows the other. For instance, an attacker knowing the value of DH1 and having control over DH2 could have DH2 be HChacha20(HChacha20(DH1, 0), p), Causing half of CK_prev(2) to be correlated with HChacha20(DH2). Changing the nonce basically forces the attacker to perform a preimage attack on HChacha20. (This is a minor concern: the attacker can only has limited control over the the value of a DH key exchange to begin with, and having the opportunity to exercise that control means they know the relevant keys anyway, so they don't need to control anything.)