对称密码和摘要算法的安全声明背后的数学模型是什么?

信息安全 密码学 加密 哈希 密码分析
2021-08-14 18:54:28

为什么 SHA-1 可以被认为是一种安全的散列函数?这是我仍然想知道的事情。

我理解为什么现代非对称算法被认为是安全的概念。它们建立在可证明“难以”解决的可靠数学问题之上,例如有限域中的离散对数或整数分解。如果了解数学概念,则安全声明和证明的概念相对容易理解。

但是当涉及到对称加密和安全散列函数时,情况就变得不那么清晰了。我知道对于分组密码和摘要算法存在很多结果和分析,但是这些结果是基于什么?

例如,当涉及到分组密码时,您可以找到很多证明密码算法 X 可以抵抗一定数量的已知攻击的证据。或者他们证明某些属性成立,例如输入的每一位都会影响输出,因为这被认为是必要的等等。

从外部看,密码和摘要算法的构造看起来像是通过应用位移、XOR 等“尽可能地摆弄和弄乱输入”。

我现在想知道的(我将不胜感激对两者都有更深入的了解):

a) 您能否向我提供一些资源(首选书籍)的指针,这些资源解释了构建一个必须考虑的设计和安全性考虑因素

a1) 密码算法

a2) 摘要算法

这可以解释的东西,如为什么的S-box必须看起来完全相同的方式它,而不是任何其他方式,可能更重要的是对我和我的理解,为什么它是否构建了不同这将是坏?

b)是否存在或正在尝试对这些“位摆弄操作”进行数学建模(例如,“代数攻击”是否基于这样的模型?)?

c) 你如何“衡量”一个摘要算法的质量,比如 SHA-1?即,你怎么能说在这里进行两位移位而不是三位或异或移位更好,为什么这些操作首先是 SHA-1 的基础?因为当时它似乎是唯一已知的会“最大程度地混淆”输入的东西?我之所以问,是因为似乎大多数 SHA-3 候选者要么基于密码算法(因为有更多的理论结果),要么基于诸如海绵函数之类的新概念。对我来说,任何 SHA 算法(MD5 也是)的定义仍然看起来像“让我们搞砸这个,好吗?” - 但它背后的原因是什么?为什么要像他们那样做?

如果您能让我深入了解这些主题中的任何一个,我将非常高兴。

3个回答

我不能给你一个让你完全满意的答案,因为没有这样的答案。我们怎么知道我们的算法是安全的?严格来说,我们没有。我们没有证据证明 SHA256、AES 或 RSA 是安全的——人们普遍认为它们是安全的,但我无法给你这个事实的数学证明,谁知道呢,普遍的信念总是有可能的错误的。

我们对这些算法的安全性的信念来自这样一个事实,即许多非常聪明、知识渊博的人已经非常努力地尝试破解这些算法,而根本没有造成太大的影响。当然,这并不能保证不存在聪明的攻击——总有可能存在一些没有人聪明到足以发现的令人难以置信的偷偷摸摸的数学捷径攻击,但是尝试找到它但失败的人越多,看起来不太可能。出于实际目的,普通攻击者似乎不太可能发现数十名非常聪明的人试图发现但失败的攻击。

你的第一反应可能是,到底是什么?为什么那些密码学家如此蹩脚?为什么他们不能证明他们的任何算法是安全的?他们是麻木吗?答案是,有一些根本原因使得很难证明加密算法或哈希函数是安全的(特殊情况除外)。粗略地说,证明像 AES 或 RSA 或 SHA256 这样的算法是安全的似乎至少与证明P != NP(计算机科学中一个臭名昭著的难题)一样难。我们很少有工具可以证明算法任务无法有效完成。从本质上讲,这就是难以证明SAT不能在多项式时间内求解(即难以证明P != NP),并且难以证明对 AES 没有捷径攻击(即 AES 不能被破坏)。所以不仅仅是密码学家是跛脚的,而是我们面临着非常困难的问题,没有人知道如何取得进展。

请注意,我上面所说的一切都不是针对散列函数或对称密钥加密的。它适用于所有计算安全的密码学,包括对称密钥加密、公钥加密、数字签名、散列函数以及我们认为理所当然的许多其他标准原语。

你的最后一个问题是:谁能教我对称密钥算法如何被分析和密码分析的理论?密码学家如何分析它们?攻击如何运作?不,我不能在这里的时间和空间限制内教你这个。围绕这些问题建立了一个完整的研究领域,其中包含关于对称密钥算法分析技术的知识渊博的文献。(例如,参见FSECRYPTOEUROCRYPT会议。)学习这些材料需要多年的专门研究。不幸的是,我无法在此处的可用空间中教给您所有这些内容。非常简短的版本是:密码学家已经开发了一套大型攻击技术,作为起点,首先分析任何新的原语,看看这些攻击中的任何一个是否会起作用。如果原语抵抗所有已知的攻击技术,那么密码学家会花时间尝试设计针对原语的临时或自定义攻击。密码学家还研究原语的人为弱化版本(例如,使用更少的轮次),以了解对那些弱化版本的最佳攻击,以试图推断出完整的东西。如果经过许多人年的努力,没有人成功地攻击该计划,那么人们开始获得更多的信心。最近,

但归根结底,它既是一门科学,也是一门艺术。审查一个新的原始人是极其昂贵的:它需要天赋异禀的专家们数十年的努力。出于这个原因,密码学的聪明用户通常会尝试使用现有的、经过审查的原语,而不是发明自己的原语。如果您发明了自己的方案,那么您极不可能像标准方案那样安排对您自己的方案进行的分析和审查——所以不要那样做。不要“自己动手”。相反,建立在现有的、标准的、公认的原语上,如 AES、SHA256、RSA 等。

@DW 说得好;简而言之:认为密码算法的唯一已知方法是让数百名密码学家对其进行几年的研究。从智力上讲,这最终不能令人满意,但人们仍然可以使用它(例如,整个医学是建立在更不稳定的基础上的,但它仍然是一门非常有用的艺术)。

对于细节(即如何选择 S-box,什么是“雪崩效应”,如何用代数研究事物......),请参阅(一如既往)应用密码学手册,它开始有点旧但还是一个很好的参考,可以免费下载。另一本好书是Antoine Joux的算法密码分析。

我的一个问题仍然没有解决。我仍然不知道为什么首先将 XOR、位移等用于哈希和密码 - 如果这背后有任何数学推理,为什么正是这些操作而不是别的?

使用 XOR 的原因之一是因为 XOR 有一个重要的属性:可逆性。如果你用一个键对一个数字进行异或,然后再用同一个键对结果进行异或,你将得到你的原始数字。