Why this brute force attack doesn't reduce all cryptographic hash functions' security bits against collision attacks to N/3?Are cryptographic hash functions perfect hash functions?Has a collision ever been found for SHA-1/2/3 when truncated to 128 bits?Brute-force attack given multiple hash prefixesWould it matter if my miner was hashing random vs incremental values?Is this SHA256 hash implementation secure from rainbow table, brute forcing attacks?What are the odds of collisions for a hash function with 256-bit output?usefulness of a collision attack that's not also a 2nd pre-image attackIs there a way one can combine two correlated hash outputs to maximize the collision resistance?

Is the Amazon rainforest the "world's lungs"?

Commercial company wants me to list all prior "inventions", give up everything not listed

Can I get a PhD for developing an educational software?

Why does glibc's strlen need to be so complicated to run fast?

Did the Apollo Guidance Computer really use 60% of the world's ICs in 1963?

Counting the number of strings starting with "t" and containing 2 vowels and 2 consonants

Could the UK amend the European Withdrawal Act and revoke the Article 50 invocation?

Which meaning of "must" does the Slow spell use?

Count the number of triangles

Did anybody find out it was Anakin who blew up the command center?

Can an object tethered to a spaceship be pulled out of event horizon?

Drawing probabilities on a simplex in TikZ

Is there any problem with a full installation on a USB drive?

Can someone identify this unusual plane at airport?

Why did Lucius make a deal out of Buckbeak hurting Draco but not about Draco being turned into a ferret?

Is Nikon d500 a good fit for nature and ambient-lighting portraits and occasional other uses?

How could a self contained organic body propel itself in space

Unlock your Lock

How do solar inverter systems easily add AC power sources together?

Is there an in-universe explanation given to the senior Imperial Navy Officers as to why Darth Vader serves Emperor Palpatine?

Book featuring a child learning from a crowdsourced AI book

What was the point of "Substance"?

Why is there not a willingness from the world to step in between Pakistan and India?

Notice period 60 days but I need to join in 45 days



Why this brute force attack doesn't reduce all cryptographic hash functions' security bits against collision attacks to N/3?


Are cryptographic hash functions perfect hash functions?Has a collision ever been found for SHA-1/2/3 when truncated to 128 bits?Brute-force attack given multiple hash prefixesWould it matter if my miner was hashing random vs incremental values?Is this SHA256 hash implementation secure from rainbow table, brute forcing attacks?What are the odds of collisions for a hash function with 256-bit output?usefulness of a collision attack that's not also a 2nd pre-image attackIs there a way one can combine two correlated hash outputs to maximize the collision resistance?






.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty margin-bottom:0;








2












$begingroup$


The traditional brute force collision attack is generate $2^N/2$ (unique) random strings, hash them and this results in ~50% chance for collision.
The attack talked in the question's title is generate hashes by the sequence $H_0 = F(S), H_n = F(S||H_n-1)$, where $S$ is a string to make collision with, $F$ is the hash function, and the sequence stops at $2^N/3$.



The above attack needs less calls to the hash function because it relies on the fact that each sequential hashing reduces the number of possible hashes. When hashing $2^N$ random strings, there will be $(1-(1-frac12^N)^2^N)2^N$ possible hashes because of all the collisions.



The sequence that tells the fraction of the possible hashes for each hash in the sequence is $P_0 = 1, P_n = 1 - (1-frac12^N)^2^NP_n-1$, which roughly approximates to $P_n = P_n-1 - fracP_n-1^22$ as $lim_P_n-1to 0$, which can be approximated into a function $P(n) = frac2n + 2$. (these reductions in precision make it easier for future calculations)



The chance for a collision to NOT happen for a hash in the sequence against all of it's following hashes is $C_n = (1 - frac1P_n2^N)^M - n - 1$ where $M$ is the sequence's length, because the fraction is so close to $1$, it can be approximated to $C_n = 1 - fracM - nP_n2^N = 1 - fracMn - n^22^N + 1$. Now to approximate the multiplication of all $C$s ($C_0C_1...C_M)$ to get the chance for collision for all hashes combined, we can discard the multiplication (because again, $C_n$ is very close to $1$) and add all the subtracted parts and subtract them from $1$, which results in $1 - fracM^3/2-M^3/42^N+1 = 1 - fracM^3/42^N+1$, and to reach ~50% collision rate $M = 2^(N+3)/3$, which is roughly just $2^N/3$.



Is there a reason why this won't work?










share|improve this question









New contributor



Yanai Eliyahu is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.






$endgroup$













  • $begingroup$
    Welcome to Cryptography. Could you elaborate The above attack needs less calls to the hash function because it relies on the fact that each sequential hashing reduces the number of possible hashes.
    $endgroup$
    – kelalaka
    9 hours ago










  • $begingroup$
    @kelalaka The sentence after that meant to support that statement, is it out of place?
    $endgroup$
    – Yanai Eliyahu
    8 hours ago










  • $begingroup$
    @kelalaka I didn't get the first 2 sentences. This is the same birthday attack just that the possible hashes are decaying overtime, so security is reduced.
    $endgroup$
    – Yanai Eliyahu
    8 hours ago

















2












$begingroup$


The traditional brute force collision attack is generate $2^N/2$ (unique) random strings, hash them and this results in ~50% chance for collision.
The attack talked in the question's title is generate hashes by the sequence $H_0 = F(S), H_n = F(S||H_n-1)$, where $S$ is a string to make collision with, $F$ is the hash function, and the sequence stops at $2^N/3$.



The above attack needs less calls to the hash function because it relies on the fact that each sequential hashing reduces the number of possible hashes. When hashing $2^N$ random strings, there will be $(1-(1-frac12^N)^2^N)2^N$ possible hashes because of all the collisions.



