Smallest Guaranteed hash collision cycle lengthCycles in SHA256Change in probability of collision when removing digits from MD5 hexadecimal hash valuescollision resistant summarizer for long hash valuesEmpty message Hash lengthHash collision using the leading 40-bits of SHA-1SHA1 Partial CollisionFloyd's cycle finding algorithm on SHA256If a SHA256 hash with high entropy is then hashed with one made from low entropy, is the resulting hash higher/same/lower entropy?How to implement a hash function $H colon 0,1^* to mathbbZ_p^*$?Do identical strings always have the same SHA-256 value?Is there an $n$-bit hash function such that $n$ is equal to the length of input and the collision resistance is close/equal to $2^n/2$?
Usage of the relative pronoun "dont"
What kind of action are dodge and disengage?
When the match time is called, does the current turn end immediately?
Was the dragon prowess intentionally downplayed in S08E04?
Is it possible to pass a pointer to an operator as an argument like a pointer to a function?
Why did the soldiers of the North disobey Jon?
Cuban Primes
Iterate lines of string variable in bash
Why is so much ransomware breakable?
Deleting the same lines from a list
Can I pay my credit card?
What formula to chose a nonlinear formula?
How to deal with the extreme reverberation in big cathedrals when playing the pipe organs?
How can I make dummy text (like lipsum) grey?
A person lacking money who shows off a lot
What are the effects of eating many berries from the Goodberry spell per day?
Is it standard for US-based universities to consider the ethnicity of an applicant during PhD admissions?
What kind of environment would favor hermaphroditism in a sentient species over regular, old sexes?
Failing students when it might cause them economic ruin
Why is vowel phonology represented in a trapezoid instead of a square?
Have there been any examples of re-usable rockets in the past?
"Counterexample" for the Inverse function theorem
Who is frowning in the sentence "Daisy looked at Tom frowning"?
How does the Heat Metal spell interact with a follow-up Frostbite spell?
Smallest Guaranteed hash collision cycle length
Cycles in SHA256Change in probability of collision when removing digits from MD5 hexadecimal hash valuescollision resistant summarizer for long hash valuesEmpty message Hash lengthHash collision using the leading 40-bits of SHA-1SHA1 Partial CollisionFloyd's cycle finding algorithm on SHA256If a SHA256 hash with high entropy is then hashed with one made from low entropy, is the resulting hash higher/same/lower entropy?How to implement a hash function $H colon 0,1^* to mathbbZ_p^*$?Do identical strings always have the same SHA-256 value?Is there an $n$-bit hash function such that $n$ is equal to the length of input and the collision resistance is close/equal to $2^n/2$?
$begingroup$
If I take the sha-256 of an empty string, and apply the hash function $2^256!$ times, will I end up with the same hash that I started with?
Is the smallest required cycle equal to the LCM of $1$ to $2^256$?
hash
$endgroup$
add a comment |
$begingroup$
If I take the sha-256 of an empty string, and apply the hash function $2^256!$ times, will I end up with the same hash that I started with?
Is the smallest required cycle equal to the LCM of $1$ to $2^256$?
hash
$endgroup$
add a comment |
$begingroup$
If I take the sha-256 of an empty string, and apply the hash function $2^256!$ times, will I end up with the same hash that I started with?
Is the smallest required cycle equal to the LCM of $1$ to $2^256$?
hash
$endgroup$
If I take the sha-256 of an empty string, and apply the hash function $2^256!$ times, will I end up with the same hash that I started with?
Is the smallest required cycle equal to the LCM of $1$ to $2^256$?
hash
hash
edited May 11 at 17:13
AleksanderRas
3,2541939
3,2541939
asked May 11 at 16:18
WilliamWilliam
1485
1485
add a comment |
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
In a uniform random function, which is a mostly reasonable model for SHA-256, you are not guaranteed that any particular element lies in a cycle: it could go $A mapsto B mapsto C mapsto B$ and therefore never return to $A$.
In fact, only a tiny minority of elements are likely on cycles at all—the expected number of elements on cycles in a uniform function of $n$ elements grows with $frac 1 2 sqrt2pi n$; for SHA-256, this is about $2^128$ of $2^256$ possible 256-bitstrings, i.e. the probability that any particular element is on a SHA-256 cycle is about $2^-128$.
However, if you just want to know how long you must pursue a hash chain before it cycles somewhere—not necessarily back to where you started ($A$), but somewhere you started going in circles lost in the desert trying to follow your own tracks like a pair of Belgian detectives ($B$)—the length of that chain turns out to have the same distribution as the number of elements on a cycle, with expectation $frac 1 2 sqrt2pi n$, and the expected length of the cycle itself is $frac 1 4 sqrt2pi n$.
So on average you'd have to follow $2^128$ elements before you ever come back upon your footsteps somewhere in a SHA-256 hash chain, and the average cycle length is about $2^127$, so you'd skip half your footsteps when you cycle back.
Here's an illustration that I stole from fgrieu of a 7-bit hash function—the vast majority of points, the grey dots, are not on cycles at all; only the red dots are on cycles:
Of course, in principle it could turn out that SHA-256 is actually a permutation of $0,1^256$ and is a single giant cycle, in which case you would actually have to tread $2^256$ steps—this, rather than the much larger $2^256!$, is the maximum number of steps before you are 100% guaranteed to have cycled back upon your footsteps. But it is exceedingly unlikely that SHA-256 is a permutation, let alone a cyclic permutation—this would be an astonishing development if proven.
See Harris 1960 (paywall-free) for everything you need to know about statistics of uniform random functions, permutations, and derangements.
$endgroup$
1
$begingroup$
This is such a wonderful answer and happily went ahead and answered what my follow up questions would be. I’m glad that others are interested enough in this topic to share their knowledge!
$endgroup$
– William
May 11 at 21:03
$begingroup$
It could also be a permutation with many smaller cycles.
$endgroup$
– Paŭlo Ebermann
May 12 at 0:23
$begingroup$
Why do you say that it is exceedingly unlikely that SHA256 is a single cycle? (I'm not challenging your claim, I'm genuinely curious)
$endgroup$
– DreamConspiracy
May 12 at 1:06
$begingroup$
Nice. My answer would have been similar. Unfortunately all these excellent questions pop up when it's after midnight here.
$endgroup$
– kodlu
May 12 at 1:27
1
$begingroup$
@DreamConspiracy Only about $1/e^2^256$ of all 256-bit functions are permutations, and of those, only a tiny fraction consist of a single cycle.
$endgroup$
– Squeamish Ossifrage
May 12 at 2:48
add a comment |
$begingroup$
There is a big difference between what we know for sure and what we expect.
We don't know for sure almost anything, We don't know what is the cycle structure of sha256 We don't know how big any cycle is including one starting with an empty string.
We however expect sha256 to behave like a random function. So we expect it to contain many cycles. Each with on the order of 2^128 elements. The graph of random function has many different connected components each with a single cycle and a bunch of tree segments leading into the cycles. We however expect only a logarithmic number of cycles. Thus the vast majority of points are not on a cycle.
We do not know if the empty string is part of a cycle. It is likely it leads into a cycle it is not part of. It is ridiculously unlikely sha256 consists of a single cycle so that when starting with the empty string we would go through all others before returning to it. If this were the case it would hold for any starting point.It would also make sha256 a permutation. We can't currently disprove it, but we like to think of sha256 as a random function making these have probability 0 for all practical purposes.
$endgroup$
add a comment |
$begingroup$
If I take the sha-256 of an empty string, and apply the hash function (2^256)! times, will I end up with the same hash that I started with?
It's not guaranteed (and it would appear to be unlikely).
SHA-256 is not invertible and so while you're guaranteed to run into a cycle with at most $2^256+1$ iterations, that cycle might not include the initial element.
For example, SHA-256 might act like this simplified example:
SHA(0) -> 1
SHA(1) -> 2
SHA(2) -> 1
If our hash function acted like this, then it would matter how many times we iterated $SHA^n(0)$; we'd never come back to our initial 0 value.
$endgroup$
add a comment |
Your Answer
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "281"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcrypto.stackexchange.com%2fquestions%2f70474%2fsmallest-guaranteed-hash-collision-cycle-length%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
In a uniform random function, which is a mostly reasonable model for SHA-256, you are not guaranteed that any particular element lies in a cycle: it could go $A mapsto B mapsto C mapsto B$ and therefore never return to $A$.
In fact, only a tiny minority of elements are likely on cycles at all—the expected number of elements on cycles in a uniform function of $n$ elements grows with $frac 1 2 sqrt2pi n$; for SHA-256, this is about $2^128$ of $2^256$ possible 256-bitstrings, i.e. the probability that any particular element is on a SHA-256 cycle is about $2^-128$.
However, if you just want to know how long you must pursue a hash chain before it cycles somewhere—not necessarily back to where you started ($A$), but somewhere you started going in circles lost in the desert trying to follow your own tracks like a pair of Belgian detectives ($B$)—the length of that chain turns out to have the same distribution as the number of elements on a cycle, with expectation $frac 1 2 sqrt2pi n$, and the expected length of the cycle itself is $frac 1 4 sqrt2pi n$.
So on average you'd have to follow $2^128$ elements before you ever come back upon your footsteps somewhere in a SHA-256 hash chain, and the average cycle length is about $2^127$, so you'd skip half your footsteps when you cycle back.
Here's an illustration that I stole from fgrieu of a 7-bit hash function—the vast majority of points, the grey dots, are not on cycles at all; only the red dots are on cycles:
Of course, in principle it could turn out that SHA-256 is actually a permutation of $0,1^256$ and is a single giant cycle, in which case you would actually have to tread $2^256$ steps—this, rather than the much larger $2^256!$, is the maximum number of steps before you are 100% guaranteed to have cycled back upon your footsteps. But it is exceedingly unlikely that SHA-256 is a permutation, let alone a cyclic permutation—this would be an astonishing development if proven.
See Harris 1960 (paywall-free) for everything you need to know about statistics of uniform random functions, permutations, and derangements.
$endgroup$
1
$begingroup$
This is such a wonderful answer and happily went ahead and answered what my follow up questions would be. I’m glad that others are interested enough in this topic to share their knowledge!
$endgroup$
– William
May 11 at 21:03
$begingroup$
It could also be a permutation with many smaller cycles.
$endgroup$
– Paŭlo Ebermann
May 12 at 0:23
$begingroup$
Why do you say that it is exceedingly unlikely that SHA256 is a single cycle? (I'm not challenging your claim, I'm genuinely curious)
$endgroup$
– DreamConspiracy
May 12 at 1:06
$begingroup$
Nice. My answer would have been similar. Unfortunately all these excellent questions pop up when it's after midnight here.
$endgroup$
– kodlu
May 12 at 1:27
1
$begingroup$
@DreamConspiracy Only about $1/e^2^256$ of all 256-bit functions are permutations, and of those, only a tiny fraction consist of a single cycle.
$endgroup$
– Squeamish Ossifrage
May 12 at 2:48
add a comment |
$begingroup$
In a uniform random function, which is a mostly reasonable model for SHA-256, you are not guaranteed that any particular element lies in a cycle: it could go $A mapsto B mapsto C mapsto B$ and therefore never return to $A$.
In fact, only a tiny minority of elements are likely on cycles at all—the expected number of elements on cycles in a uniform function of $n$ elements grows with $frac 1 2 sqrt2pi n$; for SHA-256, this is about $2^128$ of $2^256$ possible 256-bitstrings, i.e. the probability that any particular element is on a SHA-256 cycle is about $2^-128$.
However, if you just want to know how long you must pursue a hash chain before it cycles somewhere—not necessarily back to where you started ($A$), but somewhere you started going in circles lost in the desert trying to follow your own tracks like a pair of Belgian detectives ($B$)—the length of that chain turns out to have the same distribution as the number of elements on a cycle, with expectation $frac 1 2 sqrt2pi n$, and the expected length of the cycle itself is $frac 1 4 sqrt2pi n$.
So on average you'd have to follow $2^128$ elements before you ever come back upon your footsteps somewhere in a SHA-256 hash chain, and the average cycle length is about $2^127$, so you'd skip half your footsteps when you cycle back.
Here's an illustration that I stole from fgrieu of a 7-bit hash function—the vast majority of points, the grey dots, are not on cycles at all; only the red dots are on cycles:
Of course, in principle it could turn out that SHA-256 is actually a permutation of $0,1^256$ and is a single giant cycle, in which case you would actually have to tread $2^256$ steps—this, rather than the much larger $2^256!$, is the maximum number of steps before you are 100% guaranteed to have cycled back upon your footsteps. But it is exceedingly unlikely that SHA-256 is a permutation, let alone a cyclic permutation—this would be an astonishing development if proven.
See Harris 1960 (paywall-free) for everything you need to know about statistics of uniform random functions, permutations, and derangements.
$endgroup$
1
$begingroup$
This is such a wonderful answer and happily went ahead and answered what my follow up questions would be. I’m glad that others are interested enough in this topic to share their knowledge!
$endgroup$
– William
May 11 at 21:03
$begingroup$
It could also be a permutation with many smaller cycles.
$endgroup$
– Paŭlo Ebermann
May 12 at 0:23
$begingroup$
Why do you say that it is exceedingly unlikely that SHA256 is a single cycle? (I'm not challenging your claim, I'm genuinely curious)
$endgroup$
– DreamConspiracy
May 12 at 1:06
$begingroup$
Nice. My answer would have been similar. Unfortunately all these excellent questions pop up when it's after midnight here.
$endgroup$
– kodlu
May 12 at 1:27
1
$begingroup$
@DreamConspiracy Only about $1/e^2^256$ of all 256-bit functions are permutations, and of those, only a tiny fraction consist of a single cycle.
$endgroup$
– Squeamish Ossifrage
May 12 at 2:48
add a comment |
$begingroup$
In a uniform random function, which is a mostly reasonable model for SHA-256, you are not guaranteed that any particular element lies in a cycle: it could go $A mapsto B mapsto C mapsto B$ and therefore never return to $A$.
In fact, only a tiny minority of elements are likely on cycles at all—the expected number of elements on cycles in a uniform function of $n$ elements grows with $frac 1 2 sqrt2pi n$; for SHA-256, this is about $2^128$ of $2^256$ possible 256-bitstrings, i.e. the probability that any particular element is on a SHA-256 cycle is about $2^-128$.
However, if you just want to know how long you must pursue a hash chain before it cycles somewhere—not necessarily back to where you started ($A$), but somewhere you started going in circles lost in the desert trying to follow your own tracks like a pair of Belgian detectives ($B$)—the length of that chain turns out to have the same distribution as the number of elements on a cycle, with expectation $frac 1 2 sqrt2pi n$, and the expected length of the cycle itself is $frac 1 4 sqrt2pi n$.
So on average you'd have to follow $2^128$ elements before you ever come back upon your footsteps somewhere in a SHA-256 hash chain, and the average cycle length is about $2^127$, so you'd skip half your footsteps when you cycle back.
Here's an illustration that I stole from fgrieu of a 7-bit hash function—the vast majority of points, the grey dots, are not on cycles at all; only the red dots are on cycles:
Of course, in principle it could turn out that SHA-256 is actually a permutation of $0,1^256$ and is a single giant cycle, in which case you would actually have to tread $2^256$ steps—this, rather than the much larger $2^256!$, is the maximum number of steps before you are 100% guaranteed to have cycled back upon your footsteps. But it is exceedingly unlikely that SHA-256 is a permutation, let alone a cyclic permutation—this would be an astonishing development if proven.
See Harris 1960 (paywall-free) for everything you need to know about statistics of uniform random functions, permutations, and derangements.
$endgroup$
In a uniform random function, which is a mostly reasonable model for SHA-256, you are not guaranteed that any particular element lies in a cycle: it could go $A mapsto B mapsto C mapsto B$ and therefore never return to $A$.
In fact, only a tiny minority of elements are likely on cycles at all—the expected number of elements on cycles in a uniform function of $n$ elements grows with $frac 1 2 sqrt2pi n$; for SHA-256, this is about $2^128$ of $2^256$ possible 256-bitstrings, i.e. the probability that any particular element is on a SHA-256 cycle is about $2^-128$.
However, if you just want to know how long you must pursue a hash chain before it cycles somewhere—not necessarily back to where you started ($A$), but somewhere you started going in circles lost in the desert trying to follow your own tracks like a pair of Belgian detectives ($B$)—the length of that chain turns out to have the same distribution as the number of elements on a cycle, with expectation $frac 1 2 sqrt2pi n$, and the expected length of the cycle itself is $frac 1 4 sqrt2pi n$.
So on average you'd have to follow $2^128$ elements before you ever come back upon your footsteps somewhere in a SHA-256 hash chain, and the average cycle length is about $2^127$, so you'd skip half your footsteps when you cycle back.
Here's an illustration that I stole from fgrieu of a 7-bit hash function—the vast majority of points, the grey dots, are not on cycles at all; only the red dots are on cycles:
Of course, in principle it could turn out that SHA-256 is actually a permutation of $0,1^256$ and is a single giant cycle, in which case you would actually have to tread $2^256$ steps—this, rather than the much larger $2^256!$, is the maximum number of steps before you are 100% guaranteed to have cycled back upon your footsteps. But it is exceedingly unlikely that SHA-256 is a permutation, let alone a cyclic permutation—this would be an astonishing development if proven.
See Harris 1960 (paywall-free) for everything you need to know about statistics of uniform random functions, permutations, and derangements.
edited May 12 at 2:51
answered May 11 at 17:31
Squeamish OssifrageSqueamish Ossifrage
24.8k136111
24.8k136111
1
$begingroup$
This is such a wonderful answer and happily went ahead and answered what my follow up questions would be. I’m glad that others are interested enough in this topic to share their knowledge!
$endgroup$
– William
May 11 at 21:03
$begingroup$
It could also be a permutation with many smaller cycles.
$endgroup$
– Paŭlo Ebermann
May 12 at 0:23
$begingroup$
Why do you say that it is exceedingly unlikely that SHA256 is a single cycle? (I'm not challenging your claim, I'm genuinely curious)
$endgroup$
– DreamConspiracy
May 12 at 1:06
$begingroup$
Nice. My answer would have been similar. Unfortunately all these excellent questions pop up when it's after midnight here.
$endgroup$
– kodlu
May 12 at 1:27
1
$begingroup$
@DreamConspiracy Only about $1/e^2^256$ of all 256-bit functions are permutations, and of those, only a tiny fraction consist of a single cycle.
$endgroup$
– Squeamish Ossifrage
May 12 at 2:48
add a comment |
1
$begingroup$
This is such a wonderful answer and happily went ahead and answered what my follow up questions would be. I’m glad that others are interested enough in this topic to share their knowledge!
$endgroup$
– William
May 11 at 21:03
$begingroup$
It could also be a permutation with many smaller cycles.
$endgroup$
– Paŭlo Ebermann
May 12 at 0:23
$begingroup$
Why do you say that it is exceedingly unlikely that SHA256 is a single cycle? (I'm not challenging your claim, I'm genuinely curious)
$endgroup$
– DreamConspiracy
May 12 at 1:06
$begingroup$
Nice. My answer would have been similar. Unfortunately all these excellent questions pop up when it's after midnight here.
$endgroup$
– kodlu
May 12 at 1:27
1
$begingroup$
@DreamConspiracy Only about $1/e^2^256$ of all 256-bit functions are permutations, and of those, only a tiny fraction consist of a single cycle.
$endgroup$
– Squeamish Ossifrage
May 12 at 2:48
1
1
$begingroup$
This is such a wonderful answer and happily went ahead and answered what my follow up questions would be. I’m glad that others are interested enough in this topic to share their knowledge!
$endgroup$
– William
May 11 at 21:03
$begingroup$
This is such a wonderful answer and happily went ahead and answered what my follow up questions would be. I’m glad that others are interested enough in this topic to share their knowledge!
$endgroup$
– William
May 11 at 21:03
$begingroup$
It could also be a permutation with many smaller cycles.
$endgroup$
– Paŭlo Ebermann
May 12 at 0:23
$begingroup$
It could also be a permutation with many smaller cycles.
$endgroup$
– Paŭlo Ebermann
May 12 at 0:23
$begingroup$
Why do you say that it is exceedingly unlikely that SHA256 is a single cycle? (I'm not challenging your claim, I'm genuinely curious)
$endgroup$
– DreamConspiracy
May 12 at 1:06
$begingroup$
Why do you say that it is exceedingly unlikely that SHA256 is a single cycle? (I'm not challenging your claim, I'm genuinely curious)
$endgroup$
– DreamConspiracy
May 12 at 1:06
$begingroup$
Nice. My answer would have been similar. Unfortunately all these excellent questions pop up when it's after midnight here.
$endgroup$
– kodlu
May 12 at 1:27
$begingroup$
Nice. My answer would have been similar. Unfortunately all these excellent questions pop up when it's after midnight here.
$endgroup$
– kodlu
May 12 at 1:27
1
1
$begingroup$
@DreamConspiracy Only about $1/e^2^256$ of all 256-bit functions are permutations, and of those, only a tiny fraction consist of a single cycle.
$endgroup$
– Squeamish Ossifrage
May 12 at 2:48
$begingroup$
@DreamConspiracy Only about $1/e^2^256$ of all 256-bit functions are permutations, and of those, only a tiny fraction consist of a single cycle.
$endgroup$
– Squeamish Ossifrage
May 12 at 2:48
add a comment |
$begingroup$
There is a big difference between what we know for sure and what we expect.
We don't know for sure almost anything, We don't know what is the cycle structure of sha256 We don't know how big any cycle is including one starting with an empty string.
We however expect sha256 to behave like a random function. So we expect it to contain many cycles. Each with on the order of 2^128 elements. The graph of random function has many different connected components each with a single cycle and a bunch of tree segments leading into the cycles. We however expect only a logarithmic number of cycles. Thus the vast majority of points are not on a cycle.
We do not know if the empty string is part of a cycle. It is likely it leads into a cycle it is not part of. It is ridiculously unlikely sha256 consists of a single cycle so that when starting with the empty string we would go through all others before returning to it. If this were the case it would hold for any starting point.It would also make sha256 a permutation. We can't currently disprove it, but we like to think of sha256 as a random function making these have probability 0 for all practical purposes.
$endgroup$
add a comment |
$begingroup$
There is a big difference between what we know for sure and what we expect.
We don't know for sure almost anything, We don't know what is the cycle structure of sha256 We don't know how big any cycle is including one starting with an empty string.
We however expect sha256 to behave like a random function. So we expect it to contain many cycles. Each with on the order of 2^128 elements. The graph of random function has many different connected components each with a single cycle and a bunch of tree segments leading into the cycles. We however expect only a logarithmic number of cycles. Thus the vast majority of points are not on a cycle.
We do not know if the empty string is part of a cycle. It is likely it leads into a cycle it is not part of. It is ridiculously unlikely sha256 consists of a single cycle so that when starting with the empty string we would go through all others before returning to it. If this were the case it would hold for any starting point.It would also make sha256 a permutation. We can't currently disprove it, but we like to think of sha256 as a random function making these have probability 0 for all practical purposes.
$endgroup$
add a comment |
$begingroup$
There is a big difference between what we know for sure and what we expect.
We don't know for sure almost anything, We don't know what is the cycle structure of sha256 We don't know how big any cycle is including one starting with an empty string.
We however expect sha256 to behave like a random function. So we expect it to contain many cycles. Each with on the order of 2^128 elements. The graph of random function has many different connected components each with a single cycle and a bunch of tree segments leading into the cycles. We however expect only a logarithmic number of cycles. Thus the vast majority of points are not on a cycle.
We do not know if the empty string is part of a cycle. It is likely it leads into a cycle it is not part of. It is ridiculously unlikely sha256 consists of a single cycle so that when starting with the empty string we would go through all others before returning to it. If this were the case it would hold for any starting point.It would also make sha256 a permutation. We can't currently disprove it, but we like to think of sha256 as a random function making these have probability 0 for all practical purposes.
$endgroup$
There is a big difference between what we know for sure and what we expect.
We don't know for sure almost anything, We don't know what is the cycle structure of sha256 We don't know how big any cycle is including one starting with an empty string.
We however expect sha256 to behave like a random function. So we expect it to contain many cycles. Each with on the order of 2^128 elements. The graph of random function has many different connected components each with a single cycle and a bunch of tree segments leading into the cycles. We however expect only a logarithmic number of cycles. Thus the vast majority of points are not on a cycle.
We do not know if the empty string is part of a cycle. It is likely it leads into a cycle it is not part of. It is ridiculously unlikely sha256 consists of a single cycle so that when starting with the empty string we would go through all others before returning to it. If this were the case it would hold for any starting point.It would also make sha256 a permutation. We can't currently disprove it, but we like to think of sha256 as a random function making these have probability 0 for all practical purposes.
answered May 11 at 17:45
Meir MaorMeir Maor
5,43211030
5,43211030
add a comment |
add a comment |
$begingroup$
If I take the sha-256 of an empty string, and apply the hash function (2^256)! times, will I end up with the same hash that I started with?
It's not guaranteed (and it would appear to be unlikely).
SHA-256 is not invertible and so while you're guaranteed to run into a cycle with at most $2^256+1$ iterations, that cycle might not include the initial element.
For example, SHA-256 might act like this simplified example:
SHA(0) -> 1
SHA(1) -> 2
SHA(2) -> 1
If our hash function acted like this, then it would matter how many times we iterated $SHA^n(0)$; we'd never come back to our initial 0 value.
$endgroup$
add a comment |
$begingroup$
If I take the sha-256 of an empty string, and apply the hash function (2^256)! times, will I end up with the same hash that I started with?
It's not guaranteed (and it would appear to be unlikely).
SHA-256 is not invertible and so while you're guaranteed to run into a cycle with at most $2^256+1$ iterations, that cycle might not include the initial element.
For example, SHA-256 might act like this simplified example:
SHA(0) -> 1
SHA(1) -> 2
SHA(2) -> 1
If our hash function acted like this, then it would matter how many times we iterated $SHA^n(0)$; we'd never come back to our initial 0 value.
$endgroup$
add a comment |
$begingroup$
If I take the sha-256 of an empty string, and apply the hash function (2^256)! times, will I end up with the same hash that I started with?
It's not guaranteed (and it would appear to be unlikely).
SHA-256 is not invertible and so while you're guaranteed to run into a cycle with at most $2^256+1$ iterations, that cycle might not include the initial element.
For example, SHA-256 might act like this simplified example:
SHA(0) -> 1
SHA(1) -> 2
SHA(2) -> 1
If our hash function acted like this, then it would matter how many times we iterated $SHA^n(0)$; we'd never come back to our initial 0 value.
$endgroup$
If I take the sha-256 of an empty string, and apply the hash function (2^256)! times, will I end up with the same hash that I started with?
It's not guaranteed (and it would appear to be unlikely).
SHA-256 is not invertible and so while you're guaranteed to run into a cycle with at most $2^256+1$ iterations, that cycle might not include the initial element.
For example, SHA-256 might act like this simplified example:
SHA(0) -> 1
SHA(1) -> 2
SHA(2) -> 1
If our hash function acted like this, then it would matter how many times we iterated $SHA^n(0)$; we'd never come back to our initial 0 value.
answered May 11 at 16:46
ponchoponcho
95.4k2153249
95.4k2153249
add a comment |
add a comment |
Thanks for contributing an answer to Cryptography Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcrypto.stackexchange.com%2fquestions%2f70474%2fsmallest-guaranteed-hash-collision-cycle-length%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown