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: unruh on 12 Apr 2010 20:57 On 2010-04-12, Sal <here(a)softcom.net> wrote: > On Apr 8, 9:23?am, "Scott Fluhrer" <sfluh...(a)ix.netcom.com> wrote: >> "Noob" <r...(a)127.0.0.1> wrote in message >> >> news:hpkl7e$tg2$1(a)speranza.aioe.org... >> >> >> >> >> > Therefore, the probability that AT LEAST ONE string hashes to the >> > candidate hash is PP = 1 - (1-p)^N >> >> > As far as I can tell, the question asked is: How many strings must one >> > consider before it is likely one finds at least one collision. >> >> Well, no, the OP asked "what is the expected value of the number of attempts >> until a match is found". ?"Expected number" is not "how many you have to do >> before you get to 50%". ?To put it in statistics terms, the expected value >> is the mean number of attempts, not the median. >> >> -- >> poncho > > 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, that is a different question. The "expected value" is a technical term meaning "the mean" which in this case is exactly 2^512. Yours could be called the median value which is slightly less than 2^512.
From: Scott Fluhrer on 12 Apr 2010 21:00 "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. -- poncho
From: David Bernier on 13 Apr 2010 01:51 unruh wrote: > On 2010-04-12, Sal <here(a)softcom.net> wrote: >> On Apr 8, 9:23?am, "Scott Fluhrer" <sfluh...(a)ix.netcom.com> wrote: >>> "Noob" <r...(a)127.0.0.1> wrote in message >>> >>> news:hpkl7e$tg2$1(a)speranza.aioe.org... >>> >>> >>> >>> >>>> Therefore, the probability that AT LEAST ONE string hashes to the >>>> candidate hash is PP = 1 - (1-p)^N >>>> As far as I can tell, the question asked is: How many strings must one >>>> consider before it is likely one finds at least one collision. >>> Well, no, the OP asked "what is the expected value of the number of attempts >>> until a match is found". ?"Expected number" is not "how many you have to do >>> before you get to 50%". ?To put it in statistics terms, the expected value >>> is the mean number of attempts, not the median. >>> >>> -- >>> poncho >> 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, that is a different question. The "expected value" is a technical > term meaning "the mean" which in this case is exactly 2^512. > Yours could be called the median value which is slightly less than > 2^512. A related topic: birthday attacks on hash functions. Wikipedia has an article on birthday attacks, reduced to the simpler problem of finding two distinct messages with the same hash value (a collision). I'd say the collision probabilities after 'n' random messages give an upper limit or upper bound on the security/assurance provided by supposedly secure hash functions. For a 512-bit hash, with n = 1.6 x 10^68 random messages, the Wikipedia article gives a probability of one or more hash collision as 10^(-18): < http://en.wikipedia.org/wiki/Birthday_attack > . I thought SHA-256 should be pretty good, but I guess it depends on one's requirements. About the SHA-2 family: < http://en.wikipedia.org/wiki/SHA-2 > . David Bernier
From: Kristian Gj�steen on 13 Apr 2010 02:55 David Bernier <david250(a)videotron.ca> wrote: >For a 512-bit hash, with n = 1.6 x 10^68 random messages, >the Wikipedia article gives a probability of one or >more hash collision as 10^(-18): >< http://en.wikipedia.org/wiki/Birthday_attack > . > >I thought SHA-256 should be pretty good, but I guess it depends >on one's requirements. Which requirement that has to do with collisions isn't satisfied by SHA-256? -- Kristian Gj�steen
From: David Bernier on 13 Apr 2010 04:53
wrote: > David Bernier <david250(a)videotron.ca> wrote: >> For a 512-bit hash, with n = 1.6 x 10^68 random messages, >> the Wikipedia article gives a probability of one or >> more hash collision as 10^(-18): >> < http://en.wikipedia.org/wiki/Birthday_attack > . >> >> I thought SHA-256 should be pretty good, but I guess it depends >> on one's requirements. > > Which requirement that has to do with collisions isn't satisfied by > SHA-256? I don't know. The Wikipedia article on SHA-2 just says this: << In cryptography, SHA-2 is a set of cryptographic hash functions (SHA-224, SHA-256, SHA-384, SHA-512) designed by the National Security Agency (NSA) and published in 2001 by the NIST as a U.S. Federal Information Processing Standard. >> Then there's the NIST page about the hash function competition for what will become "SHA-3" : < http://csrc.nist.gov/groups/ST/hash/sha-3/index.html > . David Bernier |