NSA或GCHQ等密码破解机构在过去40年来一直进行一流的未公开密码学研究，我们如何才能推断出对称密码密码分析能力呢？ br />
鉴于这些机构可能拥有与差分密码分析同等实用性的未公开且未知的密码分析技术，我们可以针对这些密码建立什么样的计算下界（我们只知道差分密码分析，因为有人NSA / IBM重新发现了它）？例如，我们是否可以在不了解差分密码分析的情况下为在md5中发现冲突的难易程度制定一个好的下限？
这个问题仅限于对称密码。
#1 楼
应用密码学是一本正在变得不那么流行的书。国家安全局有很多预算，但没有无限的预算，还有其他组织，特别是大型私营公司，也有令人印象深刻的手段。例如，谷歌或苹果公司是在密码学领域从事研发活动的公司，它们有可能在给定的问题上投入10亿美元（而且与联邦机构相比，他们这样做可能更容易管理，更灵活） 。此外，公共密码学研究领域也发生了一些变化。在1980年代初期，有两次专门讨论密码学的会议。在2011年，有一百多个！该领域已经简单地扩展，膨胀，以至于没有任何一个组织，甚至是NSA，Microsoft或Apple，都无法声称使用了不可忽略的一部分可用脑资源。这是最近发生的变化：从我个人的经验来看，通货膨胀确实从1995年左右开始真正地开始。他们不告诉自己雇用的人以及从事的工作。但是我们可以估算出国家安全局发现先进的密码分析技术而逃避了公共学者的掌握的可能性。正如莱布尼兹（Leibniz）所说，发现是“四处游走”的思想的产物，而真正做出发现的人是一个随机选择。换句话说，如果国家安全局雇用了1％的顶级密码学家，那么他们将获得1％的预付款。即使存在诸如科学资本之类的东西（当科学家与许多其他科学家一起在实验室工作时，科学家的工作效率会大大提高，并且在相同主题上有很强的本地传统），但美国国家安全局仍然遥不可及其他人。
另一点是关于激励措施。 NSA是一个预算陷阱，但是它有目标：即保护美国不受敌人（世界其他地方）的侵害。当国家安全局说算法很好（例如AES）时，其他美国组织（公共和私有）都开始使用它。可以肯定的是，NSA希望能够打破广泛使用的加密系统；但是，（对于我而言）这对他们来说是NSA的一个更为重要的目标，他们希望美国组织使用的加密技术不会被敌人破坏。因此，对于NSA来说，推广一种只有当他们有充分的理由相信只有他们才能破解它时才可以破解的算法才有意义。与所有机密服务一样，国家安全局（NSA）知道什么是机密：他们保留自己的秘密，但他们还假设自己并不完全了解竞争对手的秘密。相应地，我再次发现NSA知道如何破解AES是不切实际的，因为他们一直挥之不去地将其称为“解决方案”，并且丝毫没有计划定义另一种对称加密标准的计划，即使只是作为一个标准。备份。
所以这就是我对秘密组织的未知能力进行推理的原因：我查看了他们的资源，并将他们的可观察到的行动与他们的目标相匹配。这得出以下结论：如果NSA可以打破AES，那么他们要么可以使用某些非地球的技术和科学（电影中的流行主题，例如《黑衣人》），要么他们不是真的在试图保护这种技术。他们应该保护的组织。或两者兼有。
在纯科学的层面上，我们没有证据证明对称基元确实存在（特别是哈希函数；但是我们也不知道是否有可能以图灵所说的方式使用带有内部密码的对称密码。内存表示短于$ \ log n！$位：表示$ n $位上随机选择的排列所需的位量）。现在我们有了候选者：定义的分组密码，我们不知道如何破解。而不是我们知道无法破解的分组密码。因此，没有真正的“下界”可与未知的密码分析技术相抵触。
评论
$ \ begingroup $
您的评论似乎无视ECHELON，美国与英国，澳大利亚，新西兰和加拿大合作监视电话（和其他）通信。 ECHELON牵涉到许多政府级别的工业间谍活动。尽管他们本国的工业隐私受到了威胁，但美国还是高兴地加入了ECHELON。
$ \ endgroup $
– DanBeale
2011年9月2日在18:57
$ \ begingroup $
强大的加密符合所有人的利益，包括NSA。强大的加密==安全的商业。如果政府需要访问某些东西，则有很多途径来获取密钥，包括因未交出密钥而对您进行监禁。
$ \ endgroup $
–duffbeer703
2011年9月5日20:00
$ \ begingroup $
他们总是可以求助于“ Jack Bauer边道攻击”，这涉及到他们在您的膝盖上钻孔，直到您揭示关键。数十亿美元的超级计算机或带有$ 50锤钻的特工...嘿，我想您可以为人权付出代价！
$ \ endgroup $
–多项式
2011年11月23日14:12
$ \ begingroup $
还有一种可能是，这种攻击非常困难，这种攻击只能在民族国家中使用，民族国家通常不会“出示证件”来从事诸如工业间谍活动。
$ \ endgroup $
–Hulkingtickets
13年7月10日在19:27
#2 楼
分组密码中的大多数漏洞都与密钥安全性有关。除了密钥大小小于256位或更少的加密轮次以外，针对任何事物的成功攻击都是不可行的。圣杯是关键管理。对AES的横向攻击依赖于管理不善或实现上的错误（弱PRNGS，定时攻击，位注入，选择性明文等）。打破较难的问题（AES），而是攻击较容易的问题（横向攻击）。阅读PRISM幻灯片时，该程序的成本太低，无法包括任何类型的计算密集型任务。推断PRISM是一项关键的共享工作，这还不是一个遥远的跨越。如果任何一个命题都是正确的，那么任何认真的密码学家都需要使用每个组件都已知的系统，并且不包括封闭源代码操作系统和软件黑匣子。 NSA拥有比AES还要强的蛮力向量的可行性。布鲁斯·施耐尔（Bruce Schneier）可以访问斯诺登的文档，并说数学是正确的，但该软件存在缺陷，这就是国家安全局解密分叉数据流的方式。评论
$ \ begingroup $
在标准级别上破坏安全性意味着使用开放的已知协议和组件可能是不安全的
$ \ endgroup $
– Richie车架
2013年9月7日上午9:40
#3 楼
在对这些密码的攻击上，我们可以建立什么样的计算下界[...]
目前我们无法证明这样的结果，理论上证明了强大的下界破解候选密码基元所需的资源量意味着将$ \ mathsf {P} $与$ \ mathsf {NP} $（百万美元问题）分开，这与我们今天所知道的这两个相等是一致的，我们也许生活在称为Algorithmica，Heuristica或Pessiland的世界之一（在Impagliazzo的五个世界中）。
#4 楼
本周的启示使这个问题（及其答案）焕然一新。施耐尔社论非常好：
http://www.theguardian.com/ world / 2013 / sep / 05 / nsa-如何保持安全监视
纽约时报（NYT）有一个图形，总结了迄今为止显示的NSA功能： //www.nytimes.com/interactive/2013/09/05/us/unlocking-private-communications.html?ref=us&_r=0
VPN，SSH，SSL，“加密聊天”（阅读说明；听起来像OTR）。协议缺陷？实施缺陷？密码中断？所有这些？谁知道。
我的宠物猜测实际上涵盖了整个图形，是他们对椭圆曲线上的离散对数感兴趣。或者至少是NIST说服所有人使用的曲线。 “？”，至少对于某些特定的曲线参数而言，这是通常未知的。比众所周知的。 （我承认，这甚至更具投机性。）因此，我将停止以明文形式发送IV。我将为每个会话协商两个密钥：一个用于保护IV，另一个用于保护数据流。
但是我首先要担心密钥交换，因为到目前为止的泄漏听起来是弱点。
评论
$ \ begingroup $
关注NIST曲线的人应改用Shamus标准曲线，或自行生成。如果存在IV问题，那么协商2个密钥不是答案，而是使用不同的操作模式或使用随机预填充板用主密钥对IV进行加密。
$ \ endgroup $
– Richie车架
2013年9月7日上午9:48
$ \ begingroup $
鉴于NSA枚举了不同的系统，VPN，SSHm.m。人们可以推测他们发现的东西是那些系统特有的。毕竟，如果他们坏了，例如RSA，基于此的系统不安全性随之而来。另外，这些系统中的许多系统可以使用不同的基础密码，因此仅写“ VPN”就没有意义，如果您破坏了RSA，则必须写“ VPN with RSA”。
$ \ endgroup $
–财产
2013年9月7日上午10:30
$ \ begingroup $
在CBC模式下（这仍然很常见），IV仅“保护”您的第一个纯文本块。以加密方式传输并没有太大帮助。
$ \ endgroup $
–PaŭloEbermann
2013年9月7日15:35
$ \ begingroup $
@PaŭloEbermann：显然，我的假设暗示“避免CBC模式”。我说的是CTR，GCM，OCB等。
$ \ endgroup $
– Nemo
2013年9月7日在16:39
$ \ begingroup $
@Morty：该图形是NYT的，而不是NSA的。到目前为止已发布的实际文档（尽管已编辑）强烈建议对TLS进行实用的密码分析攻击（如果没有其他措施）。这意味着以下一项或多项：协议，RC4、3DES，AES，RSA，DH或ECDH。我会将钱投入ECDH（具有NIST曲线）。整数和有限域已被详尽地公开研究了几个世纪。椭圆曲线仅使用了几十年，密码学家对此的关注度最高。另外，NSA一直在大力推动ECC。
$ \ endgroup $
– Nemo
2013年9月7日在16:52
#5 楼
要证明对密码攻击（对称或非对称）的下限非常困难。众所周知，正如其他人提到的，该问题与P！= NP的问题纠缠在一起。但这实际上比这还要困难！因为P！= NP问题谈论的是最坏情况下的复杂性，而这并不是您真正感兴趣的。因此，即使您设法证明给定的系统都是NP难以破解的（例如RSA，ECC等，实际上大多数情况下都不认为是这种情况），并且P！= NP，您只会知道在最坏的情况下打破它需要花费指数时间（例如一些键），但可能几乎所有情况都可以很快解决！因此，您需要一个更强大的结果，例如，关于平均复杂度的结果，但即使这样可能也不足以确保系统合理地安全。当然，理想情况下，您希望的是最低限度的最佳情况复杂度，但这很难形式化和推理，因为对于任何密码系统而言，“某些”算法总是会出现“简单”情况。例如，您可以想象一个算法具有一个内置的查找表，该查找表将首先尝试10000个硬编码键，因此它可以快速破解这些键，因此对于该算法而言，这是最好的情况。而且由于下限结果必须适用于所有算法，因此可以证明，任何密码系统唯一可以证明的最佳情况下限是O（1）（或O（n），允许程序实际写下来键）！在对称密码中也可以看到形式化复杂性的困难。这里的密钥大小通常是固定的，这意味着不适用用于推理复杂性的常规框架，因为在这些框架中，您正在研究问题大小达到无穷大时复杂性如何增长。如果只有有限数量的实例（固定密钥大小的对称系统就是这种情况），那么对于任何给定的“破解”算法，都有一个固定值M，即该算法所需的最大操作数，即使对于最坏的情况下。因此，该算法的时间复杂度变为O（1）（以M量级为常数）。以某种方式消除了不能真正解决问题但使用查找表作弊的算法，也许是通过在分析中包括程序大小，并允许少量情况与算法“成比例”，这与算法的大小成比例算法等。但这似乎要困难得多，而且与现在的方法大不相同。
评论
$ \ begingroup $
您的答案很好地阐述了复杂性理论在密码学中的适用性，但并不能真正回答问题。
$ \ endgroup $
–PaŭloEbermann
2013年9月7日15:12
#6 楼
推理任何实体（国家级代理机构，大公司，其他非国家行为体）的密码能力的方法是避免猜测和寻找证据，其中有很多： br />泄露了有关密码原语，方法等的文档，
特别是已被严格掌握的信息
前内部人士的证词
无意披露
他们通常会采取什么措施来保护彼此之间的信息互不相干
他们如何为自己使用加密技术：关键时间表，哈希，密码，盐等。
他们应该避免什么
关于颠倒密码和伪随机数生成器等的事实；有关后门的事实，设计上的其他漏洞以及涉及可疑密码，哈希等的标准化推动。
其他所有内容都应放在括号内，我们决不能成为确认偏见的受害者。
评论
我认为这是一个有趣的问题，美国政府以外的每个密码学用户都必须问一个问题。虽然像NSA这样的组织确实提供了很少的有关其功能的信息（而且问题可能更笼统，并适用于所有此类组织），但信息量却非零。即使在没有信息的情况下，这个问题也会演变为另一个有趣且重要的问题：为什么我们应该对算法X原则上的安全性充满信心？Applied Crypto即将投入使用。我很想看到社区对于NSA在该领域当前实力的共识。这不是客观的，但是社区共识本身是有价值的。感知是现实和一切。 :-)
是的，这是一个好问题。每个人都应该有这个问题。没有人能很好回答的事实是一个重要事实，因此最好在此站点上发布问题。围绕着许多最重要的问题并没有真正的答案。不确定性和无知是我们必须面对并决定如何管理的原因。
@gokoon-我的修改是否符合您希望对此问题提出的要求？
不要过多地关注特定的组织，例如美国国家安全局（NSA）。也许您认为NSA是好人，不会做任何坏事（即使他们有这种能力），或者您至少认为他们在您身边，不会对您做任何坏事。但是，我们是否有理由相信中国或俄罗斯的分类密码学研究不及美国或英国先进？另外，某些用户（例如欧洲人）可能会对NSA在其通讯中拥有这种权力的可能性感到不适。