题 使用相同的哈希码生成两个不同的字符串


我想做一些测试,这些测试需要一些具有相同哈希码的字符串,但不是相同的字符串。我找不到任何例子,所以我决定写一个简单的程序来为我做。

下面的代码反复生成两个随机字符串,直到它们生成相同的哈希码。

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

这段代码似乎有效(理论上),但可能需要几个世纪才能完成。所以我反过来考虑从一个哈希码生成两个字符串。

我知道从哈希码中检索字符串是不可能的,但是可以从中生成可能的字符串吗?

我正在使用Visual Studio 2015社区版。版本:14.0.23107.0D14REL。

.NET Framework:4.6.00081。


31
2017-08-15 17:21


起源


如果您只想进行测试,可以创建一个类并覆盖 GetHashCode 具有错误的实现,返回固定值,有效地在任何地方产生冲突。 - Alejandro
只需几秒钟,生日悖论就能让它变得快速。 “1241308”.GetHashCode()==“699391”.GetHashCode(),32位代码,“942”。GetHashCode()==“9331582”.GetHashCode(),64位代码。 - Hans Passant
利用生日悖论是通过存储到目前为止生成的所有字符串来完成的。每次生成一个新的时,都会检查所有其他的。它极大地增加了找到匹配的机会。如果有N个哈希码,则在检查N / 2个字符串后,您的方法将有50%的机会发现冲突。检查√N字符串后,生日方法有50%的几率。对于N = ~40亿的32位哈希码,这是检查20亿个字符串或其中65000个字符串之间的差异。 - John Kugelman
@ScottChamberlain:那不是真的。数学仅适用于散列值近似均匀随机的情况。如果不是,您可以轻松地需要更多哈希来发现碰撞 (恩。 hash(x) = x%INT_MAX,你会迭代 INT_MAX 找到碰撞前的值)。 - BlueRaja - Danny Pflughoeft
如果您使用的是64位,则可以使用 "\0Anything" 和 "\0Really, anything will work." - 为什么String.GetHashCode()在32位和64位版本的CLR中实现不同?。当然,最好为您当前的实现寻找这些字符串 - \0 不会一直有效。 - Kobi


答案:


通过重复比较随机字符串来找到两个字符串几乎是永远的。而是生成字符串并通过哈希码将它们存储在字典中。然后查找每个。匹配发现很快。

匹配发现!! xqzrbn和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;
}

32
2017-08-15 17:42



感谢你的回答。 @ScottChamberlain和SamuelNeff。看来生成字符串的方法也会影响机会!更多字符减少了获得相同哈希码的机会。 - M.kazem Akhgary
@ M.kazemAkhgary那不是真的,你觉得这样,因为alpha方法使用更多的CPU功率dus需要更长的时间才能找到匹配。项目数量应相同。 - Behrooz
@Behrooz字典可以“爬行”的唯一方法是存储大量具有完全相同HashCode的值但是 Equals( 回报 false。用一个 int 这是不可能的 (x.GetHashCode() == y.GetHashCode()) && (x.Equals(y) == false) - Scott Chamberlain
@Behrooz看 我的这个老答案 我会更详细地介绍这个过程,而不是评论允许的。 - Scott Chamberlain
@Behrooz注意O(1)并不意味着快速,它意味着恒定的时间。它可以一直很慢,仍然是O(1)。这并不是说字典很慢,只是说一般。字典的性能取决于桶的数量和桶间密钥的分布(哈希码的随机性)。 - Samuel Neff


利用这个 生日悖论。而不是直接测试两个字符串,测试之前看到的所有字符串。

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

对于我的机器,它产生输出

“699391”和“1241308”具有相同的哈希码-1612916492

几乎是瞬间。

由于在.NET中如何对字符串进行哈希处理,您可能无法获得与我完全相同的输出,但它应该同样快。


25
2017-08-15 17:41