How to safely derive a value from a secret? I have a use case of symmetric encryption with a single-use random key K known only by the sender and the receiver:



In my scheme, Bob is able to send beforehand a tiny amount of information to Alice. Alice must send her data through Eve, which is an untrusted network. V is the "address" of Bob (not secret): a single-use random value which means "please send the encrypted data to bucket V".

Bob has extremely limited bandwidth when first speaking to Alice.
I'd like to achieve an important improvement: let Bob send only 1 value to Alice:



Alice and Bob would tacitly derive the same value V, from their shared secret K.

How can Alice and Bob compute an identical random-ish, non-secret value for V?

In the diagram, V = AES.encrypt(42, K) where 42 is a public constant, but I don't know if it is a good idea.
Obviously, it is very important for me that Eve cannot guess the value of K, knowing N, V and 42.

My system currently uses AES and K has 83 bits of entropy.
To derive additional identity information from a key you can use a KBKDF - a key based key derivation function. One of the more modern ones is HKDF-expand which is based on HMAC. Any hash or HMAC based function is of course one way; adversaries should not be able to learn any information about the key, unless the key is too short or not random enough in the first place.

KBKDF's differ from password based key derivation functions or PBKDFs such as PBKDF2 in the sense that they do not require a work factor (or iteration count) and they may not use a salt either.

KBKDF's can often contain label or other $\text{Info}$ input parameter to distinguish between output keys, something that PBKDF's commonly do not feature. In this case the label may for instance be a single character "V" to indicate that you are indeed deriving a value for that particular field. This means that the derived key is specific to that input value, other keys derived using an other label will be entirely unrelated to the derived value for "V".

When specifying $\text{Info}$ it may be a good idea to also include some (statically sized) identity strings for the participants, so that the key for sending from Alice to Bob is different from the one used in the other direction.



Note that HKDF is still a relative heavyweight algorithm - if just because it uses HMAC instead of a hash. If the implementation size or speed is a concern then you could replace it with an extremely simple alternative such as ANS X9.63 KDF which consists of a hash over a statically sized key, a label/other info and a statically sized big endian counter of 4 bytes.

In formulas:

$$K_i = \text{H}(\text{IKM} \mathbin \| \text{I2OSP}(i, 4) \mathbin \| \text{Info})$$

and $\text{OKM}$ is the leftmost bytes of $K_1 \dots K_n$ with $n$ set high enough to get the required Output Keying Material, $\text{OKM}$.

Here:


The $K_i$ is a full block of output keying material, each block the size of the hash function $\text H$ being used;
$\text{H}$ is the hash function configured for the KDF, e.g. SHA-256;
$\text{IKM}$ is the Input Keying Material to the KDF ($K$ in your diagram);
The operator $\|$ means concatenation 
$\text{I2OSP}$ converts a number to - in this case 4 - bytes, using unsigned big endian encoding;
$\text{Info}$ could be the ASCII string $\texttt{"V"}$ as explained above;
$\text{OKM}$ the output keying material which can be used to create a derived key


For AES the output keying material is the key, as AES simply consists of (pseudo) random bytes.

This creates a variable length output that is specific to the input keying material and the $\text{Info}$ octet string, which makes it possible to derive multiple keys for the same input keying material. 



So with all that your key derivation scheme could be e.g. SHA-256(key | 00000001h | "V"). If you need more key information you can simply increase the counter to 00000002h (the point is never to use the same input for the hash of course) and concatenate the output of the result. If you need less than a full number of output blocks then you should simply use the leftmost bytes of the result. If you want to derive more information from a static key then simply introduce another counter.

KDF's are very flexible, often to the point that they are too flexible. this makes it near impossible to standardize on algorithm, so describe the one you are using well.