# Re: AES 256 based key derivation function.

On Oct 23, 11:43 pm, Kristian Gjøsteen <kristiag+n...@xxxxxxxxxxxx>
wrote:
Fabrice  <fabrice.gaut...@xxxxxxxxx> wrote:
Now, I'm wondering how to do this properly using AES 256. That is,
RootKey and Derived Key are 256 bits, and Public Value could be up to
256 bits.

Assume AES-CBC-MAC is a secure PRF for fixed-size messages and for
significantly less than 2^64 invocations. We define the function

f(rk, x0||x1||x2) = AES(rk, x2 + AES(rk, x1 + AES(rk, x0))).

Then

dk = f(rk, 0||PV) || f(rk, 1||PV)

is secure but somewhat wasteful at six AES invocations per derived
key. If you can store AES(rk,0) and AES(rk,1), this goes down to four
AES invocations.

With

g(rk, x0||x1) = AES(rk, x1 + AES(rk, x0))

we can do

tk = g(rk, PV)
dk = AES(tk, 0) || AES(tk, 1)

which is secure and maybe more efficient, at four AES invocations
plus one extra key schedule.

More speculatively, you could try

tk = g(rk,PV)
dk = tk || AES(rk, tk)

This requires three AES invocations and no extra key schedule. It may
be possible to prove it secure...

--
Kristian Gjøsteen

How does one define security of the Key Derivation Function in this
case ?
Your second proposal, dk=tk || AES(rk,tk), can only yield 2^128
different dk (because tk is 128 bits), whereas the first one would
produce 2^256 keys.

So should I say the strength of the derived key is only 128 bits in
the second example, instead of 256 in the first one ?

I doesnt seem true because, even if an attacker had to try all the
possible tk (2^128), it has no way to know AES(rk, tk)

That is, even though the attacker know that there is only 2^128
possible dk, it doesnt knows which ones among 2^256.

.