假设您使用的是相当受限的平台（例如，低端嵌入式设备），没有内置加密功能，但是您确实可以访问简单的流密码；例如RC4或eSTREAM密码之一。您还可以利用该流密码构建其他哪些加密原语？特别是，是否有任何可行的方法可以仅根据流密码来构建密码哈希函数和/或MAC？
我们已经有关于将哈希值转换为流密码的问题。以及将流密码转换为分组密码的方法，但是这种特殊的转换似乎尚未涵盖。
显然，如果平台约束允许，人们可以忽略流密码而只是从头开始实施标准的哈希函数。我想知道的是，拥有流密码是否可能使它在代码大小，内存使用和/或速度方面比它做得更好。
将流密码视为一种黑盒会很好，仅使用部分流密码的方案（例如RC4-Hash，可惜有实际的碰撞攻击）也很有趣，至少在它们足够简单的情况下也是如此。
#1 楼
我很确定，不建议使用流模型来构造加密哈希。我手头没有完整的理论证明，但可以从著名的流密码RC4的角度考虑它。它容易受到相关密钥攻击。现在，要使用RC4构造哈希函数，您需要争辩说它应该能够抵抗更强大的对抗模型，即选择键攻击，从而使攻击者可以针对键调度中的弱点。我确定RC4不会考虑使用全选键（如果我错了，请更正我）。另一方面，您允许对手在加密散列函数的任何形式的阻力（除了尚未正式定义的选定目标强制前缀阻力）的定义的第一部分中选择密钥！因此，我很确定这是不可取的。但是，如果从理论的角度来看很少的结果，Coron等人。证明了理想密码模型和随机预言模型之间的等效性。这提供了一些希望：将流密码转换为理想密码模型中的分组密码安全，然后等效地将其转换为随机预言模型中的安全密码；但是我们陷入了困境（如何从RO模型转到哈希函数的实例化。毕竟，百万美元的问题是，在Canetti等人的研究表明随机oracle模型存在缺陷之后，我们是否信任随机oracle模型！
评论
$ \ begingroup $
反对票否定，您能说出您对答案不满意的原因吗？
$ \ endgroup $
–贾拉杰
2012年3月31日15:34
$ \ begingroup $
我没有对您投反对票，但我确实认为您和B-Con的答案都只涉及部分问题。就像你们俩都正确指出的那样，由于$ H（m）= S（m）$是安全的流密码，因此即使没有$ S（m）$是安全的流密码，也没有先验的理由安全要求；实际上，Indesteege和Preneel对RC4-Hash的分析似乎证明，这种天真的方法应用于RC4时不会产生安全的哈希。但是，这并不意味着在应用到……时，就不会有过少的幼稚构造会产生安全哈希（或MAC）的情况。
$ \ endgroup $
–伊尔马里·卡洛宁（Ilmari Karonen）
2012年4月1日下午14:53
$ \ begingroup $
...一种安全的流密码，例如为散列找到冲突或以比暴力破解概率更好的伪造MAC，将意味着对于流密码而言，优于暴力破解识别器。当然，答案很可能是目前尚无这样的构造（尽管，如果我没记错的话，至少对于MAC来说，Carter-Wegman的构造似乎提供了一个例子），但我宁愿在接受这样的否定答案之前，请等待更长的时间。
$ \ endgroup $
–伊尔马里·卡洛宁（Ilmari Karonen）
2012年4月1日在15:01
$ \ begingroup $
@Illmari：是的，我只是想解决一个简单的问题。我编辑了答案以强调这一点。 // @ Jalaj：我也被否决了，所以似乎有人不喜欢我们的答案。 （也许是因为它们提供的信息更多且结论性较低。）
$ \ endgroup $
– B-Con
2012年4月3日19:33
#2 楼
伪随机生成器（PRG）和哈希函数都是伪随机函数（PRF），但是它们具有不同的安全注意事项。 （至少从历史上看，它们确实如此。向前推进其中的一些可能会更加紧密地对齐。）因此，对于在较旧的安全性约束下设计的现有PRG构造散列，对于使用明文作为PRG的密钥，PRG输出作为哈希。请参阅以下摘要：为什么不应该将流密码用于哈希。#3 楼
这真是个坏主意。大多数流密码（当然是RC4）以及任何处于反模式构造的内容最终都将PRNG XOR到明文中。这对于加密是很好的-信息理论非常容易理解-但它不是哈希函数的基础。哈希函数和密码的目标是不同的。事实证明，您可以将分组密码转换为哈希函数，但即使如此，也没有任何分组密码能够构成良好的哈希函数。
这样想吧-密码就像一个纸牌游戏。它依赖于这样一个事实，即您看不到对手手中的东西，而不确定性则使它变得困难或难以处理。但是哈希函数就像下棋一样。每个人都知道一切，哈希函数的目标是使其变得如此复杂，以至于您无法向后移动，并且没有简单的方法可以预测向前。
评论
$ \ begingroup $
可以将流密码的PRNG部分视为密钥的随机函数，然后将消息作为密钥进行散列，而不是在明文位置。
$ \ endgroup $
–PaŭloEbermann
2012年4月13日23:06
#4 楼
编辑：请参阅注释，此构造不是可证明是安全的经过进一步思考，答案是“是”，您可以从流密码构造哈希。 （几天前我的其他回答只是否定的，例如，如何不构造它。）这是一种构造。
首先从流密码$ S $构建一个分组密码$ B $。 ：
从$ S $中获取PRG $ P $。
您可以使用CGM结构从PRG中构建PRF家族$ F $。使用$ P $来构建$ F $。
您可以使用Feistel网络从PRF来构建PRP（分组密码）$ B $。 （Luby-Rackoff定理指出，可以使用Feistel网络的3轮（或4轮，取决于安全需求）来使用安全PRF来构建安全PRP。）使用$ F $来构建$ B $。
现在我们有PRG提供的PRP。 （而且我们没有像其他流密码那样使用哈希来阻止密码构造；在这种构造中使用哈希似乎是无用的循环）。现在，根据分组密码构建哈希：
您可以使用Davies-Meyer压缩功能从PRP构建抗碰撞压缩功能$ h $。使用$ B $构建$ h $。 （编辑：不一定-DM需要理想的密码，该密码比$ B $强。在此步骤中不会遵循安全证明。这可以通过找到其他$ h $构造或$ B $构造来解决。 ，但我还没有找到。）
您可以使用Merkle–Damgård结构从抗碰撞压缩函数构建抗碰撞哈希函数$ H $。使用$ h $来构建$ H $。
关于您的实际考虑：效率高吗？我一般不会说话，所以让我们分析一下这种结构。流行的哈希函数（例如MD5和SHA家族）使用相同的Merkle–Damgård构造，因此，将我们的$ M $与它们进行比较，我们只专注于分析$ h $。
速度：每次$ h $迭代，我们都会进行3轮以上的Feistel网络，其中每一轮都包括键入$ F $并从中生成少量输出。由于CGM的工作原理，对我们的$ F $进行键控并自己生成$ n $位输出本身需要$ P $的$ n $重新键和$ P $的$ n $数量的$ P $输出，这取决于CGM构造的工作原理。它是可并行的。因此，我们的$ n $位$ h $需要至少$ 3n $键的$ P $和$ P $的$ 6n ^ 2 $位输出。考虑到现代流密码的速度，这与现代哈希算法相比非常慢，但是在以下情况下可能是实用的：哈希稀少，哈希输入很小或哈希不是很紧迫的时间。
实现开销：我们需要实现CGM构建，Feistel网络和DM功能。从$ P $构建$ F $会重复使用$ P $的实现，并添加一个反馈循环，将$ n $位的输出推回到$ P $的键中，分支条件为1位，且不超过$输入之外的n $个附加位将需要一次存储在内存中。 Feistel网络的构建开销最小，只需几个XOR和阵列交换。 DM结构只是Feistel网络和另一个XOR的一对输入。看起来它比SHA-2压缩功能的开销要少。
我们应该可以在此方案上进行改进。与通过PRP相比，我们也许可以更直接地从PRF构建压缩功能。效率的最大损失是CGM，也许另一种构造可能比CGM更有效地将PRG转换为PRF。
编辑：如果我们可以不同地构建压缩函数，这可能会起作用。在此之前，这只是一个有趣的构造，没有安全证明。我将其保留为将来自己或其他人修复的起点。
评论
$ \ begingroup $
嗯，那肯定是一种结构。但是，您尚未证明它是安全的结构。例如，Luby-Rackoff使用标准的分组密码假设（密钥是秘密的，并且相关的密钥攻击不适用）来生成安全的PRF； Davies-Meyer构造假设我们有理想的分组密码（输出本质上是密码和明文的随机函数）。 Luby-Rackoff结构是否还提供Davies-Meyer所需的其他属性？我不会这么认为。
$ \ endgroup $
–雨披
2012年4月4日22:11
$ \ begingroup $
你是对的。我不明智地掩盖了这一步骤（我不知道DM需要IC），而且看起来很致命：PRP不足以实现压缩功能（第4页）。我能找到的最好的是10轮Luby-Rackoff在完全CPCA下提供安全性。另一方面，我找不到需要比理想密码少的压缩函数。由于从$ S $到$ B $的安全性和从$ h $到$ H $的安全性似乎很明确，因此我将保留此安全性，以防将来的自身或其他人能够弥合差距。
$ \ endgroup $
– B-Con
2012年4月13日18:24
$ \ begingroup $
如果您有PRF，为什么我们不能直接将其用作压缩功能？似乎首先从PRF构建PRP，然后使用Davies-Meyer从中删除P方面，似乎是不必要的开销？
$ \ endgroup $
–PaŭloEbermann
15年5月25日在16:42
评论
如果您查看通用哈希函数的安全性要求，您会注意到与众所周知的加密哈希函数的安全性要求（即抗碰撞性）的不同。引入UOWHF的原因是为了构建高效的签名方案，而不依赖于诸如抗碰撞性之类的更强属性。Carter-Wegman MAC可以进行经过身份验证的加密，但是对于快速，安全的哈希函数而言，它们并不成功。正如Jalaj指出的那样，存在一系列不同的安全要求。
是的你可以。这是因为可以使用分组密码进行哈希，并且我们知道可以从流密码进行分组密码。因此，通过传递属性，我们可以观察到可以根据流密码进行哈希运算。希望对您有所帮助！