The sequence that tells the fraction of the possible hashes for each hash in the sequence is $P_0 = 1, P_n = 1 - (1-frac12^N)^2^NP_n-1$, which roughly approximates to $P_n = P_n-1 - fracP_n-1^22$ as $lim_P_n-1to 0$, which can be approximated into a function $P(n) = frac2n + 2$. (these reductions in precision make it easier for future calculations)



The chance for a collision to NOT happen for a hash in the sequence against all of it's following hashes is $C_n = (1 - frac1P_n2^N)^M - n - 1$ where $M$ is the sequence's length, because the fraction is so close to $1$, it can be approximated to $C_n = 1 - fracM - nP_n2^N = 1 - fracMn - n^22^N + 1$. Now to approximate the multiplication of all $C$s ($C_0C_1...C_M)$ to get the chance for collision for all hashes combined, we can discard the multiplication (because again, $C_n$ is very close to $1$) and add all the subtracted parts and subtract them from $1$, which results in $1 - fracM^3/2-M^3/42^N+1 = 1 - fracM^3/42^N+1$, and to reach ~50% collision rate $M = 2^(N+3)/3$, which is roughly just $2^N/3$.



Is there a reason why this won't work?










share|improve this question









New contributor



Yanai Eliyahu is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.






$endgroup$













  • $begingroup$
    Welcome to Cryptography. Could you elaborate The above attack needs less calls to the hash function because it relies on the fact that each sequential hashing reduces the number of possible hashes.
    $endgroup$
    – kelalaka
    9 hours ago










  • $begingroup$
    @kelalaka The sentence after that meant to support that statement, is it out of place?
    $endgroup$
    – Yanai Eliyahu
    8 hours ago










  • $begingroup$
    @kelalaka I didn't get the first 2 sentences. This is the same birthday attack just that the possible hashes are decaying overtime, so security is reduced.
    $endgroup$
    – Yanai Eliyahu
    8 hours ago













2












2








2





$begingroup$


The traditional brute force collision attack is generate $2^N/2$ (unique) random strings, hash them and this results in ~50% chance for collision.
The attack talked in the question's title is generate hashes by the sequence $H_0 = F(S), H_n = F(S||H_n-1)$, where $S$ is a string to make collision with, $F$ is the hash function, and the sequence stops at $2^N/3$.



The above attack needs less calls to the hash function because it relies on the fact that each sequential hashing reduces the number of possible hashes. When hashing $2^N$ random strings, there will be $(1-(1-frac12^N)^2^N)2^N$ possible hashes because of all the collisions.



The sequence that tells the fraction of the possible hashes for each hash in the sequence is $P_0 = 1, P_n = 1 - (1-frac12^N)^2^NP_n-1$, which roughly approximates to $P_n = P_n-1 - fracP_n-1^22$ as $lim_P_n-1to 0$, which can be approximated into a function $P(n) = frac2n + 2$. (these reductions in precision make it easier for future calculations)



The chance for a collision to NOT happen for a hash in the sequence against all of it's following hashes is $C_n = (1 - frac1P_n2^N)^M - n - 1$ where $M$ is the sequence's length, because the fraction is so close to $1$, it can be approximated to $C_n = 1 - fracM - nP_n2^N = 1 - fracMn - n^22^N + 1$. Now to approximate the multiplication of all $C$s ($C_0C_1...C_M)$ to get the chance for collision for all hashes combined, we can discard the multiplication (because again, $C_n$ is very close to $1$) and add all the subtracted parts and subtract them from $1$, which results in $1 - fracM^3/2-M^3/42^N+1 = 1 - fracM^3/42^N+1$, and to reach ~50% collision rate $M = 2^(N+3)/3$, which is roughly just $2^N/3$.



Is there a reason why this won't work?










share|improve this question









New contributor



Yanai Eliyahu is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.






$endgroup$




The traditional brute force collision attack is generate $2^N/2$ (unique) random strings, hash them and this results in ~50% chance for collision.
The attack talked in the question's title is generate hashes by the sequence $H_0 = F(S), H_n = F(S||H_n-1)$, where $S$ is a string to make collision with, $F$ is the hash function, and the sequence stops at $2^N/3$.



The above attack needs less calls to the hash function because it relies on the fact that each sequential hashing reduces the number of possible hashes. When hashing $2^N$ random strings, there will be $(1-(1-frac12^N)^2^N)2^N$ possible hashes because of all the collisions.



The sequence that tells the fraction of the possible hashes for each hash in the sequence is $P_0 = 1, P_n = 1 - (1-frac12^N)^2^NP_n-1$, which roughly approximates to $P_n = P_n-1 - fracP_n-1^22$ as $lim_P_n-1to 0$, which can be approximated into a function $P(n) = frac2n + 2$. (these reductions in precision make it easier for future calculations)



The chance for a collision to NOT happen for a hash in the sequence against all of it's following hashes is $C_n = (1 - frac1P_n2^N)^M - n - 1$ where $M$ is the sequence's length, because the fraction is so close to $1$, it can be approximated to $C_n = 1 - fracM - nP_n2^N = 1 - fracMn - n^22^N + 1$. Now to approximate the multiplication of all $C$s ($C_0C_1...C_M)$ to get the chance for collision for all hashes combined, we can discard the multiplication (because again, $C_n$ is very close to $1$) and add all the subtracted parts and subtract them from $1$, which results in $1 - fracM^3/2-M^3/42^N+1 = 1 - fracM^3/42^N+1$, and to reach ~50% collision rate $M = 2^(N+3)/3$, which is roughly just $2^N/3$.



Is there a reason why this won't work?







hash collision-resistance brute-force-attack






share|improve this question









New contributor



Yanai Eliyahu is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.










share|improve this question









New contributor



Yanai Eliyahu is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.








share|improve this question




share|improve this question








edited 8 hours ago







Yanai Eliyahu













New contributor



Yanai Eliyahu is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.








asked 9 hours ago









Yanai EliyahuYanai Eliyahu

133 bronze badges




133 bronze badges




New contributor



Yanai Eliyahu is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.




New contributor




