10

Is there an x where SHA1(x) == x? I'm looking for a proof or a strong argument against it.

Cole Tobin
  • 9,206
  • 15
  • 49
  • 74
forki23
  • 2,784
  • 1
  • 28
  • 42
  • 1
    I forgot the algo, but I suggest taking and input and output to the circuit to be the same and try to formulate the conditions on internal gates, see if any of them are conflicting, if not then its possible else its not. Thanks – Mahesh Velaga Feb 26 '10 at 09:25
  • 2
    thats called "fixed point", http://en.wikipedia.org/wiki/Fixed_point_%28mathematics%29 – Nick Dandoulakis Feb 26 '10 at 09:26

2 Answers2

6

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%.

Community
  • 1
  • 1
abc
  • 516
  • 2
  • 3
  • 1
    That's not what I'm looking for. Saying 63% is like saying "maybe or maybe not". ;-) – forki23 Feb 26 '10 at 12:22
  • 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 Feb 26 '10 at 12:28
  • 3
    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 Feb 26 '10 at 12:41
2

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 Dandoulakis
  • 42,588
  • 16
  • 104
  • 136
  • If I understand this correctly, then it's not really proven, but we have only a small chance to find a example. – forki23 Feb 26 '10 at 09:59
  • 1
    @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 Dandoulakis Feb 26 '10 at 10:08
  • 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 Feb 26 '10 at 10:11
  • 3
    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 Feb 26 '10 at 12:07