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

From: Uri Blumenthal <[email-masked]>
Date: Sun, 23 Mar 2003 03:34:23 -0500

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.

---

From: Mats Näslund <[email-masked]>
Date: Sun, 23 Mar 2003 14:59:59 +0100

Hi Uri,

>       Continue (3) and (4) for the reminder of the 

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

>       using the full block size, until the desired amount of 

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

> Whether this is a desired property, is left for the

----------------------------------------------
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
[email-masked]
https://www1.ietf.org/mailman/listinfo/cfrg

---

From: [email-masked] (David Wagner)
Date: 23 Mar 2003 18:22:15 GMT

Uri Blumenthal  wrote:
>Here's a proposed PRF based on AES block cipher.

For those who aren't on IPSec mailing list, Hugo Krawczyk and I have
pointed out that this construction requires something more than just
the assumption that AES is a PRP -- some additional assumptions are
required for this construction to be secure.

In general, I am somewhat skeptical of constructions which assume that
AES is something more than a PRP; most analysis of AES has been on its
security as a PRP.

Also, in general, given that we already have PRF's with well-justified
security arguments, I think any new proposal of a PRF ought to come
with a careful proof of security under some well-specified set of
assumptions.
_______________________________________________
Cfrg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/cfrg

---

From: Uri Blumenthal <[email-masked]>
Date: Sun, 23 Mar 2003 14:06:44 -0500

> required for this construction to be secure.

However we seem to disagree as to what other assumptions - if
any - are necessary. We are currently discussing those off-line,
but if anybody on the list would like to contribute, you're
most welcome!

> AES is something more than a PRP; most analysis of AES has been on its

I do not think that a stronger assumption is needed (or indeed can
be made). Being a PRP [family] means that whatever key [PRP family
index] you choose, the specific function is a PRP. Which should be
enough for the proposed construction. I'm in the process of putting
together a more "formal" proof, and again, feel free to jump in.

> with a careful proof of security under some well-specified set of

It looks that whatever arguments can be made against this construction,
the very same ones apply to the existing PRF's, such as HMAC - because
in case of AES the PRP property is necessary (otherwise it's not an
acceptable block cipher), and in case of SHA it's merely believed
as nobody proved otherwise that it is a PRF (and if it isn't,
it still is an acceptable hash, which it was designed to be).
The existing PRF's security is reduced to that of SHA - and
SHA is LIKELY (but doesn't have to) have the ascribed to
it properties. This construct's security is reduced to
that of AES - which MUST have the ascribed property
(or else it is broken). However as David pointed
out, this reduction is not shown convincingly
yet - which I'm busy with now (David, thanks
for putting me to work :-).

Also the justification for creating a new PRF is simple - if you have
a pure AES-based protocol suite (encryption, integrity, MAC), you may
want to have your PRF also AES-based - especially if crypto hardware
is involved (for example a custom ASIC, where it matters whether
you place another algorithm on the chip).

---

From: Uri Blumenthal <[email-masked]>
Date: Sun, 23 Mar 2003 14:22:20 -0500

Mats Näslund wrote:
> only get an effective key-size of 128, or?

The effective key size is that of the AES key size. So if one
uses AES with 128-bit key - then it's 128 bits, if AES with
256 bits - then it's 256 bits. And there's no way to make
it stronger. At least this is my understanding.

So whatever entropy the initial secret has, the resulting
entropy will be no greater than the key size of AES.

But for SHA-based PRF the resulting entropy is no greater  than
SHA output size (160 bits at most), and the same applies to MD5
(128 bits at most). Am I correct?

 > Also, since the OFB starts from 00....0 it seems you could have
 > vulnerability to off-line pre-computation attacks.

I'm not sure I fully follow. Precomputation of the PRF output
for a bunch of assumed keys (because it shouldn't be feasible
to precompute OFB output for a reasonable-sized portion of
AES keyspace)? Could you amplify please?

