2
$\begingroup$

I'm aware that MD5 is broken, and collisions have been found for it. I'm interested in other hashes (SHA-1, SHA-2, SHA-3) when truncated to the same digest size, i.e. 128 bits.

The time complexity of a collision attack is 2^(n/2) (the "birthday attack"). So in the case of a 128 bit hash, one would have to hash 2^64 inputs for a 50% probability of finding any two inputs hashing to the same value (though a collision might be found much earlier in practice).

The currently fastest single Bitcoin mining machine performs about 5 trillion double SHA-256 hashes per second, so assuming 10 trillion/sec for single ones, and assuming the inputs tested would not be larger than one block it would amount to:

2^64 / 10*10^12 / 31536000 = 5.85 years

To scan enough hashes to yield a 50% chance of a collision. Though at that point the machine would have to allocate at least 16 * 2^64 ~= 2.95+e20 bytes ~= 295 exabytes of memory for storing the previous hashes. With today's computing capabilities, this seems somewhat reachable (though not very trivial, and may be extremely expensive to handle the enormous memory/storage requirements).

Has this already been tried/achieved? any references? (I'm interested mostly in attacks using brute-force search, but more sophisticated ones are also relevant).

Improve this question
$\endgroup$
6
  • $\begingroup$ I'd guess no, but it's only a guess, because I can't think of any sitatuation where you'd want to use a 128-bit hash function. And hence this would be "just for fun" and it looks to expensive for that. (Maybe NSA did though...) $\endgroup$
    – SEJPM
    Commented May 19, 2015 at 11:32
  • $\begingroup$ Also note that there are ways to search for such a collision that radically reduce the amount of memory required (at not that huge of a computational cost). $\endgroup$
    – poncho
    Commented May 19, 2015 at 19:09
  • $\begingroup$ additional note: Using a single machine is pointless, such an attack would use many machines and effectively reduce the time needed to a lot less, like a few days. (NSA certainly can do this I think) $\endgroup$
    – SEJPM
    Commented May 19, 2015 at 19:23
  • $\begingroup$ @SOJPM: sure, I gave the example to show that it could be even done with one machine. Managing and distributing the CPU power wouldn't really a problem (I guess it's a sort of a "embarrassingly parallelizable" problem). The monster memory/storage requirements would be much more challenging, though.. $\endgroup$
    – Anon2000
    Commented May 19, 2015 at 19:49
  • $\begingroup$ @poncho: I'm really interested what kind of approach you describe. Is this some way to order the workload for efficient memory utilization, or based on a more theoretical attack? $\endgroup$
    – Anon2000
    Commented May 19, 2015 at 19:50

1 Answer 1

Reset to default
2
$\begingroup$

I'm not aware of any case where somebody actually searched for such a collision.

However it would certainly be possible as the same workload ($2^{64}$) was already accomplished a few years ago (2002) by this project, having brute-forced RC5-64.

Now assume you'd use the full power of the bitcoin blockchain (300 Peta-Hashes / s = 600 Peta-Hashes /s for single hashing(19th may 2015)) you'd expect a (64-bit-)collision after 30.74 seconds ($=2^{64}/600*10^{15}$).

As noted correctly by poncho there are algorithms that help you overcome the massive amount of memory you calculated. Of particular interest would be a "memoryless" variation of Yuval's birthday attack(book page: 369, pdf page: 50 of the "Handbook of applied Cryptography").
This related question may be helpful.

Improve this answer
$\endgroup$
16
  • $\begingroup$ I was actually expecting this to be a sort of a prefix-tree or some other data structure.. (at least something I could perhaps more easily understand :) ). It turned out to be a bit more challenging than I expected. I guess it'll to take me some time to figure it out. It's sort of hard for me though, to imagine how this process could be "memoryless" in concept. Is there some easier, less mathematically precise explanation for how exactly it is this possible to go through 2^64 unpredictable values and find a single duplicate without needing to somehow memorize them? $\endgroup$
    – Anon2000
    Commented May 19, 2015 at 20:21
  • $\begingroup$ the basic idea of the paper cited in the related question is to find a collision using cycle-finding. This means you calculate $x_1=h(x_1)$ and $x_2=h(h(x_2))$ as soon as $x_2=x_1$ you've found a collision (if you remembered the pre-images...) this requires you to store only a small amount of data (the current values and the pre-images) and you'll still find the answer in $O(2^{n/2})$. The fact that this works has to do that random mappings (-> hashes) follow some path and start to cycle and you basically let the one always make 2 steps on the cycle and the other only one until they meet. $\endgroup$
    – SEJPM
    Commented May 19, 2015 at 20:30
  • $\begingroup$ @Anon2000: one obvious way is to do iterated hashing (where we compute $x_i = Hash_{128}(x_{i-1})$, and stop at distinguished points (say, the first 32 bits are all zero), and store the initial/final values in a table. Build up a long list of such table entries (circa $2^{32}$ should do), and look for collisions in the final value -- if we find one, then the two chains merge (and finding where the chains merge is straight-forward). That's not a zero-memory solution, however it gets the memory requirements small enough... $\endgroup$
    – poncho
    Commented May 19, 2015 at 20:31
  • $\begingroup$ @SEJPM Surprisingly, I managed to somehow understand your suggestion first! perhaps not 100% though, at least not yet.. There's one interesting thing though, is that the "cycle" you describe when performing h(h(h(...))) is actually a "collision" (i.e. an already seen hash) right? however that particular collision is not necessarily the one that would be eventually found? or do the tortoise and the hare start at the same values? and if they do I guess it is? what if the hare misses a collision found by the tortoise?.. (this isn't very easy to reason about..) $\endgroup$
    – Anon2000
    Commented May 19, 2015 at 21:02
  • 2
    $\begingroup$ @Anon2000: yes, the method that SOJPM suggested is known as rho cycle finding. The approach that I suggested (which is rather different) is more related to the Hellman time-memory tradeoff. I suspect the method I suggested is more practical (for one, it's more parallelizable; rather important if you're contemplating $2^{64}$ computations...) $\endgroup$
    – poncho
    Commented May 19, 2015 at 22:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.