c# - Genera dos cadenas diferentes con el mismo código hash

string hashcode

Question

Quiero hacer algunas pruebas que requieren algunas cadenas con el mismo código hash, pero no las mismas cadenas. No pude encontrar ningún ejemplo, así que decidí escribir un programa simple para hacerlo por mí.

El siguiente código genera dos cadenas aleatorias una y otra vez hasta que generan el mismo código hash.

    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;
    }

Este código parece estar funcionando (teóricamente), pero puede tardar siglos en completarse. Así que estaba pensando en hacer lo contrario y generar dos cadenas a partir de un código hash.

Sé que no es posible recuperar una cadena de un código hash, pero ¿es posible generar cadenas posibles a partir de ella?

Estoy usando Visual Studio 2015 Community Edition. Versión: 14.0.23107.0D14REL.

.NET Framework: 4.6.00081.

Answer 1

Aproveche la paradoja del cumpleaños . En lugar de solo probar dos cadenas directamente, pruebe todas las cadenas que ha visto antes.

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();
        }
    }
}

Para mi máquina produce la salida.

"699391" y "1241308" tienen el mismo código hash -1612916492

casi al instante.

Debido a la forma en que se procesan las cadenas en .NET, es posible que no obtengas exactamente el mismo resultado que yo, pero debe ser igual de rápido.

Answer 2

Encontrar dos cadenas comparando repetidamente cadenas aleatorias llevará prácticamente para siempre. En su lugar, generar cadenas y almacenarlas en un diccionario por hashcode. Entonces mira cada uno. Partido encontrado bastante rápido.

¡¡COINCIDENCIA ENCONTRADA!! xqzrbn y código hash krumld 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;
}