众所周知的散列函数有“不可能”的输出值吗？

Question

我想知道的是余域和图像

例如，SHA-1输出160位摘要.能否证明每一个160位的可能序列都是SHA-1的一个可能输出(尽管相应的预图像很难计算，精心设计)，或者根据哈希函数的构造可以证明某些输出是不可能的？

这个关于哈希函数输出一致性的问题似乎是相关的。，虽然我感兴趣的不是整体的一致性，更多的是关于特定输出的任何预图像的可证明的存在/不存在。

Answer 1

No，不知道任何常用的加密散列都有不可能的输出值(即适当大小的位串，以作为输出，但任何输入消息都无法达到这一点)。至少对于MD5，SHA(-1/-2)家族的FIPS 180-4，沙三 of FIPS 202，RIPEMD-xxx，Blake/2，Tiger/2，漩涡。

事实上，令人惊讶的是，如此不可能的产值存在，更令人惊讶的是，它能够被展示出来：

• 对于被建模为随机函数的散列，当有多个$n\,2^n$输入时，存在这样值的概率低于$1/2$对于$n$-位哈希；而当有更大的消息输入集时，该概率会降低。详情请参见这。
• 对于带有Davies-Meier的Merkle-Damg rd散列圆函数，消息块最多是输出的两倍，长度填充最多约为块大小的四分之一(如MD5和直接较大的继承者)，假设底层的分组密码是伪随机排列，通过上述推理的适配，很可能所有的输出都用一个消息块达到；更有可能的是，它们都是用两个消息块达到的。其他任何东西似乎都需要底层分组密码的严重缺陷，而且任何已知的这样的缺陷似乎都要小得多。
• 对于SHA-3的海绵结构，可以提出一个类似的论点，即海绵函数的严重缺陷需要有一些无法达到的输出值。