[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Cfrg] AES-based PRF - comment please
Uri,
Few remarks:
1. I think that there is some terminology confusion here with respect to the
meaning of the name "pseudorandom function" (PRF). In the cryptographic
theory, a PRF is an abstraction (i.e., a primitive) with specific
mathematical properties. Within IKE there is a construct (used for key
derivation) that is called "PRF"; the reason for the name was that in
the mind of the protocol designers this construct was to be modeled as
a PRF in a security proof of IKE. However, there is of course no necessity
to model the IKE-PRF construct as a PRF. Indeed, what you seem to suggest
is that we can perhaps do otherwise.
2. In crypto-theory, a PRF is guaranteed to provide security only when its
key is SECRET and RANDOM (ie, uniformly distributed).
If the key is either not secret or not random then all bets are off - no
security whatsoever is guaranteed.
3. The security requirements from block-ciphers are typically aligned with
the requirements from PRFs (or rather PRPs (pseudorandom permulations)).
That is, security is required and analyzed only for the case where the key
is SECRET and RANDOM. Nothing is required when the key is either not secret
or not random.
4. You seem to want to construct a key-derivation function that can take
a bunch of inputs of variable length (some of them are secret, some public,
some random, some not) and somehow generate out of these a sequence of
pseudorandom bits, which is as long as necessary. your general methodology
is as follows:
I. Using some hash function H, "hash down" the input material into a value
v that is of the right size for a PRF F. (You essentially make no distinction
between the S input and the N input to your construct.)
This corresponds to your steps 1-4.
II. Run F in OFB with key v and input 0*, to generate as many output bits as
necessary. This corresponds to your step 5.
Your hope is that H is good enough so that v will be sufficiently
"pseudorandom", even if the input is neither completely random nor
completely secret.
Furthermore, you are using AES both for H and for F.
5. While using AES for F is sound, my impression is that using AES as the
(essentially keyless) hash function H is rather risky and definitely not
well analyzed. This is not to say that it's necessarily a bad idea; rather,
I'd say that this requires much more justification and analysis - both in
terms of general cryptographic modeling and in terms of AES specifically.
Certainly, this property that you need from H does not follow from
collision resistance.
(Ofcourse, the "easy way out" would be to model AES as a random oracle.
Then the analysis is completely trivialized and everything becomes perfectly
secure on paper. But this is no real analysis - we know that AES is NOT
a random oracle and we need an analysis based on realistic
assumptions on/ modeling of AES.)
Hope this makes sense.
Ran
> From cfrg-admin@ietf.org Sun Mar 23 03:58:26 2003
>
> 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.
>
> --------------020208050107040706040902
> Content-Type: text/plain;
> name="aes-prf.txt"
> Content-Disposition: inline;
> filename="aes-prf.txt"
> Content-Transfer-Encoding: 7bit
>
> 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.
>
> --------------020208050107040706040902--
>
> _______________________________________________
> Cfrg mailing list
> Cfrg@ietf.org
> https://www1.ietf.org/mailman/listinfo/cfrg
>
_______________________________________________
Cfrg mailing list
Cfrg@ietf.org
https://www1.ietf.org/mailman/listinfo/cfrg