更快的MD5替代方案？

我正在开发一个程序,搜索整个驱动​​器的给定文件.目前,我计算了已知文件的MD5哈希值,然后递归扫描所有文件,寻找匹配项.

唯一的问题是MD5在大文件上的速度非常慢.是否有更快的替代方案,我可以使用,同时保留一个非常小的误报可能性？

所有代码都在C#中.

谢谢.

更新

我已经读过,即使MD5也可以非常快,磁盘I/O应该是限制因素.这让我相信我的代码可能不是最佳的.这种方法有什么问题吗？

        MD5 md5 = MD5.Create();
        StringBuilder sb = new StringBuilder();
        try
        {
            using (FileStream fs = File.Open(fileName, FileMode.Open, FileAccess.Read))
            {
                foreach (byte b in md5.ComputeHash(fs))
                    sb.Append(b.ToString("X2"));
            }
            return sb.ToString();
        }
        catch (Exception)
        {
            return "";
        }

Michael Burr.. 44

我希望你只有在文件大小匹配时才检查MD5匹配.

另一个优化是对第一个1K(或其他任意,但相当小的数字)进行快速校验和,并确保在处理整个文件之前匹配.

当然,所有这些都假设您只是在寻找特定文件的匹配/无匹配决策.

1> Michael Burr..：

---

我希望你只有在文件大小匹配时才检查MD5匹配.

另一个优化是对第一个1K(或其他任意,但相当小的数字)进行快速校验和,并确保在处理整个文件之前匹配.

当然,所有这些都假设您只是在寻找特定文件的匹配/无匹配决策.

---

切片为+1.当第一个字节不同时,无需哈希37演出.

2> 小智..：

---

无论加密要求如何,都存在哈希冲突的可能性,因此不能使用散列函数来保证两个文件完全相同.

我曾经写过类似的代码,我通过首先索引所有文件然后丢弃任何不同大小的文件来快速运行.然后对剩余的条目执行快速哈希比较(在每个文件的一部分上)(比较该步骤的字节被证明不太有用 - 许多文件类型具有在文件的开头具有相同字节的公共头部).然后使用MD5检查在此阶段之后留下的任何文件,如果MD5匹配,则最后对整个文件进行字节比较,以确保内容相同.

3> Adam Byrtek..：

---

首先考虑一下你的瓶颈是什么:哈希函数本身还是磁盘访问速度？如果您受磁盘限制,更改散列算法将不会给您带来太多帮助.根据您的描述,我暗示您始终扫描整个磁盘以找到匹配项 - 考虑首先构建索引,然后仅将给定哈希与索引匹配,这将更快.

4> jalf..：

---

只是线性读取文件？读取整个文件,计算md5哈希值,然后比较哈希值似乎毫无意义.

按顺序读取文件,一次几个字节,允许您在读取后丢弃绝大多数文件,比如4个字节.并且您将节省计算散列函数的所有处理开销,这些函数在您的情况下不会提供任何内容.

如果你已经有了驱动器中所有文件的哈希值,那么比较它们是有意义的,但如果你必须动态计算它们,那么哈希似乎没有任何优势.

我在这里错过了什么吗？在这种情况下,哈希会给你带来什么？

---

至少,如果你可以存储哈希加上前几个字节(最好是超过4个,因为这通常是文件格式魔术数字的大小),那么你可以丢弃绝大多数只打开文件并读取的文件几个字节.

5> CesarB..：

---

使用MD5比较文件有一个小问题:已知的文件对不同但MD5 相同.

这意味着您可以使用MD5来判断文件是否不同(如果MD5不同,文件必须不同),但是您不能使用MD5来判断文件是否相等(如果文件相同,则MD5必须是相同,但如果MD5相等,文件可能相同也可能不相等.

您应该使用尚未被破坏的哈希函数(如SHA-1),或者(如提到的@SoapBox)仅使用MD5作为查找候选者以进行更深入比较的快速方法.

参考文献:

http://www.win.tue.nl/hashclash/SoftIntCodeSign/

---

@Ingo:是的,但是对于MD5,我们知道如何创建一对具有相同哈希值的文件(不仅如此,但已经知道了几个这样的对).对于尚未被破坏的加密哈希,我们不能故意创建这样的一对,并且意外创建它具有极小的概率,足够小以至于我们可以将其视为根本不可能(至少在那之前)哈希也被打破了).

---

正确,但这一般适用于散列.当散列是n比特长时,只有2 ^ n个可能的散列值.但是不同文件的数量是无穷无尽的.因此,具有相同散列值的不同文件对的数量也是无穷无尽的.

---

他的用例似乎不是一个关心攻击的用例,所以它可能无关紧要.