Re: AES 256 based key derivation function.

On Oct 23, 11:43 pm, Kristian Gjøsteen <kristiag+n...@xxxxxxxxxxxx>
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))).


        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.


        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.