Yanai Eliyahu is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
















  • $begingroup$
    Welcome to Cryptography. Could you elaborate The above attack needs less calls to the hash function because it relies on the fact that each sequential hashing reduces the number of possible hashes.
    $endgroup$
    – kelalaka
    9 hours ago










  • $begingroup$
    @kelalaka The sentence after that meant to support that statement, is it out of place?
    $endgroup$
    – Yanai Eliyahu
    8 hours ago










  • $begingroup$
    @kelalaka I didn't get the first 2 sentences. This is the same birthday attack just that the possible hashes are decaying overtime, so security is reduced.
    $endgroup$
    – Yanai Eliyahu
    8 hours ago
















  • $begingroup$
    Welcome to Cryptography. Could you elaborate The above attack needs less calls to the hash function because it relies on the fact that each sequential hashing reduces the number of possible hashes.
    $endgroup$
    – kelalaka
    9 hours ago










  • $begingroup$
    @kelalaka The sentence after that meant to support that statement, is it out of place?
    $endgroup$
    – Yanai Eliyahu
    8 hours ago










  • $begingroup$
    @kelalaka I didn't get the first 2 sentences. This is the same birthday attack just that the possible hashes are decaying overtime, so security is reduced.
    $endgroup$
    – Yanai Eliyahu
    8 hours ago















$begingroup$
Welcome to Cryptography. Could you elaborate The above attack needs less calls to the hash function because it relies on the fact that each sequential hashing reduces the number of possible hashes.
$endgroup$
– kelalaka
9 hours ago




$begingroup$
Welcome to Cryptography. Could you elaborate The above attack needs less calls to the hash function because it relies on the fact that each sequential hashing reduces the number of possible hashes.
$endgroup$
– kelalaka
9 hours ago












$begingroup$
@kelalaka The sentence after that meant to support that statement, is it out of place?
$endgroup$
– Yanai Eliyahu
8 hours ago




$begingroup$
@kelalaka The sentence after that meant to support that statement, is it out of place?
$endgroup$
– Yanai Eliyahu
8 hours ago












$begingroup$
@kelalaka I didn't get the first 2 sentences. This is the same birthday attack just that the possible hashes are decaying overtime, so security is reduced.
$endgroup$
– Yanai Eliyahu
8 hours ago




$begingroup$
@kelalaka I didn't get the first 2 sentences. This is the same birthday attack just that the possible hashes are decaying overtime, so security is reduced.
$endgroup$
– Yanai Eliyahu
8 hours ago










2 Answers
2






active

oldest

votes


















3













$begingroup$

It is correct that the set of possible $H_n$ over all the possible $S$ reduces as $n$ grows. However the attack evaluates the $H_i$ for a fixed random $S$, not for multiple $S$; thus that reduction is immaterial to the success of the attack.



In other words: it is evaluated the number of possible $H_i$ for random $S$ as a function of $i$, and from that drawn conclusions for collision probability among the $H_i$ for sequential $i$ and a particular $S$. The conclusions are thus not justified, and, it happens, quite incorrect.



When we model $F$ as a random function, then until there is a collision the $H_i$ are random, and hence the probability of collision among the $H_i$ with $0le i<n$ is per the birthday bound.






share|improve this answer











$endgroup$














  • $begingroup$
    each $H_i$ is random from set of $2/(n+2)*2^N$ hashes, no? That's the whole point, it's the birthday problem, but reduced for each subsequent $H_i$.
    $endgroup$
    – Yanai Eliyahu
    8 hours ago











  • $begingroup$
    @Yanai Eliyahu: more precisely, for any fixed $i$, $H_i$ is random in a set of size typicaly less than $2^N$ and reducing with $i$, when the seed $S$ is uniformly random. $n$ does not come into play here. An approximation of the size of this set may be $2/(i+2)*2^N$ (depending on the particular $H$), but again since the actual $S$ is fixed, the size of that set is immaterial to the probability of collision among the $H_i$ with $0le i<n$
    $endgroup$
    – fgrieu
    8 hours ago











  • $begingroup$
    you mean because there is only 1 string, there is no collision?
    $endgroup$
    – Yanai Eliyahu
    8 hours ago










  • $begingroup$
    @Yanai Eliyahu: yes, I mean that since there is a single $S$, there is single $H_i$ for any given $i$, Thus no collision for a given $i$. If we had a magic box that performs $i$ iterated hashes in a blink, and we used that box for many $S$, then the size of the set of the possible $H_i$ would matter. But no magic box in sight.
    $endgroup$
    – fgrieu
    8 hours ago







  • 1




    $begingroup$
    Got it... it makes sense now, I tested that attack on fixed $S$, and it worked like normal birthday problem, but when I only used $H_0$ and $H_1$ and made many strings it worked as expected (improved collision chance), but reaching higher $M$ reduces the collision chance to the birthday problem.
    $endgroup$
    – Yanai Eliyahu
    8 hours ago


















2













$begingroup$

Let $M$ be the number of queries to a uniform random function $F$ at distinct points $X_1, X_2, dots, X_M$. The probability of a repeated value $F(X_i) = F(X_j)$ for $i ne j$ is at most $M^2!big/2^N$ by the birthday paradox. For $M = 2^N/3$, this is $2^2N/3!big/2^N = 1big/2^N - 2N/3 = 1big/2^N/3$. If your calculation doesn't fit this bound, there's an error in your calculation.



‘But what if we come upon a short cycle in $H mapsto F(S mathbin| H)$?’, you ask. The expected cycle length of a uniform random function is $frac12sqrt2pi,2^N approx 2^N/2$ (Harris 1960 Eqs. 3.2, 3.4, 3.11; paywall-free), so no, this method doesn't improve the expected cost.



Using a clever tortoise-chasing-hare algorithm to find a cycle, rather than making a big table and checking for duplicates, may reduce the memory or area*time cost of an attack, as in the van Oorschot–Wiener parallel collision search machine, but it doesn't escape the birthday bound!






share|improve this answer









