Talk:Hash functions based on block ciphers

From Wikipedia, the free encyclopedia

This article is part of WikiProject Cryptography, an attempt to build a comprehensive and detailed guide to cryptography in the Wikipedia. If you would like to participate, you can choose to edit the article attached to this page, or visit the project page, where you can join the project and see a list of open tasks.

Contents 1 Attack on Davies-Meyer 2 Comparisons? 3 Merkle-Damgård image 4 Might be enough to write like an encyclopedia

[edit] Attack on Davies-Meyer

Ok, the merge of several other articles into this one is done, sort of. There is some more information in the old Davies-Meyer article about an attack that I did not merge since I did not understand it. If I just cut and paste that paragraph it will make even less sense since it depends on the notification established further up in the old article and I have changed that notification in this article. So for now I left the old Davies-Meyer article as it is (not turned it into a redirect). I left a note about it and link to it in the Davies-Meyer section of this article. I hope some one can make sense to it and rewrite it properly and merge it some day. --David Göthberg 06:05, 28 January 2006 (UTC)

The fixed point attack that I removed from the old Davies-Meyer article keeps coming back. That attack is not at all “easy” as some claim but requires exponential time (2^block size). The fixed point can be found easily only if the used block cipher has been already broken - and is easily broken. If the block cipher is secure then the Davies-Meyer is secure. Atwater 19:00, 21 July 2006 (UTC) Atwater

According to Bruce Schneier this "is not really worth worrying about"[4] He probably meant in practice, this is not worth worrying about. In the Eurocrypt 2005 paper with Kelsey, Schneier DOES use the fixpoint attack to show that the MD construction is far from being a random oracle, and so in a sense more brittle than one would wish it to be. However their attack is completely impractical because to be effective, it requires gigantic messages. 71.142.222.181 19:04, 9 March 2007 (UTC)

[edit] Comparisons?

I'm curious if one of these methods is preferred to another in general, or under certain circumstances. Are there certain applications where one method is more appropriate than another? 150.135.65.20 19:05, 30 January 2006 (UTC)

Well, I am not a crypto analyst but my gutt feeling is that of the three methods described in the article so far the last one (Miyaguchi-Preneel) is the most secure.

However, a slight modification of it might be twice as fast in some cases and perhaps about as secure. Many block cryptos today take keys twice the size of their block size, say 256-bit keys and 128-bit block size. So instead doing like in Davies-Meyer would be twice as fast. That is, to feed the messages blocks (m) as keys (256 bits at a time) and the previous hash (H) as cleartext to be encrypted. But you could still XOR in both m an H onto the output like in Miyaguchi-Preneel since that seems more robust then Davies-Meyer.

But note that many cryptos only have 64-bit block size and with the methods so far described in the article thus only produces 64-bit hashes which is far to short to be secure for most needs. Also note that even 128-bit hashes (produced by 128-bit block cryptos) might be to short to be fully secure. Thankfully there is methods to make for instance 256-bit hashes out of block cryptos that has the block size of 128-bit. Two such methods are MDC-2 and MDC-4. MDC-4 seems to be the most secure of all methods I have seen so far but also the slowest. We will probably add those methods to the article some day. (Much work to be done...)

If you don't want to wait until we added MDC-2 and MDC-4 to the article you can read about them in the Handbook of Applied Cryptography. You can follow that link and freely and legally download the book as pdf-files! Chapter 9, page 342 describes MDC-2 and MDC-4 in detail.

--David Göthberg 10:07, 2 February 2006 (UTC)

Thanks a lot! --JeffryJohnston 00:36, 3 February 2006 (UTC)

[edit] Merkle-Damgård image

I took the liberty to revert to the first image. (The colourful one made by me but which really is only a slight extension of Matt_Crypto's old version.) Note that the other pictures on this page on purpose is colourmatched with this image (yellow boxes) to make it clearer where they fit in the Merkle-Damgård structure. I have tested the different images on the chatters in #crypto on irc.freenode.net and they prefered the colourful version. --David Göthberg 08:10, 6 March 2006 (UTC)

Your version certainly looks nicer. I don't suppose you could tweak it to show the padding as in Mangojuice's diagram? — Matt Crypto 08:43, 6 March 2006 (UTC)

Ok, since both of you seem to want it like that I'll give it a shot. I am also thinking of removing the pink balls around IV and HASH and only use text for them. I'll see how that looks. (Sorry Matt, but I think that might look better.) Oh, and I should mention that last week I read through the source code of about 10 different hash functions and discovered that most do not use a finalisation function. (Apart from doing the "100..." + length padding of course.) But since some use it I think I will keep the finalisation function box but mention in the text of the Merkle-Damgård article that only some hashes use a finalisation function. But I will still have the length padding fed to a separate compression function, since length padding within the last message block is just a speed optimisation that not all hashes use and that optimisation I think I explain well in the length padding example in the Merkle-Damgård article. --David Göthberg 10:18, 6 March 2006 (UTC)

[edit] Might be enough to write like an encyclopedia

"The resulting hash size is big enough. 64-bit is too small, 128-bit might be enough."

What does this mean? What are the criteria? If your 128-bit key is secure, shouldn't it require 2^64 operations to find even a collision? Why isn't that big enough? Or is there something being left unsaid about how secure the block based ciphers are?