eap Mailing List: RE: methods and expert reviews

[Walker, Jesse (jesse.walker]

This is a follow up to my earlier review of EAP-PSK. There is one
suggested improvement that I made that does not work, so can itself be
improved upon.

> The first is to try to use AES in CBC-MAC mode, but for that we need a
> key; one idea for a key is the PSK:
> 
>       IV := AES-128-CBC-MAC(PSK, M)
> 
> This is not ideal, however, because PSK would be used in two different
> ways --once for hashing and a second time for key derivation--and
multiple
> usages of a single key is almost always a bad idea. While reuse in
this
> case may appear benign on first glance, why should we bother with an
> approach that will require a tricky analysis to confirm that it is
indeed
> safe? A variant would be to use some "well-known" key as the CBC-MAC
key,
> although this key would always be block cipher dependent:
> 
>       K := 00000000000000000000000000000000 (* AES dependent key! *)
>       IV := AES-128-CBC-MAC(K, M)
>
> In either case, the "hashing" scheme relies on the assumption that a
block > cipher in CBC-MAC mode is a pseudo-random function, so the
resulting
> output should be collision resistant for each pair of identities and
> length (at least if we construct M properly). If you prefer, use OMAC1
> mode instead of CBC-MAC. Relying on CBC-MAC for hashing is an
egregious
> but probably effective hack.
>
> A second way to compute IV might be to Davies-Meyer hash M under
AES-128:
>
>       Partition M = M1 M2 ... Mn into 128 bit blocks
>       H := 00000000000000000000000000000000
>       for i = 1 to n do
>               H := AES-128-Encrypt(Mi, H) XOR H
>       IV := H
>

Yesterday while paging through the proceedings of EUROCRYPT 2005 from
last week, I ran across a gem of a paper by Black, Cochran, and
Shrimpton [1] that is relevant to this discussion. In it they prove that
we cannot get collision resistance out of a block cipher based hashing
construction cheaply; something like the Davies-Meyer construction is
the most efficient you can hope for. Since we need collision resistance
here, their result rules out my first suggestion, and leaves us with
only something like the second as viable.

I don't think this is a big deal for hashing the identities in IV,
because that calculation is done only once, during the configuration of
the long-lived keys. I suggested the same pair of algorithms again for
hashing RAND_S and RAND_P at the beginning of each session, and there
the expense is too great:

> Returning to the trust assumption, the peer has to assume that the
server
> will generate a different RAND_S on every instance of the protocol. We
> will see in the protocol analysis this is not a good
assumption--replay
> attacks are feasible against the peer--and indeed, it is unnecessary.
It
> is almost always a good idea to remove unnecessary assumptions when we
can.
> We could perhaps remove the trust assumption about RAND_S by again
hashing
> together RAND_S and RAND_P to obtain the RB value to use, e.g.:
> 
>       RB := AES-128-CBC-MAC(0^128, RAND_S || RAND_P || 0^117 || 0x480)
> 
> using the CBC-MAC hashing method with a 0 key, or
> 
>       H := 00000000000000000000000000000000
>       H := AES-Encrypt-128(RAND_P, H) XOR H
>       H := AES-Encrypt-128(RAND_S, H) XOR H
>       RB := AES-Encrypt-128(0^117 || 0x480, H) XOR H
> 
> using Davies-Meyer hashing. Etc.

Davies-Meyer hashing is too expensive when done this way, because it
costs three key schedule initializations. However, since the CBC-MAC
hack won't work by the Black-Cochran-Shrimpton result, we either have to
forgo the function or else live with a performance penalty or else live
with only one of the RAND-x's as input to the session key derivation.

A computationally better alternative might be a different hack, e.g.:

        RB := AES-128-Encrypt(RAND_S, RAND_P) XOR RAND_P

This requires only one key schedule initialization, during session
initialization, which ought not be too onerous. This provides genuine
collision resistance (if the underlying block cipher is secure). This
does not mix the length into RB, but it is difficult to believe a prefix
attack on this construction is possible, because it hashes the minimum
amount of data (a single block) as it is.

References

[1] J. Black, M. Cochran, and T. Shrimpton, "On the Impossibility of
Highly-Efficient Blockcipher-Based Hash Functions," EUROCRYPT 2005, pp
526-541