Varnish不散列

大量与哈希冲突相关的安全建议让很多人盯着Varnish，想知道它是否受到了影响。

答案是否定的，但解释可能并不是你们大多数人所期待的：

Varnish不会散列，至少在默认情况下不会，即使它散列了，它仍然尽可能地对攻击免疫。

为了理解到底发生了什么，我必须从香农的信息论中引入一个概念：“熵”。

熵很难解释，根据传说，这就是为什么香农从热力学中重复使用这个术语的原因。

在这种情况下，我们可以不考虑熵，因为我们的“键”有多大不同：

Low entropy (1 bit):
        /foo/bar/barf/some/cms/content/article?article=2
        /foo/bar/barf/some/cms/content/article?article=3

High entropy (65 bits):
        /i?ee30d0770eb460634e9d5dcfb562a2c5.html
        /i?bca3633d52607f38a107cb5297fd66e5.html

散列包括根据键计算散列索引，并将对象存储在由该键索引的数组中。

通常情况下，键是一个字符串，索引是一个(较小的)整数，散列函数的任务是将键压缩到整数中，而不会损失任何信息。

不用说，你一开始的熵越大，你就能承受得起失去的越多，而失去一些你几乎总是会失去。

散列函数有两个家族，快速的和好的，安全建议是关于快速的。

好的比较慢，但可能不会慢到你所关心的程度，因此，如果你想修复你的网络应用程序：

更改：：

FOO=某项法令 [$somekey]

致：

FOO=某项法令 [md5($somekey)]

忘了那些建议吧。

是的，没错：加密散列算法是很好的算法，它们被构建为不会丢弃任何熵，并且它们被构建为非常难以预测冲突，这正是咨询中快速散列函数的问题所在。

瓦尼什做了什么

避免散列冲突的方法是不使用散列：改用树。在那里，每个物体都有自己的位置，没有碰撞。

Varnish可以做到这一点，但有一点扭曲。

Varnish中的“key”可以很长；默认情况下，它们包括：：

sub vcl_hash {
    hash_data(req.url);
    if (req.http.host) {
        hash_data(req.http.host);
    } else {
        hash_data(server.ip);
    }
    return (hash);
}

但一些用户会在其中添加Cookie、用户标识和许多其他零碎的字符串，最终密钥可以是千字节长的，而且通常情况下，就像上面的第一个例子一样，第一个差异可能要到密钥很远的时候才会出现。

树通常需要有密钥的副本，以便能够判断它们是否匹配，更重要的是，需要比较树叶，以便重新平衡树和其他类似的数据结构的奥秘。

这将为Varnish增加另一个每个对象的内存负载，在上面看到的过于常见的情况下，为每个对象存储48个相同的字符会让人感觉特别愚蠢。

但此外，我们希望树进行查找的速度非常快，最好是无锁的查找，这意味着我们不能(实际上)使用任何自动平衡自身的“智能”树，等等。

如果您的密钥在到达的顺序上看起来像随机数据，那么您(通常)不需要“智能”树，但我们可以期待相反的情况，因为在第一个例子中，文章编号4、5、6等被添加到CMS中。

但我们可以让密钥看起来像随机的，同时使它们变小和固定大小，为这一任务而设计的完美函数是“好的”散列函数，也就是加密函数。

因此，Varnish所做的就是“密钥压缩”：提供给hash_data()的所有字符串都通过一个名为SHA256的加密散列算法进行推送，顾名思义，无论您提供多少位，该算法都会输出256位(=32字节)。

这并没有消除密钥存储要求，但现在所有密钥都是32字节的，可以直接放入数据结构中：：

struct objhead {
        [...]
        unsigned char           digest[DIGEST_LEN];
};

在上面的例子中，对于1比特的熵差，SHA256的输出变为：

/foo/bar/barf/some/cms/content/article?article=2
-> 14f0553caa5c796650ec82256e3f111ae2f20020a4b9029f135a01610932054e
/foo/bar/barf/some/cms/content/article?article=3
-> 4d45b9544077921575c3c5a2a14c779bff6c4830d1fbafe4bd7e03e5dd93ca05

这应该是足够随机的。

但键压缩确实带来了冲突的风险，因为即使是SHA256也不能保证所有可能的输入都有不同的输出：尝试通过SHA256推送所有可能的33字节文件，迟早会发生冲突。

然而，碰撞的风险非常小，我几乎可以向你保证，你将在名誉和金钱上完全抵消碰撞可能造成的任何不便，因为你将是第一个发现SHA256碰撞的人。

保尔-亨宁，2012-01-03