Formal description of KDF1 and KDF2

Question

I've seen many descriptions of KDF1 and KDF2 by now, but most documents simply point to specifications that are behind a pay wall. These standards are not specific to the KDF's; they just use these KDF's as sub-part of an algorithm description (key agreement). Does somebody have a formal description of both KDF's that adheres to the standards?

The description should include additional information to derive a key such as OtherInfo field or label, or indicate their absence. Needless to say the other input parameters and the use of the internal counter would be needed for the full algorithm as well.

The standards can be found in IEEE Std 1363-2000, ANSI X9.42 (KDF1) and ISO 18033-2 (KDF2). That last standard defines OID's for them, KDF1 is 1.0.18033.2.5.1 and KDF2 is 1.0.18033.2.5.2 (unprotected links to oid-info.com).

Answer 1

FCD 18033-2 Encryption algorithms — Part 2: Asymmetric ciphers - the final committee draft (FCD) of ISO/IEC 18033 - by Victor Shoup is publicly available from his website and specifies (in section 6.2) that KDF1 is

For an octet string $x$ and a non-negative integer $l$, $\operatorname{KDF1(x,l)}$ is defined to be the first $l$ octets of

$$\operatorname{Hash.eval}(x || \operatorname{I2OSP}(0, 4)) || ··· || \operatorname{Hash.eval}(x || \operatorname{I2OSP}(k − 1, 4)),$$

where $$k = \lceil l/\text{Hash.len} \rceil $$

The binary counter representation should translate to 4 bytes in big endian.

KDF2 is identical but starts counting from 1 instead of 0.

Answer 2

Here is a list of differences of these KDF's in various standards, taken from Analysis of ECIES and Other Cryptosystems Based on Elliptic Curves written by V. Gayoso Martínez, F. Hernández Álvarez, L. Hernández Encinas and C. Sánchez Ávila.

Unfortunately it is missing KDF's that are defined for X9.42: DH over a multiplicative group. It seems to define two KDF's, where the concatenation based KDF is compatible with ANS X9.63 specified below.

X9.42 also seems to define an ASN.1 based KDF as specified in RFC 2631: Diffie-Hellman Key Agreement Method, so that one is incompatible with KDF1 and KDF2 as the counter is included in the ASN.1 structure.

ANSI X9.63 allows to use an arbitrary parameter as an input to the KDF function, but does not mention the content of that optional parameter. In comparison, the so-called DHAES mode in IEEE 1363a mandates to use the binary representation of the sender’s public key as an input parameter.

...

ISO/IEC 18033-2 does not allow parameters in the KDF function, whereas IEEE 1363a allows the usage of parameters in that function.

IEEE 1363a suggests to use always the same set of parameters and functions for a given public key. In comparison, ISO/IEC 18033-2 mandates not to change under any circumstance those parameters for the same receiver’s public key.

...

ISO/IEC 18033-2 does not allow input parameters in the KDF function, whilst SEC 1 allows to include this additional information, even though in the test vectors included in the GEC 2 document [32] no additional parameters have been used.

SEC 1 does not explicitly include the sender’s ephemeral public key in the KDF computation. However, it mentions that the public key could be one of the elements used as input parameters in that function.

The main thing to take from this is that the official KDF1 and KDF2 as defined by ISO do not take parameters, so the answer of orip is correct.

---

However, sometimes it makes sense to do include parameters, e.g. to let the KDF generate multiple keys from the same key input material (the original versions of the key agreement specifications split the output in two separate keys, a MAC and ENC key, of which the order differs, this is more efficient but less neat). So for that reason I'll include ANS X9.63 KDF below; it should be compatible with KDF2 except for the additional $\text{SharedInfo}$.

The SEC 1: Elliptic Curve Cryptography, May 21, 2009, Version 2.0 standard defines the X9.63 KDF. The fact that a draft 1.99 of the paper states that X9.63 is still in draft phase at the time of writing shows that these documents were generated in parallel.

3.6.1 ANS X9.63 Key Derivation Function

Keying data should be calculated using ANSI-X9.63-KDF as follows:

Setup: Select one of the approved hash functions listed in Section 3.5. Let $\text{Hash}$ denote the hash function chosen, $\text{hashlen}$ denote the length in octets of hash values computed using $\text{Hash}$, and $\text{hashmaxlen}$ denote the maximum length in octets of messages that can be hashed using $\text{Hash}$.

Input: The input to the key derivation function is:

1. An octet string $Z$ which is the shared secret value. value.
2. An integer $\text{keydatalen}$ which is the length in octets of the keying data to be generated.
3. (Optional) An octet string $\text{SharedInfo}$ which consists of some data shared by the entities intended to share the shared secret value $Z$.

Output: The keying data $K$ which is an octet string of length $\text{keydatalen}$ octets, or $\texttt{“invalid”}$.

Actions: Calculate the keying data $K$ as follows:

1. Check that $|Z| + |\text{SharedInfo}| + 4 < \text{hashmaxlen}$.
   If $|Z| + |\text{SharedInfo}| + 4 \ge \text{hashmaxlen}$, output $\texttt{“invalid”}$ and stop.

2. Check that $\text{keydatalen} < \text{hashlen} × (2^{32} − 1)$.
   If $\text{keydatalen} \ge \text{hashlen} × (2^{32} − 1)$, output $\texttt{“invalid”}$ and stop.

3. Initiate a 4 octet, big-endian octet string $\text{Counter}$ as $\texttt{00000001}_{16}$.

4. For $i = 1$ to $\lceil \text{keydatalen} / \text{hashlen} \rceil$, do the following:

4.1. Compute: $K_i = \text{Hash}(Z \mathbin \| \text{Counter} \mathbin \| [\text{SharedInfo}])$ using the selected hash function from the list of approved hash functions in Section 3.5.

4.2. Increment $\text{Counter}$.

4.3. Increment $i$ (note: probably a bug in the spec, we're already iterating over $i$).

5. Set $K$ to be the leftmost keydatalen octets of: $K_1 \mathbin \| K_2 \mathbin \| \dots \mathbin \| K_{\lceil \text{keydatalen} / \text{hashlen} \rceil}$.

6. Output $K$.

---

There is also the NIST SP 800-56B specifying the aptly named "5.5.1 The Single-step Key-Derivation Function" (think of a name, guys) where they manage to put the counter in front of the keying material so that it is incompatible with all the schemes above. Although it contains a full (but pretentious and overly complex) way of specifying $\text{OtherInfo}$ (their version of $\text{SharedInfo}$) I would consider it completely useless for this reason alone.

Answer 3

So... Googling around KDF1 is supposedly the same as MGF1 as defined in PKCS#1 2.1, which can be found in Appendix B of RFC 3447. KDF2 is nearly the same as KDF1 except the counter runs from 1 to n instead of from 0 to n - 1.