Etydhv

My objective is to find a hash collision of my modified hash function. Assuming my modified hash only outputs the first 36 bits of SHA-1. As we know, SHA-1 is a 160-bit hash value, hence, we only need to output 9 characters out of 40 characters for comparison.

How i begin my program is by hashing a string (I have a SHA-1 algorithm running and i will name it as sha1. I have also ensured that the output of the SHA-1 algorithm is correct.)

Firstly, i would hardcode 2 string and extract out 9 characters out of 40 characters since i require only the first 36 bits of SHA-1. The function below basically return a true if a collision is found and false if a collision is not found

public static boolean findCollision(int x1, int x2) 

 String message1 = "I tried " + x1 + " iteration to find a collision";
 String message2 = "I tried " + x2 + " iteration to find a collision"; 


 //hashing my string and extracting 9 characters
 String message_hash1 = sha1(message1);
 String message_hash2 = sha1(message2);

 String modified_hash1 = message_hash1.substring(0, 9);
 String modified_hash2 = message_hash2.substring(0, 9);

 if (modified_hash1.equals(modified_hash2)) 
 return true; 
 else 
 return false;

Lastly, i will have a main function that will random Integers up to MAX_VALUE in a infinite loop and will break out if and only if a hash is found.

public static void main(String[] args) 

 Random random = new Random();
 int x1 = 0;
 int x2 = 0;
 int counter = 0;

 while (true) 

 while(true)

 x1 = random.nextInt(Integer.MAX_VALUE);
 x2 = random.nextInt(Integer.MAX_VALUE);

 if (x1 != x2) 
 break; 
 

 if (findCollision(x1, x2) == true) 
 break;
 
 counter++;
 

 System.out.println("nNumber of trials: " + counter);

If i tried taking only the first 24 bits of SHA-1, i could easily find a collision. However, i'm unable to find a collision for 36 bits instead despite running it for hours. Hence, I'm wondering what is other alternative way for me to find a collision with just 36 bits of SHA-1.

With 24 bits, there are approximately 16.8 million possible hashes, so on average, you'd have to try 8.4 million pairs until you find a collision. With 36 bits, the numbers have to be multiplied by 4096, which yields 68 respectively 34 billion. You can cut this in half by not computing two hashes during each iteration, but instead computing one before the loop and keeping it constant.

However, that is probably still more time than you want to spend. One way to reduce that time is to utilize the Birthday Paradox (https://en.m.wikipedia.org/wiki/Birthday_problem). By computing a list of hashes and comparing each one with each other your chances of finding a collision are much higher. I won't try to type a complete algorithm on this phone screen, though :-)

I realized that while typing this, you should look into the Birthday Attack, which will probably much more elaborated than my answer, lol.

Considering your have 36 bits of data, it means you have a total number of possibilities of $2^36 = 68719476736$. Based on the Pigeonhole principle, if you compared the hashed of 68719476736 different strings, you'd get a collision.

So that's easy! All you need to do is run this (pseudocode):

hashset = (new hashset that uses your hashing algorithm)
for(i = 0; i < 68719476736 + 1; i++) 

 if hashset.contains(string(i)) break; 

 hashset.add(string(i));


print("This took " + i + " tried!")

With this, you're guaranteed to get a collision. But there's a problem. If every iteration took 100 milliseconds, you'd need about 217 years to get a solution. Tell your teacher your great-great-grandchildren will get back to you with a solution. You could also buy 2000 computers to run this in ~40 days.

My algorithm is pretty much guaranteed to finish (assuming none of the computers crash in any way), yours isn't. This is more of a lesson on "how to test things", which is valuable for developers. When you want to test something, try not to be random. The thing with your algorithm is that maybe you wouldn't ever get collisions. I understand that you kind of need randomness if you want this to finish running this one day.

So the question is, what could we do to make this better?

We could check about how many different strings we'd need to get a good enough chance there's a collision. It's kind of the Birthday Problem which gives us an easy way to calculate what are the chances n different persons have the same birthday in a group of m persons.

We can use the formula under Approximation of number of people and adapt it to our problem to understand that if we had 68719476736 + 1 strings in our possession (for example, every number between 1 and 68719476736 + 1), you'd need to pick 308652 of those to have about 50% chances of having a collision.

What you could try is randomly take 308652 numbers between 1 and 68719476736 + 1 and hash them to find a collision. Repeat this as long as you don't have a collision.

The pseudocode would look like this :

generator = RandomBigIntGenerator()
numbers = []

for(i = 0; i < 308652; i++) 
 numbers.add(generator.random(1,68719476736+1))


hashset = (With your hashing function)
for n in numbers 
 if hashset.contains(n) 
 print("yay done");
 break;
 
 hashset.add(m);

All in all, you can hope to have collisions, but you need computing power.

In a code review point of view :

• You need to keep track of the strings you already tried, they give you valuable information that can actually help you find collision.


• Don't be too random when you create your strings.


• Understand that 68719476736 is a biiggg number, but still so much smaller than the 1461501637330902918203684832716283019655932542976 possible values the SHA1 have :)