Generate two different strings with the same hashcode

Question

I want to do some tests which require some strings with the same hash code, but not the same strings. I couldn't find any examples, so I decided to write a simple program to do it for me.

The code below generates two random strings over and over until they generate the same hash code.

    static Random r = new Random();     static void Main(string[] args)     {         string str1, str2;         do         {             str1 = GenerateString();             str2 = GenerateString();         } while (str1.GetHashCode() != str2.GetHashCode() && str1 != str2);          Console.WriteLine("{0}\n{1}", str1, str2);     }      static string GenerateString()     {         string s = "";         while (s.Length < 6)         {             s += (char)r.Next(char.MaxValue);         }         return s;     } 

This code seems to be working (theoretically), but it may take centuries to complete. So I was thinking of doing vice versa and generate two strings from one hash code.

I know it's not possible to retrieve a string from a hash code, but is it possible to generate possible strings from it?

I'm using Visual Studio 2015 Community Edition. Version: 14.0.23107.0D14REL.

.NET Framework: 4.6.00081.

Answer 1

Finding two strings by repeatedly comparing random strings will take practically forever. Instead generate strings and store them in an a dictionary by hashcode. Then look up each. Match found pretty quickly.

MATCH FOUND!! xqzrbn and krumld hash code 80425224

void Main() {      var lookup = new Dictionary<int,string>();      while(true) {         var s = RandomString();                 var h = s.GetHashCode();         string s2;         if (lookup.TryGetValue(h, out s2) && s2 != s) {             Console.WriteLine("MATCH FOUND!! {0} and {1} hash code {2}",                 lookup[h],                 s,                 h);             break;         }         lookup[h] = s;          if (lookup.Count % 1000 == 0) {             Console.WriteLine(lookup.Count);         }     } }  static Random r = new Random();  // Define other methods and classes here static string RandomString() {      var s = ((char)r.Next((int)'a',((int)'z')+1)).ToString() +             ((char)r.Next((int)'a',((int)'z')+1)).ToString() +             ((char)r.Next((int)'a',((int)'z')+1)).ToString() +             ((char)r.Next((int)'a',((int)'z')+1)).ToString() +             ((char)r.Next((int)'a',((int)'z')+1)).ToString() +             ((char)r.Next((int)'a',((int)'z')+1)).ToString();      return s; } 

Answer 2

Take advantage of the Birthday Paradox. Instead of only testing two strings directly, test all strings you have seen before.

using System; using System.Collections.Generic;  namespace ConsoleApplication2 {     class Program     {         static void Main(string[] args)         {             var words = new Dictionary<int, string>();              int i = 0;             string teststring;             while (true)             {                 i++;                 teststring = i.ToString();                 try                 {                     words.Add(teststring.GetHashCode(), teststring);                 }                 catch (Exception)                 {                     break;                 }             }              var collisionHash = teststring.GetHashCode();             Console.WriteLine("\"{0}\" and \"{1}\" have the same hash code {2}", words[collisionHash], teststring, collisionHash);             Console.ReadLine();         }     } } 

For my machine it produces the output

"699391" and "1241308" have the same hash code -1612916492

almost instantly.

Due to how strings are hashed in .NET you may not get the exact same output as me, but it should be just as fast.