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: David T. Ashley on 6 Apr 2010 17:30 Assume that I have an SHA-512 hash of a file (512 bits). Assume that I want to find a second file with the same hash and can't attack the hash function (i.e. I can only repeatedly try new files). This is harder than a birthday attack, right? The mathematics of a birthday attack http://en.wikipedia.org/wiki/Birthday_attack are results for finding a collision in a set of attempts. Having a single hash already and trying to match it is harder, right (you are looking for a SPECIFIC collision rather than any collision)? And what is the expected value of the number of attempts until a match is found? I want to say approximately 2^511, but that would be too simple .... Thanks, Datesfat
From: robertwessel2 on 6 Apr 2010 17:55 On Apr 6, 4:30 pm, "David T. Ashley" <dash...(a)gmail.com> wrote: > Assume that I have an SHA-512 hash of a file (512 bits). Assume that I want > to find a second file with the same hash and can't attack the hash function > (i.e. I can only repeatedly try new files). > > This is harder than a birthday attack, right? The mathematics of a birthday > attack > > http://en.wikipedia.org/wiki/Birthday_attack > > are results for finding a collision in a set of attempts. Having a single > hash already and trying to match it is harder, right (you are looking for a > SPECIFIC collision rather than any collision)? > > And what is the expected value of the number of attempts until a match is > found? I want to say approximately 2^511, but that would be too simple .... That's called a preimage attack (or resistance thereto). If there are no weaknesses in SHA-512, then your estimate is exactly right. I don't know of any significant results against SHA-2, but there have certainly been some against MD5 and SHA-1, but as far as I know no one has actually successfully completed any actual preimage attacks against MD5 or SHA-x. But a preimage attack against MD5 is theoretically possible in about 2**116 operations (which is still quite impractical, but is significantly worse than the 2**128 we'd hope for). There have been a number of success collisions generated for MD5 and SHA-1, including the generation of a fake MD5 based SSL certificate (IIRC, an MD5 collision is now possible in less than 2**52 operations).
From: Greg Rose on 6 Apr 2010 18:15 In article <98WdnZxwQIpmOibWnZ2dnUVZ_jSdnZ2d(a)giganews.com>, David T. Ashley <dashley(a)gmail.com> wrote: >Assume that I have an SHA-512 hash of a file (512 bits). Assume that I want >to find a second file with the same hash and can't attack the hash function >(i.e. I can only repeatedly try new files). > >This is harder than a birthday attack, right? The mathematics of a birthday >attack > >http://en.wikipedia.org/wiki/Birthday_attack > >are results for finding a collision in a set of attempts. Having a single >hash already and trying to match it is harder, right (you are looking for a >SPECIFIC collision rather than any collision)? > >And what is the expected value of the number of attempts until a match is >found? I want to say approximately 2^511, but that would be too simple .... Sometimes the simple answer is correct. Greg. --
From: Scott Fluhrer on 6 Apr 2010 22:48 "David T. Ashley" <dashley(a)gmail.com> wrote in message news:98WdnZxwQIpmOibWnZ2dnUVZ_jSdnZ2d(a)giganews.com... > Assume that I have an SHA-512 hash of a file (512 bits). Assume that I > want to find a second file with the same hash and can't attack the hash > function (i.e. I can only repeatedly try new files). > > This is harder than a birthday attack, right? The mathematics of a > birthday attack > > http://en.wikipedia.org/wiki/Birthday_attack > > are results for finding a collision in a set of attempts. Having a single > hash already and trying to match it is harder, right (you are looking for > a SPECIFIC collision rather than any collision)? > > And what is the expected value of the number of attempts until a match is > found? I want to say approximately 2^511, but that would be too simple > .... Actually, if we model SHA-512 as a random oracle, the expected number of attempts is actually 2^512. This is because SHA-512 is a function, not a permutation, and so finding one value that doesn't hash to the right value doesn't make any other value apriori more likely to succeed (as opposed to, say, searching for a plaintext block that AES encrypts with an unknown key to a specific ciphertext block; we know that we'll come across the right one after a maximum of 2^128 attempts, and so any failed attempt makes the next attempt more likely to happen to be value you're searching for). -- poncho
From: Jonathan Degolyer on 7 Apr 2010 01:39
On Apr 6, 10:48 pm, "Scott Fluhrer" <sfluh...(a)ix.netcom.com> wrote: > "David T. Ashley" <dash...(a)gmail.com> wrote in messagenews:98WdnZxwQIpmOibWnZ2dnUVZ_jSdnZ2d(a)giganews.com... > > > > > Assume that I have an SHA-512 hash of a file (512 bits). Assume that I > > want to find a second file with the same hash and can't attack the hash > > function (i.e. I can only repeatedly try new files). > > > This is harder than a birthday attack, right? The mathematics of a > > birthday attack > > >http://en.wikipedia.org/wiki/Birthday_attack > > > are results for finding a collision in a set of attempts. Having a single > > hash already and trying to match it is harder, right (you are looking for > > a SPECIFIC collision rather than any collision)? > > > And what is the expected value of the number of attempts until a match is > > found? I want to say approximately 2^511, but that would be too simple > > .... > > Actually, if we model SHA-512 as a random oracle, the expected number of > attempts is actually 2^512. This is because SHA-512 is a function, not a > permutation, and so finding one value that doesn't hash to the right value > doesn't make any other value apriori more likely to succeed (as opposed to, > say, searching for a plaintext block that AES encrypts with an unknown key > to a specific ciphertext block; we know that we'll come across the right one > after a maximum of 2^128 attempts, and so any failed attempt makes the next > attempt more likely to happen to be value you're searching for). > > -- > poncho @Scott Fluhrer Well, my calculator doesn't have the sufficient degree of precision for finding the odds of collisions using 512 bit hash functions, but for 256 bit hash functions I get a slightly different result from what you describe: Assumption: For any randomly selected message, mx, the probability that h(mx) will collide with a specific 256 bit digest, h(ma), is 1 in 2^256. Additional assumption: the number of possible messages that can be hashed is infinite, or so gargantuan as to be effectively infinite, such that failing to produce a collision with one random message does not increase the collision odds of any other randomly selected message. Under these assumptions, the odds that a randomly chosen message will NOT collide with a specific digest is thus 1-(2^-256). And the odds that _not even one_ out of y many randomly chosen messages will collide with the target digest is {1-(2^-256)}^y. So, if my math is right (and it's one o'clock in the morning, so that's a pretty big if), then there is a 63% chance with 2^256 randomly chosen messages that at least one of them will collide with the target digest. With just 2^255 randomly chosen messages there is only a 39% chance of a collision. So to have a 50% chance of finding a collision with a specific digest you need to hash slightly less than 2^256 random messages (approximately 2^255.5). Presumably there is a similar result for 512-bit hash functions, though I cannot confirm that with my crappy equipment. Also I may be completely off in my assumptions and/or calculations -- it wouldn't be the first time, and certainly won't be the last. |