Re: [Cfrg] AES-based PRF - comment please

[Mats Näslund <mats.naslund@era.ericsson.se>]

Hi Uri,

Uri Blumenthal wrote:

> 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.
It could be that I missunderstand the constuction/notation, could
you provide it in "mathematical" notation? However, modulo that, it
seems that at this point (after step 4), all the "entropy" has been 
"hashed down" to key-buffer size (i.e. 128 bits say). This means
that even if the original S was, say a 1024 bit DH key, the
uncertainty of the internal state at this point is only 128 bits,
so....

>    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.
...if the desired output length is, say 256 bits, you will still
only get an effective key-size of 128, or? Also, since the OFB starts
from 00....0 it seems you could have vulnerability to off-line
pre-computation attacks.

In other words, there seems to be a bottle-neck just after
that step 4 that upper bounds the effective entropy, is that
right?

Have you looked at ISO/IEC 18033-2 ? they have a similar PRF
(mapping aribitrary length to arbitrary length) that is (if I remember
correctly) basically running SHA1 is "counter mode", keyed by the
input key.

Cheers

/Mats

> 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.

----------------------------------------------
Mats Näslund, PhD, Senior Specialist
Communications Security Lab, Ericsson Research
SE-16480 Stockholm, Sweden
Visiting adr: Torshamnsgatan 23, Kista
Phone/Fax: (+46 8) 58533739/4047020


_______________________________________________
Cfrg mailing list
Cfrg@ietf.org
https://www1.ietf.org/mailman/listinfo/cfrg