将密码转换为哈希函数

#1 楼

不仅可以将分组密码转换为哈希函数，而且可以。

常用的哈希函数（MD5，SHA-1，SHA-256 ...）使用Merkle-Damgård构造，该构造依赖于运行状态r被初始化为常规值。然后，将输入数据拆分为多个块，每个块均用作块密码的密钥：r使用当前块作为密钥用E加密；结果与r相加（或异或），这将为下一个块产生新的状态r。最后获得的状态是哈希输出。

如果要将Merkle-Damgård构造应用于AES等标准分组密码，则会遇到以下问题：


内部状态的大小是哈希输出的大小，也是密码的块大小。 AES是一种128位的块密码，导致产生128位的输出，相对于当今的技术而言，该输出太小了（它意味着最多264个评估仅能抵抗冲突，这虽然昂贵但可行）。 /> MD构造行使分组密码的不寻常特征。特别是，将输入数据用作密钥，并且冲突攻击（哈希函数的主要问题）对应于基础密码上的相关密钥攻击。当分组密码用于其设计目的（即加密）时，对于分组密码而言，相关密钥攻击不是问题。已知AES在相关密钥方面有轻微的弱点，但这对加密来说不是问题。如果在基于MD的哈希函数中将AES用作构造块，这将成为一个问题。 （抵御相关密钥攻击不是AES竞争的设计标准。）

因此，基于MD的哈希函数使用自定义块密码，该密码被设计为对相关密钥攻击特别健壮（或至少，因此我们希望如此）。对于SHA-1，内部分组密码使用自己的名称SHACAL来祝福。

另一个示例是Whirlpool，它基于块密码“ W”，具有更大块大小（512位）的AES派生词以及经过改进的密钥调度，使其对相关密钥的抵抗能力更强（不幸的是，它也使速度更慢） ）。这解决了上面说明的问题。 （惠而浦不使用Merkle-Damgård构造，而是使用Miyaguchi-Preneel，这是一个独特的构造，具有自己的怪癖。）

另一个例子是SHA-3候选者之一的Skein。它建立在一个称为Threefish的内部分组密码的基础上；同样，具有大块的块密码（“标准” Skein中为512位，可扩展为1024位）。


一些SHA-3候选对象不重用AES，而是重用了一部分AES；特别是ECHO和SHAvite-3。这个想法是要能够使用旨在加速AES的硬件来优化哈希函数，尤其是最近x86处理器的AES-NI操作码。但这并没有重用块密码本身。

必须记住的是，用块密码构建哈希函数很困难。这是不同的用法上下文。一个根本的区别是，分组密码具有攻击者不知道（并试图猜测）的密钥，而哈希函数没有秘密（当尝试建立冲突时，攻击者知道哈希函数中每个操作的所有知识） ）。

#2 楼

有许多众所周知的方法，可以从分组密码构造哈希函数。

对许多经典方法进行了彻底（但对于初学者来说是可读的）的处理方法，以及可以从PGV的基于块密码的哈希函数构造的黑盒分析中找到各种构造，PGV基于更早的基于块密码的哈希函数：一种综合方法（又名PGV）。 >
所谓的PGV方案包括常见的Davies-Meyer（例如MD5，SHA-1 / 2），Matyas-Meyer-Oseas（例如Skein）和Miyaguchi-Preneel单向压缩函数，每种压缩函数均使用块构建

每种PGV方案（总共64个，只有其中一些是安全的）是对向块密码的密钥和明文输入中提供消息块和当前哈希值的某种置换，具有对分组密码输入/输出值的各种反馈/前馈操作。

例如在Davies-Meyer中，每个消息块都用作密钥，使用块密码对先前的哈希值进行加密，然后将结果与先前的哈希值进行异或运算，以生成下一个哈希值。

然后通常将压缩函数的一种方式与Merkle–Damgård链构造一起使用，以构造有用的哈希函数。

