3 ms·
> there may be some hash functions for which H(concat(a, a)) = F(H(a)) I'll give a shot at why this implies that H is not a secure hash function, though I coul
by okbake 12y ago
> there may be some hash functions for which H(concat(a, a)) = F(H(a))
I'll give a shot at why this implies that H is not a secure hash function, though I could be wrong. The outputs of a secure hash function should be randomly distributed across the set of all possible outputs. If H is a secure hash function that outputs a value in the set {0,1}^128 (a 128 bit output), then H(a) and H(a+a) should both be 128 bit outputs whose mapping are indistinguishable from values chosen truly at random from this set. Although there is a discernable pattern in the two inputs to H (the concatenation), there should be no discernable pattern in the two outputs of H that you could use to reliably map H(a) to H(a+a) for any given a.
- dllthomas 12y agoI don't think this follows. "Random output" is an idealized model that no actual, specific hash function achieves. I already said that having such an F would worry me, but "if F is computable, H is not secure" is a strong statement and I'm wondering whether it's backed up by math, not-quite-math-but-good-reasoning, or handwavy bluster. Please don't take this as an attack, though - I appreciate the attempt!
- bmm6o 12y agoI don't think I'm able to make a much more rigorous argument, but I will note that you seem to be applying two different criteria here. If you want to criticize modeling a hash function as a PRF as too idealized, then you aren't going to get a mathematical answer (since it will start with "let H be a PRF").
- dllthomas 12y agoA maximally strong mathematical answer is showing that given that F and H(a), we can reconstruct too much about a, for any H and corresponding F. There are probably other similarly strong forms of argument - I'm not saying that's the only one - but you can see how it differs from "Well, it's just not random."