单向散列函数如何工作？

Question

我阅读了有关md5哈希的维基百科文章,但我仍然无法理解哈希如何不能"重构"回到原始文本.

有人可以向对密码学知之甚少的人解释这是如何工作的吗？该功能的哪一部分使其成为单向的？

Answer 1

因为到目前为止每个人都已经简单地定义了哈希函数是什么,所以我会咬人.

单向函数不仅仅是一个散列函数 - 一个丢失信息的函数 - 而是一个函数f,给定一个图像y(现有答案中的"SE"或294),很难找到一个前映像x这样的f(x)=y.

这就是他们被称为单向的原因:您可以计算图像,但无法找到给定图像的预图像.

迄今为止在现有答案中提出的普通散列函数都没有这个属性.它们都不是单向加密哈希函数.例如,给定"SE",您可以轻松地选择输入"SXXXE",这是一个具有X-encode("SXXXE")= SE属性的输入.

没有"简单"的单向函数.他们必须很好地混合他们的输入,不仅你不会在输出中识别输入,而且你也不会识别另一个输入.

SHA-1和MD5曾经是流行的单向函数,但它们几乎都被破坏了(专家知道如何为给定的图像创建预图像,或者几乎能够这样做).正在进行一项竞赛,选择一种新的标准,将命名为SHA-3.

反转单向函数的一种显而易见的方法是计算许多图像,并将它们保存在一个表中,该表将每个图像与产生它的前​​图像相关联.为了使这在实践中不可能,所有单向函数都具有大输出,至少64位但可能更大(最多,例如512位).

编辑:大多数加密哈希函数如何工作？

通常,它们的核心是一个函数,它对一个位块(块密码)进行复杂的转换.该函数应该是近似双射的(它不应该将太多的序列映射到同一图像,因为这会导致后面的弱点)但它不一定是完全双射的.并且该函数被迭代固定次数,足以使输入(或任何可能的输入)无法识别.

以Skein为例,它是SHA-3环境的强有力候选者之一.其核心功能重复72次.函数的创建者知道如何有时将输出与某些输入相关联的唯一迭代次数是25.他们说它的"安全系数"为2.9.

Answer 2

想想一个非常基本的哈希 - 对于输入字符串,返回每个字符的ASCII值之和.

hash( 'abc' ) = ascii('a')+ascii('b')+ascii('c')
              = 97 + 98 + 99
              = 294

现在,给定哈希值294,你能说出原始字符串是什么吗？显然不是,因为'abc'和'cba'(和无数其他人)给出相同的哈希值.

加密哈希函数的工作方式相同,只是显然算法要复杂得多.总是会发生碰撞,但是如果你知道字符串s哈希h,那么构造另一个也是哈希的字符串应该非常困难("计算上不可行")h.

Answer 3

在这里拍摄一个简单的类比而不是复杂的解释.

首先,让我们将主题分为两部分,单向操作和散列.什么是单向操作,为什么要一个？

调用一种方式操作,因为它们不可逆.加法和乘法等大多数典型操作都可以反转,而模除法不能反转.为什么这很重要？因为你想提供一个输出值,1)在没有原始输入的情况下很难复制,2)无法确定输出的输入.

可逆

增加:

4 + 3 = 7  

这可以通过取总和并减去其中一个加数来反转

7 - 3 = 4  

乘法:

4 * 5 = 20  

这可以通过取出产品并除以其中一个因素来逆转

20 / 4 = 5

不可逆转

模数师:

22 % 7 = 1  

这是无法逆转的,因为你没有可以对商进行操作而红利可以重构除数(反之亦然).

你能找到一个填写"？"的操作吗？是什么？

1  ?  7 = 22  
1  ?  22 = 7

话虽如此,单向散列函数具有与模除法相同的数学质量.

为什么这很重要？

可以说我给了你一个钥匙给一个有一千个储物柜的公共汽车总站的储物柜,并要求你把它交给我的银行家.作为一个聪明的人,更不用说可疑了,你会立即查看钥匙,看看钥匙上写的是什么储物柜号码.知道了这一点,我做了一些狡猾的事情; 首先,我发现两个数字,当使用模数除法给出一个数字,范围在1到1000之间,第二个我擦除原始数字并在其上写上数字对的除数,第二个我选择了一个有一个数字的总线终端通过让人们每天用钥匙尝试一个储物柜来保护储物柜免受歹徒的伤害,第三,银行家已经知道了分红,所以当他拿到钥匙时,他可以做数学计算并找出剩余部分并知道打开哪个储物柜.

如果我明智地选择操作数,我可以接近商与被除数之间的一对一关系,迫使你尝试每个储物柜,因为答案将可能输入的结果扩展到所需数字范围内,储物柜可在终端使用.基本上,这意味着即使您知道其中一个操作数,也无法获得有关剩余部分的任何知识.

所以,现在我可以"信任"你将钥匙交给合法的主人而不用担心你可以轻易猜到它属于哪个储物柜.当然,你可以通过暴力搜索所有的储物柜,但这需要将近3年的时间,我的银行家有足够的时间来使用钥匙并清空储物柜.

有关不同哈希函数的更多细节,请参阅其他答案.

Answer 4

这是一个非常简单的例子.假设我是一个初学密码学家,我创建了一个哈希函数,它执行以下操作:

int SimpleHash(file) {
    return 0 if file.length is even;
    return 1 if file.length is odd;
}

现在这是测试. SimpleHash(specialFile)是0. 我的原始文件是 什么？