$endgroup$














  • $begingroup$
    +1 for the classical reference to Harris, and a softcopy, which already has most of the results in later papers by crypto experts...
    $endgroup$
    – kodlu
    3 hours ago










  • $begingroup$
    I feel like Harris's paper answers about a quarter of all the questions on this site!
    $endgroup$
    – Squeamish Ossifrage
    3 hours ago













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



);






Yanai Eliyahu is a new contributor. Be nice, and check out our Code of Conduct.









draft saved

draft discarded


















StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcrypto.stackexchange.com%2fquestions%2f72850%2fwhy-this-brute-force-attack-doesnt-reduce-all-cryptographic-hash-functions-sec%23new-answer', 'question_page');

);

Post as a guest















Required, but never shown

























2 Answers
2






active

oldest

votes








2 Answers
2






active

oldest

votes









active

oldest

votes






active

oldest

votes









3













$begingroup$

It is correct that the set of possible $H_n$ over all the possible $S$ reduces as $n$ grows. However the attack evaluates the $H_i$ for a fixed random $S$, not for multiple $S$; thus that reduction is immaterial to the success of the attack.



In other words: it is evaluated the number of possible $H_i$ for random $S$ as a function of $i$, and from that drawn conclusions for collision probability among the $H_i$ for sequential $i$ and a particular $S$. The conclusions are thus not justified, and, it happens, quite incorrect.



When we model $F$ as a random function, then until there is a collision the $H_i$ are random, and hence the probability of collision among the $H_i$ with $0le i<n$ is per the birthday bound.






share|improve this answer











$endgroup$














  • $begingroup$
    each $H_i$ is random from set of $2/(n+2)*2^N$ hashes, no? That's the whole point, it's the birthday problem, but reduced for each subsequent $H_i$.
    $endgroup$
    – Yanai Eliyahu
    8 hours ago











  • $begingroup$
    @Yanai Eliyahu: more precisely, for any fixed $i$, $H_i$ is random in a set of size typicaly less than $2^N$ and reducing with $i$, when the seed $S$ is uniformly random. $n$ does not come into play here. An approximation of the size of this set may be $2/(i+2)*2^N$ (depending on the particular $H$), but again since the actual $S$ is fixed, the size of that set is immaterial to the probability of collision among the $H_i$ with $0le i<n$
    $endgroup$
    – fgrieu
    8 hours ago











  • $begingroup$
    you mean because there is only 1 string, there is no collision?
    $endgroup$
    – Yanai Eliyahu
    8 hours ago










  • $begingroup$
    @Yanai Eliyahu: yes, I mean that since there is a single $S$, there is single $H_i$ for any given $i$, Thus no collision for a given $i$. If we had a magic box that performs $i$ iterated hashes in a blink, and we used that box for many $S$, then the size of the set of the possible $H_i$ would matter. But no magic box in sight.
    $endgroup$
    – fgrieu
    8 hours ago







  • 1




    $begingroup$
    Got it... it makes sense now, I tested that attack on fixed $S$, and it worked like normal birthday problem, but when I only used $H_0$ and $H_1$ and made many strings it worked as expected (improved collision chance), but reaching higher $M$ reduces the collision chance to the birthday problem.
    $endgroup$
    – Yanai Eliyahu
    8 hours ago















3













$begingroup$

It is correct that the set of possible $H_n$ over all the possible $S$ reduces as $n$ grows. However the attack evaluates the $H_i$ for a fixed random $S$, not for multiple $S$; thus that reduction is immaterial to the success of the attack.



In other words: it is evaluated the number of possible $H_i$ for random $S$ as a function of $i$, and from that drawn conclusions for collision probability among the $H_i$ for sequential $i$ and a particular $S$. The conclusions are thus not justified, and, it happens, quite incorrect.



When we model $F$ as a random function, then until there is a collision the $H_i$ are random, and hence the probability of collision among the $H_i$ with $0le i<n$ is per the birthday bound.






share|improve this answer











$endgroup$














  • $begingroup$
    each $H_i$ is random from set of $2/(n+2)*2^N$ hashes, no? That's the whole point, it's the birthday problem, but reduced for each subsequent $H_i$.
    $endgroup$
    – Yanai Eliyahu
    8 hours ago











  • $begingroup$
    @Yanai Eliyahu: more precisely, for any fixed $i$, $H_i$ is random in a set of size typicaly less than $2^N$ and reducing with $i$, when the seed $S$ is uniformly random. $n$ does not come into play here. An approximation of the size of this set may be $2/(i+2)*2^N$ (depending on the particular $H$), but again since the actual $S$ is fixed, the size of that set is immaterial to the probability of collision among the $H_i$ with $0le i<n$
    $endgroup$
    – fgrieu
    8 hours ago











  • $begingroup$
    you mean because there is only 1 string, there is no collision?
    $endgroup$
    – Yanai Eliyahu
    8 hours ago










  • $begingroup$
    @Yanai Eliyahu: yes, I mean that since there is a single $S$, there is single $H_i$ for any given $i$, Thus no collision for a given $i$. If we had a magic box that performs $i$ iterated hashes in a blink, and we used that box for many $S$, then the size of the set of the possible $H_i$ would matter. But no magic box in sight.
    $endgroup$
    – fgrieu
    8 hours ago







  • 1




    $begingroup$
    Got it... it makes sense now, I tested that attack on fixed $S$, and it worked like normal birthday problem, but when I only used $H_0$ and $H_1$ and made many strings it worked as expected (improved collision chance), but reaching higher $M$ reduces the collision chance to the birthday problem.
    $endgroup$
    – Yanai Eliyahu
    8 hours ago













3














3










3







$begingroup$

It is correct that the set of possible $H_n$ over all the possible $S$ reduces as $n$ grows. However the attack evaluates the $H_i$ for a fixed random $S$, not for multiple $S$; thus that reduction is immaterial to the success of the attack.



