Talk:One-way compression function: Difference between revisions

Revision as of 00:21, 29 August 2006

Latest revision as of 05:47, 4 February 2024

(19 intermediate revisions by 12 users not shown)

Line 1:

{{WikiProject banner shell|class=C|

{{CryptographyProject}}

{{WikiProject Cryptography |importance=Top |computer-science-importance=high}}

}}

== 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 [[Davies-Meyer hash|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. --[[User:Davidgothberg|David Göthberg]] 06:05, 28 January 2006 (UTC)

::''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. [[User:71.142.222.181|71.142.222.181]] 19:04, 9 March 2007 (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. [[User:Atwater|Atwater]] 19:00, 21 July 2006 (UTC) Atwater

My earlier statement (which I now have removed from this discussion) that the finding of a fixed point requires “exponential time” was not correct: fixed point can be easily found for a Davies-Meyer construction. The correct way is to say that fixed points do not enable the attacker to go below the birthday paradox bound (2^n/2 time) when Merkle-Damgård (MD) strengthening (bitlength of the message is appended at its end) is used. However the fixed points enable a slightly more efficient second preimage attack than a Merkle-Damgård construction whose f-function does not provide easy calculation of fixed points. The Kelsey and Schneier attack applies to every Merkle-Damgård construction, not just the Davies-Meyer. For Davies-Meyer (using fixed points) to attack a 2^k-message-block message the attack requires 3 x 2^n/2+1+2^n-k+1 time which does not go below the birthday paradox (2^n/2) limit. If fixed points are not used i.e. the construction is other than Davies-Meyer (e.g Matyas-Meyer-Oseas, Miyaguchi-Preneel) then this attack can be done in k x 2^n/2+1+2^n-k+1 time. Note that when messages get shorter the complexity of the attack approaches 2ⁿ.[[User:Atwater|Atwater]] ([[User talk:Atwater|talk]]) 16:24, 19 February 2009 (UTC)

== Comparisons? ==

Line 16 ⟶ 20:

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

The [[Skein (hash function)]] designers specifically chose "Matyas-Meyer-Oseas" over "Davies-Meyer".

Page 44 of [http://www.schneier.com/skein1.1.pdf "The Skein Hash Function Family"] briefly gives a couple of reasons.

Do any of those reasons apply to the "Miyaguchi-Preneel" arrangement?

Could someone explain those reasons in this article? --[[Special:Contributions/68.0.124.33|68.0.124.33]] ([[User talk:68.0.124.33|talk]]) 15:02, 1 December 2008 (UTC)

== Merkle-Damgård image ==

Line 30 ⟶ 39:

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?

--[[User:72.18.229.146|72.18.229.146]] 00:21, 29 August 2006

:Because the most powerful computing systems available to some organisations nowadays probably can do about 2⁶⁴ operations. Thus a 128-bit hash might not be secure against such powerful adversaries. And in some cases you want your hash to be secure say at least 10 years into the future too. If you want to read more you can for instance read the ''[http://www.cacr.math.uwaterloo.ca/hac/ Handbook of Applied Cryptography]'' that we link to in the references. You can follow that link and freely and legally download the book as pdf-files. --[[User:Davidgothberg|David Göthberg]] 19:46, 10 June 2007 (UTC)

== What is E? ==

I see a function E() in the equations, but I can't figure out from the context what this function is. Could someone fill it in more completely? [[User:mbset]] 13:50, 9 June 2007

:E() is the encrypt function of the block cipher used. So <math>E_{m}{(H)}</math> means to encrypt the data "H" and use the key "m". --[[User:Davidgothberg|David Göthberg]] 19:46, 10 June 2007 (UTC)

== Article move ==

I moved this article from [[Hash functions based on block ciphers]] to [[One-way compression function]] since that is what this article really is about. The [[Merkle-Damgård hash function]] article takes care of the rest of the description of how compression functions are used to build hashes. --[[User:Davidgothberg|David Göthberg]] 04:52, 26 July 2007 (UTC)

== If "the block cipher is secure" ==

What in the world does this statement mean? It makes the entire article rather confusing. Do we mean "If the block cipher is ideal"? I'm not even sure that statement holds w.r.t. all of these constructions. This needs to be fixed, removed, elaborated on. Any suggestions?

: I've made some small changes. Not sure if the black box model and the ideal cipher model are exactly the same. Similar to the random oracle model there exist some (contrieved?) constructions that are secure in the ideal cipher model, but not secure with any instantiation of a block cipher, hence showing that the "ideal cipher world = real world" assumption cannot be made in general. [[Special:Contributions/85.2.78.238|85.2.78.238]] ([[User talk:85.2.78.238|talk]]) 08:10, 19 November 2007 (UTC)

: I'm not yet satisfied with my changes, but are looking for some specific references. In particular, in order to get a secure hash function the block cipher needs some properties that would not be necessary to just make encryption secure. [[Special:Contributions/85.2.78.238|85.2.78.238]] ([[User talk:85.2.78.238|talk]]) 08:46, 19 November 2007 (UTC)

== Ciphers with Expensive Key Setup ==

Might be useful to note that block ciphers with expensive key setup (e.g. [[Twofish]]) do not interact well with any of these constructions because the key setup must be done once for every message block. [[User:Aragorn2|Aragorn2]] ([[User talk:Aragorn2|talk]]) 11:31, 12 June 2019 (UTC)