Re: AES-based PRF for IKEv2

[Russ Housley <housley@vigilsec.com>]

Uri:

Steps 1 thru 4 are pretty  slow.  You keep computing the AES key schedule 
over and over.  In 802.11, we have found that this is a very expensive 
operation.  Can it be avoided?

Russ

At 06:43 PM 3/20/2003 -0500, Uri Blumenthal wrote:
>Folks,
>
>Here's a proposal for an AES-based PRF that takes variable-length
>input and produces variable-length output.
>
>Please comment.
>
>Thank you!
>
>Regards,
>Uri.
>
>
>PROPOSAL: AES-BASED PRF FOR IKEv2.
>
>The goal is to produce requested amount of pseudo
>random bits, using AES (or other block cipher) and
>variable-length input for both secret parameter, and
>publicly known parameter. Should work with variable
>key length, preferably support different block sizes.
>Preferably, the construct is provably secure.
>
>The following idea is based on Rijndael submission
>to NIST. It is assumed that AES is the block cipher
>that will be used, but the construct is generic
>enough to accomodate other block ciphers.
>
>
>PRF(S, N)  ALGORITHM.
>
>Two parameters - one is secret, the other one may be
>known. No assumption on the quality of randomness of
>either one is made. Assume that S is secret and N is
>known. No limitation on size of S, N.
>
>Outputs pseudo-random stream of bits in 128-bit chunks
>(variable-length output).
>
>Block cipher is assumed, with key-buffer for key, and
>data-buffer for plaintext. AES is assumed, but any
>other un-broken blok cipher should do.
>
>Algorithm:
>
>    1. Fill the key-buffer with S. If S is shorter than
>       the key-buffer, pad the key buffer with zeroes.
>
>    2. If any bits of S are left after step (1), place
>       them in the data-buffer. Append parameter N to
>       the data-buffer. Pad the data-buffer with zeroes
>       if necessary, to make it multiple of cipher block
>       size, and at least as long as key-buffer.
>
>    3. Encrypt as many blocks of data-buffer as necessary
>       to fill key-buffer.
>
>    4. Take the output of (3) and fill the key-buffer.
>       Continue (3) and (4) for the reminder of the
>       data-buffer.
>
>    5. At this point the encryption engine is ready to produce
>       Pseudo-Random stream.  Now run the encryption engine in
>       OFB mode (starting with input buffer filled with zeroes)
>       using the full block size, until the desired amount of
>       output bits is produced.
>
>
>RATIONALE.
>
>a. All the theory of block cipher security is based on the
>assumption that the key is unknown to the attacker. Thus
>we key the encryption engine with the secret parameter.
>
>b. It is preferred to move away from the given secret
>parameter (which is likely to be Diffie-Hellman output).
>That is why at least one key change is performed.
>
>c. Variable-length input and output is desirable - this is
>accomplished.
>
>
>SECURITY PROPERTIES.
>
>A block cipher being a Pseudo Random Permutation, if the
>S parameter is secret, the following hold true:
>
>    - output of (3) is pseudo-random.
>    - output of (5) is pseudo-random.