对窄管道加密哈希函数设计的关注有多有效?

窄管道散列函数样式最近受到攻击,尤其是一些 SHA-3 前景。 这种反对合法吗? 它可以比 这张纸 解释得更多吗?

4
2022-06-07 14:36:12
资源 分享
答案: 2

您是在询问正在进行的研究级对话是否具有品质或其他方面。 这很难理解,因为专家们正在积极地为这些东西提供服务,而你永远不明白会发生什么:批评可能会失败(就像 Courtois 在 10 年前造成重大恐慌之后对 AES 的代数攻击一样)或得到回报(就像小云王一样是MD5罢工)。

你渴望我的观点看法? 我会提供它:散列函数安全性的存在证据(这是您在调查交易中指出的论文)没有多大说服力。 除非你能表现出真正的攻击,否则我不相信警报系统的钟声应该响起。 下面是一个合适的例子:

考虑一些 SHA-3 散列函数 $H$。 (对于不知情的人,加密哈希函数是从任意大小的字符串到某个已定义修复大小的映射;它是一个公共函数;没有密钥。)因为 $H$ 具有无限域和有限数组,所以根据鸽子洞原理,存在碰撞。 因此 $H$ 不是抗崩溃的,因此它也很麻烦。

假的吧? 存在性证据在计算设置中并不能说明太多。 自然有意外,但希望是我们不能发现他们。

也就是说,有其他各种论文提供了对细长管道结构的令人难以置信的攻击,因此即使在没有具体的合理打击的情况下,如果永远不会有任何类型的因素拒绝它,情绪肯定会相对于该技术扩大。 尽管令人沮丧,但密码学仍然部分精神当它涉及设计原语时(定义我们非常依赖本能和冲动而不是证据,因为哈希特征以及块密码和整数分解等不存在安全证据)。

修改为添加: 我选择在下面保密。 我的博士学位是密码学,我有 5 到 6 个与密码散列有关的文件,而且我是美国“相当不错”的地方的教授。您可以考虑到这一点阅读上述意见,或者您可以丢弃它作为“怀疑”和“未经证实”。 我会把它留给你。

3
2022-06-07 15:02:30
资源

这是一个简单的学术攻击,在对任何类型的给定哈希函数的安全住宅或商业财产执行实际攻击时,它的规模相当小,没有任何重大价值。

描述需要一些数学知识,虽然很明显,但如果学究式地讨论使用形式数学是很奇怪的。 但是,由于这种迂腐是本网站的首选,我肯定会提供未知的以及纯粹正确的形式数学响应,然后澄清它,以便实际上对官方数学符号不是特别了解的人希望理解它。 当然,最初的论文使用了官方的数学推理,从不费心去解释它,这就是为什么它无法实现,也是我首先问这个问题的原因。

就个人而言,我真的觉得那些依靠这种东西并且不费心以对不想学习专业符号符号迷宫的人有意义的方式来解释它的论文应该被杂志拒绝. 那么也许写它们的人肯定会学会互动。

所以,下面是半无用的 算术 部分:


有这样一个功能:

$$f(x) \to y$$ $${ X \equiv \{ a \mid a \in \mathbb Z, 0 \leq a < 2^n \} }, { x \in X }$$ $${ Y \equiv \{ a \mid a \in \mathbb Z, 0 \leq a < 2^m \} }, { y \in Y }$$

在用作随机预言机的合适哈希函数中,$f(x)$ 将集合 $X$ 的每个特定成员映射到集合 $Y$ 的完全随机参与者。 我们将 $O$ 定义为 $f$ 的变体,因此:

$$O \equiv \{ {y \in Y} \mid {y = f(x)}, x \in X \}$$ $$O \subseteq Y$$

如果 $n < m$ 它显然是 $O \neq Y$ 的情况。 此外,如果是 $n = m$,那么在最有可能的情况下,$O \neq Y$(尽管 $O \subset Y$)也会成立。 尽管随着 $n$ 比 $m$ 扩大,$O = Y$ 变得越来越可能。

最终结果通常是 $\frac{n(O)}{n(Y)} = {1 - \frac{1}{e}}$ 时 $n = m$,就像窄管道散列函数中的情况一样。 ${1 - \frac{1}{e} } \approx 0.632$,所以这意味着 $Y$ 的一半多一点的成员肯定会从 $X$ 映射到。

$$\frac{2^n}{2} = 2^{n-1}$$ $$\frac{2^n}{\frac{1}{1 - \frac{1}{e}}} = {2^{n-\log_2 {1 - \frac{1}{e}}}} \approx {2^{n-0.66}}$$

这意味着如果 $n = m$,$\log_2 n(O)$ 比 $\log_2 n(Y)$ 小约 0.66。 如果 $n$ 比 $m$ 大很多,就像在广泛的管道布局中一样,那么很可能是 $O = Y$ 所以 $n(O) = n(Y)$。


不太正式,窄流水线布局将 $n$ 小位值映射到附加 $n$ 位值。 如果此映射是完全任意的映射,则意味着某些值肯定不会出现在结果中,因为考虑到某些结果值会有多个输入值映射到它。

事实证明,结果值的数量是(在普通情况下)$2^n \cdot (1 - \frac{1}{e})$。 考虑到 ${1 - \frac{1}{e}} \approx 0.632$ 表明几乎 50% 的可能输出值实际上不会发生。 在你考虑之前,这听起来有点可怕。 如果你去掉了结果范围的一半,这表明你只有效地去掉了一位,并且假设你丢失的输出数组不到百分之五十,你有效地去掉了不到一位。 这是非常小的。

所以,这是一个有效的攻击,是的。 然而,这并不意味着它会引起所有的烦恼。

0
2022-06-07 14:58:29
资源