MD5这样的哈希函数如何独特？

Question

我知道MD5有一些碰撞,但这更像是关于散列函数的高级问题.

如果MD5将任意字符串散列为32位十六进制值,那么根据Pigeonhole原则,这肯定不是唯一的,因为有更多唯一的任意字符串,而不是唯一的32位十六进制值.

Answer 1

你是正确的,它不能保证唯一性,但在32位十六进制值(16 ^ 32)中大约有3.402823669209387e + 38个不同的值.这意味着,假设算法背后的数学分布很好,你的几率非常小,会有重复.您必须记住,当您考虑如何使用它时,可以复制.MD5通常用于确定某些内容是否已更改(即它是校验和).如果可以修改某些内容并导致相同的MD5校验和,那将是非常不可能的.

编辑:(鉴于最近的新闻:SHA1哈希)上面的答案仍然存在,但你不应该期望MD5哈希作为任何类型的安全检查反对操纵.SHA-1哈希值碰撞的可能性为2 ^ 32(超过40亿),并且已经证明可以设计输入以产生相同的值.(很久以前就证明这是针对MD5的).如果您希望确保没有人恶意修改某些内容来生成相同的哈希值,那么现在需要SHA-2才能获得可靠的保证.

另一方面,如果它不在安全检查环境中,MD5仍然具有它的用处.

可以认为SHA-2哈希值足够便宜,无论如何都应该使用它.

Answer 2

你是绝对正确的.但是哈希不是"独特的",它们是"足够独特".

Answer 3

正如其他人所指出的,像MD5这样的散列函数的目标是提供一种方法,可以轻松地检查两个对象是否相同,而不知道它们原来是什么(密码)还是完整地比较它们(大文件).

假设你有一个对象O和它的哈希^ h _Ø.您获得另一个对象P并希望检查它是否相等O.这可能是一个密码,或者你下载的文件(在这种情况下,你不会有O而是H的散列_Ø与前来P,最有可能的).首先,你哈希P得到^ h _P.

现在有两种可能性:

1. h _O和h _P不同.这必须意味着O并且P是不同的,因为在2个值/对象上使用相同的散列必须产生相同的值.哈希是确定性的. 没有误报.

2. h _O和h _P相等.如你所说,由于鸽笼原理,这可能意味着不同的物体散列到相同的值,并可能需要采取进一步的行动.

   一个.因为可能性的数量是如此之高,如果你在你的哈希函数的信心也可能是不够的说"好有一个2 1 ¹²⁸偶然碰撞(理想情况下),所以我们可以假定O= P,这可能对于工作例如,如果限制字符的长度和复杂性,就会出现密码.这就是为什么你看到密码存储在数据库中而不是密码本身的原因.b.你可能认为只是因为哈希出来的并不代表对象是平等的,直接比较O和P. 你可能有误报.

因此,虽然您可能有误报,但您不会有误报.根据您的应用程序,以及您是否希望对象始终相同或始终不同,散列可能是多余的步骤.

Answer 4

从定义的本质来看,加密单向散列函数不是Injective.在散列函数方面,"唯一"是没有意义的.这些函数由其他属性测量,这些属性通过使得难以创建给定散列的预映像来影响它们的强度.例如,我们可能会关心通过更改前映像中的单个位来影响多少图像位.我们可能会关心进行暴力攻击的难度(找到给定散列图像的prie-image).我们可能会关心找到碰撞的难度:找到两个具有相同散列图像的预映像,用于生日攻击.

Answer 5

虽然如果要散列的值比生成的散列长得多，则可能会发生冲突，但对于大多数用途来说，冲突的数量仍然足够低（总共有2 ¹²⁸个可能的散列，因此两个随机字符串生成理论上，相同的哈希值接近 10 ³⁸中的 1 ）。

MD5 主要是为了进行完整性检查而创建的，因此它对最小的更改非常敏感。输入的微小修改将导致截然不同的输出。这就是为什么仅根据哈希值很难猜测密码的原因。

虽然哈希本身是不可逆的，但仍然可以通过纯粹的蛮力找到可能的输入值。这就是为什么如果您使用 MD5 存储密码哈希值，则应始终确保添加盐：如果您在输入字符串中包含盐，则匹配的输入字符串必须包含完全相同的盐才能得到相同的结果。输出字符串，否则与输出匹配的原始输入字符串在自动加盐后将无法匹配（即您不能只是“反转”MD5 并使用它来登录，因为反转的 MD5 哈希很可能不是加盐的）最初导致创建哈希的字符串）。

因此，哈希值不是唯一的，但可以通过身份验证机制使其足够唯一（这是密码限制代替加盐的一个有点合理的论点：产生相同哈希值的字符串集可能包含许多字符串）不遵守密码限制，因此通过暴力破解哈希值更加困难——显然盐仍然是一个好主意）。

更大的散列意味着同一输入集有更大的可能散列集，因此重叠的可能性更低，但在处理能力充分提高到使暴力破解 MD5 变得微不足道之前，对于大多数用途来说，它仍然是一个不错的选择。