Re: Symmetric ciphers as hash functions
On 10/30/05, Arash Partow [EMAIL PROTECTED] wrote: How does one properly use a symmetric cipher as a cryptographic hash function? I seem to be going around in circles. The usual method is to feed the data into the key slot of the cipher, and to use a fixed IV in the plaintext slot. Then, add the IV to the output ciphertext. If the data is too big, break it up into pieces and chain these constructions together. The output of one block becomes the input IV of the next block. To prevent length extension attacks, pad with an unambiguous final suffix that includes the message length. This is basically the Merkle/Damgard construction. CP - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Symmetric ciphers as hash functions
Not so... the SHA family are all unbalanced Feistel structures. Sorry, I guess I am thinking of AES. I don't know where I got the doesn't need to be invertible bit, I must be conflating it with something else. He should also take a look at OCB, CCM, and CBC-MAC modes. Perhaps he intends to hide the hash inside the encryption, in which case he might be better off doing authentication+encryption. -- http://www.lightconsulting.com/~travis/ -- We already have enough fast, insecure systems. -- Schneier Ferguson GPG fingerprint: 50A1 15C5 A9DE 23B9 ED98 C93E 38E9 204A 94C2 641B - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Symmetric ciphers as hash functions
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? 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? Are there any papers/books/etc that explain the implementation/use of symmetric ciphers (particularly AES) as cryptographic hash functions? btw I know that hash functions and symmetric ciphers share the same structural heritage (feistel rounds etc...), I just don't seem to be making the usage link at this point in time... :D The latest hashes, such as SHA-1, gave up on Feistel. It's not necessary for the hash to be invertible, but OTOH there's no guarantee of the lack of collisions. -- http://www.lightconsulting.com/~travis/ -- We already have enough fast, insecure systems. -- Schneier Ferguson GPG fingerprint: 50A1 15C5 A9DE 23B9 ED98 C93E 38E9 204A 94C2 641B - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Symmetric ciphers as hash functions
At 01:33 2005-11-01 -0600, Travis H. wrote: The latest hashes, such as SHA-1, gave up on Feistel. Not so... the SHA family are all unbalanced Feistel structures. Basically, for SHA-1 a complex function of 4 words and key material (in this case expanded data to be hashed) is combined with the fifth word. The fact that the four words don't change is the giveaway that it's a feistel structure. The later SHAs have a more complicated structure, blurring the boundary a bit, but I'd still call them unbalanced Feistel. Greg. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Symmetric ciphers as hash functions
In message [EMAIL PROTECTED], 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 [EMAIL PROTECTED]
Re: Symmetric ciphers as hash functions
Travis H. [EMAIL PROTECTED] 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? Not in the least. Building new strong tools by using older tools that are known to be strong is part of the traditional cryptography mindset, and there is nothing remotely wrong with it, provided it works. If your attitude were correct, we wouldn't have constructs like HMAC, would we? Perry - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Symmetric ciphers as hash functions
Hi all, How does one properly use a symmetric cipher as a cryptographic hash function? I seem to be going around in circles. Initially I thought you choose some known key and encrypt the data with the key, using either the encrypted text or the internal state of the cipher as the hash value, turns out all one needs to do to break it, is decrypt the hash value with the known key and you get a value which will produce the same hash value. Reversing the situation (using the data as the key and a known plain- text) makes a plaintext attack seem like a joy etc.. Are there any papers/books/etc that explain the implementation/use of symmetric ciphers (particularly AES) as cryptographic hash functions? btw I know that hash functions and symmetric ciphers share the same structural heritage (feistel rounds etc...), I just don't seem to be making the usage link at this point in time... :D Any help would be very much appreciated. Kind regards Arash Partow Be one who knows what they don't know, Instead of being one who knows not what they don't know, Thinking they know everything about all things. http://www.partow.net - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Symmetric ciphers as hash functions
Tom Shrimpton (http://www.cs.pdx.edu/~teshrim/) does research in this area (ie. using block ciphers to build hash functions). See the papers on his web site; in particular: Black-Box Analysis of the Block-Cipher-Based Hash-Function Constructions from PGV [pdf] [ps] John Black, Phillip Rogaway, and Thomas Shrimpton -James Arash Partow wrote: Hi all, How does one properly use a symmetric cipher as a cryptographic hash function? I seem to be going around in circles. Initially I thought you choose some known key and encrypt the data with the key, using either the encrypted text or the internal state of the cipher as the hash value, turns out all one needs to do to break it, is decrypt the hash value with the known key and you get a value which will produce the same hash value. Reversing the situation (using the data as the key and a known plain- text) makes a plaintext attack seem like a joy etc.. Are there any papers/books/etc that explain the implementation/use of symmetric ciphers (particularly AES) as cryptographic hash functions? btw I know that hash functions and symmetric ciphers share the same structural heritage (feistel rounds etc...), I just don't seem to be making the usage link at this point in time... :D Any help would be very much appreciated. Kind regards Arash Partow Be one who knows what they don't know, Instead of being one who knows not what they don't know, Thinking they know everything about all things. http://www.partow.net - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED] - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
