相同的字符串,不同的 HashCode?

昨晚睡觉前偶然看到这篇文章,觉得很有启发。最近博文数量堪忧,所以刚好拿来凑数。原文是英语的,那老夫就大体“转述“一下好了。

问题

原文提到,在 .NET Core 中使用 String 的 HashCode 时,对于相同的字符串,会出现不一样的哈希值,老夫刚看到这段话时也是一脸懵逼。按理说,作为查找和判断的快速实现,对于相同或者等同的对象,应该返回相同的哈希值才对。

按照一般的设想,对于一个 String,我们“心目中“的理想实现应该类似于下面这样(下面这段是 Java 8 的实现):

    public int hashCode() {
        int h = hash;
        if (h == 0 && value.length > 0) {
            char val[] = value;

            for (int i = 0; i < value.length; i++) {
                h = 31 * h + val[i];
            }
            hash = h;
        }
        return h;
    }

但是我们在 .NET Core 里,编写如下代码(老夫用的是 Visual Studio For Mac 7.7):

        static void Main(string[] args)
        {
            String a = "abc", b = "abc";

            Console.WriteLine(String.Format("{0}, {1}", a.GetHashCode(), b.GetHashCode()));
        }

来运行一下:

在相同的实例里对于两个 “abc” 字符串返回的是相同的哈希值,而第二次运行时,哈希值就变了。这是什么鬼!翻看 String 类的源代码,是这样的:

        public override int GetHashCode() {
 
#if FEATURE_RANDOMIZED_STRING_HASHING
            if(HashHelpers.s_UseRandomizedStringHashing)
            {
                return InternalMarvin32HashString(this, this.Length, 0);
            }
#endif // FEATURE_RANDOMIZED_STRING_HASHING
 
            unsafe {
                fixed (char *src = this) {

            ... 省略固定哈希值的代码
        }

在新版本的 .NET 实现里,FEATURE_RANDOMIZED_STRING_HASHING 是默认开启的,也就是说这是 M$ 有意为之。

按照 M$ 的文档,使用哈希值有以下注意事项(省略了一些与本文不相关的):

  • 不要将哈希值持久化(比如存储到数据库里);
  • 不要将哈希值作为 key 存储在 key/value 形式的集合里;
  • 不要将哈希值应用于本进程以外的地方(例如发送给其他进程甚至其他服务器)。

而这都是因为,哈希值是随机化的,在不同的应用程序甚至是相同应用的不同进程里,都可能不是一致的!

为什么?

根据这个说法,这是为了防止 DoS 攻击而有意为之。

神马?哈希值会导致 DoS 攻击?是的,攻击者的手段就是这么难以想象,啥歪门邪道也有,毕竟普通人能想到的手段早就被堵住了。

我们知道,哈希表在内存中通常是以数组的形式存储,对于某个对象,根据其哈希值存储于某一位置。当出现冲突时,大多数实现都是使用链表(冲突多了会变成红黑树,但不是每个库都会这样做)来存储冲突的元素,类似下图(图片也抄袭自原博文):

Collisions in a hash table

这种攻击方式就是,故意找到冲突的哈希值给乃存储,让乃在相同的桶中存储一堆:

Hash flooding resulting in polynomial slowdown

所以,在这种情况下,插入元素的复杂度变成了 O(n),插入 N 个元素的复杂度暴涨至 O(n^2),和原设计相差甚远。有些框架会看情况把链表变成红黑树,所以效率会稍微高一点,但是仍旧远高于原设计的 O(1)。

在很多 Web 框架的实现里,框架会先将 POST 到的参数放在一个 Map 里,以便后续处理。此时,攻击者可以找到一堆哈希值相同的参数,系统则会频繁处理这种冲突的参数,耗尽处理资源最终导致服务器无法响应别的请求。在攻击示范里,服务器花费了 11 小时的时间处理一个 4MB 的请求。

乃可以说直接改造一下 Web 服务即可呀?但是哈希表的使用实在是太多了,为了避免没发现的地方出现问题, M$ 决定采用随机化的哈希值来绕过所有类似的攻击问题。

实际上当冲突达到一定程度的时候,系统会自动对哈希表进行扩容,而一般情况下扩容是翻倍扩容,在同一位置的元素会以一半对一半的概率映射到原来或者新的位置上。即使使用更复杂的策略让这些元素分散开也不行,毕竟你的哈希表的实现攻击者是可以知道的(况且现在开源又是主流),所以总可以根据你的策略找到一堆哈希值相同的字符串。

那么解决方案好像就只有随机化了,让每一个程序产生的哈希值不同、甚至每一个进程不同,这样攻击者就无法实现此目的了。

怎么办

如果我们是按照规范来使用哈希值的,那么不会遇到什么问题。我们要始终记住 HashCode 的初衷:在 key/value 集合操作时快速判断是否是不同的元素,而此处所说的 key/value 集合通常是存储于内存中的,再程序重新运行时重新生成。除此之外的一切目的都是不对的,要赶紧改进。

虽然说可能很多库暂时都还是使用的固定哈希算法(例如 Java 和 Python),但是今后还是有可能会做出和 M$ 类似的改动。所以我们还是应该按照规范来使用 HashCode,如果不注意,可能就出大 bug 了。

如果我们有需要把哈希值进行持久化(例如老夫曾经做过的一个项目就是要把一些非常复杂对象存储于数据库,此时需要用哈希值快速判断是否已经存储过了),那么一定要重写 GetHashCode 方法,尤其是在自行计算 HashCode 的时候,一定要注意库是不是采用了随机化的哈希值,例如新版 .NET 里的 String,否则即使你想要实现固定的哈希值,但是你调用的库是随机的,那实际上也变成随机化的了。

同时还要注意的是,如果我们要把程序部署在风险很高的公网上,自行实现的 GetHashCode 是否能应对上述 DoS 攻击的情况。

发表评论

Fill in your details below or click an icon to log in:

WordPress.com 徽标

You are commenting using your WordPress.com account. Log Out /  更改 )

Google+ photo

You are commenting using your Google+ account. Log Out /  更改 )

Twitter picture

You are commenting using your Twitter account. Log Out /  更改 )

Facebook photo

You are commenting using your Facebook account. Log Out /  更改 )

Connecting to %s