In other words: it is evaluated the number of possible $H_i$ for random $S$ as a function of $i$, and from that drawn conclusions for collision probability among the $H_i$ for sequential $i$ and a particular $S$. The conclusions are thus not justified, and, it happens, quite incorrect.



When we model $F$ as a random function, then until there is a collision the $H_i$ are random, and hence the probability of collision among the $H_i$ with $0le i<n$ is per the birthday bound.






share|improve this answer











$endgroup$



It is correct that the set of possible $H_n$ over all the possible $S$ reduces as $n$ grows. However the attack evaluates the $H_i$ for a fixed random $S$, not for multiple $S$; thus that reduction is immaterial to the success of the attack.



In other words: it is evaluated the number of possible $H_i$ for random $S$ as a function of $i$, and from that drawn conclusions for collision probability among the $H_i$ for sequential $i$ and a particular $S$. The conclusions are thus not justified, and, it happens, quite incorrect.



When we model $F$ as a random function, then until there is a collision the $H_i$ are random, and hence the probability of collision among the $H_i$ with $0le i<n$ is per the birthday bound.







share|improve this answer














share|improve this answer



share|improve this answer








edited 8 hours ago

























answered 8 hours ago









fgrieufgrieu

84.6k7 gold badges188 silver badges370 bronze badges




84.6k7 gold badges188 silver badges370 bronze badges














  • $begingroup$
    each $H_i$ is random from set of $2/(n+2)*2^N$ hashes, no? That's the whole point, it's the birthday problem, but reduced for each subsequent $H_i$.
    $endgroup$
    – Yanai Eliyahu
    8 hours ago











  • $begingroup$
    @Yanai Eliyahu: more precisely, for any fixed $i$, $H_i$ is random in a set of size typicaly less than $2^N$ and reducing with $i$, when the seed $S$ is uniformly random. $n$ does not come into play here. An approximation of the size of this set may be $2/(i+2)*2^N$ (depending on the particular $H$), but again since the actual $S$ is fixed, the size of that set is immaterial to the probability of collision among the $H_i$ with $0le i<n$
    $endgroup$
    – fgrieu
    8 hours ago











  • $begingroup$
    you mean because there is only 1 string, there is no collision?
    $endgroup$
    – Yanai Eliyahu
    8 hours ago










  • $begingroup$
    @Yanai Eliyahu: yes, I mean that since there is a single $S$, there is single $H_i$ for any given $i$, Thus no collision for a given $i$. If we had a magic box that performs $i$ iterated hashes in a blink, and we used that box for many $S$, then the size of the set of the possible $H_i$ would matter. But no magic box in sight.
    $endgroup$
    – fgrieu
    8 hours ago







  • 1




    $begingroup$
    Got it... it makes sense now, I tested that attack on fixed $S$, and it worked like normal birthday problem, but when I only used $H_0$ and $H_1$ and made many strings it worked as expected (improved collision chance), but reaching higher $M$ reduces the collision chance to the birthday problem.
    $endgroup$
    – Yanai Eliyahu
    8 hours ago
















  • $begingroup$
    each $H_i$ is random from set of $2/(n+2)*2^N$ hashes, no? That's the whole point, it's the birthday problem, but reduced for each subsequent $H_i$.
    $endgroup$
    – Yanai Eliyahu
    8 hours ago











  • $begingroup$
    @Yanai Eliyahu: more precisely, for any fixed $i$, $H_i$ is random in a set of size typicaly less than $2^N$ and reducing with $i$, when the seed $S$ is uniformly random. $n$ does not come into play here. An approximation of the size of this set may be $2/(i+2)*2^N$ (depending on the particular $H$), but again since the actual $S$ is fixed, the size of that set is immaterial to the probability of collision among the $H_i$ with $0le i<n$
    $endgroup$
    – fgrieu
    8 hours ago











  • $begingroup$
    you mean because there is only 1 string, there is no collision?
    $endgroup$
    – Yanai Eliyahu
    8 hours ago










  • $begingroup$
    @Yanai Eliyahu: yes, I mean that since there is a single $S$, there is single $H_i$ for any given $i$, Thus no collision for a given $i$. If we had a magic box that performs $i$ iterated hashes in a blink, and we used that box for many $S$, then the size of the set of the possible $H_i$ would matter. But no magic box in sight.
    $endgroup$
    – fgrieu
    8 hours ago







  • 1




    $begingroup$
    Got it... it makes sense now, I tested that attack on fixed $S$, and it worked like normal birthday problem, but when I only used $H_0$ and $H_1$ and made many strings it worked as expected (improved collision chance), but reaching higher $M$ reduces the collision chance to the birthday problem.
    $endgroup$
    – Yanai Eliyahu
    8 hours ago















$begingroup$
each $H_i$ is random from set of $2/(n+2)*2^N$ hashes, no? That's the whole point, it's the birthday problem, but reduced for each subsequent $H_i$.
$endgroup$
– Yanai Eliyahu
8 hours ago





$begingroup$
each $H_i$ is random from set of $2/(n+2)*2^N$ hashes, no? That's the whole point, it's the birthday problem, but reduced for each subsequent $H_i$.
$endgroup$
– Yanai Eliyahu
8 hours ago













$begingroup$
@Yanai Eliyahu: more precisely, for any fixed $i$, $H_i$ is random in a set of size typicaly less than $2^N$ and reducing with $i$, when the seed $S$ is uniformly random. $n$ does not come into play here. An approximation of the size of this set may be $2/(i+2)*2^N$ (depending on the particular $H$), but again since the actual $S$ is fixed, the size of that set is immaterial to the probability of collision among the $H_i$ with $0le i<n$
$endgroup$
– fgrieu
8 hours ago





$begingroup$
@Yanai Eliyahu: more precisely, for any fixed $i$, $H_i$ is random in a set of size typicaly less than $2^N$ and reducing with $i$, when the seed $S$ is uniformly random. $n$ does not come into play here. An approximation of the size of this set may be $2/(i+2)*2^N$ (depending on the particular $H$), but again since the actual $S$ is fixed, the size of that set is immaterial to the probability of collision among the $H_i$ with $0le i<n$
$endgroup$
– fgrieu
8 hours ago













