logo标签列表

这个校验算法能否进行改进？

c++algorithmchecksum
5

我们有一个非常老旧的、不受支持的程序，可以在SMB共享之间复制文件。它具有检查和复制文件内容前是否发生更改的校验和算法。该算法似乎很容易被欺骗——我们刚刚发现了一个例子，其中两个文件除了一个'1'变成了'2'外完全相同，但返回相同的校验和。以下是该算法：

unsigned long GetFileCheckSum(CString PathFilename)
{
        FILE* File;
        unsigned long CheckSum = 0;
        unsigned long Data = 0;
        unsigned long Count = 0;

        if ((File = fopen(PathFilename, "rb")) != NULL)
        {
                while (fread(&Data, 1, sizeof(unsigned long), File) != FALSE)
                {
                        CheckSum ^= Data + ++Count;
                        Data = 0;
                }
                fclose(File);
        }
        return CheckSum;
}

我不是一个很擅长编程的人（我是一名系统管理员），但我知道基于异或的校验和会相当粗糙。使用这种算法，两个大小相同但内容不同的文件返回相同的校验和的几率有多大？（我不期望得到精确答案，“远程”或“相当可能”都可以。）

如何在不影响性能的情况下改进它？

最后，fread() 是怎么回事？我快速浏览了文档，但还是没看懂。是将 Data 依次设置为文件的每个字节吗？编辑：好吧，它将文件读入到 unsigned long（假设这里是32位操作系统）块中。每个块包含什么？如果文件内容是 abcd，第一次传递时 Data 的值是什么？它是（在 Perl 中）：

(ord('a') << 24) & (ord('b') << 16) & (ord('c') << 8) & ord('d')
2
fread正在将一个元素读入到Data的地址。被读取的元素大小是无符号长整型的大小（8个字节，我想）。 - Robert Harvey
无符号长整型的大小取决于处理器架构（32/64位），这就是为什么要使用sizeof的原因。 - schnaader
假设是大端系统，那么这是正确的。在小端系统上则相反。 - ephemient
8个回答
7

MD5常用于验证传输文件的完整性。源代码在c++中已经很容易获取。该算法被广泛认为是一种快速而准确的算法。

另请参阅强大且快速的校验和算法？

附注：MD5仅适用于验证来自可信源的文件完整性。如果提前完成并同时制作两个文件，则可以创建具有相同MD5校验和的两个文件。但是，制作与另一个文件具有相同MD5的文件是极其困难的。 - rlbond
如果您不关心加密强度，MD4比MD5简单快速一些，CRC-32则明显更简单快速。但是，它们都无法与OP（已破解）的“校验和”速度相匹敌。 - ephemient
我认为 MD4 和 CRC32 在速度上会相等，因为它们都很可能受到 I/O 限制。即使是现代 CPU，MD5 也可能受到 I/O 限制。 - MSalters
啊，OP正在进行4字节读取，那几乎肯定会受到I/O限制。嗯，如果你只在内存中工作，我认为我的排名仍然有效。 - ephemient
5
我建议您查看Fletcher's checksum，特别是fletcher-32，它应该相当快，并且可以检测出当前XOR链无法检测到的各种问题。
3
您可以通过使用类似于以下公式的公式来轻松改进算法：
Checksum = (Checksum * a + Data * b) + c;

如果a、b和c都是大质数，则此操作应返回良好的结果。此后，旋转（而不是移位）校验和的位将进一步改善其性能。
使用质数，这是与线性同余生成器类似的算法-它保证长周期和良好的分布。
我不确定那如何有助于分发！它有助于加强对恶意攻击的防御。 - Martin York
假设这些文件都是许多ASCII文本，这将确保您不会总是将约5个字节的差异进行XOR运算，并将熵分散到校验和中。 - Paul Fisher
0

SHA-1和（最近更多地是SHA-2）提供了出色的哈希函数，我相信由于更好的哈希属性而慢慢取代MD5。它们所有的实现（md2、sha等）都非常高效，并返回一个几个字符长的缓冲区的哈希值（尽管始终是固定长度）。它们被证明比将哈希值缩小为整数更可靠。如果我可以选择，我会使用SHA-2。请点击this link查看实现SHA校验和的库。

如果您不想编译这些库，Linux（以及可能是Cygwin）有以下可执行文件：md5sum、sha1sum、sha224sum、sha256sum、sha384sum、sha512sum；您可以提供您的文件，它们将打印出十六进制字符串的校验和。您可以使用popen来执行这些程序--像这样：

