This article is rated C-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | ||||||||||||||
|
I just read through source code for about ten of the more well known hash algorithms. It seems they do not work exactly as I thought. That is, there are some factual errors in this article. (All my fault, I inserted those errors.) I will correct those errors in the article after I thought a bit more about it and done some checking in my books. -- David Göthberg 19:31, 22 February 2006 (UTC)
How about "Merkle-Damgård hash construction"?
I originally choose the name "Merkle-Damgård construction" for this article since that is what Handbook of Applied Cryptography by Menezes & Co calls it. (Note that Merkle-Damgård strengthening just means the length padding, not the whole construction.)
User:Mangojuice changed it to "Merkle-Damgård hash function". I agree that using the term "hash" in the name is very nice. But in itself it is not a hash function. It only becomes a hash function when used together with a compression function. Of course hash functions that use Merkle-Damgård (just about all hash functions out there) are "Merkle-Damgård hash functions". So perhaps we should use the name "Merkle-Damgård hash construction" or "Merkle-Damgård hash construct"? Oh, and is there any difference in meaning between "construction" and "construct"? As far as I can understand from the dictionaries I have both can be used in this case.
-- David Göthberg 11:13, 6 March 2006 (UTC)
References 1 and 2 are dated 1989, but Merkle used the construction in his 1979 Ph.D. thesis (see http://www.merkle.com/papers/Thesis1979.pdf, chapter 2). Unless there's a reference to something earlier than 1979, Merkle's thesis would be the first use (and the text should be changed accordingly). —Preceding unsigned comment added by 68.209.119.202 ( talk • contribs) 05:53, 28 May 2006
In the example, both the length and a terminating '1' are used. If the length is given then surely the terminator is unnecessary. Perhaps it could be either changed or a note added explaining why both are required if it is so. penagate [ talk| contribs 08:55, 26 June 2008 (UTC)
Aren't points 1 and 3 equivalent or a subset/superset of the other? 87.254.83.229 ( talk) 03:36, 23 December 2008 (UTC)
Since I am not in the mood and currently don't have the time to edit the article itself, here goes:
I disagree with parts of the content in the new "Wide pipe construction" section in this article:
-- David Göthberg ( talk) 07:24, 24 July 2011 (UTC)
Though having a basic familiarity with hash functions, I went to Wikipedia to brush up on the Merkle-Damgard construction. Two aspects of the current diagram
(which also appears in the article on cryptographic hash functions) at first confused me. The n'th message block is depicted as the same length as all the others, when in fact it is usually shorter; and the two upper rows, with arrows going e.g. from block 1 to block 1 below, made me think some processing of contents was happening, rather than a no-op. Though lacking the nice colors, the former diagram
is free of the first of these confusing features, and in addition nicely indicates the compression of the data by using trapezoids to represent the compression function. The present figure is visually nicer, and available in different resolutions, so the best thing would be to redraw it to 1) eliminate the top row, 2) represent message block n by a visibly shorter rectangle, and 3) use trapezoids to indicate compression. I would try to draw this myself, but lack the necessary skills. If someone undertakes revision of the drawing to incorporate some or all of these suggestions, here's another thing to consider. The construction of the padding is a rather subtle matter, depending on the length of the whole message, not just the last block. The fact that the padding depends on all the preceding blocks might be indicated graphically, e.g. by a large horizontally oriented brace symbol "}" at the top, spanning all n original message blocks, with a arrow labeled "MD-compliant padding" extending from the brace to the padding that extends the last block to the same length as the others. But this may be more trouble than it's worth, because the text example explains it so well, and my suggested drawing would not capture cases where the original last block is only slightly too short, causing the padding to overflow into an n+1'st block. CharlesHBennett ( talk) 14:43, 15 September 2015 (UTC)
Not long ago there was a flurry of methods for producing collisions in MD5 (and others), a once popular hash function that uses the MD construction. These were perfected to the point that a modest laptop took only some minutes to find instances of colliding messages, and led to the mandatory deprecation of MD5 for, basically, all new applications. Now, IIRC, these methods all worked by finding 2 pairs of consecutive message blocks (say, A:B and A':B') such that any differences between the intermediate hash values after blocks A and A' were nullified after blocks B and B', respectively. That is, roughly, one had H(A:B)==H(A':B') even though H(A)!=H(A'), meaning, this method found collisions in the full hash function without giving any hint of an instance of a collision for the compression function. Doesn't this conflict with what is claimed in Merkle's thesis, namely, that a secure compression function plus the MD construction generates a secure hash? As far as i see it, the only way to reconcile these 2 facts is to admit that MD5's compression function has thus been proven to be insecure, even though nobody knows of a single instance of compression-function collision, nor any way to obtain it that is better than the birthday attack (which must work against all functions). Or am i misunderstanding something here? — Preceding unsigned comment added by 89.180.144.158 ( talk) 21:02, 1 February 2017 (UTC)
After reading the CWI site referenced in the paragraph about the Nostradamus, or 'herding' attack, i decided to change said paragraph because the previous version (which alluded to 'committing to an output h') might mislead the reader into thinking that significant progress had been made in finding preimages for MD5, as 'output' usually refers to the final result of the hash calculation. I believe the altered version to be both significantly more descriptive and more correct. — Preceding unsigned comment added by 89.180.151.104 ( talk) 21:53, 1 February 2017 (UTC)
The first source has a broken link 46.114.111.156 ( talk) 07:49, 23 February 2022 (UTC)
This article is rated C-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | ||||||||||||||
|
I just read through source code for about ten of the more well known hash algorithms. It seems they do not work exactly as I thought. That is, there are some factual errors in this article. (All my fault, I inserted those errors.) I will correct those errors in the article after I thought a bit more about it and done some checking in my books. -- David Göthberg 19:31, 22 February 2006 (UTC)
How about "Merkle-Damgård hash construction"?
I originally choose the name "Merkle-Damgård construction" for this article since that is what Handbook of Applied Cryptography by Menezes & Co calls it. (Note that Merkle-Damgård strengthening just means the length padding, not the whole construction.)
User:Mangojuice changed it to "Merkle-Damgård hash function". I agree that using the term "hash" in the name is very nice. But in itself it is not a hash function. It only becomes a hash function when used together with a compression function. Of course hash functions that use Merkle-Damgård (just about all hash functions out there) are "Merkle-Damgård hash functions". So perhaps we should use the name "Merkle-Damgård hash construction" or "Merkle-Damgård hash construct"? Oh, and is there any difference in meaning between "construction" and "construct"? As far as I can understand from the dictionaries I have both can be used in this case.
-- David Göthberg 11:13, 6 March 2006 (UTC)
References 1 and 2 are dated 1989, but Merkle used the construction in his 1979 Ph.D. thesis (see http://www.merkle.com/papers/Thesis1979.pdf, chapter 2). Unless there's a reference to something earlier than 1979, Merkle's thesis would be the first use (and the text should be changed accordingly). —Preceding unsigned comment added by 68.209.119.202 ( talk • contribs) 05:53, 28 May 2006
In the example, both the length and a terminating '1' are used. If the length is given then surely the terminator is unnecessary. Perhaps it could be either changed or a note added explaining why both are required if it is so. penagate [ talk| contribs 08:55, 26 June 2008 (UTC)
Aren't points 1 and 3 equivalent or a subset/superset of the other? 87.254.83.229 ( talk) 03:36, 23 December 2008 (UTC)
Since I am not in the mood and currently don't have the time to edit the article itself, here goes:
I disagree with parts of the content in the new "Wide pipe construction" section in this article:
-- David Göthberg ( talk) 07:24, 24 July 2011 (UTC)
Though having a basic familiarity with hash functions, I went to Wikipedia to brush up on the Merkle-Damgard construction. Two aspects of the current diagram
(which also appears in the article on cryptographic hash functions) at first confused me. The n'th message block is depicted as the same length as all the others, when in fact it is usually shorter; and the two upper rows, with arrows going e.g. from block 1 to block 1 below, made me think some processing of contents was happening, rather than a no-op. Though lacking the nice colors, the former diagram
is free of the first of these confusing features, and in addition nicely indicates the compression of the data by using trapezoids to represent the compression function. The present figure is visually nicer, and available in different resolutions, so the best thing would be to redraw it to 1) eliminate the top row, 2) represent message block n by a visibly shorter rectangle, and 3) use trapezoids to indicate compression. I would try to draw this myself, but lack the necessary skills. If someone undertakes revision of the drawing to incorporate some or all of these suggestions, here's another thing to consider. The construction of the padding is a rather subtle matter, depending on the length of the whole message, not just the last block. The fact that the padding depends on all the preceding blocks might be indicated graphically, e.g. by a large horizontally oriented brace symbol "}" at the top, spanning all n original message blocks, with a arrow labeled "MD-compliant padding" extending from the brace to the padding that extends the last block to the same length as the others. But this may be more trouble than it's worth, because the text example explains it so well, and my suggested drawing would not capture cases where the original last block is only slightly too short, causing the padding to overflow into an n+1'st block. CharlesHBennett ( talk) 14:43, 15 September 2015 (UTC)
Not long ago there was a flurry of methods for producing collisions in MD5 (and others), a once popular hash function that uses the MD construction. These were perfected to the point that a modest laptop took only some minutes to find instances of colliding messages, and led to the mandatory deprecation of MD5 for, basically, all new applications. Now, IIRC, these methods all worked by finding 2 pairs of consecutive message blocks (say, A:B and A':B') such that any differences between the intermediate hash values after blocks A and A' were nullified after blocks B and B', respectively. That is, roughly, one had H(A:B)==H(A':B') even though H(A)!=H(A'), meaning, this method found collisions in the full hash function without giving any hint of an instance of a collision for the compression function. Doesn't this conflict with what is claimed in Merkle's thesis, namely, that a secure compression function plus the MD construction generates a secure hash? As far as i see it, the only way to reconcile these 2 facts is to admit that MD5's compression function has thus been proven to be insecure, even though nobody knows of a single instance of compression-function collision, nor any way to obtain it that is better than the birthday attack (which must work against all functions). Or am i misunderstanding something here? — Preceding unsigned comment added by 89.180.144.158 ( talk) 21:02, 1 February 2017 (UTC)
After reading the CWI site referenced in the paragraph about the Nostradamus, or 'herding' attack, i decided to change said paragraph because the previous version (which alluded to 'committing to an output h') might mislead the reader into thinking that significant progress had been made in finding preimages for MD5, as 'output' usually refers to the final result of the hash calculation. I believe the altered version to be both significantly more descriptive and more correct. — Preceding unsigned comment added by 89.180.151.104 ( talk) 21:53, 1 February 2017 (UTC)
The first source has a broken link 46.114.111.156 ( talk) 07:49, 23 February 2022 (UTC)