关于加密哈希函数的重点是什么？

Question

我正在阅读关于MD5哈希值的这个问题,接受的答案让我困惑.据我所知,cryptopgraphic哈希函数的一个主要属性是找到具有相同哈希值的两个不同消息(输入)是不可行的.

然而,为什么MD5哈希值不可逆的问题的共识答案呢？是由于输入字符串的无限数量将产生相同的输出. 这似乎与我完全矛盾.

另外,令我困惑的是,算法是公开的,但哈希值仍然是不可逆的.这是因为散列函数中总是存在数据丢失,因此无法分辨哪些数据被丢弃了吗？

当输入数据大小小于固定输出数据大小时(例如,散列密码"abc")会发生什么？

编辑:

好的,让我看看我是否有这个:

1. 实际上,很难从哈希中推断出输入,因为有无限量的输入字符串会产生相同的输出(不可逆属性).
2. 然而,找到生成相同输出的多个输入字符串的单个实例也非常非常困难(抗冲突属性).

Answer 1

警告:答案很长

我认为所有这些答案都缺少加密哈希函数的一个非常重要的属性:不仅无法计算散列的原始消息来获取给定的哈希值,因此无法计算任何会散列到给定哈希值的消息.这称为原像抗性.

(通过"不可能" - 我的意思是没有人知道如何在比猜测每个可能的消息所花费的时间更短的时间内完成它,直到你猜到散列到哈希值的那个消息.)

(尽管人们普遍相信MD5的不安全性,但是MD5仍然可以抵抗preimage.任何不相信我的人都可以自由地给我任何哈希值2aaddf751bff2121cc51dc709e866f19.MD5没有的是碰撞阻力,这完全不同于其他东西.)

现在,如果你不能在加密哈希函数中"向后工作"的唯一原因是因为哈希函数丢弃数据来创建哈希值,那么它就不能保证前映像素阻力:你仍然可以"向后工作",只需插入随机数据散列函数丢弃数据的任何地方,虽然你不会提出原始消息,但你仍然会得到一个哈希到所需散列值的消息.但你不能.

所以问题变成了:为什么不呢？(或者,换句话说,你如何使功能preimage抗性？)

答案是加密哈希函数模拟混沌系统.他们接受你的信息,把它分成块,混合这些块,让一些块相互交互,混合这些块,并重复那么多次(好吧,一个加密哈希函数做到这一点;其他人有他们的自己的方法).由于块彼此交互,块C不仅必须与块D交互以产生块A,而且它必须与块E交互以产生块B.现在,当然,你可以找到块C,D的值, E会在你的哈希值中产生块A和B,但是当你往后走时,突然你需要一个与C交互的块F来制作D,并且用E来制作B,并且没有这样的块可以在同一时间!你必须猜到C,D和E的错误值.

虽然并非所有加密哈希函数都与上面描述的块交互完全相同,但它们也有相同的想法:如果你试图"向后工作",那么你最终将会遇到很多死胡同,以及它的时间你需要尝试足够的值来生成一个数百到数百年的预成像(取决于散列函数),这比尝试消息所需的时间要好得多,直到找到一个有效的消息.

Answer 2

1:散列的主要目的是将非常大的空间映射到较小但仍然非常大的空间(例如,MD5,它将采用'任何'并将其转换为大小为2 ^ 128的空间 - 大,但不像aleph-0那么大.)

除了其他功能外,良好的哈希值可以均匀地填充目标空间.坏哈希以一种笨重的方式填充空间,为许多常见输入提供相同的哈希值.

想象一下这个愚蠢的哈希函数sum(),它只是添加输入数字的所有数字:它成功地向下映射,但是有一堆冲突(具有相同输出的输入,如3和12和21)处于低位输出空间的末端和空间的上端几乎是空的.结果,它使用空间非常差,容易破裂等.

因此,即使使用目标空间也很难找到具有相同输出的两个输入,只需要几率:如果MD5是完美的,那么两个输入具有相同输出的几率将是2 ^ - 128.这是相当不错的几率:你可以做到最好,而不需要求助于更大的输出空间.(事实上​​,MD5并不完美,这是使其易受攻击的因素之一.)

但是大量的输入将映射到任何给定的散列仍然是正确的,因为输入空间是"无限的",并且将无穷大除以2 ^ 128仍然会给你无穷大.

2:是的,散列总是会导致数据丢失,除非您的输出空间与输入空间相同或大于输入空间 - 在这种情况下,您可能不需要哈希!

3:对于较小的输入,最佳做法是对输入加盐.实际上,这对于任何加密哈希都是很好的做法,因为否则攻击者可以为您提供特定的输入并尝试找出您正在使用的哈希."Salt"只是您在输入中附加(或前置)的一组附加信息; 然后哈希结果.

编辑:在密码学中,哈希函数抵抗前映像攻击也很重要,直观地说,即使知道许多其他输入/输出对,也难以猜测给定输出的输入."sum"函数可能很容易被猜到(但是因为它破坏了数据仍然可能不容易反转).

Answer 3

你可能会感到困惑,因为答案给你举的问题 是混乱的.加密哈希函数的一个要求是它应该是抗图像的.也就是说,如果您知道MD5(x)但不知道消息x,则很难找到任何x'(等于x或与x不同),使得MD5(x')= MD5(x).

抗原像素是一种不可逆的特性.如果给定y = f(x),则函数是可逆的,恰好有一个x适合(这是否容易).例如,定义f(x)= x mod 10.那么f是不可逆的.从f(x)= 7,你无法确定x是17,27还是别的.但f不具有前像抗性,因为很容易找到f(x)= 7的值x'.x'= 17,27,12341237等都可以.

在进行加密时,您通常需要具有抗原图像的功能(以及其他属性,如抗冲击性),而不仅仅是不可逆的功能.