3 ms·
No, you're still missing the point :) He's saying that SHA1'(m) = SHA1'(n) implies that SHA1"(m) = SHA1"(n). Let's do this with a very simple, silly hash func
by jibiki 17y ago
No, you're still missing the point :)
He's saying that SHA1'(m) = SHA1'(n) implies that SHA1"(m) = SHA1"(n).
Let's do this with a very simple, silly hash function.
Let h(x) = (x/2)%10 (in integer arithmetic, e.g, 5/2 = 2, so h(5) = (5/2)%10 = 2%10 = 2.) So then let h2(x) = h(h(x)) = (h(x)/2)%10, and h3(x) = h(h(h(x))) = (h2(x)/2) % 10.
Here's a table:
x: h h2 h3
0 0 0 0
1 0 0 0
2 1 0 0
3 1 0 0
4 2 1 0
5 2 1 0
6 3 1 0
7 3 1 0
8 4 2 1
9 4 2 1
10 5 2 1
11 5 2 1
12 6 3 1
13 6 3 1
14 7 3 1
15 7 3 1
16 8 4 2
17 8 4 2
18 9 4 2
19 9 4 2
20 0 0 0
21 0 0 0
...
Hopefully this table shows that collisions are much more likely for h2 than for h, and more likely for h3 than for h2. The range of h3 is smaller than the range of h2 which is smaller than the range of h.
- paulgb 17y agoRight, that's what I had in mind. Of course, it's a bit of a jump to assume that the result is the same when you use a cryptographic hash function instead of a trivial one. But regardless of the hash function, the same problem will occur unless there are no collisions for input between 0 and 2^160 - 1 (inclusive). From what I can tell, SHA1 can't guarantee this.