单向压缩和链构造通常也与其他技术（例如前缀）结合在哈希函数中免费填充以防止扩展攻击，以及出于各种安全性和个性化原因而使用调整和其他参数。

也可以（但不太有用）朝相反的方向构造分组密码

试图通过使用诸如CBC之类的模式链接分组密码来构造哈希函数几乎肯定是一个坏主意，甚至可能显示为PGV安全性的形式上不安全证明。

CBC模式下的分组密码是至少两种常见的消息身份验证代码算法（CMAC和CBC-MAC）的基础，但是Mac是与哈希函数不同的野兽。

#3 楼

是的，我们可以从分组密码构建一个哈希函数，这很常见，尽管为此目的设计了分组密码，但是在下面我重点介绍AES时，在（不同的）问题中提到了这个问题，该问题促使了目前的答案[之所以搬到这里，是因为发现上述问题重复了。]

SHA-1和SHA-2系列使用的一种经典的从分组密码中获取哈希函数的方法是：Davies- Merkle–Damgård哈希中的Meyer压缩函数：


消息被填充以形成$ n $块$ M_i $，其大小与块密码的密钥相同（通常将其附加消息的单个1位，然后是一定数量的0位，然后是消息的原始长度（以64位为单位），数字0是最低的非负整数，以使最终结果是块密码的倍数密钥大小）;
$ H_0 $设置为块密码块宽度的无用值;
对于$ i $从$ 0 $到$ n-1 $计算得出$ H_ {i + 1} = \ text {ENC} _ {M_i}（H_i）\ oplus H_i $（其中$ \ text {ENC} $的下标是关键字）； < br哈希是$ H_n $。

如果使用AES-256，我们将获得$ 128 $位哈希，其中$ n = \ lfloor（l + 320）/ 256 \ rfloor $ AES加密（和子密钥派生），其中$ l $是消息长度（以位为单位）。还有其他构造，但这是使用三个AES密码之一时效率较低的一种。它的主要缺点是输出宽度有限，这使暴力冲突搜索成为一个现实问题（它需要大约$ 2 ^ {64} $加密，并且可以高效地分发，请参阅使用密码分析应用程序的并行冲突搜索）。此外，还有第二次前映像攻击，其加密费用为$ 2 ^ {129} / n + 2 ^ {65} $，这是Merkle–Damgård哈希的通用加密（归因于RD Dean在其1999年论文第5.3.1节中，并且也进行了披露）作者：J。Kelsey和B. Schneier在关于n位哈希函数的第二张原像中，其工作量不到2n。）

通过Hirose构造来构建压缩函数，我们可以将输出宽度增加一倍，达到$ 256 $ -bit（以获得更强大的抗碰撞性），而加密的价格大约是加密的四倍（并且密钥派生只有两倍），但是与SHA-256相比，这仍然意味着哈希运算速度很慢，除非可能是AES-256是硬件加速的）：


消息被填充以形成$ n $块$ M_i $如上，除了块大小是块密码密钥的宽度减去块密码块的宽度之外（因此我们在AES-256中使用$ 128 $位的消息块大小;在AES中使用$ 64 $位的消息块大小） -192，我们就不能使用AES-128）。
$ G_0 $和$ H_0 $设置为分组密码块宽度的“ nothing-up-my-sleeves”值；
计算从$ 0 $到$ n-1 $的$ i $（$ C $为非零，no-up-my-sleeves值）
$ \ begin {align *}
G_ {i + 1}＆= \ text {ENC} _ {H_i || M_i}（G_i）\ oplus G_i \\
H_ {i + 1}＆= \ text {ENC} _ {H_i || M_i }（G_i \ oplus C）\ oplus（G_i \ op lus C）
\ end {align *} $
哈希为$ G_n || H_n $。

Davies-Meyer和Hirose压缩函数均具有安全参数， Merkle-Damgård哈希在假设分组密码与随机密码在计算上无法区分的情况下，在其输出大小所暗示的碰撞攻击限制内具有抗碰撞能力。我看不到AES的已知的较小的相关关键弱点是不切实际的威胁[更新：但是那些已知的攻击只会变得更好；因此有些人给出了更谨慎的建议；我已经对此提出了一个问题。]