显然,没有办法知道(尽管你很可能很容易发现我的哈希基于文件长度).没有办法根据哈希"重建"我的文件,因为哈希不包含我的文件所做的一切.

Answer 5

哈希是一种(非常)有损编码.

为了给你一个更简单的例子,想象一个名为X编码的5个字母单词的虚构双字母编码.X编码的算法很简单:取字的第一个和最后一个字母.

所以,

X-encode( SAUCE ) = SE
X-encode( BLOCK ) = BK

显然,您无法从其编码SE重建SAUCE(假设我们的可能输入范围是所有5个字母的单词).这个词可以很容易地成为SPACE.

另外,SAUCE和SPACE都将SE作为编码产生的事实被称为冲突,你可以看到X-ecoding不会产生非常好的哈希值.:)

Answer 6

简单来说,哈希函数的工作原理是将输入数据混乱.

例如,参见MD5.它按512位块处理输入数据.每个块分为16个32位字.共有64个步骤,每个步骤使用16个输入字中的一个.因此,在算法过程中每个单词使用四次.这是单向性的来源:任何输入位在几个地方输入,在两个这样的输入之间,该函数将所有当前数据混合在一起,这样每个输入位都会影响128位运行状态的大部分.这可以防止您通过仅查看部分数据来反转函数或计算碰撞.您必须查看整个128位,并且128位块的空间太宽而无法有效地通过.

现在MD5在这方面做得不好,因为可以找到该功能的冲突.从密码学的角度来看,MD5是一种轮换加密功能.一个消息块M(512位)的处理使用输入状态V(128位值)并计算新状态V'为V'= V + E(M,V)其中'+'是字 - 明智的加法,'E'恰好是一个对称加密函数(又名'分组密码'),它使用M作为密钥,V作为要加密的消息.仔细看看,E can是一种"扩展的Feistel网络",类似于DES分组密码,有四分之三而不是两半.细节在这里并不重要; 我的观点是,在使用该结构的哈希函数(称为"Merkle-Damgård")中,什么是"好"哈希函数,类似于使分组密码"安全"的原因.对MD5的成功碰撞攻击使用差分密码分析,这是一种旨在首先攻击分组密码的工具.

从良好的分组密码到良好的散列函数,有一个不可忽视的步骤.使用Merkle-Damgård结构,如果底层分组密码能够抵抗"相关密钥攻击",则散列函数是安全的,这是一种相当模糊的特性,块密码很少被强化,因为对于对称加密,相关的密钥攻击几乎没有任何实际意义.影响.例如,AES加密结果证明不会像所希望的那样抵抗相关的密钥攻击,这并没有引发普遍的恐慌.这种阻力不是AES设计时所寻求的性能的一部分.它只是阻止将AES转换为哈希函数.有一个名为Whirlpool的哈希函数,它建立在Rijndael的衍生物上,"Rijndael"是成为AES的初始名称;

此外,还有其他结构可用于构建散列函数.当前的标准功能(MD5,SHA-1和"SHA-2"系列,又称SHA-224,SHA-256,SHA-384和SHA-512)是Merkle-Damgård功能,但许多功能都是接班人不是.由NIST(美国联邦组织处理此类事情)组织的持续竞争,选择一种新的标准哈希函数,称为"SHA-3".有关详情,请参阅此页面.现在,他们从最初的51人中减少了14名候选人(不包括十几名额外的人,这些人未能通过编写完整提交的管理测试来编写并运行正确的代码).

现在让我们看一下概念.安全散列函数应该看起来像一个随机的oracle:oracle是一个黑盒子,当给出消息M作为输入时,输出一个答案h(M),它是在输出空间中均匀地选择的(即所有n)如果散列函数输出长度为n),则为-bit字符串.如果再次给出相同的消息M作为输入,则oracle输出与先前相同的值.除了那个限制之外,oracle的输出在非先前使用的输入M上是不可预测的.人们可以把oracle想象成一个投掷骰子的侏儒的容器,并在一本大书中仔细记录输入信息和相应的输出,这样他就会尊重他的oracle合同.由于侏儒本身并不知道,因此无法预测下一个输出是什么.

如果存在随机oracle,则反转散列函数的成本为2 ^ n:为了得到给定的输出,没有比使用不同的输入消息更好的策略,直到产生预期值.由于均匀的随机选择,每次尝试的成功概率为1 /(2 ^ n),并且对投掷骰子的侏儒的平均请求数将为2 ^ n.对于碰撞(找到产生相同散列值的两个不同输入),成本约为*1.4*2 ^(n/2)*(粗略地说,带有*1.4*2 ^(n/2)*输出,我们可以组装大约2 ^ n对输出,每个输出的概率为1 /(2 ^ n)匹配,即具有两个具有相同输出的不同输入).这些是随机预言可以做到的最好的.

因此,我们寻找与随机oracle一样好的散列函数:它们必须混合输入数据,使得我们无法比简单地调用函数2 ^(n/2)更有效地找到碰撞.)次.散列函数的祸根是数学结构,即允许攻击者查看散列函数内部状态(大,至少为n位)的快捷方式,作为生成在更短空间中的数学对象的变体.对对称加密系统进行了30年的公共研究,已经产生了一整套可以应用的概念和工具(扩散,雪崩,差分,线性......).然而,最重要的是,我们没有证据证明随机的神谕实际上可能存在.我们想要一个不能被攻击的哈希函数.我们有是哈希函数的考生,对于没有攻击,目前已知的,并且,稍微好一些,我们有一些功能其中一些类型的攻击可以证明没有工作.

还有一些研究要做.