1
$\begingroup$

My question is Is is possible to compute a string given that after applying a SHA256 function the result is the same string?

$\endgroup$
7
  • $\begingroup$ Can you clarify: do you mean two inputs having the same SHA256 output? That would be a SHA256 collision. I didn't think any were yet found for SHA256, but maybe the crypto exchange would have the latest news. $\endgroup$
    – C8H10N4O2
    Aug 20 '20 at 21:08
  • 1
    $\begingroup$ @C8H10N4O2 I think OP is asking for a fixed point of SHA256. $\endgroup$
    – orlp
    Aug 21 '20 at 1:36
  • $\begingroup$ There is an infinite number of strings and a finite number of SHA256 outputs. $\endgroup$
    – greybeard
    Aug 21 '20 at 4:32
  • $\begingroup$ @greybeard That does not automatically mean there is a fixed point. $\endgroup$
    – orlp
    Aug 21 '20 at 13:40
  • $\begingroup$ If looking for fixed point computation, see the crypoo exchange. Here is one such thread: crypto.stackexchange.com/questions/48580/… $\endgroup$
    – C8H10N4O2
    Aug 21 '20 at 14:54
2
$\begingroup$

No one knows. It is believed to be computationally infeasible to find such a string, if one exists. No one knows whether such a string exists.

By standard heuristics (modelling SHA256 as a random function), there is approximately a $1/e\approx 0.368$ chance that no such input exists, and approximately a $0.632$ chance that such an input exists, so if I were forced to bet, I would bet that it's more likely there exists such an input than that there doesn't, but no one knows. Don't interpret this chance too seriously: for the specific SHA256 function, either such an input exists or it doesn't. We don't know which is the case.

If such an input is found, it is believed that it would take about $2^{256}$ steps of computation to find it, which is completely infeasible.

$\endgroup$
6
  • $\begingroup$ Can you expand a bit on the heuristic used? If SHA256 is a random function, then it has an infinite domain and a finite codomain, so shouldn't a fixed-point (actually, infinitely many fixed points) exist almost-surely? $\endgroup$
    – Steven
    Feb 13 at 23:20
  • $\begingroup$ @Steven, no. It might cycle with period length > 1. The heuristic is: $\Pr[f(x) \ne x] = 1 - 1/2^{256}$; so $\Pr[\forall x . f(x) \ne x] \approx \prod_x \Pr[f(x) \ne x] = (1 - 1/2^{256})^{2^{256}} \approx 1/e$. $\endgroup$
    – D.W.
    Feb 13 at 23:23
  • $\begingroup$ sorry if I'm missing something stupid. Are you assuming that SHA256 will cycle with a period of at most $2^{256}$? $\endgroup$
    – Steven
    Feb 13 at 23:30
  • $\begingroup$ @Steven, I wouldn't say I'm assuming it, but it is true. If you are iteratively applying SHA256, all that matters is its behavior on $\{0,1\}^{256}$ (after the first iteration, you're only working with 256-bit values, because the output of SHA256 has 256 bits). $\endgroup$
    – D.W.
    Feb 13 at 23:47
  • $\begingroup$ @Steven, $f(x) \in [0 : 2^{256})$. For $x = f(x)$, we must also have $x \in [0 : 2^{256})$, so we don't care about other strings. $\endgroup$
    – user114966
    Feb 13 at 23:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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