[Cfrg] AES-based PRF - comment please

[Uri Blumenthal <uri@bell-labs.com>]

Folks,

Here's a proposed PRF based on AES block cipher. Its purpose is
to allow variable length input and output for AES, including
keying material. It can be useful for AES-only protocol suites
in IKEv2. It is based directly on Rijndael submission paper,
where they describe how to use Rijndael as Hash and as PRF.

Ted Ts'o asked me to post it here, which is my pleasure to do.
I look for comments, improvements and criticism.

Thank you!

Regards,
Uri.

P.S. IKEv2 will use AES as block cipher, and g^xy as S. But it
would be nice if the construct holds for generic block cipher
and generic secret S.
PROPOSAL: AES-BASED PSEUDO RANDOM FUNCTION FOR IKEv2.

PRF(S, N)

The goal is to produce requested amount of pseudo
random bits, using AES (or other block cipher) and 
variable-length input for both parameters: the secret
one (e.g. DH output) and the one publicly known (e.g.
concatenation of nonces). Should work with variable
key length, preferably support different block sizes.
Preferably, the construct is provably secure.

The following idea is implementing recommendation from
Rijndael Submission Paper to NIST, in particular - for
using AES as Pseudo Random Function. It is assumed that
AES is the block cipher that will be used, but the 
construct is generic enough to accomodate other 
block ciphers with no weak keys.



ALGORITHM:  PRF(S, N)

S is secret, N may be known. No assumption on the quality 
of randomness is made for either parameter. No limitation 
on size of S, N. 

Outputs pseudo-random stream of bits in  cipher blocksize
chunks (128-bit for AES). Bu default - outputs the number
of bits equal to blocksize. Optionally the amount of
output bits can be specified.

Block cipher is assumed, with key-buffer for key, and
data-buffer for plaintext. AES is a natural choice.

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. Encryption engine is keyed with secret parameter because
all the theory of block cipher security is based on the
assumption that it is the key which is unknown to the 
attacker. No analysis exists (as far as I know) for the 
case when the key is known, but the plaintext and/or 
ciphertext aren't.

b. Changing the key at step (4) mitigates the Related Keys
attack.

c. OFB mode in step (5) allows producing [practically] any
amount of output bits, much larger than the cipher block 
size.



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.



CONSIDERATIONS.

Security of this PRF is based on three assumptions: (a) block
cipher used is not broken, (b) the secret parameter is unknown
to the attacker, and (c) there is no property of the key space
that makes a class of keys weak. 

If a weak secret - such as a short passwod - is used for parameter
S, then it is possible to break this algorithm by dictionary
attack. Note that this vulnerability exists in HMAC as well,
and is unavoidable (unless one uses protocols such as PAK, 
EKE/SPEKE, etc).


DESIGN ALTERNATIVE.

Instead of zeroizing the data-buffer in the step (5),
one can leave it as is, effectively filled with the
new key. Cryptographic property of this is one-way-ness,
as it is impossible to invert E{K}K not knowing the key. 
Whether this is a desired property, is left for the
discussion.