为什么使用MD4进行缓存？

Question

卡巴奇是一个流行的工具，用于加速GCC和其他编译器的重新编译。它的工作方式是缓存以前的编译，并检测同一编译何时再次完成。检测使用MD4散列。

我很好奇(a)为什么这样的缓存工具会使用任何加密哈希函数，(b)在所有可用的加密散列函数中，为什么要特别使用MD4。

关于(a)，使用加密散列函数的好处是什么，而不是某些不考虑密码学设计的散列函数？例如，Java内置哈希函数似乎与密码学中使用(或以前使用)的已知密码不相对应。为什么不使用这些非加密散列函数之一呢？考虑到MD4's已知的弱点，我无法想象它是出于对更大安全的渴望而选择的。

关于(b)项，假设有一些使用加密散列的基础，为什么要特别使用MD4？我理解使用现代密码散列函数是没有意义的，因为这些函数通常是计算密集型的，这违背了缓存工具加快访问时间的目的。因此，MD4必须至少在一定程度上用于速度。但是它绝对是最快的加密哈希函数，还是其他的更快呢？如果它不是最快的，那么MD4在缓存中还有哪些其他优势(例如，MD5)？

Answer 1

通常的非密码散列(如CRC-32 )在统计上是很好的，但是在这里缓存想要避免的是假阳性--重新编译被声明为与前一个相同，但不是。一种通常只产生32位的非密码散列只从其输出大小和它的统计特性来看，有很高的假阳性风险。加密散列的输出要大得多，这使得假阳性的风险可以忽略不计。

这不是一个安全问题:所有的输入都来自用户，所以如果用户故意造成冲突，那么他只是在与自己战斗。因此，可以使用加密中断的散列函数。

现在，对于MD4相对于更常见的函数(如MD5或SHA-1)的具体选择，人们只能推测，但我的猜测是它是关于性能的；毕竟，ccache是为了使编译更快。MD4速度非常快(甚至比某些平台上的CRC-32还要快)。当然，散列比任何编译过程都快，甚至比读取文件更快，所以使用MD5而不是MD4对ccache的总体性能没有显著影响。许多与绩效相关的决定实际上都是凭直觉做出的，而不考虑实际的措施，看是否有一个必须解决的绩效问题。

从这个图书馆的工作来看，很少有密码散列函数至少与MD4一样快。BLAKE2是BlakeSHA-3候选产品的最新衍生产品，它可能是实现接近MD4性能水平的加密安全哈希函数的最佳选择。但是，正如我上面所写的，在ccache的情况下，性能很可能不是一个真正的问题。

Answer 2

密码散列函数通常具有这样的属性，即稍有不同的输入会产生截然不同的输出。任何碰撞通常都应该有非常不同的输入。

此属性不适用于大多数非加密校验和。小的更改可能导致类似的校验和，而在某些角落中，一些小的更改可以以生成相同校验和的方式相互抵消。

源代码的变化通常很小，因此在检查源代码更改的上下文中，使用非密码校验和时发生碰撞的风险相当高。例如，版本控制工具git使用SHA-1散列作为代码修订的唯一标识符。

为什么特别是MD4？好吧，你得问问ccache开发人员。这是一个非常古老的工具，直到1992年MD5才被标准化。可能MD4只是开发此特性时可用的最明显的选择，后来没有人觉得有必要替换该算法，因为它做了它应该做的事情。