Symmetric ciphers as hash functions

[Steven M. Bellovin]

In message <d4f1333a0510312333k44e882e7l75adbff3a12b02c3 at mail.gmail.com>, "Trav
is H." writes:
>> How does one properly use a symmetric cipher as a cryptographic hash
>> function? I seem to be going around in circles.
>
>Isn't this is like asking a mechanic how to use a screwdriver as a hammer?

Given that we seem to know much more about block cipher design than 
hash function design, finding a hash function that is provably as 
strong as a block cipher is a great idea.
>
>> Reversing the situation (using the data as the key and a known plain-
>> text) makes a plaintext attack seem like a joy etc..
>
>This is exactly how traditional Unix crypt(3) implementations used
>DES, although they used a null string as the input and added some salt
>to prevent dictionary attacks.  What exactly do you mean by "plaintext
>attack"?  If we choose the plaintext, then we can compute the hash...
>what's the problem?  All hashes I can think of work this way.
>
>Incidentally, does anyone know how crypt(3) used salt, and why it used
>so little instead of using a 64-bit IV in some mode with feedback?
>
Have you read the Morris and Thompson paper?  If not, see
http://citeseer.ist.psu.edu/morris79password.html

Briefly, though, the 12 bits of salt were used to permute the E-box in 
DES.  They limited the salt to 12 bits because there was little need for
any more.  The salt served three purposes: discouraging hardware attacks 
based on off-the-shelf DES chips; rendering precomputed dictionaries 
prohibitively expensive; and forcing an attacker to attack individually each 
password in a file.  If you have 500 passwords -- a lot for 1978 -- and 
4K choices, the odds are high that you won't get much overlap in salt 
space.  Even with 15K entries, a high figure even today, you're not going
to increase the attacker's work factor by more than a few bits.  As for 
the dictionary size -- they felt (probably correctly) that the size 
expansion was already large enough that that wasn't a feasible path for 
the attacker.

		--Steven M. Bellovin, http://www.cs.columbia.edu/~smb



---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com