$begingroup$
you mean because there is only 1 string, there is no collision?
$endgroup$
– Yanai Eliyahu
8 hours ago




$begingroup$
you mean because there is only 1 string, there is no collision?
$endgroup$
– Yanai Eliyahu
8 hours ago












$begingroup$
@Yanai Eliyahu: yes, I mean that since there is a single $S$, there is single $H_i$ for any given $i$, Thus no collision for a given $i$. If we had a magic box that performs $i$ iterated hashes in a blink, and we used that box for many $S$, then the size of the set of the possible $H_i$ would matter. But no magic box in sight.
$endgroup$
– fgrieu
8 hours ago





$begingroup$
@Yanai Eliyahu: yes, I mean that since there is a single $S$, there is single $H_i$ for any given $i$, Thus no collision for a given $i$. If we had a magic box that performs $i$ iterated hashes in a blink, and we used that box for many $S$, then the size of the set of the possible $H_i$ would matter. But no magic box in sight.
$endgroup$
– fgrieu
8 hours ago





1




1




$begingroup$
Got it... it makes sense now, I tested that attack on fixed $S$, and it worked like normal birthday problem, but when I only used $H_0$ and $H_1$ and made many strings it worked as expected (improved collision chance), but reaching higher $M$ reduces the collision chance to the birthday problem.
$endgroup$
– Yanai Eliyahu
8 hours ago




$begingroup$
Got it... it makes sense now, I tested that attack on fixed $S$, and it worked like normal birthday problem, but when I only used $H_0$ and $H_1$ and made many strings it worked as expected (improved collision chance), but reaching higher $M$ reduces the collision chance to the birthday problem.
$endgroup$
– Yanai Eliyahu
8 hours ago













2













$begingroup$

Let $M$ be the number of queries to a uniform random function $F$ at distinct points $X_1, X_2, dots, X_M$. The probability of a repeated value $F(X_i) = F(X_j)$ for $i ne j$ is at most $M^2!big/2^N$ by the birthday paradox. For $M = 2^N/3$, this is $2^2N/3!big/2^N = 1big/2^N - 2N/3 = 1big/2^N/3$. If your calculation doesn't fit this bound, there's an error in your calculation.



‘But what if we come upon a short cycle in $H mapsto F(S mathbin| H)$?’, you ask. The expected cycle length of a uniform random function is $frac12sqrt2pi,2^N approx 2^N/2$ (Harris 1960 Eqs. 3.2, 3.4, 3.11; paywall-free), so no, this method doesn't improve the expected cost.



Using a clever tortoise-chasing-hare algorithm to find a cycle, rather than making a big table and checking for duplicates, may reduce the memory or area*time cost of an attack, as in the van Oorschot–Wiener parallel collision search machine, but it doesn't escape the birthday bound!






share|improve this answer









$endgroup$














  • $begingroup$
    +1 for the classical reference to Harris, and a softcopy, which already has most of the results in later papers by crypto experts...
    $endgroup$
    – kodlu
    3 hours ago










  • $begingroup$
    I feel like Harris's paper answers about a quarter of all the questions on this site!
    $endgroup$
    – Squeamish Ossifrage
    3 hours ago















2













$begingroup$

Let $M$ be the number of queries to a uniform random function $F$ at distinct points $X_1, X_2, dots, X_M$. The probability of a repeated value $F(X_i) = F(X_j)$ for $i ne j$ is at most $M^2!big/2^N$ by the birthday paradox. For $M = 2^N/3$, this is $2^2N/3!big/2^N = 1big/2^N - 2N/3 = 1big/2^N/3$. If your calculation doesn't fit this bound, there's an error in your calculation.



‘But what if we come upon a short cycle in $H mapsto F(S mathbin| H)$?’, you ask. The expected cycle length of a uniform random function is $frac12sqrt2pi,2^N approx 2^N/2$ (Harris 1960 Eqs. 3.2, 3.4, 3.11; paywall-free), so no, this method doesn't improve the expected cost.



Using a clever tortoise-chasing-hare algorithm to find a cycle, rather than making a big table and checking for duplicates, may reduce the memory or area*time cost of an attack, as in the van Oorschot–Wiener parallel collision search machine, but it doesn't escape the birthday bound!






share|improve this answer









$endgroup$














  • $begingroup$
    +1 for the classical reference to Harris, and a softcopy, which already has most of the results in later papers by crypto experts...
    $endgroup$
    – kodlu
    3 hours ago










  • $begingroup$
    I feel like Harris's paper answers about a quarter of all the questions on this site!
    $endgroup$
    – Squeamish Ossifrage
    3 hours ago













2














2










2







$begingroup$

Let $M$ be the number of queries to a uniform random function $F$ at distinct points $X_1, X_2, dots, X_M$. The probability of a repeated value $F(X_i) = F(X_j)$ for $i ne j$ is at most $M^2!big/2^N$ by the birthday paradox. For $M = 2^N/3$, this is $2^2N/3!big/2^N = 1big/2^N - 2N/3 = 1big/2^N/3$. If your calculation doesn't fit this bound, there's an error in your calculation.



‘But what if we come upon a short cycle in $H mapsto F(S mathbin| H)$?’, you ask. The expected cycle length of a uniform random function is $frac12sqrt2pi,2^N approx 2^N/2$ (Harris 1960 Eqs. 3.2, 3.4, 3.11; paywall-free), so no, this method doesn't improve the expected cost.



Using a clever tortoise-chasing-hare algorithm to find a cycle, rather than making a big table and checking for duplicates, may reduce the memory or area*time cost of an attack, as in the van Oorschot–Wiener parallel collision search machine, but it doesn't escape the birthday bound!






share|improve this answer









$endgroup$



