Re: Strong PRNG with AES or 3-DES

John Kelsey (kelsey@plnet.net)
Mon, 10 Aug 1998 02:03:09 -0500

• Next message: Ben Laurie: "Re: Strong PRNG with AES or 3-DES"
• Previous message: John Kelsey: "Re: Strong PRNG with AES or 3-DES"
• Maybe in reply to: Bob Baldwin: "Strong PRNG with AES or 3-DES"

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

[ To: CodherPlunks ## Date: 08/09/98 ##
  Subject: Re: Strong PRNG with AES or 3-DES ]

>Date: Fri, 7 Aug 1998 14:06:53 -0700 (PDT)
>From: bram <bram@gawth.com>
>cc: CodherPlunks@toad.com
>Subject: Re: Strong PRNG with AES or 3-DES

>Don't the techniques for building hashes from block ciphers
>open them up to completely different kinds of attacks, thus
>making reckless transformation of one into the other not a
>good idea?

Sort-of. The general Davies-Meyer mode for building hashes
from block ciphers allows the attacker to control the key
value, but not the plaintext value. If the block cipher was
designed with a lot of concern for chosen-plaintext attacks,
but no concern about related-key attacks, then you can have
big problems. (GOST, TEA, and 3-Way are good examples of
this.)

Collision-finding attacks amount to trying to find some pair
of keys that cause a zero difference in the output of the
cipher for some specific, known input to the cipher. (An
attacker can't *choose* the plaintext to the cipher, but he
can choose the previous message blocks. If he can afford
2^n trial hashes, he can generate 2^n different plaintexts,
and use the one that is most suited to his chosen-key
attack. (Note that hash function attacks are chosen-key
attacks, not just related-key attacks. The attacker gets to
choose the whole key.)

I think if a block cipher is designed to resist that kind of
attack, it's reasonable to use it in Davies-Meyer mode to
build a hash function. Most of the AES submissions I have
looked at have reasonably strong key schedules, though I am
not sure how well they will do against actual chosen-key
attacks. We designed Twofish to resist related-key attacks,
but I am not sure there aren't chosen-key attacks against
it.

It's worth noting that 128-bit block ciphers won't give you
a sufficiently strong hash function in Davies-Meyer mode,
even if there are no chosen-key attacks, since you end up
with a 128-bit hash function output, and thus a 2^{64}
collision-finding attack.

>-Bram

- --John Kelsey, kelsey@counterpane.com / kelsey@plnet.net
NEW PGP print = 5D91 6F57 2646 83F9 6D7F 9C87 886D 88AF

-----BEGIN PGP SIGNATURE-----
Version: 2.6.2

iQCVAwUBNc6cwCZv+/Ry/LrBAQEoTAP9EvqbdfTtQWGa/PTCQ2JuOvb/rBcl/DbD
RP2dAYmEoywSzV6Wq4dhqxlZKqCx0zEc2g+VqcFupKF1ofIOHzDP40HCY6NKR60+
87ItdoZafYzcNAuq3hMqYHEB3Dh4ygAWgLAdzhSoTzlj6wRjpqWQl1fELEMfHHOX
n5c1WcOd/w4=
=G2xV
-----END PGP SIGNATURE-----

--John Kelsey, kelsey@counterpane.com / kelsey@plnet.net
NEW PGP print = 5D91 6F57 2646 83F9 6D7F 9C87 886D 88AF

• Next message: Ben Laurie: "Re: Strong PRNG with AES or 3-DES"
• Previous message: John Kelsey: "Re: Strong PRNG with AES or 3-DES"
• Maybe in reply to: Bob Baldwin: "Strong PRNG with AES or 3-DES"