Difficulty of Matching an SHA-512 Hash By Brute Force
in [Cryptography]
|
Prev: Computer Bunker
Next: Difficulty of Matching an SHA-512 Hash By Brute Force SecureRandom sr = SecureRandom.getInstance("SHA1PRNG");
From: Mike Amling on 18 Apr 2010 08:21 Scott Fluhrer wrote: > "Sal" <here(a)softcom.net> wrote in message > news:8012e1bf-2b3a-46a0-805c-1d31f1d7a280(a)b33g2000yqc.googlegroups.com... > >> Can't compute it, but for accuracy isn't this the REAL solution? Find >> N where: >> >> ((2^512)-1)/2^512 * ((2^512)-2)/2^512 * ((2^512)-3)/2^512 * ... * >> ((2^512)-N)/2^512 ~ 50% > > No, it is not (even if the question were "how many attempts have to do > before you get to 50% probability of one attempt succeeding"). The > probability of the first attempt failing is indeed ((2^512)-1)/2^512, > however the probability of the first two attempts both failing is > ((2^512)-1)/2^512 * ((2^512)-1)/2^512, not ((2^512)-1)/2^512 * > ((2^512)-2)/2^512. That's because the hashes of the two attempts (assuming > that the values hashed are distinct) are independent, and so the probability > of second one succeeding is independent of the probability of the first one > succeeding. > > The answer to that question is the value of N such that ((2^512)-1)/2^512) > ** N ~ 50%. Noob gave the correct solution to that: N ~ ln(2) / 2**512. ln(2)/2**512 is a pretty small number. I could more easily believe 2**512/ln(2). --Mike Amling
From: Scott Fluhrer on 18 Apr 2010 10:58
"Mike Amling" <mamling(a)rmcis.com> wrote in message news:830bt6FmnmU1(a)mid.individual.net... > Scott Fluhrer wrote: >> "Sal" <here(a)softcom.net> wrote in message >> news:8012e1bf-2b3a-46a0-805c-1d31f1d7a280(a)b33g2000yqc.googlegroups.com... >> >>> Can't compute it, but for accuracy isn't this the REAL solution? Find >>> N where: >>> >>> ((2^512)-1)/2^512 * ((2^512)-2)/2^512 * ((2^512)-3)/2^512 * ... * >>> ((2^512)-N)/2^512 ~ 50% >> >> No, it is not (even if the question were "how many attempts have to do >> before you get to 50% probability of one attempt succeeding"). The >> probability of the first attempt failing is indeed ((2^512)-1)/2^512, >> however the probability of the first two attempts both failing is >> ((2^512)-1)/2^512 * ((2^512)-1)/2^512, not ((2^512)-1)/2^512 * >> ((2^512)-2)/2^512. That's because the hashes of the two attempts >> (assuming that the values hashed are distinct) are independent, and so >> the probability of second one succeeding is independent of the >> probability of the first one succeeding. >> >> The answer to that question is the value of N such that >> ((2^512)-1)/2^512) ** N ~ 50%. Noob gave the correct solution to that: N >> ~ ln(2) / 2**512. > > ln(2)/2**512 is a pretty small number. I could more easily believe > 2**512/ln(2). Doh! The correct answer is: N ~ ln(2) * 2**512. -- poncho |