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

[David Hopwood <david.hopwood@zetnet.co.uk>]

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

John Viega wrote:
> 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.

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

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

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

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

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 <david.hopwood@zetnet.co.uk>

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


-----BEGIN PGP SIGNATURE-----
Version: 2.6.3i
Charset: noconv

iQEVAwUBPn7s6zkCAxeYt5gVAQEEfAf/b8XvssotoZLVuecea3zOGBx20R9C3vgM
5ejMQn8nEmQhKwVypHexpl2sASnaTQLMVw9biC/J3GxUqY9zajeqnfCf4I4VOYaS
AiDrLfRpAuEFdlVgeUb/X5vIUjFDqYc1H3DRjjRtUgGlAJngayxOsd18cW5qvDei
4o3apSMghnJIdjjTkUOt5+J8+tlgUOI7PBikVS5uTVkEGRa1dgTFWiwHkEqdMbHD
LkCXrKljtMI1rQVV7t4OLLpTXUXRWCFhNuff4IgqSbkA1Nf9nGsB86fT35e/5lEr
060y8TaJnx90pDSIvTSJzKKXosqz3w9GicbG+2mNwQkOWE1BnCzgnw==
=QIGi
-----END PGP SIGNATURE-----
_______________________________________________
Cfrg mailing list
Cfrg@ietf.org
https://www1.ietf.org/mailman/listinfo/cfrg