促使当前答案的（不同的）问题问CBC是否可用。不，CBC不适用于根据分组密码构造散列。 CBC加密不会提供固定宽度的输出。在CBC-MAC中，所有加密通用的密钥是什么？它一定是对手所知道的（哈希中没有秘密），并且独立于消息开头之后的块，这允许对消息结尾进行操作以得到所需的结果。

#4 楼

是的，绝对有可能。有关今天广泛使用的示例，请参阅bcrypt，这是一种基于河豚密码的密码哈希算法。

引用维基百科，


Provos和Mazières利用了这一优势，并将其进一步发展。他们开发了一种针对河豚的新密钥设置算法，将生成的密码称为“ Eksblowfish”（“昂贵的密钥调度河豚”）。密钥设置以标准Blowfish密钥设置的修改形式开始，其中salt和密码都用于设置所有子密钥。然后有许多轮使用标准的Blowfish键控算法，交替使用盐和密码作为键，每一轮都从上一轮的子键状态开始。从密码学的角度来看，这并不比标准的Blowfish密钥时间表强，但是重新配置密钥的次数是可配置的。因此，此过程可以任意设置为缓慢，这有助于阻止对哈希或盐的暴力攻击。

#5 楼

是的，可以根据分组密码构造哈希函数，甚至消息认证码（MAC）。最简单的方法是简单地使用预选密钥以链接模式（例如CBC）对输入数据进行加密，然后将密码的最后一个输出块用作哈希。但是，这种简单方法存在一些问题。根据哈希函数所需的属性，可以使用多种方法。可以在《应用密码学手册》第9章中找到对该主题的出色处理，尤其是从第9.4.1节“基于分组密码的哈希函数”开始。

请注意，构造与写上述书时相比，现在认为加密强度高的散列要困难得多。我强烈建议您使用SHA256，SHA384，SHA512，SHA-3或SHA-3候选者之一-或基于其中之一的MAC-除非您有充分的理由不这样做。

#6 楼

构建散列函数的一种非常常见的方法是使用Enc(k, m) xor m作为将输入k||m映射到较短输出的压缩函数，其中Enc使用块密码对单个块进行加密。

此密码的块大小对应于哈希的输出大小，并且至少应为256位以确保安全。

密码不应遭受相关的密钥攻击，并且重新密钥必须快速。

许多常见的哈希函数，包括SHA-1，SHA-2，Blake和Skein都是基于这种构造的（有微小的变化）。 SHA-3是一个值得注意的例外，因为它使用了无密钥的排列并省略了前馈（对消息进行异化处理，使压缩不可逆）。

此处不是一个好的选择，因为默认情况下，AES它只有128位块（rijndael支持256位块），并且遭受相关的密钥攻击。


不起作用的是简单地使用固定的IV和CBC模式加密消息。使用它作为哈希。这种结构称为CBC-MAC。它可以用作安全的MAC，但不能用作未加密的哈希。有关此内容的更多信息，请查看：Matt Green：为什么我讨厌CBC-MAC。

#7 楼

“加密”哈希函数通常必须具有两个属性：


它具有抗冲突性，这意味着没有有效的（概率多项式时间对手）可以找到两个不同的消息映射到相同的哈希值
正在压缩，这意味着需要一个“长”字符串并输出一个较短的哈希值。

使用分组密码对字符串进行简单加密，然后将输出用作哈希值不一定有效，因为加密需要一个秘密密钥，所以输出不一定要比输入短，并且无法保证collisi导通电阻。通常，它们只是具有不同“要求”的两个不同的加密基元。

但是，有一些方法可以根据分组密码构建哈希函数（例如Davies-Meyer构造）。
以下内容可能对您来说很有趣：
http://en.wikipedia.org/wiki/Cryptographic_hash_function#Hash_functions_based_on_block_ciphers