const int maxBuf=1024;
char buf[maxBuf];
FILE* f = popen( "sha224sum myfile", "w" );
int bytesRead = f.read( buf, maxBuf );
fclose( f );

显然，这将运行得相当慢，但是作为有用的第一步很好。 如果速度是一个问题，考虑到像这样的文件哈希操作和I/O绑定（内存和磁盘访问将成为您的瓶颈），我预计所有这些算法都会以产生无符号整数的算法一样快地运行。Perl和Python也带有MD5 SHA1和SHA2的实现，可能与C/C++中的实现一样快。

SHA-1在密码学方面比MD-5具有更好的特性。但这在这里是无关紧要的。 - MSalters
可能。这取决于应用程序。这里有一个关于MD5（密码学）问题的讨论。http://en.wikipedia.org/wiki/MD5（顺便说一句，它也指出SHA1在密码学目的上已经被破解了。） - user48956
0

看起来你的算法似乎没有处理那些大小不是4字节整数倍的文件。fread的返回值不是布尔值，而是实际读取的字节数，如果遇到EOF或错误，它将与4不同。你没有检查这两种情况，而只是假设如果它没有返回0，你就有4个有效字节在“data”中用于计算哈希。

如果你真的想使用哈希，我建议你做几件事情。首先，使用一个简单的加密哈希，比如MD5，而不是CRC32。CRC32适用于检查数据的有效性，但对于跨越文件系统并确保没有冲突，它不是一个很好的工具，因为在其他评论中提到的生日悖论。其次，不要自己编写函数。找到一个现有的实现。最后，考虑简单地使用rsync来复制文件，而不是自己开发解决方案。

我认为（假设没有错误且文件长度> sizeof(long)），哈希将返回一致的结果，因为最后读取的位将始终从上一次迭代中保留下来。 - BCS
这依赖于代码中的两个缺陷来确保正确的功能。如果有人添加了代码以在每个循环之间重置“数据”为0，则也会产生一致的结果，但现在CRC的任何先前存储的值都是不正确的。 - Jherico
马丁删除的回答实际上是正确的。在这个应用程序中，你正在尝试检测两个特定文件是否相同，而不是一个文件与集合中的任何文件是否匹配。因此，生日问题并不适用。 - erickson
@Jhericho：我们无法使用rsync，因为我们正在处理一个有数百万个文件的100Gb+文件系统。当文件更改时，需要快速将其传播到许多其他服务器（100+），因此我们在进行更改时同时触发特定文件的复制。有时也会推送未更改的文件，因此需要进行校验和。Rsync可能会因> 100Gb而崩溃，并且肯定需要很长时间才能传播更改。我们的解决方案不够优雅，但目前我们卡在这里。 - markdrayton
即使你正在处理一个“可能已更改”的文件列表，你仍然可以将该列表提供给rsync，并告诉rsync使用校验和来确定文件是否已更改。但这样做仍然是在重新发明轮子。 - Jherico
显示剩余3条评论
0

fread 位元組一次讀取文件。每個位元組大小為 long（在c中，這不是一個明確的大小，但您可以假設為32或64位元）。根據緩衝方式，可能不壞。另一方面，將較大的位元組讀入數組並循環遍歷可能會更快。

0
即使是“昂贵”的加密哈希函数通常也需要多次迭代才能花费大量时间。虽然不再推荐用于密码学目的，因为用户会有意尝试创建碰撞，但像SHA1和MD5这样的功能广泛可用且适合此目的。
如果需要更小的哈希值，则CRC可以使用，但效果不佳。 n位CRC将不能检测到比n位长的少量更改。例如，假设文件中只是单个美元金额被更改，从$12,345变为$34,567。32位CRC可能会忽略该更改。
截断较长的加密哈希结果比CRC更可靠地检测更改。
0
{
   CheckSum ^= Data + ++Count;
   Data = 0;
}

我认为 "++Count" 并没有做太多的工作。这段代码等同于

{
  CheckSum ^= Data;
}

仅仅异或一系列字节是不够的，尤其是对于文本文件。

我建议使用哈希函数。

1
++Count做了很多工作，例如它可以防止像chk(ABCD) = chk(DCBA)这样的微不足道的冲突，当使用^= Data时会发生这种情况（这里的A、B、C、D是指无符号长整型）。 - schnaader
好的，但请注意它仅影响每轮中的第4个字节，每256次循环中的第3个字节，每65536次循环中的第2个字节等。 - Nick Dandoulakis
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接