0

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

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

我必须从图像文件中散列多少个字符,以降低发生事故的可能性?有更好的索引方案吗?

4

2 回答 2

2

一旦您从散列中留下任何字节,您就可以让某人有机会(有意或无意地)创建一个仅在这些字节上有所不同的文件,因此散列相同。

该图像实际上与原始图像有多大不同,在某种程度上取决于您从散列中遗漏了多少字节以及在哪里。但是您首先必须决定您可以容忍哪些哈希冲突(故意/意外和主要/次要),然后您可以考虑您可以使用多快的哈希函数,以及您需要在其中包含多少数据。

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

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

您可以通过实现一些完全无关紧要的散列(例如文件中所有 4 字节字的异或)来计算出使用不太安全的散列可以运行多快的限制,并查看运行速度有多快。如果这仍然太慢,那么您需要放弃准确性并且只对文件的一部分进行哈希处理(假设您已经尽最大努力优化 I/O)。

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

顺便说一句,除非由一个非常称职的摄影师故意这样做(或者除非图像是故意后处理来实现这一点的),否则在右下角拍摄两张相同场景的照片,在开始时不会产生相同的字节的图像数据。如果您处于无法控制光线的环境中,甚至不会关闭。试试看。当使用为图像加时间戳的典型相机完成时,它肯定不会产生相同的文件。因此,如果你只是试图防御事故,那么问题会比你试图防御欺骗要容易得多。

于 2012-09-27T08:33:11.230 回答
0

我认为最有效的方法是选择随机字节(先前选择的,并且始终是静态的)并计算 XOR 或其他一些简单的哈希应该足够好。

于 2012-09-27T07:37:15.910 回答