Take the 2-minute tour ×
Information Security Stack Exchange is a question and answer site for Information security professionals. It's 100% free, no registration required.

Narrow pipe hash function designs have recently come under fire, particularly in reference to some SHA-3 candidates. Is this criticism valid? Can it be explained more simply than this paper does?

I'm curious because I want to know if this is a criteria by which old hash functions can be evaluated as well.

share|improve this question
    
Apparently asking this question at 3am in the morning PDT is not the best way to get an answer. :-) –  Omnifarious May 22 '11 at 16:47
    
Although there are some cryptographers here, I think that math.stackexchange.com would be more appropriate for this question. –  john May 22 '11 at 18:55
1  
@john, in my humble opinion, this is a perfectly reasonable place to ask. I'd bet there are more folks with knowledge of applied cryptography here than on math.stackexchange.com. –  D.W. May 23 '11 at 0:15
    
@D.W. Since we have Thomas all is OK. But I would argue that a question about hash function internals is more about hardcore theoretical cryptography, not applied. Anyway, the best fit would probably be area51.stackexchange.com/proposals/15811/cryptography when it comes live. –  john May 23 '11 at 0:22
    
@john, you might think so, but that's not my experience. I will tell you that (a) I know crypto well, (b) I've checked the math and CS theory stack exchanges for their crypto questions in detail, and (c) they are very much the wrong place to get good advice on this kind of question (about real-world crypto primitives). The quality of advice on cryptography here is much higher than on the math or CS theory stackexchanges. On the other hand, if the cryptography stackexchange does get created, I agree that will be a better place for this type of question. –  D.W. May 27 '11 at 6:10

1 Answer 1

up vote 4 down vote accepted

In a very strict and narrow view, the narrow pipe criticism is a valid attack, in that it shows that a hash function with a 256-bit output size and a "narrow pipe" (running state no larger than the output) offers, at most, the preimage resistance that could be achieved with a hash function with an output of 255.34 bits. On a more practical point of view, this has no consequence whatsoever on actual security. Gligoroski offered this paper as an argument for wide-pipe designs, in particular his own proposal for SHA-3, called Blue Midnight Wish.

Aumasson, one of the designers of BLAKE, another SHA-3 candidate (a narrow-pipe design), said that this attack was of the kind "my-pipe-is-bigger-than-yours" and was not very serious. It is however quite telling that among all the research result on the 14 second-round SHA-3 candidates, the narrow pipe criticism by Gligoroski is probably the best known attack -- which means that all 14 functions are, as far as we know, quite robust. One can also note that for the 3rd round of the SHA-3 competition, BLAKE was selected, but not BMW.

MD4, MD5, SHA-1, SHA-256 and SHA-512 are narrow-pipe designs and nobody misses a heartbeat on that fact.

The reason this attack works (for very low values of works) is that a random function is not likely to have a 1 -> 1 mapping of inputs to outputs if it's a truly random function. In fact, the way the math works out, a perfect random mapping would only produce 1 - 1/e of the possible output space. This works out to 0.632 or so, and since a little less than half the outputs won't happen, reduces the difficulty of finding a pre-image by a partial bit (a full bit would be if half the outputs wouldn't happen).

As you can see, this is purely theoretical and frankly rather silly.

share|improve this answer
    
This is a very reassuring answer. But I'm still curious as to why a narrow pipe design reduce the preimage resistance from 256 to 255.34 bits? –  Omnifarious May 22 '11 at 23:08
2  
@Omnifarious, it is a technical detail that is thoroughly irrelevant in practice. (Does anyone realise how ridiculously impossible it is to mount an attack of complexity 2^255.34?) The technical explanation has to do with the fact that a random function is unlikely to be a bijection, and in fact, a random function f:S->S likely hits only a 1-1/e = 0.632 fraction of the possible outputs. But this is a technical detail that 99.9% of hash function users can safely ignore. –  D.W. May 23 '11 at 0:14
    
@D.W. - I agree that it's a nit-picky technical detail that is thoroughly irrelevant in practice. But details like have the habit of showing up in other contexts in which they are not relevant. This whole thing really irritates me. When I'm told I want to understand, I'm given a little pat on the head and told "you don't need to know kid". Well, how do people go from not knowing anything to being cryptographers except by asking questions and getting complete explanations? –  Omnifarious May 23 '11 at 5:29
    
I've submitted an edit that adds a simple explanation of the mathematics behind the paper. Once the edit is approved, I will accept the answer. –  Omnifarious May 23 '11 at 5:46
    
@D.W.: I'm not irritated with you. Thank you for the answer. I'm irritated in general with the kind of response I get to cryptography related questions. Your answer (in a comment no less) was the only answer on either this site or math.stackexchange.com that helped me understand what was going on. And I've had similar experiences (and even less helpful answers) for the other cryptography related question. –  Omnifarious May 27 '11 at 14:20

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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