I'm learning more about the Merkle–Damgård construction, including its "alternatives".

I think I know how the Wide Pipe construction works, but am confused about the different images being used online.

Wikipedia uses this one, which has two lines going through the compression function. However, this one, scroll down to "Alternatives to Merkle-Damgård" and this one, scroll down to "The Wide-Pipe Hash: A Modified MD Hash" use an image which has just 1 line going through.

Why do the images look that different? Is one or the other simply wrong, or is there something I'm missing?

  • 1
    $\begingroup$ Could you clarify what exactly it is you are asking? Should I answer "yes, someone knows more about this"? :) $\endgroup$ – otus Jan 8 '17 at 8:09
  • $\begingroup$ I tried to make the question more clear. I'm wondering why the images I showed look that different from each other. I also don't understand the difference between the narrow pipe construction and the FWP construction. And I was wondering if someone has any sources stating the inventors of some of the schemes of one-way compression functions from block ciphers. $\endgroup$ – Cartman123 Jan 8 '17 at 12:04
  • $\begingroup$ Those are separate questions and should therefore be asked separately. Note that you'd also have a better chance of a good answer that way, score more points etc. Currently I think the question is too broad, for instance targeting multiple schemes. $\endgroup$ – Maarten Bodewes Jan 8 '17 at 12:57
  • 2
    $\begingroup$ I edited the post to include just one question, hope it narrows it down. $\endgroup$ – Cartman123 Jan 8 '17 at 13:15
  • 1
    $\begingroup$ Great. If you feel that one of the other questions also need an answer, don't hesitate to ask. Sometimes we do accept multiple questions but those need to be closely related (basically: if you suspect that it requires additional knowledge above what is asked for the main question, please separate or layer the questions). $\endgroup$ – Maarten Bodewes Jan 8 '17 at 15:58

If you're comfortable with the reasons for alternative pipe construction I won't reiterate them.

Yes you're missing something, but it's not cryptographic. It's just that informative artwork and graphic design is not the usual cryptographer's skill set. So they bodge it as best they can. So single lines can represent many things. Sometimes they can mean a standard MD width of interim hash passing through, and sometimes they represent twice the width. The feature that gives it away is the finalisation function /output compression function. If one of these exists, it suggests (graphically) that the interim hash width exceeds the input /output block widths and has to be reduced.

I understand your confusion. Figure 3 of your The Wide-Pipe Hash: A Modified MD Hash seems to show yet another alternative type of wide pipe that you might call staggered. This is my nomenclature for it as it's not specifically named, but I wouldn't call it standard wide pipe. It seems to show iterated compression functions of input width IV + message and IV width output. It's almost the fast wide pipe compression function mirrored.

The designers randomly try all sorts of weird stuff in order to improve the security of the total hash. It's called incremental development and that's how things evolve. So some of your examples are slightly different in form. They just sometimes draw /explain it very badly but then they're not graphical artists. Your wiki example doesn't name the wide pipe hash, so we don't know what the compression function is. It is entirely possible that it keeps IV compression and message block compression entirely separate until finalisation. But it's a clip art style image and not very detailed. Between subtle variations on which bit is wider than the output block width and bad drawing, it's hard to figure it out.

| improve this answer | |
  • 1
    $\begingroup$ [I deleted a previous comment to be more clear] What do you mean with "Your wiki example doesn't name the wide pipe hash"? As you can see here, they are definitely talking about the wide pipe construction. $\endgroup$ – Cartman123 Jan 25 '17 at 16:57
  • 1
    $\begingroup$ But the main difference I'm seeing between the images is that the image of wikipedia uses 2 IV's, while the other images use just 1 IV. I don't see a difference between thisimage (wide pipe), and this one (MD). Is it simply that the IV of the WP images are larger? Meaning that the IV in the image of WP might be 2 times the IV of the IV in the MD image. $\endgroup$ – Cartman123 Jan 25 '17 at 17:00
  • $\begingroup$ @Cartman123 Wiki doesn't say how wide though. Different hashes (such as Haifa) have different IV widths. Your Alternatives to Merkle-Damgård hash has a single IV but it could be 128 bits wide couldn't it? I don't think that you can categorically state that a thin black line in cryptography represents a certain bit width. Two lines could mean twice the message bit width, or two IV's propagating through the hash. It only crystallises for a specifically named hash. $\endgroup$ – Paul Uszak Jan 26 '17 at 13:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.