我知道碰撞的机会大约是1/2 ^ 64，但是“近碰撞”的机会是什么？例如。只有一个或两个十六进制数字不同。
作为相关主题，
如果您具有二进制序列并且仅更改一位，则得到完全不同的哈希，正确？那么，随机错误是否可能导致几乎相同的散列？我知道MD5已“破解”，因此恶意代理可以将任何必要的数据附加到文件中，以使其具有相同的哈希输出-但这是否在随机发生的任何合理范围内？
编辑：该主题在下面引发了一些讨论，这些讨论与（而不是更多！）内容比我最初的问题的范围要广。话虽如此-我仅指的是将哈希函数用作文件完整性检查，而不是针对攻击的防护。
#1 楼
手动检查散列函数时，我需要比较多少个十六进制数字
？
如果您实际上希望应用散列函数的完整安全性保证，请执行以下操作：全部都是。
我通常只查看前5个或后6个十六进制数字并称其为
足够好。
这样可以有效地将哈希函数的安全性降低到仅输出10-12个十六进制数字（也就是40-48位）的安全性，为此，我们可以轻松地在大约$ 2 ^ {24} $的评估中找到冲突，这很容易实现。
“近距离碰撞”的机会是什么？例如。只有一个或两个十六进制
数字是不同的。
如本答案所述，两个散列中$ n $位输出的最多$ t $位差的概率为-长度为$$ p_t = \ sum ^ t_ {k = 0} {n \选择k} 2 ^ {-n} $$，这意味着您需要大约$ \ sqrt {1 / p_t} $个评估才能得出所需的接近碰撞。查找这些值的策略可以在此答案中找到（包括低内存方法）。
#2 楼
如果您控制两端以及传输通道（例如，如果要通过USB驱动器在两台自己的计算机之间传输大文件），则可以只表面验证哈希即可。实际上，当您仅检查完整性时，甚至不需要加密安全的哈希函数，CRC应该足够。如果您担心文件可能会被篡改，那么您可以需要检查整个哈希。您没有说您使用的是哪个操作系统，但是在计算散列后应该很容易实现比较的自动化。
攻击者创建看起来几乎是与原始版本相同，但对于有动机的攻击者来说，匹配前8个字符或更多是完全可行的。考虑到这基本上等同于比特币挖矿所进行的计算，因此为此开发的特殊软件和硬件可以重复使用以创建已知前缀的哈希。
是否有可能进行随机错误导致几乎相同的哈希值
否。这样的机会是无穷的。
评论
$ \ begingroup $
我仅将其用于文件传输，因此安全性方面并不那么重要。谢谢您的帮助！
$ \ endgroup $
– Paul
'18 Sep 7'在22:10
$ \ begingroup $
比特币现在使用的是专用应用集成电路（ASIC）-实际上无法重新利用，尽管它们在视觉上证明了可以在可行的成本和努力下从技术上实现的蛮力。比特币的“目标”目前约为75位，接近19个十六进制数字零，并且继续稳定增长。
$ \ endgroup $
–dave_thompson_085
18-09-8在0:53
$ \ begingroup $
@ dave_thompson_085：但是请注意，这是一个很高的目标，因为它旨在使整个比特币矿工的收集平均需要10分钟才能找到。如果您在谈论单个对手，则它们必须非常强大才能提供可比较水平的哈希功能。
$ \ endgroup $
–凯文
18年9月8日在1:16
$ \ begingroup $
@RonJohn我提到了使用CRC的可能性，如果安全性不重要，这将比计算MD5和用于该工作的适当工具更为有效。
$ \ endgroup $
–约兰达·鲁伊斯（Yolanda Ruiz）
'18 Sep 9'在1:00
$ \ begingroup $
@YolandaRuiz：使用CRC的主要问题是许多文件格式都包含内部CRC，例如将文件加载到创建它的程序中，进行更改并存储，可能会以一种方式更改存储的CRC，以使文件的整体CRC保持不变。
$ \ endgroup $
–超级猫
18年9月9日在17:11
#3 楼
正如SEJPM♦回答的那样，为了完全安全-所有数字。最后5或6个十六进制数字，并称之为足够好。
将取决于威胁类型。如果您担心完全控制意外损坏的文件，那么AFAIK如果检查的最后6位数字，则有1600万次丢失损坏的可能性。但是，如果威胁是文件的恶意切换，则威胁程度可能会更高。攻击者可以使用恶意软件（如果是可执行文件）将其中的一个替换为原始文件，并在末尾添加字节，一次又一次尝试不同的值和组合，直到获得所需的最后6位数字为止，前提是您不是唯一的检查对象只有那些数字。从理论上讲，假设哈希函数在这种意义上是随机的，那么攻击者将在尝试1600万次之后找到合适的哈希。在常规GPU上，短文件可能要花费几秒钟。如果使用ASIC来完成，甚至更少。
但这不是一个实际的问题。验证校验和哈希的好应用会为您比较数字。
评论
$ \ begingroup $
但是，他正在查看十六进制摘要的最后5位数字，因此它们匹配的概率更像是1 / $ 2 ^ {20} $或百万分之一。
$ \ endgroup $
–约兰达·鲁伊斯（Yolanda Ruiz）
18年9月9日在14:29
$ \ begingroup $
如果我使用更重要的内容，绝对同意检查100％的数字。引发此问题的特定事件是传输一个50GB的数字数组文件，我只是在两端运行哈希以验证其是否完好无损。
$ \ endgroup $
– Paul
'18 Sep 9'在19:01
#4 楼
答案取决于目标，文件的准备方式以及对手是否知道特定数字的位置如果您仅担心传输中存在随机错误，检查每个十六进制数字会将未发现错误的几率除以16（24），因此检查5个十六进制数字会留下2-5×4 = 2-20（不到一百万分之一的机会）未发现错误的概率，这可能就足够了。
在每个肢体上检查5位数字可得出2-40（百万分之一的机会，因此，通过此程序每天进行一次手动检查，每天检查8个小时，持续100年，而所有文件中的错误均少于一次）一千个就错过了一个错误）。
如果您担心对手故意更改了传输中的文件，但是您已经准备好文件，那么检查每个十六进制数字将使攻击变得困难16倍（24倍）为对手。对于100位安全性（与到目前为止浪费比特币的努力相称），您要检查64位数字中至少100/4 = 25.
如果对手知道每个末端都检查了6位数字，只需大约26×2×4 = 248个散列即可找到通过测试的已知文件的文件变体；这是重要但可行的工作。
如果您担心对手故意更改了正在传输的文件，并且不知道原始文件是如何制作的，那么最好的保险就是检查每个十六进制数字至少使攻击次数达到4次（22个系数）对对手来说同样困难（较低的保证是由于生日问题）。为了获得100位安全性，您希望至少检查64位数字中的100/2 = 50.
如果对手知道每个末端都检查了6位数字，则只需大约26×2×2 + 1 = 225个散列即可找到两个文件（不同的）SHA-256散列将通过您的测试（通过Paul C的方法） van Oorschot和Michael J. Wiener，使用密码分析应用程序进行并行碰撞搜索，1999年在密码学杂志上，这很容易。
如在其他答案中所指出的，验证随机选择的位置上的几个数字可以得出即使针对强大的攻击者也具有良好的安全性。
#5 楼
根据您的威胁模型。如果您的威胁模型是邻居的儿子弄乱了您的wifi，那么也许只有几位数就足够了。
如果使用受信任来源的有效证书在ssl上加载了文件，则零哈希位可能是一个可以验证的合理数字。另外，如果文件和哈希来自同一媒体，并且来自同一来源，则验证是徒劳的。根据攻击者的计算能力，获取头几个/后几个是可行的。但是，获得高百分比是任何人都无法承受的。因此，即使是针对强大的攻击者，验证几个八位位组也能提供很好的安全性。我尝试记住我在选择随机八位字节方面很糟糕，自然可以连续验证几个八位字节，因此为了高置信度可能需要更多八位字节。
评论
$ \ begingroup $
“即使是针对强大的攻击者，验证几个八位字节也能提供很好的安全性”：是的！那可以量化。
$ \ endgroup $
–fgrieu♦
18年9月9日在18:59
评论
我不知道这个术语，也不想研究它并写一个答案，但是哈希函数具有一个特性，即输出应随输入的微小变化而发生剧烈变化（无论这意味着什么）。我认为sha256具有该属性。这意味着对于没有攻击者的文件传输，散列应该相同（正确传输）或完全不同（在传输过程中某些位被翻转）。这是一种合理的启发式方法，但是您对启发式安全性感到满意吗？
我不记得该技术的名称，但是某些黑帽软件专门尝试生成“模糊碰撞”，该碰撞在视觉上将第一个和最后一个字符上的哈希值匹配起来，以愚弄人类。
@JohnColeman：一个关键问题是攻击者是否能够预测您要检查的数字。如果要从64位哈希中选择甚至验证随机选择的六位数字，攻击者将不得不非常努力地将检测到的可能性降低到1％以下。但是，如果攻击者知道您要检查特定的六位数，那么散列了大约1600万个文件的攻击者将能够找到被检测到概率为0％的文件。
@没人，我想您在说的是雪崩/串级效应