Also, there are variations. One - to start OFB from the existing
buffer (which contains the key), in effect beginning OFB with
E{K}K (a non-invertible construct). Another - to skip the
first few blocks of the OFB output based on the function
of the first OFB encryption...

What would you say - does it make sense?

> that step 4 that upper bounds the effective entropy, is that

I doubt it's at the step 4. I'd say it's the consequence of
having a pseudo random function, whose key size effectively
defines an upper bound. No matter what, it wouldn't be
possible to create an AES-based PRF whose entropy is
greater than AES key size. I think step 4 doesn't
bring it any lower than that.

> correctly) basically running SHA1 is "counter mode", keyed by the

Grrrrr. No I haven't. I will. I've taken the construct from Rijndael
paper. But as I understand form your description, ISO/IEC is similar
to what I'm doing, right?

And for precomputation attack it shouldn't matter whether CTR or OFB
mode is used, correct? Please comment.

And Mats, I appreciate your review very much. Thank you!

---

From: [email-masked] (David Wagner)
Date: 23 Mar 2003 19:08:43 GMT

Uri Blumenthal  wrote:
>the very same ones apply to the existing PRF's, such as HMAC - 

I don't see it.  In the random oracle model (where SHA1 is modelled as
a random oracle), I think SHA1-HMAC is golden.

I'm happier modelling SHA1 as a random oracle than I am modelling AES as
an ideal cipher.  The former has been better studied by cryptanalysts,
I think.

I think some kind of random oracle or ideal cipher model is going to be
necessary, if we can't assume our key material is uniformly distributed
(as seems to be the case for IPSec).
_______________________________________________
Cfrg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/cfrg

---

From: Uri Blumenthal <[email-masked]>
Date: Sun, 23 Mar 2003 15:13:00 -0500

David Wagner wrote:
> I don't see it. 

Let's see. (no pun intended :-)

 > In the random oracle model (where SHA1 is modelled as

SHA was designed as a collision-resistant hash function. All
the other properties are assumed.

> I'm happier modelling SHA1 as a random oracle than I am modelling
 > AES as an ideal cipher.

Why? AES is a lot closer to an ideal cipher (unless and until broken)
than SHA - to random oracle (because if proven wrong, SHA still can
function as a crypto-hash).

 > The former has been better studied by cryptanalysts, I think.

For longer time - yes. Better? I doubt. Anyway, this is
highly subjective.

> (as seems to be the case for IPSec).

Probably so. So please do join the analysis, will you? After all,
it is for the benefit of everybody involved to get it right. BTW,
what assumptions can be made of g^xy, in your opinion?

---

From: Mats Näslund <[email-masked]>
Date: Mon, 24 Mar 2003 10:59:51 +0100

> 256 bits - then it's 256 bits. And there's no way to make

OK, my example was using a bad choice of parameters. Replace e.g.
"256" by "384" and "128" by "256"... Of course, if
you only want to provide key material at 256 bits or less, this
is not a problem. I assumed that you also might want to  e.g.
convert 2048 bits of DH key to, say 512 bits. (I really don't
have an application for this in mind, it just seems a nice
general primitive to have.)

> entropy will be no greater than the key size of AES.

Sure, any consturction which uses something of form

1) tmp = h(S || N)
2) key = g(tmp)

will be limited by the "width" of h.

I am not sure it is generally impossible by other constructions
though (?)

> (128 bits at most). Am I correct?

Right, with any "simple" construction.

> AES keyspace)? Could you amplify please?

*If* I have correctly interpreted your construction, it matches
the pattern of steps 1), 2) above. (If not, my aplogies.)

Let's assume that the keys are to be used for e.g. HMAC, and for 
simplicity, that the attacker is able to choose plaintext, p, to be
authenticated by Alice.

The attack would be:

* generate M random values of "tmp" and expand them as in step 2)
   and store valued { HMAC(k,p) }.
