Timeline for Cycles in SHA-256
Current License: CC BY-SA 4.0
20 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 2, 2019 at 15:20 | history | edited | Maarten Bodewes♦ | CC BY-SA 4.0 |
added 1 character in body; edited title
|
| Mar 31, 2019 at 19:35 | answer | added | Squeamish Ossifrage | timeline score: 10 | |
| Apr 26, 2017 at 15:52 | history | tweeted | twitter.com/StackCrypto/status/857261170415337472 | ||
| Apr 26, 2017 at 15:21 | history | edited | Ilmari Karonen | CC BY-SA 3.0 |
copyedit math formatting and punctuation for clarity, remove unnecessary meta-information (your use of "cycle" is perfectly reasonable; you don't need to append "thanks" to your question, gratitude is assumed here by default)
|
| Aug 7, 2016 at 1:06 | history | post merged (destination) | |||
| Aug 4, 2016 at 1:22 | answer | added | user991 | timeline score: 10 | |
| Aug 4, 2016 at 0:45 | comment | added | Maarten Bodewes♦ | Those loops are called cycles. Cycles are generally very large. | |
| Mar 25, 2015 at 22:47 | vote | accept | bnsh | ||
| Mar 25, 2015 at 21:07 | comment | added | Gilles 'SO- stop being evil' | Your other question about collisions on 256-bit strings is answered here (for SHA-512 but the principle is the same). | |
| Mar 25, 2015 at 18:37 | comment | added | user13741 | You're right, as it will most likely cycle long before then. | |
| Mar 25, 2015 at 18:33 | comment | added | fgrieu♦ | First statement is wrong. | |
| Mar 25, 2015 at 18:29 | comment | added | user13741 | <s>If you want to get back to a specific starting point $v$ then it will take on average $2^{256}$ iterations.</s> If you simply want to find a cycle, it will take about $2^{128}$ iterations, because of the birthday paradox. | |
| Mar 25, 2015 at 17:16 | comment | added | tylo | That does not prevent cycles at all. All you do is to get different cycles. But as fgrieu pointed out in his answer: Most values don't belong to a cycle anyway. If the function was a permutation instead, every value would belong to a cycle.One more thing about the estimations of cycle lengths: Both random functions and random permutations can have many cycles of varying lengths. Quite sure, all those numbers are too high for either case. | |
| Mar 25, 2015 at 16:55 | answer | added | fgrieu♦ | timeline score: 30 | |
| Mar 25, 2015 at 15:11 | comment | added | rmalayter | Not specifically asked, but if you want to prevent cycles with such a construction, you can concatenate a 256-bit representation of n with the previous hash value at each iteration. So $$\text{SHA256}^n(v) == {SHA256}(n_{256}||{SHA256}^{n-1}(v))$$ | |
| Mar 25, 2015 at 9:35 | comment | added | CodesInChaos | With a blockcipher (which is a permutation), the cycle length would be around $2^{255}$ with a hash the cycle length is around $2^{128}$. But of course these are just statistical values and both shorter and longer cycles exist. | |
| Mar 25, 2015 at 8:40 | answer | added | Henno Brandsma | timeline score: 2 | |
| Mar 25, 2015 at 8:29 | comment | added | user991 | The identity function is a permutation for which one would get $\: n = 1 \;$. $\;\;\;\;$ | |
| Mar 25, 2015 at 7:54 | review | First posts | |||
| Mar 25, 2015 at 9:39 | |||||
| Mar 25, 2015 at 7:52 | history | asked | bnsh | CC BY-SA 3.0 |