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$?













9












$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$?










share|improve this question











$endgroup$
















    9












    $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$?










    share|improve this question











    $endgroup$














      9












      9








      9





      $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$?










      share|improve this question











      $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






      share|improve this question















      share|improve this question













      share|improve this question




      share|improve this question








      edited May 11 at 17:13









      AleksanderRas

      3,2541939




      3,2541939










      asked May 11 at 16:18









      WilliamWilliam

      1485




      1485




















          3 Answers
          3






          active

          oldest

          votes


















          21












          $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:



          A genuine guaranteed random mapping, courtesy fgrieu



          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.






          share|improve this answer











          $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


















          5












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






          share|improve this answer









          $endgroup$




















            4












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






            share|improve this answer









            $endgroup$













              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
              );



              );













              draft saved

              draft discarded


















              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









              21












              $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:



              A genuine guaranteed random mapping, courtesy fgrieu



              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.






              share|improve this answer











              $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















              21












              $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:



              A genuine guaranteed random mapping, courtesy fgrieu



              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.






              share|improve this answer











              $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













              21












              21








              21





              $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:



              A genuine guaranteed random mapping, courtesy fgrieu



              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.






              share|improve this answer











              $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:



              A genuine guaranteed random mapping, courtesy fgrieu



              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.







              share|improve this answer














              share|improve this answer



              share|improve this answer








              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












              • 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











              5












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






              share|improve this answer









              $endgroup$

















                5












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






                share|improve this answer









                $endgroup$















                  5












                  5








                  5





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






                  share|improve this answer









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







                  share|improve this answer












                  share|improve this answer



                  share|improve this answer










                  answered May 11 at 17:45









                  Meir MaorMeir Maor

                  5,43211030




                  5,43211030





















                      4












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






                      share|improve this answer









                      $endgroup$

















                        4












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






                        share|improve this answer









                        $endgroup$















                          4












                          4








                          4





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






                          share|improve this answer









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







                          share|improve this answer












                          share|improve this answer



                          share|improve this answer










                          answered May 11 at 16:46









                          ponchoponcho

                          95.4k2153249




                          95.4k2153249



























                              draft saved

                              draft discarded
















































                              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.




                              draft saved


                              draft discarded














                              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





















































                              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







                              Popular posts from this blog

                              Category:9 (number) SubcategoriesMedia in category "9 (number)"Navigation menuUpload mediaGND ID: 4485639-8Library of Congress authority ID: sh85091979ReasonatorScholiaStatistics

                              Circuit construction for execution of conditional statements using least significant bitHow are two different registers being used as “control”?How exactly is the stated composite state of the two registers being produced using the $R_zz$ controlled rotations?Efficiently performing controlled rotations in HHLWould this quantum algorithm implementation work?How to prepare a superposed states of odd integers from $1$ to $sqrtN$?Why is this implementation of the order finding algorithm not working?Circuit construction for Hamiltonian simulationHow can I invert the least significant bit of a certain term of a superposed state?Implementing an oracleImplementing a controlled sum operation

                              Magento 2 “No Payment Methods” in Admin New OrderHow to integrate Paypal Express Checkout with the Magento APIMagento 1.5 - Sales > Order > edit order and shipping methods disappearAuto Invoice Check/Money Order Payment methodAdd more simple payment methods?Shipping methods not showingWhat should I do to change payment methods if changing the configuration has no effects?1.9 - No Payment Methods showing upMy Payment Methods not Showing for downloadable/virtual product when checkout?Magento2 API to access internal payment methodHow to call an existing payment methods in the registration form?