* sit back and watch N sessions, each HMAC:ing the message you chose,
   and look for collisions in your list

Though somewhat pathologic, this seems to enable finding keys with
traditional "square root" time/memory trade off. Adding "salt" in
step 2) (or making sure that all MACs are randomized) seems to
fix this though.

> What would you say - does it make sense?

Well, if you randomize the srating point of the OFB, it seems fine.

> to what I'm doing, right?

It seems so, though I would need to re-cap.

> mode is used, correct? Please comment.

Correct. The same TMTO attack applies also to CTR if the starting
point is not randomized properly. If it is, both seem OK.

> And Mats, I appreciate your review very much. Thank you!

Sure. I think it would be nice to have an "all-AES-based" security.
It would also have been nice if the 256-bit block version of Rijndael
was standardized so that you could get 256 bit hashes using the same
primitive.

Best,

/Mats

---

From: Mats Näslund <[email-masked]>
Date: Mon, 24 Mar 2003 11:02:56 +0100

Uri Blumenthal wrote:

[snip]

> what assumptions can be made of g^xy, in your opinion?

There are quite a few things known about the "absolute" distribution
of this (and other properties). Igor Shparlinski's new book provides
a nice compilation of such results.

/Mats

---

From: John Viega <[email-masked]>
Date: Sun, 23 Mar 2003 23:07:27 -0500

This has become somewhat a popular topic, particularly since Peter 
Gutmann's "Crypto Gardening Guide".  In that, Peter argued for more 
versatile PRFs that could be adapted to a wide variety of situations.  
He talked about things like iteration counts, etc.

I'd actually like to know why PKCS #5's PBKDF2 isn't sufficient for 
Peter's needs, because I have found it useful for all of mine.  It's 
also very easy to adapt to use with AES.

The standard implementation for PBKDF2 that I've seen uses HMAC-SHA1 
internally.  One can replace that with OMAC, with one issue.  The way 
HMAC-SHA1 is used relies on the fact that it can accept arbitrary sized 
keys, whereas OMAC requires a fixed sized keys.  The easiest way to 
handle that problem is by using a hash function based on a block cipher 
like Davies-Meyer, but, IIRC, the proof for those constructions are in 
the ideal cipher model.

I think you could probably avoid the hash-from-cipher construction by 
keying with the first keylen bytes, and then take the rest (if any), 
and prepend "len(key) || key leftovers" to the MAC input.  But, I 
haven't given it much thought, and there may be something disastrously 
wrong with that.

I've got code lying around implementing PBKDF2 with Davis-Meyer and 
OMAC that I'd be happy to share for anyone who's interested.

John

---

From: David Hopwood <[email-masked]>
Date: Mon, 24 Mar 2003 11:34:46 +0000

-----BEGIN PGP SIGNED MESSAGE-----

> also very easy to adapt to use with AES.

As a password hash, PBKDF2 has two warts:

  - the computationally intensive part is repeated for each block
    of output required (say n hash outputs). This means that an attacker
    doing a dictionary search will gain an n-times advantage relative to
    the optimum.
  - unlike some other password hashes like bcrypt, there is no attempt to
    make the hash difficult for an attacker to optimise for a hardware-based
    keysearch machine.

These warts don't apply when it is used just as a variable-length
input/output PRF with a small iteration count - but in that case PBKDF2 is
arguably unnecessarily complicated, since VIO-PRFs don't need salt or
iteration counts.

FWIW, my preferred VIO-PRF is this:

    HMAC-PRF(hash)(key, seed) =
        HMAC(hash)(key, I2OSP(0, 4) || seed) ||
        HMAC(hash)(key, I2OSP(1, 4) || seed) ||
        HMAC(hash)(key, I2OSP(2, 4) || seed) ||
        ...

