F-KDF — Key derivation

F-KDF (Key derivation) is part of Cryptographic Library and Symmetric Primitives in the UC functionality encyclopedia. Status: a canonical, well-established UC functionality.

Functionality

Reading the box: \(\square\) marks a key never generated; \(\bot\) is a call the functionality has nothing to answer for — no key at that pointer. \(\mathtt{Known}\) tracks which keys the simulator already has real access to. \(\mathtt{Derived}\) is the functionality’s own memory of every derivation it has already answered, keyed by the pair (source key, seed) — consulting it before asking the adversary again is what makes derivation deterministic: the same seed against the same key yields the same output, on the first ask or the hundredth.

Functionality \(\mathcal{F}_{\mathsf{KDF}}\)

\(\mathit{pid}\),   \(\mathbf{P}\),   \(\mathbf{N}\),   \(\mathbf{U} := \{(\mathcal{A},\mathsf{serves})\}\),   \(\mathit{par} := \bot\)

Initialize():

1. \(\mathtt{Keys}, \mathtt{Known} \gets \varnothing\)
2. \(\mathtt{Key} : \mathcal{F}_{\mathsf{KDF}}.\mathbf{P} \times \mathbb{N} \rightharpoonup \mathtt{Keys}\)
3. \(\mathtt{Next} : \mathcal{F}_{\mathsf{KDF}}.\mathbf{P} \to \mathbb{N}\)
4. \(\mathtt{Next}[*] \gets 0\)
5. \(\mathtt{Derived} : \mathtt{Keys} \times \{0,1\}^{*} \rightharpoonup \mathtt{Keys}\)
6. \(\mathtt{Derived}[*,*] \gets \square\)

id.KeyGen()from id′

7. \((\mathit{corr}, k) \gets \mathcal{A}\bigl(\mathit{id}.\mathsf{KeyGen}\bigr)\)
8. \(k \gets \mathsf{San}[\mathsf{Clean}_{k}](k; \mathtt{Keys})\)
9. \(\mathtt{Keys} \gets \mathtt{Keys} \cup \{k\}\)
10. \(\textbf{if}\ \mathit{corr} = 1\ \textbf{then}\)
11. \(\mathtt{Known} \gets \mathtt{Known} \cup \{k\}\)
12. \(\mathit{ptr} \gets \mathtt{Next}[\mathit{id}.P]\);  \(\mathtt{Next}[\mathit{id}.P] \gets \mathit{ptr} + 1\)
13. \(\mathtt{Key}[\mathit{id}.P, \mathit{ptr}] \gets k\)
14. \(\textbf{return}\ \mathit{ptr}\)

id.Store(k)from id′

15. \(\textbf{if}\ k \in \mathtt{Keys} \setminus \mathtt{Known}\ \textbf{then}\)
16. \(\textbf{return}\ \bot\)// a bare guess of an unknown key is refused
17. \(\mathtt{Keys} \gets \mathtt{Keys} \cup \{k\}\);  \(\mathtt{Known} \gets \mathtt{Known} \cup \{k\}\)
18. \(\mathit{ptr} \gets \mathtt{Next}[\mathit{id}.P]\);  \(\mathtt{Next}[\mathit{id}.P] \gets \mathit{ptr} + 1\)
19. \(\mathtt{Key}[\mathit{id}.P, \mathit{ptr}] \gets k\)
20. \(\textbf{return}\ \mathit{ptr}\)

id.Derive(ptr, s)from id′

21. \(k \gets \mathtt{Key}[\mathit{id}.P, \mathit{ptr}]\)
22. \(\textbf{if}\ k = \square\ \textbf{then}\)
23. \(\textbf{return}\ \bot\)
24. \(\textbf{if}\ \mathtt{Derived}[k, s] = \square\ \textbf{then}\)
25. \(k' \gets \mathcal{A}\bigl(\mathit{id}.\mathsf{Derive}, s, k \in \mathtt{Known}\bigr)\)
26. \(k' \gets \mathsf{San}[\mathsf{Clean}_{k'}](k'; k, \mathtt{Keys}, \mathtt{Known})\)
27. \(\mathtt{Keys} \gets \mathtt{Keys} \cup \{k'\}\)
28. \(\textbf{if}\ k \in \mathtt{Known}\ \textbf{then}\)
29. \(\mathtt{Known} \gets \mathtt{Known} \cup \{k'\}\)
30. \(\mathtt{Derived}[k, s] \gets k'\)
31. \(\mathit{ptr}' \gets \mathtt{Next}[\mathit{id}.P]\);  \(\mathtt{Next}[\mathit{id}.P] \gets \mathit{ptr}' + 1\)
32. \(\mathtt{Key}[\mathit{id}.P, \mathit{ptr}'] \gets \mathtt{Derived}[k, s]\)
33. \(\textbf{return}\ \mathit{ptr}'\)

id.Leak()from id′

34. \(\textbf{return}\ \{(\mathit{ptr}, \mathtt{Key}[\mathit{id}.P, \mathit{ptr}])\}_{\mathit{ptr} < \mathtt{Next}[\mathit{id}.P]}\)

Clean_k(k; Keys):

35. \(\textbf{return}\ k \in \{0,1\}^{*} \ \wedge\ k \notin \mathtt{Keys}\)

Clean_k'(k'; k, Keys, Known):

36. \(\textbf{if}\ k \in \mathtt{Known}\ \textbf{then}\)
37. \(\textbf{return}\ k' \notin \mathtt{Keys} \setminus \mathtt{Known}\)
38. \(\textbf{return}\ k' \notin \mathtt{Keys}\)

The box is transcribed from Küsters and Tuengerthal, Ideal key derivation and encryption in simulation-based security, ePrint 2010/295, revision 20101011:201701, Figure 6, p. 32 — item 12 (Derive) of their single functionality \(\mathcal{F}_{\mathsf{crypto}}\) (F-MAC draws on items 13–14 of the same figure). KeyGen/Store are the paper’s generic key-management commands, kept here only so the box has a key to derive from.

The one substantive choice made in translating this: the source parameterizes Derive by a target type for the new key, since a derived key can become an encryption key, a MAC key, or another derivation seed inside the paper’s shared, multi-primitive functionality. A box that only ever produces one kind of thing — another key, usable as this box’s own input — has no second type to name, so that parameter is dropped rather than transcribed as a no-op.

Known realizations

Realized, Section 3.2 (p. 10 of the same paper), by protocol \(\mathcal{P}_{\mathsf{crypto}}\): it instantiates a derived key as a pseudorandom function of the source key, keyed on the seed, once the source key is in real use — which is exactly what the paper’s realization theorem requires that PRF to withstand.

Properties

• Determinism. The same key and seed always derive the same output — the \(\mathtt{Derived}\) lookup guarding the whole adversary call. A UC functionality could instead let the adversary answer afresh every time; this one deliberately doesn’t.
• Freshness under an unknown source. Deriving from a key the simulator does not hold produces a key that is, in turn, entirely new (Clean_k'’s second branch) — never a value that collides with anything generated so far, ideal or real.
• No downgrade from a known source. Deriving from a key the simulator already holds can only produce another key the simulator holds (Clean_k'’s first branch) — real-world knowledge propagates forward through derivation; it never becomes ideal by passing through this box.

Formal artifacts

No machine-checked formalization yet.

References:

• Küsters and Tuengerthal. Ideal key derivation and encryption in simulation-based security. In Topics in Cryptology – CT-RSA 2011, volume 6558 of LNCS, pages 161–179, 2011. Figure 6, p. 32 of revision 20101011:201701, item 12, the definition transcribed above.