Key derivation design to avoid key leaks

I have the first function that generates keys from AES decryption (128-bit key). It takes seed as input:

derived_key_1 = AES-DEC(key, seed)


seed and key are both fixed values that the attacker cannot changed. Attacker knows the value of seed. His first goal is to get derived_key_1.

He dooes have an extra capability. He has access to another function defined as follows:

temp_key = AES-DEC(key, chosen_seed)
derived_key_2 = AES-DEC(temp_key, seed)


where chosen_seed is controlled by the attacker. He can observed derived_key_2.

Assume the AES is implemented in hardware and AES primitive itself does not have timing side channel. Also attacker does not have other physical side channel (e.g., power, EM, fault, etc.) to observe other than timing of the two functions.

Are there any potential security concerns in this construction?

If there are problems, do the problems go away if I change the seed in the second function to seed_new which is still visible to the attacker, but not changeable by him.

• is this supposed to be a key derivation function (KDF) or a random number generator(RNG)? If so there're standard constructions available like the famous NIST DRBGs, Fortuna (PRNGs) and HKDF (KDF). May 7, 2015 at 18:30
• @SOJPM, I remove the standard construction request. I am familiar with those. I just want to know if this construction have problems. This is for KDF. May 9, 2015 at 7:23
• I'm just being curious now. Why did you chose AES-DEC over AES-ENC ? May 9, 2015 at 16:38
• @SOJPM, I dont think it matters. Both are PRF. May 9, 2015 at 16:46
• It doesn't matter at all. I was just curious as the "normal" intuition usually tells people to use AES-ENC. And they aren't PRF but PRP. May 9, 2015 at 16:56

I finally found out what you're asking for:

A specific (working?) related-key attack on AES!

For this answer I changed the notation a bit:

• AES-DEC(K,P) got converted to $D_K(P)$
• derived_key_X got converted to $DK_X$
• seed (which is known) got converted to $S_K$
• chosen_seed got converted to $S_C$
• temp_key got converted to $K_T$

So for an attacker to uncover $DK_1=D_K(S_K)$ he'd need to know $K$. There's no other way in doing this.
Now you're asking if knowing $DK_2=D_{D_K(S_C)}(S_K)$ does help. Let's de-construct this. An attacker can choose $S_C$ to be decrypted to $K_T=D_K(S_C)$, in order to learn $K_T$ he'd need to get K which is infeasible for AES. Now as the attacker has no chance to know $K_T$ there's the question left if $DK_2=D_{K_T}(S_K)$ does help him anyhow. He can't deduce $K_T$ from this equation as this would be a known-plaintext attack, which is infeasible on AES. The final question is if there're some strange relationships that may help the attacker in uncovering $K$ and hence $DK_1$.
No, he'd be (maybe) able to brute-force by trying out every possible $S_C$ until $K_T=D_K(S_C)=K$ which is extremely unlikely, as he could as well just brute force the normal key as he has no control over the value of $K_T$.