Note that it has no entropy bottleneck; for each <hash output length> of
PRF output, the key and seed both contribute fully to the entropy of the
output (limited only by the hash *block* size). It as as secure in the sense
of a VIO-PRF, as plain HMAC is as a VI-PRF (this also extends to the subset
of related-key attacks that can be formalised using the "PRF-RK" property
given at <http://groups.google.com/groups?selm=3D6466C6.1EC9E8E%40zetnet.co.uk>).

> like Davies-Meyer, but, IIRC, the proof for those constructions are in

Davies-Meyer is construction i = 5 in [BRS02]. IMHO, constructions i = 1..4
from that paper are strictly better than Davies-Meyer, since they use the
cipher "the right way round", i.e. with either the fixed initial chaining
value h_0, or a previous ciphertext output h_{i-1} as the key. Provided that
h_0 is not a weak key, I find this more reasonable than the other constructions
(i = 5..20) that are keyed by m_i or (m_i xor h_{i-1}), so that an attacker is
able to influence the key. Even rather minor weaknesses in the cipher's key
schedule (such as just two related keys out of the whole key space) can render
those constructions insecure; see
<http://groups.google.com/groups?selm=3D4DCBC2.8846BF59%40zetnet.co.uk>.

[There is nothing to choose between my preferred 4 alternatives from that
paper, so anyone who wants to use one of these as a hash function might as
well use i = 1.
<http://www.users.zetnet.co.uk/hopwood/crypto/scan/md.html#BRS-Hn> nails
down some details.]

> and prepend "len(key) || key leftovers" to the MAC input.

I would avoid this in cases where the first keylen bytes are not guaranteed
to have sufficient entropy on their own.

[BRS02] John Black, Phillip Rogaway, Thomas Shrimpton,
        "Black-Box Analysis of the Block-Cipher-Based Hash-Function
         Constructions from PGV" (full version),
        IACR e-print 2002/066, June 3 2002.
        <http://eprint.iacr.org/2002/066/>

- -- 
David Hopwood <[email-masked]>

Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5  0F 69 8C D4 FA 66 15 01
Nothing in this message is intended to be legally binding. If I revoke a
public key but refuse to specify why, it is because the private key has been
seized under the Regulation of Investigatory Powers Act; see www.fipr.org/rip

---

From: David Hopwood <[email-masked]>
Date: Mon, 24 Mar 2003 18:56:02 +0000

-----BEGIN PGP SIGNED MESSAGE-----

>         HMAC(hash)(key, I2OSP(2, 4) || seed) ||

(I2OSP(i, 4) is a 4-byte big-endian representation of i.)

> output (limited only by the hash *block* size).

Sorry, I was wrong here. HMAC is defined as:

  HMAC(hash)(key, msg) = hash((k XOR opad) || hash((k XOR ipad) || msg))

                       where k = key' zero-extended to B bytes
                             key' = key,       if |key| <= B
                             key' = hash(key), if |key| > B
                             B = hash block size in bytes

Let L be the hash chaining variable size in bytes (usually equal to its output
length). Because k is at the start of the hash inputs (before the 'I2OSP(i, 4)'
counter), the maximum entropy contribution of the key is 2*L bytes when
|key| <= B, or L bytes when |key| > B.

Although this isn't really a problem for typical hash sizes, I think it's worth
considering how to fix it, if we are going to recommend a hash-based VIO-PRF.

This approach:

  HMAC-PRF2(hash)(key, seed) =
      HMAC(hash)(I2OSP(0, 4) || key, I2OSP(0, 4) || seed) ||
      HMAC(hash)(I2OSP(1, 4) || key, I2OSP(1, 4) || seed) ||
      HMAC(hash)(I2OSP(2, 4) || key, I2OSP(2, 4) || seed) ||
      ...

doesn't obviously preserve the security of HMAC as a PRF, for the model that
assumes non-related keys. I'll have to think about this some more - I'm fairly
sure that avoiding the hash output size bottleneck is possible.

- --