6
$\begingroup$

I need cryptography advice regarding this issue.

Kamus is a service that encrypts secrets for applications running on Kubernetes. When using AES (actually, Rijndael) symmetric encryption, Kamus uses a single key to encrypt the secrets for all apps.

Let's say I want to create from the generic key, a key that is unique per application - so that secrets that are encrypted for a specific application will not be able to decrypt with the key of another application (this is the case when using a KMS). I'm looking for an algorithm to "derive" a key from the application name (the service account name, to be accurate), something like:

f(key, name) = key

Is there an algorithm that I can use? What is the best approach here?

$\endgroup$
3
  • 3
    $\begingroup$ HKDF(key + name, digest_len) $\endgroup$
    – SamG101
    Dec 22 '19 at 19:50
  • $\begingroup$ @SamG101 HKDF not defined as you listed. If we combine extract and expand then HKDF(IKM , Salt, info, length) $\endgroup$
    – kelalaka
    Dec 23 '19 at 9:24
  • 3
    $\begingroup$ Ohh right yes you're right, I was just suggesting the concept $\endgroup$
    – SamG101
    Dec 23 '19 at 9:26
14
$\begingroup$

Multiple Key Generation from a Master key

HMAC-based Key Derivation Function (HKDF) rfc5869 is what you are looking for. HMAC security proof uses the fact that the compression function of the underlying hash is itself a PRF.

HKDF follows the "extract-then-expand" paradigm, where the KDF logically consists of two modules. The first stage takes the input keying material and "extracts" from it a fixed-length pseudorandom key K. The second stage "expands" the key K into several additional pseudorandom keys (the output of the KDF).

Extract:

$$\text{HKDF-Extract}(salt, IKM) \to PRK,$$where $PRK$ is a pseudorandom key.

If the Input Key Material (IKM) is already a random key, as in your case, then the extract is not necessary, Expand is enough. HKDF can be used without the salt, however, using salt adds to the strengthening of HKDF and supporting source-independent extraction. Two different salts with the same $IKM$ result in fundamentally two different $PRK$s. And, in general, $x$ different salts with the same $IKM$ result in fundamentally $x$ different $PRK$s.

Expand:

$$\text{KDF-Expand}(PRK, info, L) \to OKM,$$where OKM is Output Keying Material. L is the desired key length.

The info can be used for the application-specific tag to derive different keys.

$$\text{KDF-Expand}(\text{Inittal Key}, \text{"application 1"}, 128) \to OKM_1$$ $$\text{KDF-Expand}(\text{Inittal Key}, \text{"application 2"}, 256) \to OKM_2$$


What is the probability of generating the same key, i.e. collision

It is hard to talk about directly on the HKDF, however, if we model it as a uniform random function $f$, where $f(x)$ is uniform random HKDF value for each combined input ( $x = salt || IKM $) then we can turn back to birthday collisions.

Let $P(C; n, k)$ denotes the usual collision probability among $n$ people with $k$ possible birthdays. And, the usual way is to calculate from the complement $P(D; n, k) = 1 - P(C; n, k)$, that is all birthdays are distinct. Then we can approximate by

\begin{equation} P(C; n, k) = 1 - P(D; n, k) \leq \frac{n^2}{k}. \end{equation} where $n \leq k/2$. The detail is everyhwere, and therefore skipped.

We have two cases;

  1. The collision on the generating the $x$s. You may consider this as salt collision too if IKM is set fixed. For $n$ inputs $x_1,x_2,\ldots,x_n$ the collision probability is $P(C; n, k)$. When this occurs, that is the conditional probability than the outputs $f(x_1),f(x_2), \ldots, f(x_n)$ will have a collision with probaility 1.

  2. If the inputs $x_i$s are distinct then this has $P(D; n, k) = 1 - P(C; n, k)$ probability. Now, conditionally on this we can have collision on the outputs $f(x_1),f(x_2), \ldots, f(x_n)$ with $P(C; n, k)$ probability.

Now sum up the above, then we have;

$$P(C; n, k) + (1 - P(C; n, k)) \cdot P(C; n, k) \\ = 2 P(C; n, k) - P(C; n, k)^2 \leq 2 \frac{n^2}{k}$$

So, this is just double of the usual collision attack. If you are not going to generate $2^{64}$ keys for a 128-bit key it then is not a problem for you. This case may be a problem with the multi-target attack. This is why you need to use AES-256.

You may notice that $2^{64}$ with 128 makes 2, this is due to the fact that the probability bound is not good for $n \approx \sqrt{k}$, there are tighter bound however when the input passes $\sqrt{k}$ it fastly approaches to 1.

It is important to note that 50% probability is too high in the sense of the adversary. One should stop way earlier than this. If you use AES-256, you should use it ( or ChaCha20 that has a 256-bit key), then the amount generating a collision is beyond us.


Note: There is also old KDF1 and KDF2

$$K_i = \operatorname{KDF}(K_{master}, i) = \operatorname{H}(K_{master} \mathbin\| c)$$ where $c$ is 4 byte encoded $i$, and it was commonly used wiht MD5,SHA-1, and SHA-256.


A sample code with python hkdf that contains the pop count on the output's x-or;

from hkdf import hkdf_extract,hkdf_expand
from binascii import unhexlify,b2a_hex
import sys

def bxor(b1, b2): # use xor for bytes
    parts = []
    for b1, b2 in zip(b1, b2):
        parts.append(bytes([b1 ^ b2]))
    return b''.join(parts)

prk = hkdf_extract(unhexlify(b"8e94ef805b93e683ff18"), b"asecretpassword")
key1 = hkdf_expand(prk, b"application 1", 16)
key2 = hkdf_expand(prk, b"application 2", 16)

print (b2a_hex(key1))
print (b2a_hex(key2))

#count the number of differnt bits by x-or and popup count.
print (bin(int.from_bytes(bxor(key1,key2), byteorder=sys.byteorder))[2:].count('1'))

outputs

 b'd6208cd3e14955c6ae0dc7f5ecd38a68'
 b'3b310a2e8cc9f4854237e966d289d9ba'
 64
$\endgroup$
1
  • 3
    $\begingroup$ Thanks! This is exactly what I'm looking for :) $\endgroup$ Dec 23 '19 at 6:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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