2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ How long did the 52 bit collision take to find? If you are just using brute force, it should take a proportionate amount of time to find a different size collision. $\endgroup$ – Ella Rose Oct 30 '16 at 22:12
  • $\begingroup$ @EllaRose it took me about 15 minutes. It seems I am now running out of memory before computing the end answer which is bizarre $\endgroup$ – Gallieon474 Oct 30 '16 at 22:52
3
$\begingroup$

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:

exponential growth showing days-needed-to-crack when brute-forcing linkedin SHA1 hashes

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


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.

$\endgroup$
  • $\begingroup$ Thanks for that. Much appreciated. I do wish we could talk about the coding aspect as I think the problem is the way I am thinking about it. I have posted it on SO too. $\endgroup$ – Gallieon474 Oct 31 '16 at 8:39
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ wow, that is a novel way so I suppose a dictionary to store and the for loop for scanning is needed? $\endgroup$ – Gallieon474 Nov 1 '16 at 11:30
  • $\begingroup$ @Gallieon474: Yes, a dictionary to hold the database is needed (but with $N = 2^{n/4}$, it's an expected $2^{n/4}$ in size; so, for $n=30$, and 32 bytes to hold each entry, it's about a Megabyte), and the points I gave are implicitly within a large loop... $\endgroup$ – poncho Nov 1 '16 at 12:23
  • $\begingroup$ not the best coder but I will try this out. Thanks! $\endgroup$ – Gallieon474 Nov 1 '16 at 18:19
  • $\begingroup$ not the best coder but will try and figure this out. $\endgroup$ – Gallieon474 Nov 1 '16 at 18:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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