Does |{ x | x = sha1(x)}| > 0 hold?
I'm looking for a proof or a strong argument against it.
views:
211answers:
2
+3
A:
Read about fixed point attack on this wiki entry One-way compression function - Davies-Meyer
Most widely used hash functions, including MD5, SHA-1 and SHA-2
use Merkle-Damgård construction.
Nick D
2010-02-26 09:32:04
If I understand this correctly, then it's not really proven, but we have only a small chance to find a example.
forki23
2010-02-26 09:59:27
@forki23, I believe it's possible to find a fixed point value so Merkle-Damgård method is only for strengthening the hash algorithms.
Nick D
2010-02-26 10:08:05
The problem with that construction as applied to the current question is that the appended length is known a priori; the input is as long as the output.
MSalters
2010-02-26 10:11:40
The fixed point attack looks for strings x, y, where y is one block, such that hash(x) = hash(x || y). So it is not the same as looking for a fixed point.
abc
2010-02-26 12:07:06
+5
A:
The same arguments apply here as for the question Is there an MD5 fixed point? I.e. for a randomly chosen function it is about 63%.
abc
2010-02-26 12:03:59
That's not what I'm looking for. Saying 63% is like saying "maybe or maybe not". ;-)
forki23
2010-02-26 12:22:06
And I think an important point is, that SHA1 is not a random function and therefor the correct answer can only be yes or no.
forki23
2010-02-26 12:28:40
The argument says, that unless you can exploit special properties of SHA1, it will be hard to find strong arguments either for or against fixed points. And hopefully, SHA1 does not have any unknown special properties.
abc
2010-02-26 12:41:33