Let $M$ be the number of queries to a uniform random function $F$ at distinct points $X_1, X_2, dots, X_M$. The probability of a repeated value $F(X_i) = F(X_j)$ for $i ne j$ is at most $M^2!big/2^N$ by the birthday paradox. For $M = 2^N/3$, this is $2^2N/3!big/2^N = 1big/2^N - 2N/3 = 1big/2^N/3$. If your calculation doesn't fit this bound, there's an error in your calculation.



‘But what if we come upon a short cycle in $H mapsto F(S mathbin| H)$?’, you ask. The expected cycle length of a uniform random function is $frac12sqrt2pi,2^N approx 2^N/2$ (Harris 1960 Eqs. 3.2, 3.4, 3.11; paywall-free), so no, this method doesn't improve the expected cost.



Using a clever tortoise-chasing-hare algorithm to find a cycle, rather than making a big table and checking for duplicates, may reduce the memory or area*time cost of an attack, as in the van Oorschot–Wiener parallel collision search machine, but it doesn't escape the birthday bound!







share|improve this answer












share|improve this answer



share|improve this answer










answered 6 hours ago









Squeamish OssifrageSqueamish Ossifrage

31.1k1 gold badge52 silver badges133 bronze badges




31.1k1 gold badge52 silver badges133 bronze badges














  • $begingroup$
    +1 for the classical reference to Harris, and a softcopy, which already has most of the results in later papers by crypto experts...
    $endgroup$
    – kodlu
    3 hours ago










  • $begingroup$
    I feel like Harris's paper answers about a quarter of all the questions on this site!
    $endgroup$
    – Squeamish Ossifrage
    3 hours ago
















  • $begingroup$
    +1 for the classical reference to Harris, and a softcopy, which already has most of the results in later papers by crypto experts...
    $endgroup$
    – kodlu
    3 hours ago










  • $begingroup$
    I feel like Harris's paper answers about a quarter of all the questions on this site!
    $endgroup$
    – Squeamish Ossifrage
    3 hours ago















$begingroup$
+1 for the classical reference to Harris, and a softcopy, which already has most of the results in later papers by crypto experts...
$endgroup$
– kodlu
3 hours ago




$begingroup$
+1 for the classical reference to Harris, and a softcopy, which already has most of the results in later papers by crypto experts...
$endgroup$
– kodlu
3 hours ago












$begingroup$
I feel like Harris's paper answers about a quarter of all the questions on this site!
$endgroup$
– Squeamish Ossifrage
3 hours ago




$begingroup$
I feel like Harris's paper answers about a quarter of all the questions on this site!
$endgroup$
– Squeamish Ossifrage
3 hours ago










Yanai Eliyahu is a new contributor. Be nice, and check out our Code of Conduct.









draft saved

draft discarded


















Yanai Eliyahu is a new contributor. Be nice, and check out our Code of Conduct.












Yanai Eliyahu is a new contributor. Be nice, and check out our Code of Conduct.











Yanai Eliyahu is a new contributor. Be nice, and check out our Code of Conduct.














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%2f72850%2fwhy-this-brute-force-attack-doesnt-reduce-all-cryptographic-hash-functions-sec%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

19. јануар Садржај Догађаји Рођења Смрти Празници и дани сећања Види још Референце Мени за навигацијуу

