android - 如何充分散列图像以避免碰撞？

Question

我想使用哈希值来唯一标识来自 Android 手机的照片，以回答关于does server have xyz? 的查询和fetch image which hashed to xyz 。我面对这个:

1. 散列整个图像可能很慢，因此我只想散列图像文件的前几个单位(字节)，而不是整个文件。
2. 由于构图，前几个字符不足，例如，用户拍了一张场景照片，然后在照片底部添加回形针后又拍了同一场景的第二张照片框架
3. 前几个字符不足以避免哈希冲突，即可能导致用户混淆。

我必须从图像文件中散列多少个字符，才能将发生事故的可能性降到最低？有没有更好的索引方案？

Answer 1

一旦您从散列中遗漏了任何字节，您就给了某人创建(有意或无意)仅在这些字节不同的文件的机会，因此散列相同。

此图像与原始图像的实际差异在某种程度上取决于您从散列中遗漏了多少字节以及遗漏的位置。但是你首先必须决定你可以容忍什么样的哈希冲突(故意/意外和主要/次要)，然后你可以考虑你可以使用多快的哈希函数，以及你需要在其中包含多少数据。

除非您愿意容忍“大块”的数据更改，否则您需要在散列中包含来自每个“大块”的字节。从 I/O 性能的角度来看，这意味着您几乎需要访问整个文件，因为即使读取一个字节也会导致硬件读取包含它的整个 block 。

可能要做的事情是从“绝对足够好”开始，例如整个文件的 SHA-256 哈希。查看速度有多慢，然后考虑如何将性能提高所需的百分比。例如，如果它只慢了 50%，您可能可以使用更快(安全性较低)但仍包括所有数据的哈希来解决问题。

您可以通过实现一些完全微不足道的散列(例如，文件中所有 4 字节字的异或)来计算使用不太安全的散列的速度限制，并查看运行速度。如果这仍然太慢，那么您需要放弃准确性并仅散列文件的一部分(假设您已经尽力优化 I/O)。

如果您愿意容忍冲突，那么对于大多数(所有？)图像格式，仅标题中就有足够的信息来唯一标识“正常”照片。这不会保护您免受蓄意碰撞或图像处理结果的影响，但除非恶意，否则时间戳、图像大小、相机型号等，连同少量图像数据实际上将唯一地识别“有人拍摄”的每个实例某物的照片”。因此，在此基础上，您可以仅散列文件的前 64-128k(或更少，我很慷慨地包括 EXIF header 的最大大小加上一些)并具有适用于大多数实际目的的散列，但可以想打就打。

顺便说一句，除非由一位非常有能力的摄影师故意完成(或者除非图像经过故意后处理以实现此目的)，否则拍摄两张右下角差异很小的同一场景的照片将不会 在图像数据的开头产生相同的字节。如果您处于无法控制光线的环境中，则甚至不能关闭。试试看。当使用为图像添加时间戳的典型相机完成时，它肯定不会产生相同的文件。因此，如果您只是试图防范事故，那么问题会比您试图防范欺骗要容易得多。