Truncated 60 bit SHA1 collision detection?

Question

So, I have managed to get a 52 bit collision for a SHA1 but after three days of brute forcing, I am unable to get a 60 bit collision.

My question is simple, how should I approach this?

I am currently using a random hex code of about 15 bits and randomly alternating between these digits. I then get the 60bit SHA1 for this and then check if its in my array. If it is I display the matching SHA1 values and the hex strings which generated them.

Frustrating isn't the word at the moment so any guidance or help will be greatly received.

Answer 1

It seems I am now running out of memory before computing the end answer which is bizarre

Typical brute-force issue.

Here’s a hint: do NOT store results in arrays as that’s most probably what’s currently causing you to run out of memory. Look at the numbers: if we would assume no collisions, you’ld need your array (read: memory allocation) to hold up to $2^{60}$ elements to store all 60-bit results; and we’re not yet counting memory you need to run the OS, to run your code, and to store things like the random 15 bits hex codes you’re hashing.

Of course – due to the fact SHA1 collisions are known to exist – your array won’t grow that big, so you won’t need to worry that you might be needing a rough 144115 Terabytes of memory to store all “SHA1 truncated to 60-bit” results. Thinking about the resources available when using an average desktop computer, a project going for 60-bits of truncated SHA1 without running out of memory should be feasable. An SHA1 hash truncated to its first 60 bits, should take around and about 60 or 120 million iterations/hash-calculations before hitting a collision – depending on how lucky you are. Unless your computer is 10 years old or older,and unless you mess up your implementation, that number of elements should easily fit into memory.

One potential solution to your memory problem is to use random hex codes as you currently do, and to store things in a tree indexed by the first 60-bits of the hash. (In case of doubt, look for “Binary Indexed Trees”, also known as “Fenwick Tree”.) Yet, if that’s indeed the best way to do it somewhat depends on implementation details, available resources, and – last but not least – used programming language. As we handle coding-related questions as “off topic” here at Crypto.SE, I’ll refrain from diving into that.

Background Info: Exponential Growth Problem

I’m assuming you did some research before practically programming things up. If you did, remind yourself of the fact that the resources required for a brute-force attack grow exponentially with the data size (here: number of bits) you are brute-forcing. Among other sources, you can find this information in the Wikipedia article about Brute-Force attacks. Note that when we talk about the exponential growth of needed resources, we’re not only talking about raw computer memory – “time” is also one of the exponentially growing factors.

Here’s a graphic (from an SHA1 brute-force project) that puts things into perspective for you:

The fact that brute-force attacks cause you to quickly run out of several kinds of resources is the main reason why password-brute-forcing tools and utilities tend to prefer “dictionary attack” methods for longer passwords, and it’s one of the main reasons why cryptanalysts dive into cryptographic algorithms to find weaknesses and/or attack vectors that allow them to avoid having to bluntly brute-force things.

Long story short: Unless you’re a governmental agency with ample resources, or you’re merely attacking something small enough to fit your desktop computer, brute-force attacks can quickly become a rather futile effort.

Optimizing Collision Attacks

Lucky for you, SHA1 is considered “broken” and some attacks have been found which are more speedy than plain “brute-forcing collisions for (truncated and non-truncated) SHA1”. For details, you might want to check the papers mentioned in an answer to “SHA-1 collisions - what about practical attacks?”

For your convenience, here’s the relevant snippet:

---

I'll assume … enough resources to perform one single attack finding two distinct 128-byte colliding messages on SHA-1 with a small change: the value of the (arbitrary) 160-bit initialization value. The later is possible

• by brute force with expected effort less than $2^{81}$ hashes (about the effort devoted to bitcoin mining in a year according to that source) using Paul C. van Oorschot and Michael J. Wiener's Parallel Collision Search with Cryptanalytic Applications (in Journal of Cryptology, January 1999, Volume 12, Issue 1; free slightly earlier version available from the first author's website);
• or with less effort using complex specialized methods exploiting weaknesses in SHA-1's compression function, with an estimated effort comparable to
  • $2^{69}$ hashes, per Xiaoyun Wang, Yiqun Lisa Yin, Hongbo Yu: Finding Collisions in the Full SHA-1, in proccedings of Crypto 2005),
  • $2^{63}$ hashes, per Xiaoyun Wang, Andrew C Yao, Frances Yao: Cryptanalysis on SHA-1, rump session of Crypto 2005; see also Martin Cochran: Notes on the Wang et al. $2^{63}$ SHA-1 Differential Path, in IACR eprint archives, 2007),
  • $2^{61}$ hashes, per Marc Stevens: New collision attacks on SHA-1 based on optimal joint local-collision analysis (in proceedings of Eurocrypt 2013, also freely available from the author's website).

---

Based on the information available in the papers mentioned above, you should be able to derive something more optimal compared to your current, non-optimized brute-force approach to find “truncated SHA1” collisions. After all, “time” is a pretty valuable resource.

Answer 2

As e-sushi mentioned, you can search for $n$-bit collisions with $O(2^{n/2})$ memory, by storing the entries you found in a table, and searching for duplicates.

However, by using a Pollard-Rho (read: cycle finding) technique, you can drastically reduce the amount of memory required, without increasing the computation drastically.

Here's how it works; you define a sequence $S_i = H(S_{i-1})$, where $H$ is (based on) your truncated hash function. As a one-way function, the sequence $S_0, S_1, S_2, ...$ will eventually repeat, and with good probability, it will not start back at the beginning of the sequence, but instead start repeating in the middle. That is, for some $i, j$, we will have $S_i \ne S_j$ and $S_{i+1} = S_{j+1}$. Our goal is to find $S_i, S_j$ (as that's our hash collision).

One approach is to select your $H$, an arbitrary starting point $S_0$, and a value $N$ (and $2^{n/4}$ is a decent starting point). We also have a data structure that will contain pairs of values $(Nk, S_{Nk})$, for integer $k$. Initialize the database with the pair $(0, S_0)$. Initialize $i$ to 0, $T$ to $S_0$, and then repeatedly:

• Compute $T := H(T)$ and $i := i+1$ (invariant: $T = S_i$)

• Scan the value $T$ to see if it appears in the database as the value $(Nk, S_{Nk})$. If so:

  • If $Nk = 0$, well, fail (we started back at the beginning value; try again with a different $S_0$)

  • If $i < 2N$, try again with the same $S_0$ and a smaller $N$

  • Otherwise we have $S_i = S_{Nk}$ but $S_{i-N} \ne S_{Nk-N}$ (we know the later inequality because we didn't find $S_{i-N}$ in the table when we processed it). Recompute the value $S_{i-N}$ (using the entry prior to it in table), and retrieve the value $S_{Nk-N}$ from the table. Successively compute $S_{i-N+j}$ and $S_{Nk-N+j}$ (for $j=1,2,3, ...$) until you find where equality holds; the previus $j$ give you the collision

• If the entry isn't in the table, if $i$ is a multiple of $N$, add the entry $(i, T)$ to the table.