Israel Cuprins Etimologie | Istorie | Geografie | Politică | Demografie | Educație | Economie | Cultură | Note explicative | Note bibliografice | Bibliografie | Legături externe | Meniu de navigaresite web oficialfacebooktweeterGoogle+Instagramcanal YouTubeInstagramtextmodificaremodificarewww.technion.ac.ilnew.huji.ac.ilwww.weizmann.ac.ilwww1.biu.ac.ilenglish.tau.ac.ilwww.haifa.ac.ilin.bgu.ac.ilwww.openu.ac.ilwww.ariel.ac.ilCIA FactbookHarta Israelului"Negotiating Jerusalem," Palestine–Israel JournalThe Schizoid Nature of Modern Hebrew: A Slavic Language in Search of a Semitic Past„Arabic in Israel: an official language and a cultural bridge”„Latest Population Statistics for Israel”„Israel Population”„Tables”„Report for Selected Countries and Subjects”Human Development Report 2016: Human Development for Everyone„Distribution of family income - Gini index”The World FactbookJerusalem Law„Israel”„Israel”„Zionist Leaders: David Ben-Gurion 1886–1973”„The status of Jerusalem”„Analysis: Kadima's big plans”„Israel's Hard-Learned Lessons”„The Legacy of Undefined Borders, Tel Aviv Notes No. 40, 5 iunie 2002”„Israel Journal: A Land Without Borders”„Population”„Israel closes decade with population of 7.5 million”Time Series-DataBank„Selected Statistics on Jerusalem Day 2007 (Hebrew)”Golan belongs to Syria, Druze protestGlobal Survey 2006: Middle East Progress Amid Global Gains in FreedomWHO: Life expectancy in Israel among highest in the worldInternational Monetary Fund, World Economic Outlook Database, April 2011: Nominal GDP list of countries. Data for the year 2010.„Israel's accession to the OECD”Popular Opinion„On the Move”Hosea 12:5„Walking the Bible Timeline”„Palestine: History”„Return to Zion”An invention called 'the Jewish people' – Haaretz – Israel NewsoriginalJewish and Non-Jewish Population of Palestine-Israel (1517–2004)ImmigrationJewishvirtuallibrary.orgChapter One: The Heralders of Zionism„The birth of modern Israel: A scrap of paper that changed history”„League of Nations: The Mandate for Palestine, 24 iulie 1922”The Population of Palestine Prior to 1948originalBackground Paper No. 47 (ST/DPI/SER.A/47)History: Foreign DominationTwo Hundred and Seventh Plenary Meeting„Israel (Labor Zionism)”Population, by Religion and Population GroupThe Suez CrisisAdolf EichmannJustice Ministry Reply to Amnesty International Report„The Interregnum”Israel Ministry of Foreign Affairs – The Palestinian National Covenant- July 1968Research on terrorism: trends, achievements & failuresThe Routledge Atlas of the Arab–Israeli conflict: The Complete History of the Struggle and the Efforts to Resolve It"George Habash, Palestinian Terrorism Tactician, Dies at 82."„1973: Arab states attack Israeli forces”Agranat Commission„Has Israel Annexed East Jerusalem?”original„After 4 Years, Intifada Still Smolders”From the End of the Cold War to 2001originalThe Oslo Accords, 1993Israel-PLO Recognition – Exchange of Letters between PM Rabin and Chairman Arafat – Sept 9- 1993Foundation for Middle East PeaceSources of Population Growth: Total Israeli Population and Settler Population, 1991–2003original„Israel marks Rabin assassination”The Wye River Memorandumoriginal„West Bank barrier route disputed, Israeli missile kills 2”"Permanent Ceasefire to Be Based on Creation Of Buffer Zone Free of Armed Personnel Other than UN, Lebanese Forces"„Hezbollah kills 8 soldiers, kidnaps two in offensive on northern border”„Olmert confirms peace talks with Syria”„Battleground Gaza: Israeli ground forces invade the strip”„IDF begins Gaza troop withdrawal, hours after ending 3-week offensive”„THE LAND: Geography and Climate”„Area of districts, sub-districts, natural regions and lakes”„Israel - Geography”„Makhteshim Country”Israel and the Palestinian Territories„Makhtesh Ramon”„The Living Dead Sea”„Temperatures reach record high in Pakistan”„Climate Extremes In Israel”Israel in figures„Deuteronom”„JNF: 240 million trees planted since 1901”„Vegetation of Israel and Neighboring Countries”Environmental Law in Israel„Executive branch”„Israel's election process explained”„The Electoral System in Israel”„Constitution for Israel”„All 120 incoming Knesset members”„Statul ISRAEL”„The Judiciary: The Court System”„Israel's high court unique in region”„Israel and the International Criminal Court: A Legal Battlefield”„Localities and population, by population group, district, sub-district and natural region”„Israel: Districts, Major Cities, Urban Localities & Metropolitan Areas”„Israel-Egypt Relations: Background & Overview of Peace Treaty”„Solana to Haaretz: New Rules of War Needed for Age of Terror”„Israel's Announcement Regarding Settlements”„United Nations Security Council Resolution 497”„Security Council resolution 478 (1980) on the status of Jerusalem”„Arabs will ask U.N. to seek razing of Israeli wall”„Olmert: Willing to trade land for peace”„Mapping Peace between Syria and Israel”„Egypt: Israel must accept the land-for-peace formula”„Israel: Age structure from 2005 to 2015”„Global, regional, and national disability-adjusted life years (DALYs) for 306 diseases and injuries and healthy life expectancy (HALE) for 188 countries, 1990–2013: quantifying the epidemiological transition”10.1016/S0140-6736(15)61340-X„World Health Statistics 2014”„Life expectancy for Israeli men world's 4th highest”„Family Structure and Well-Being Across Israel's Diverse Population”„Fertility among Jewish and Muslim Women in Israel, by Level of Religiosity, 1979-2009”„Israel leaders in birth rate, but poverty major challenge”„Ethnic Groups”„Israel's population: Over 8.5 million”„Israel - Ethnic groups”„Jews, by country of origin and age”„Minority Communities in Israel: Background & Overview”„Israel”„Language in Israel”„Selected Data from the 2011 Social Survey on Mastery of the Hebrew Language and Usage of Languages”„Religions”„5 facts about Israeli Druze, a unique religious and ethnic group”„Israël”Israel Country Study Guide„Haredi city in Negev – blessing or curse?”„New town Harish harbors hopes of being more than another Pleasantville”„List of localities, in alphabetical order”„Muncitorii români, doriți în Israel”„Prietenia româno-israeliană la nevoie se cunoaște”„The Higher Education System in Israel”„Middle East”„Academic Ranking of World Universities 2016”„Israel”„Israel”„Jewish Nobel Prize Winners”„All Nobel Prizes in Literature”„All Nobel Peace Prizes”„All Prizes in Economic Sciences”„All Nobel Prizes in Chemistry”„List of Fields Medallists”„Sakharov Prize”„Țara care și-a sfidat "destinul" și se bate umăr la umăr cu Silicon Valley”„Apple's R&D center in Israel grew to about 800 employees”„Tim Cook: Apple's Herzliya R&D center second-largest in world”„Lecții de economie de la Israel”„Land use”Israel Investment and Business GuideA Country Study: IsraelCentral Bureau of StatisticsFlorin Diaconu, „Kadima: Flexibilitate și pragmatism, dar nici un compromis în chestiuni vitale", în Revista Institutului Diplomatic Român, anul I, numărul I, semestrul I, 2006, pp. 71-72Florin Diaconu, „Likud: Dreapta israeliană constant opusă retrocedării teritoriilor cureite prin luptă în 1967", în Revista Institutului Diplomatic Român, anul I, numărul I, semestrul I, 2006, pp. 73-74MassadaIsraelul a crescut in 50 de ani cât alte state intr-un mileniuIsrael Government PortalIsraelIsraelIsraelmmmmmXX451232cb118646298(data)4027808-634110000 0004 0372 0767n7900328503691455-bb46-37e3-91d2-cb064a35ffcc1003570400564274ge1294033523775214929302638955X146498911146498911

Черчино Становништво Референце Спољашње везе Мени за навигацију46°09′29″ СГШ; 9°30′29″ ИГД / 46.15809° СГШ; 9.50814° ИГД / 46.15809; 9.5081446°09′29″ СГШ; 9°30′29″ ИГД / 46.15809° СГШ; 9.50814° ИГД / 46.15809; 9.508143179111„The GeoNames geographical database”„Istituto Nazionale di Statistica”Званични веб-сајтпроширитиуу