我们如何确定当我们的密码系统存在缺陷时，我们有足够的警告时间来更改它们吗？
我们如何确定ECC不会在一夜之间崩溃？
#1 楼
从信息论的角度来看，我们永远不会知道加密算法不会突然失败。如果我们知道这一点，我们将放弃使用它。但是，事实表明，当密码算法失败时，按照两步过程，它很容易失败：大多数密码算法在初始分析阶段都会很快失败。 ，因为我们将大量已知的破解密码的工具与专家意见一起应用到了问题上。
其余的算法已显示出通常会分阶段失败。攻击通常会在最终破坏算法之前削弱算法。通常以位为单位进行测量。如果蛮力攻击需要进行2 ^ 64次操作，并且有人发现需要进行2 ^ 58次操作的技术，那么我们说它已被6位削弱。
对于引用“过去的表现并不能预测未来的结果。”不能保证任何将来的算法都不会在任何未知的时间点中断。为了避免这种情况，大多数现代加密算法都是使用Feistel网络等众所周知的结构之一进行多轮设计的。我们通常了解如何使Feistel网络正常失效，而那些没有很好理解的机械原理经常被怀疑很多年了。结果，存在一种趋势（并非保证），可以将位的弱点作为合理的指标。
也许更好的问题是“如果当前的加密算法在一夜之间失败，那有多糟糕？ ？如果可以用美元来表示，那么至少可以尝试应用贝叶斯统计数据来针对这种可能性采取合理的防范措施。
#2 楼
我们不这样做。$ {} {} {} {} {} {} {} {} {} {} $
主持人注意：存在这个答案是出于历史意义，但是它不符合回答问题的准则，因此请不要将其用作可以在此处发布类似答案的证据。该答案及其评论已冻结，无法更改。更多信息：meta。
评论
$ \ begingroup $
较长的版本：安全是关于风险管理。 AES明天会被破解吗？几乎可以肯定不是。明年？可能不会。下个十年？可能不会。下个世纪？谁在乎？在使用AES的那一刻，与破解密码相比，您面临的风险要大得多。
$ \ endgroup $
–斯蒂芬·托瑟（Stephen Touset）
2015年6月4日，0：03
$ \ begingroup $
这个答案没有用。如果答案是全部，那么就没有理由认为我们的密码快速破解的可能性与密码逐渐破解的可能性没有任何区别。在这种情况下，就没有理由相信加密。可能是这种情况！但我希望看到一个争论。 （-1）
$ \ endgroup $
–ogogmad
2015年6月4日在11:45
$ \ begingroup $
实际上，此答案应为评论。
$ \ endgroup $
–ogogmad
2015年6月4日在11:46
$ \ begingroup $
您在评论中提出的问题与您提出的问题不同。我们不知道算法明天不会被破解，最好的办法就是采取步骤选择明天被破解的可能性很小的算法。这就缺少知道和确保算法不能被快速破坏的问题。
$ \ endgroup $
–杰拉德·戴维斯（Gerald Davis）
15年4月4日在16:42
$ \ begingroup $
我确实提供了对更有用的问题的通用答案，即“如何减少一夜之间破解算法的风险”，但老实说，最实际的答案就是上面的问题。 “知道”，“确定”，“证明”一词在密码学中往往具有字面意义。
$ \ endgroup $
–杰拉德·戴维斯（Gerald Davis）
2015年6月4日在16:52
#3 楼
yyyyyyy的答案是正确的简短版本。只有一种加密算法在数学上被证明是安全的：一次性填充。它几乎从未使用过，因为它不切实际：密钥大小与要保护的数据一样大。您可以证明，对任何具有无限计算能力的对手都是安全的算法，其本质上等同于一次性使用，因此在大多数情况下是不切实际的。
每个实用的密码算法都需要假设在实践中无法计算数学函数（因为对于实际使用的大小，最著名的方法需要数十亿台计算机才能工作数十亿年，甚至可能需要比宇宙中存在的能量还要多的能量）。我们认为，无法快速计算这些功能，因为许多非常聪明的人花了很多年的时间徒劳地尝试。从数学上讲，某天某人会找到一种更快的方法。我们认为这是不可能的，因为有这么多人失败了，但不能排除。
渐进的突破比突然的突破更有可能，因为科学的进步往往一次增加很小。科学家是站在巨人肩膀上的小矮人（正如牛顿著名的著作一样，他之前和之后的其他人也一样）。科学家的大众形象突然被开悟，并立即提出新颖实用的想法。要使想法成熟，需要花费时间（通常需要多个人）。在实际的密码基元破译之前，极不可能出现警告信号，例如相关主题的理论进展，对我们对基元数学结构的理解有所改进，从而导致较小但仍然不切实际的还原。打破它的计算要求等。
所有这些都适用于世界顶级密码学家审查过的算法。一个人或一个小团队独自提出的算法很可能会被彻底打破，因为其他人会想到自己没有想到的东西。当您让大量专家参与时，“没人想到这一点”的风险就会减少。
评论
$ \ begingroup $
也许有人会补充说，从信息理论的角度来看，一次性密码夹只是“完全安全的”-现代密码学知道更多的安全性定义，其中一些一次性密码夹完全被破坏了。
$ \ endgroup $
– yyyyyyy
2015年6月4日14:58
$ \ begingroup $
@fgrieu可以肯定地说，有一个单一的算法系列，一次填充和本质上等效的变体（关键点是至少与有效载荷一样多的关键材料，因此不切实际）？
$ \ endgroup $
–吉尔斯'所以-不再是邪恶的'
2015年6月5日，12：49
$ \ begingroup $
一个时间垫是唯一可证明的安全加密，但不是唯一可证明的安全加密算法。基于Wegman Carter构造的消息身份验证代码也被证明是安全的。而且它们也更实用，因为消耗的位数仅随消息大小成对数增长，而不是线性增长。其中一种算法提供机密性，另一种算法提供完整性，如果您既需要保密性又需要完整性，则需要将两者结合起来。
$ \ endgroup $
–卡巴斯德
2015年6月5日18:06
$ \ begingroup $
@yyyyyyy如果您在经过身份验证的加密模型下分析OTP，那么它显然会被破坏。但这是因为您使用了错误的模型来进行分析，因为OTP从未设计为提供身份验证。相反，如果您查看受Wegman Carter MAC保护的OTP，结果将有所不同。
$ \ endgroup $
–卡巴斯德
2015年6月5日18:12
$ \ begingroup $
@kasperd当然。我的评论的目的不是谴责一次性使用的方法，而是指出“已证明安全”一词是不完整的，因此有可能引起误解：它没有提及经过考虑的安全概念。
$ \ endgroup $
– yyyyyyy
2015年6月6日，11：40
#4 楼
简单的答案是没有人能证明算法在给定的时间内不会中断。可实现的目标是增加没有警告就不会进行有效攻击的可能性。有几个特征表明特定密码可能会保持安全，如果降级会“优雅地”这样做。1。时间。时间是算法强度的主要考验。全世界的研究人员都已经经历了十年打破SHA-2的努力，但迄今为止失败了，这是一个好兆头。这并不意味着SHA-2明天不会被破坏，但是与SHA-2是全新的相比，风险大大降低了。因此，在短期到中期，相对于SHA-3，我对SHA-2的安全性更有信心。有时候年龄越大越好。
2。用途广泛。时间给专家提供了攻击算法的机会，但这并不意味着如果十年没有人试图破坏xyz算法，那么十年来没有人破坏过xyz算法。打破主要算法（SHA-2，AES，ECC）的问题很大，这将引起更多关注，因为您的兄弟发明了某些算法。相应地，在常见的高使用率算法上会发生大量的密码分析。这就是为什么滚动自己的加密货币很危险的原因之一。确信它是安全的唯一方法是让大量可靠的专家在很长一段时间内尝试将其破坏。晦涩的算法根本不会发生这种情况。
3.钻头强度。 128位安全性（2 ^ 128个操作）在当今和可预见的未来都具有超出蛮力的所有实际目的。那么，如果128位已经“牢不可破”，为什么还要有更高位强度的算法呢？这是一项保险单。许多攻击降低了攻击的复杂性。因此，代替2 ^ 128个操作来查找冲突，它可能“仅”花费2 ^ 90或2 ^ 84。这些数量较大，但是只要有足够的时间，金钱和更高的效率（摩尔定律），这是可行的。另一方面，无法使用将冲突的复杂性从2 ^ 256个操作降低到偶数2 ^ 160的中断。人们应该远离算法，因为这样会增加风险，即更复杂的攻击会进一步降低这种风险，但不会带来0天的风险。这不是绝对的保证。中断可能非常严重，以至于削弱甚至更高的位强度实现，但又与其他原本不可能实现的原理相结合。
4。开放的透明加密算法/系统毋庸置疑，您不应该将您的秘密信任不能被独立验证的封闭源系统，但是这种情况比您想像的更多。例如，整个驱动器硬盘加密是一个“神奇的黑匣子”。最佳情况下，您需要独立验证散列或密文的生成方式。加密算法是确定性的，因此，如果设备或软件声称正在使用AES-256，则在给定相同的输入（明文，密钥，IV）的情况下，它应产生与另一个已知的AES-256实现相同的输出。如果没有，那么其中之一就没有实现AES-256。
5.我什么都没有。大多数密码系统需要某种形式的常数。选择所选的常数总是有风险的，因为它们以作者而非其他人已知的方式降低了系统的有效性。 “随机”常量是一个危险信号，因为随机值不可证明。如果算法将e971c59327cabde08439c813b70dae1a用作常量，并且作者说不起作用，则该算法是在CSPRNG上生成的，则应引起警告。如何验证e971c59327cabde08439c813b70dae1a是随机掷骰的结果，并且没有故意选择，因为它削弱了算法。我的袖子数通常都不会用作引入伪随机常数的方法。例如，使用前n个质数的平方根小数部分的前32位。可以选择这样的数字并满足削弱算法的条件的风险很小。
结合这些因素，可以大大降低算法在无预警的情况下崩溃的可能性，但我们无法证明密码系统今天是安全的，或者明天将保持安全。
安全的哈希算法
有“证明是安全的”哈希算法。大多数散列算法使用混合，旋转和归约函数的轮次，并且假定没有比“蛮力”更快的算法来“破坏”它们，但是问题是，对于所有这些算法，都无法证明没有更快的算法存在寻找碰撞。可能安全的哈希算法基于已知困难问题（例如整数分解）的数学证明。 “可证明”来自以下事实：可以在数学证明中证明，只要不知道基础数学问题的更快解决方案，在最坏的情况下，碰撞（或其他攻击）将需要进行给定数量的操作。 。如果该假设被证明是错误的，那么所陈述的安全性也是如此，但由于许多数学问题已被很好地理解，因此它确实提供了更牢固的理论基础。
可证明的安全哈希算法的问题在于它们通常趋向于与传统的哈希算法相比，在给定的安全级别上需要更长的时间并需要更多的资源。 SWIFFT是一种可证明安全的哈希算法的示例。它并不适合所有情况，因此这并不表示该算法可用于任何特定用途。鉴于缺乏广泛的使用，它至少会违反上述因素之一，因此出于完整性考虑，我将其包括在内。
评论
这是一个警钟，这就是SHA3竞争存在的原因，尽管众所周知SHA2没什么错，只是它的结构与SHA-1类似，而结构与SHA-1类似，与MD5类似。实际上，这种情况在密码竞赛中一直存在。有些立即落下，但是没人在使用它们，所以谁在乎。其他人表现出虚弱，但没有完全休息。所以我们也把那些扔掉。数字没有显示任何弱点，因此我们选择一个。然后我们再等几年。最终我们开始使用它。
你不能确定。您不能确定它们中的任何一个是安全的，也不能确定会提前发出中断警告。请参阅对称密码和摘要算法的安全性声明背后的数学模型是什么？以及如何证明PRNG的安全性？更多。
您可能需要阅读Katz＆Lindell撰写的《现代密码学简介》，他们将第1.4章专门介绍了密码学中假设的作用。它的本质：我们不能无条件地证明大多数密码结构，因为我们对此只有数学上的假设。 （例如：我们不能确定没有用于分解O（n）的算法）
相关问题：security.stackexchange.com/q/68377/47143