经常有人告诉我,任何密钥都可以被破解,而任何密钥的破解只是时间和资源的问题。我知道这在技术上是正确的。但是,我认为在某种意义上说密钥是不可破解的(例如,如果密钥要花费世界GDP的100倍来破解,那么在没有先进的外来文明的帮助下,它实质上是不可破解的,等。)

一年之内使用AES或Twofish等强大算法对256位密钥进行强行暴力破解要花费多少美元?

我我也很想知道一年内破解128位密钥的成本。

我主要是出于好奇而问这个问题。我对密码学不是很了解,所以如果需要的话,请随时选择您选择的算法。我对如何估算成本很感兴趣(假设您必须购买硬件,但可以选择要购买的硬件)。

评论

据xkcd称,硬件价格为5美元。

您问的是错误的问题;您可以使用批量攻击来同时攻击很多密钥

@HendrikBrummermann我从不喜欢那部漫画。它忽略了以下事实:操作按键的人员甚至不知道很大一部分按键。

@HendrikBrummermann XKCD在最常见的情况下不起作用:用户丢失了密码,并拼命试图再次访问自己的数据。

#1 楼

在美国,平均电费为每千瓦时0.12美元。对于单个服务器,我每年将使用3741 kWh作为估算值​​。一台机器每年大约$ \ $ 450 $。

假设您每秒可以执行$ 10 ^ {14} $解密。一台机器每年解密的费用为3.15美元乘以10 ^ {21} $。您一年平均需要进行$ 2 ^ {255} $次解密,因此您需要$ \ frac {2 ^ {255}} {3.15 \ times 10 ^ {21}} \ approx 1.84 \ times 10 ^ {55} $台机器。要计算出您的成本,您可以将其乘以$ \ $ 450 $并得到大约$ \ $ 8 \乘以10 ^ {57} $或8十亿美元。全球生产总值(GWP)约为$ 63 \乘以10 ^ {12} $,因此,强行强制使用256位密钥将花费$ 10 ^ {44} $乘以GWP。

您可以遵循类似的数学方法来获得强行强制使用128位密钥的成本。


注意:

我完全忽略了硬件成本,维护等。上面的估算仅用于电力。我们可以从国家安全局那里得到一些提示。雇用几千名数学家,让他们致力于打破密码,而不是尝试强行破解,会变得更好。

评论


$ \ begingroup $
因此,我制作了一个包含各种费用的电子表格。破解102位密钥需要1万亿美元,而破解73位密钥只需1000美元。我找不到您的解密来源。这是工作表:docs.google.com/spreadsheet/…
$ \ endgroup $
– Chloe
13年8月27日在18:50



$ \ begingroup $
或者,您可以雇用几千个饼干,对他们进行刑事赔偿,并让他们致力于建立对已经具有密钥的端点节点的访问。
$ \ endgroup $
–用户
16/12/26在18:58

$ \ begingroup $
尝试购买大量必要的设备(或最终用于制造该设备的材料和能源)会扭曲这些项目的世界市场,因此理论上价格会比此计算结果高得多。实际上,由于根本没有必要的材料/能量供人类使用(物理学定律排除了在那个时间范围内将必要的物质/能量运输到地球),价格(根据供求关系)将不得不上升到买家买不起的地步。但是,然后您必须考虑对货币价值的影响。
$ \ endgroup $
– John B. Lambe
18年8月27日在21:50

#2 楼

有一些热力学限制。 Bruce Schneier在《应用密码学》中对热力学局限性作了很好的解释:


热力学第二定律的后果之一是,一定量的能量对于代表信息。要
通过更改系统状态来记录单个位,需要的能量不少于$ kT $,其中$ T $是系统的绝对温度
,$ k $是玻尔兹曼常数。 (与我保持一致;
物理课程几乎结束了。)

鉴于$ k = 1.38 \ cdot 10 ^ {-16} \ mathrm {erg} / {^ \ circ} \ mathrm {Kelvin} $,
,宇宙的环境温度为$ 3.2 {^ \ circ} \ mathrm K $,这是理想的运行在$ 3.2 {^ \ circ} \ mathrm K $的计算机
每次设置或清除一点,都会消耗$ 4.4 \ cdot 10 ^ {-16} $ ergs。要运行比宇宙背景辐射还冷的计算机,需要额外的能量来运行热泵。

现在,我们太阳的年能量输出约为$ 1.21 \ cdot 10 ^ {41} $ ergs。这
足以在我们理想的计算机上提供约$ 2.7 \ cdot 10 ^ {56} $的单个更改;进行足够的状态更改,以通过其所有值放入一个187位计数器。如果我们在太阳周围建立一个戴森球,并在32年内捕获了所有能量而没有任何损失,我们就可以为一台计算机供电,使它的计数达到2美元{{192} 。当然,使用此计数器进行任何有用的计算都不会剩下能量。

但这只是一颗星星,而其中只有一颗。典型的超新星会释放出$ 10 ^ {51} $
ergs之类的东西。 (以中微子的形式释放的能量大约是一百倍,但现在让它们放开。)如果所有这些能量都可以引导到单个计算狂欢中,则为219 -bit
计数器可以循环通过其所有状态。

这些数字
与设备的技术无关。它们是热力学允许的最大值。并且它们强烈暗示
对256位密钥的强行攻击将是不可行的,除非
用物质以外的东西建造计算机并占用空间以外的东西。 br />

评论


$ \ begingroup $
我非常喜欢“物质以外的东西”和“空间以外的东西”的绝对含糊,具体的混淆,确切的存在主义。
$ \ endgroup $
–帕特里克M
15年6月22日在22:55

$ \ begingroup $
Kelvin不使用度数。这是绝对单位。
$ \ endgroup $
– Alex
2015年11月30日15:41

$ \ begingroup $
这是一本书的引文,因此,即使有错误,也应保持原样。因为开尔文(Kelvin)不应该使用度数符号进行编辑是无关紧要的,并且不会提高答案的质量。另外,当您编辑报价时,应在[方括号]之间进行编辑:english.stackexchange.com/questions/2271
$ \ endgroup $
– Biv
16/12/20在14:56

$ \ begingroup $
@MikeOunsworth第157-8页(摘自:schneier.com/blog/archives/2009/09/the_doghouse_cr.html)
$ \ endgroup $
– A. Hersean
17年8月30日在12:54

$ \ begingroup $
我喜欢这个报价,但天哪,每度erg开尔文是一个令人发指的单位。
$ \ endgroup $
–丹克鲁姆
17年9月1日15:33

#3 楼

通过穷举搜索进行256位密钥破解完全是人类所无法企及的。甚至设想一个128位密钥破解都需要花费大量的精打细算:


尝试一个密钥必须减少到单个逻辑门的翻转(相比之下,数百个实际需要的成千上万个);
该门必须比目前生产中最高效的逻辑门更具能源效率;
地球上所有的能源生产都必须转移到单个关键的破解目标。

在这些条件下(每种情况以其自己的方式是完全不现实的),可以想象出128位的密钥破解工作。 “美元”的概念有意义的地方。美元是一种货币:一种“价值”的常规表示方式,人们在假设他们可以根据需要将其转换回有形物体或服务时相互给予。因此,当总和远远超过地球上可以购买的总价值时,就没有美元的可能。截至2011年,世界生产总值介于60到80万亿美元之间:这很大程度上取决于您以什么美元为基础,以及如何将其映射为“购买力”。关键是,除了约$ 8 * 10 ^ {13} $之外,没有有意义的美元概念。

如果遵循@mikeazo参数(每台机器每年的能耗为450 \ $,其中一台机器每年可以尝试使用$ 3.2 * 10 ^ {21} $个密钥),则GWD(完全转换为能源)将允许尝试使用$ 2.5 * 10 ^ {35} $个密钥,即118位左右的空间。一个128位的密钥空间要比它大1024倍。此外,这还假定地球上产生的所有物质都可以以与最具竞争力的燃煤电厂相同的效率还原为能量,这有点乐观,因为GWD包含许多不可转换的东西,例如艺术创作:如何确切地说,你会用一首歌来发电吗?此外,计算中投入的所有能量最终都变成了热量,因此可能会产生一些气候后果,例如“地球已经煮熟”。


总结:即使您使用了世界上所有的美元(包括不存在的美元,例如累积的债务)并在整个过程中进行了油炸,您几乎无法对128位密钥进行详尽的密钥搜索的1/1000。所以这不会发生。 256位密钥搜索比128位密钥搜索困难约3,400千亿亿亿倍,所以甚至不用考虑。

评论


$ \ begingroup $
如果已经不可能破解128位密钥,那么为什么我们有256位密钥呢?
$ \ endgroup $
– Joren
2011年11月9日下午4:42

$ \ begingroup $
@Joren好问题! :)某些攻击会以一定的复杂度危害一定数量的AES攻击。例如,2009年Biryukov等人发动的袭击。等折中9轮AES,复杂度为2 ^ 39(而蛮力为2 ^ 256)。可以说,使用256位密钥而不是128位密钥是将回合数从10增加到14的最简单方法,即无需更改AES规范。顺便提一句,布鲁斯·施耐尔(Bruce Schneier)先前曾评论说,如果AES破损得太厉害,我们只需要增加回合数即可解决它。
$ \ endgroup $
– Stefano Palazzo
2011年11月9日5:25



$ \ begingroup $
@Joren:从历史上看,AES具有128位,192位和256位密钥,因为一些不灵活的美国军事法规要求使用三个不同的“安全级别”(在“真正安全”的密码系统一定很慢的前提下-在1930年代确实如此,但现在不再如此。三个密钥大小足以满足这些规定。但是没有人说下级一定要弱!如今,通过谈论量子计算机来合理化256位密钥的大小,但这是事后的想法。
$ \ endgroup $
–托马斯·波宁(Thomas Pornin)
2011年11月9日,12:03

$ \ begingroup $
@Joren“如果能够可靠地运行适当大小的能够运行Grover算法的量子计算机,它将把128位密钥降低到64位安全性,大约相当于DES。这是AES的原因之一。支持256位密钥长度。”
$ \ endgroup $
–丹尼尔
17年6月21日在14:05

#4 楼

非技术性暴力破解方法:我能想到的最具成本效益的“暴力破解”方法是雇用一帮黑帮,迫使知道密码的人放弃它。对于一个没有安全保障的人来说,一个好的流氓可能要花费约5,000美元,而您至少需要3个。如果您要寻找一个高调的家伙,那么一个好的流氓可能要花费约50,000美元,而您将需要其中的25个。因此,您正在寻找使用此方法的从15,000美元到125万美元的范围。

使用量子计算机的技术蛮力方法:

如果要走技术路线,首先需要确保可以仅在资源上检查密钥。对他人系统的任何依赖都会成为限制因素,因为在不使系统过载的情况下尝试多种组合是不可能的。

一旦您弄清楚了如何检查系统上的密钥,我建议与其他计算机并行使用量子计算机。当前,最大的量子计算机为14量子位。这种计算机理论上可以在一个操作中尝试14位的所有组合。因此,如果将其与普通计算机并行放置,则前14位可以视为一个位。这意味着您可以破解密码,就好像它是115位或243位而不是128位或256位,这是一个巨大的收益(便宜8,192倍)。

14比特计算机的成本对您的总成本而言微不足道,即使是10亿美元。因此,使用mikeazo的公式,这意味着您可以使用$ \ frac {2 ^ {242}} {7 * 10 ^ {18}} \ approx \ $ 10 ^ {54} $美元和128位破解256位代码$ \ frac {2 ^ {114}} {7 * 10 ^ {18}} \ approx \ $ 3 * 10 ^ {15} $ = \ $ 3万亿美元的代码。

总之,随着并行量子计算机中每个量子位的增加,上述价格将下降约一半,直到接近量子计算机价格成为限制因素的地步。因此,深入研究量子计算机研究人员,我们有一个要破解的代码!

评论


$ \ begingroup $
非技术方法通常称为橡胶软管密码分析,而不是蛮力分析。还应注意,就我们目前所知,量子计算机只会将对称密码(例如AES)的密钥空间减半。参见en.wikipedia.org/wiki/Quantum_computer#Potential因此,量子世界中的AES-256将等于经典世界中的AES-128。但是,该结果可以得到改善。
$ \ endgroup $
–mikeazo
2011年11月8日17:45

$ \ begingroup $
@mikeazo:黑帮很野蛮,所以“蛮横”的力量...哦,太好笑了;)对于我的真实答案,我假设有一种方法可以测试一组量子位的组合是否存在,其余位的确定组合是一种解决方案。如果该假设为假,最坏的情况是,由于256位量子计算机能够将密钥复杂度降低128位,因此可以安全地假定14位量子计算机将能够将密钥复杂度降低至少7位。位,仍然是$ 2 ^ 7 = 128 $乘以资源的收益。
$ \ endgroup $
– Briguy37
2011年11月8日19:27



$ \ begingroup $
关于具有14个量子位的量子计算机能够“在一次操作中尝试14位的所有组合”的说法是不正确的。这是一个非常诱人的假设(将量子计算机视为无数的计算机都通过量子魔术并行运行),但这是错误的-否则,具有256量子位的QC可能会在时间1中破坏256位密钥。QC确实(从理论上)提供了穷举搜索的性能提升,但并没有达到这一点:它可以将大小为$ N $的空间减小为$ \ sqrt {N} $(因此,使用QC进行256位密钥搜索应该是和128位“常规”键搜索一样困难)。
$ \ endgroup $
–托马斯·波宁(Thomas Pornin)
11年8月8日在19:36

$ \ begingroup $
@Thomas Pornin:我不知道您如何具体说出我的假设是错误的。例如,您是否可以证明不可能创建布尔量子函数来检查组合量子位中的任何答案是否为有效键?此函数将使我们可以将一位固定为0,而其余的都以qubit的形式提供给两种状态。如果结果量子函数为真,则我们固定的位为0,否则为1。因此,确定键的操作数将为键中的位数。
$ \ endgroup $
– Briguy37
2011年11月8日在21:03



$ \ begingroup $
@ Briguy37:我不能证明这一点,但是有些聪明的人可以证明。粗略地说,如果我们可以在量子计算机上以少于$ 2 ^ {n / 2} $次操作用$ n $位密钥来破解密码,那么我们可以在经典计算机上以少于$ 2 ^ n $次操作来破解电脑。这是非常技术性的问题,但是问题的一部分是,即使您有许多状态的叠加,要获得经典结果(确定的0或1)的“过滤”部分也会受到限制,并且无法“随意”完成”。
$ \ endgroup $
–托马斯·波宁(Thomas Pornin)
2011年11月8日在21:43

#5 楼

我认为没有人解决时间问题。根据Margolus-Levitin定理,每秒操作数的限制为每焦耳$ 6 \乘以10 ^ {33} $。太阳的能量输出约为$ 3.83 \ times10 ^ {26} $ J / sec。您将需要节省大约25年的太阳能量输出,才能在一年内执行$ 2 ^ {255} $运算(即使假设您每次解码只需要执行一次运算)。
另一个限制可能是普朗克时间单位,即$ 5.391 \ times10 ^ {-44} $秒。如果一台设备执行一次解密所需的时间为1普朗克时间,则一年中您需要大约$ 2 ^ {86} $台设备来执行$ 2 ^ {255} $个操作。由于地球的质量约为$ 2 ^ {92} $克,因此,如果您可以将每个设备的质量保持在2盎司以下,那么转换整个地球将为您提供足够的设备。

因为每十亿微秒执行十亿次操作将需要大约$ 2 ^ {74} $普朗克时间,所以以该速度运行的每个设备将需要小于69个硅原子的质量,以便在不超过地球质量的情况下具有足够的质量。不幸的是,在那段时间内,甚至需要穿过一个硅原子,光的传播速度就要快大约650倍。如果将其减少到每皮秒仅150万次解密,那么光每次可以穿过一个硅原子,那么您将需要更多的设备。如果每个设备的质量等于一个硅原子,那么最终的质量约为地球质量的9.7倍。

尝试在10年内强制使用256位密钥将更加实用。您只需要一个地球就能计算出的硅原子质量,就可以得到太阳能量输出的1/4。它仍然无助于散热或所需的能量总量。

$ 2 ^ {256} $是一个很大的数字。

#6 楼

加密起作用的原因是,您必须平均尝试所有可能答案集中的排列数量的1/2数量级。因此,对于128位,您必须探索128位数字的集合,如果幸运的话,您将探索不到一半的可能答案,而如果不幸的话,您将探索超过一半的可能答案。因此,使位数翻倍是可能答案数量乘以其自身的乘积。当然,这是一个非常大的数目。

量子计算机不能一次完成一个操作,而是普通计算机可以在一次计算中找到数学问题的解决方案。有一个算法,您可以使用算法来找到答案。普通计算机和量子计算机之间的区别在于,量子算法将同时检查您的集合的每个可能答案,而普通计算机一次将仅检查您问题的一个可能答案(假设使用简单的计算机而不是一个拥有多个CPU的服务器。)

关于为什么可以拥有128位密钥,如果您假设加密方法将大质数分解,这一点将变得显而易见。加密的方法是找到实际上可以找到的最大秘密质数,然后将其乘以另一个相似数量级的质数。从前面的讨论中很明显,结果将是一个数字,大约是您实际可以分解的数字的两倍,并且分解将花费大量的时间……可能比太阳花的时间还要多。烧光。

因此,您使用大量数字作为公用密码来编码消息,从而对消息进行加密,而唯一可以解码的方法就是分解公钥。只有知道这些因素的人才能对消息进行解码,因为此计算速度更快。这样的系统使用所谓的活板门功能。也就是说,除非您具有非公开的且不容易发现的其他信息,否则这些计算非常容易执行,并且极其难以进行反向计算。这确实是量子计算机的关键。事实证明,我们是否能够以公开要求的方式使用此类设备存在疑问。您看到为了使用量子计算,您必须了解如何阅读答案。您必须阅读答案的唯一方法是使用统计信息。没有别的办法了。好吧,事实证明要进行非常准确的统计是一项艰巨的任务。例如,如果您希望找到一个256位素数,则必须做足够好的统计以区分所有其他256位素数的正确256位素数,也就是说,您必须有一个答案精确到提高到256次方的2分之一。事实证明,这项任务与使用普通计算机找到相同的质数一样困难。

事实是,与交互式量子计算机有关的量子研究中为数不多的确定性结果之一是IQC =空格。结果意味着没有交互式量子计算机能够比在多项式时间内计算更快地给出结果。那些为量子研究提供资金的人声称,这并不意味着您不能进行量子计算,我想它们是对的。但是我还没有听到他们中的任何人公开发表有关如何在IQC限制范围内达到目标的公开声明。

评论


$ \ begingroup $
如今,分解256位数字并不是什么大问题,并且比强行使用类似大小的密钥要快得多。需要量子计算机进行分解的RSA密钥大小要大得多。 (顺便说一下,欢迎使用密码栈交换。)
$ \ endgroup $
–PaŭloEbermann
2011-12-22 22:34



$ \ begingroup $
最后,您已经将P和PSPACE混淆了。 PSPACE =在多项式空间(即内存)中可能的计算。 PSPACE(可能)甚至大于NP。我们不知道IQC或BQP或任何其他量子复杂性类别都大于P,但这是安全的押注,押注与P!= NP相同。
$ \ endgroup $
– zwol
2011-12-20在20:23



$ \ begingroup $
这是邮编1337 :)
$ \ endgroup $
–多项式
2012年7月23日在18:49

#7 楼

让我们以GDP和加密货币矿工为辅助工具来显示它的成本是多少。 ^ {12} $,大约等于$ 2 ^ {37} $($ 10 ^ {12}> 8 ^ {12}> 2 ^ {36} $)。
加密矿工:使用Bitmain S19 pro举个例子,它的售价约为2000美元,其哈希率是110TH / s,是Bitmain所有类型的加密矿工中哈希率最高的。请注意,110 TH / s意味着矿工每秒可以计算1100亿个哈希,大约等于$ 2 ^ {36} $。

使用蛮力攻击提取256位密钥,总共需要$ 2 ^ {256} $个操作。比特大陆S19可以使用一年($ 2 ^ {36} \ times 3600 \ times24 \ times = 2 ^ {36} \ times 3 \ times 10 ^ 7> 2 ^ {36} \ times 3 \ times 2 ^ {21 } = 3 \ x 2 ^ {57}> 2 ^ {58} $)。因此,每年进行$ 2 ^ {58} $美元的操作需要花费2000美元,然后在2018年使用美国GDP可以完成$ 2 ^ {84} $美元的操作。这样,每年将花费$ 2 ^ {172} $美元GDP($ 2 ^ {256} / 2 ^ {84} = 2 ^ {172} $),以使蛮力攻击成功。对于我们来说,这仍然是一个巨大的数字,所以我们就算了吧。

#8 楼

如果您将全部内容的一部分拿走,任何事情都是易碎的。密钥由“部分”组成,如果您这样对待它,它可以更快地解决您的问题。表数据然后同步前进。真正的2.67 ghz cpu可以以每分钟1.3触发器的速度在16位线程上以每8位128位的速度破解,可以在11.67小时内破解128位...显然,您需要编写代码以根据加密类型来处理解密。

评论


$ \ begingroup $
您的数学完全错误。
$ \ endgroup $
–吉尔斯'所以-不再是邪恶的'
2015年3月29日14:52

$ \ begingroup $
幸运的是,电影和电视节目完全破解了完全错误的加密图像。实际上,没有办法区分部分正确的密钥。所有通过符号来破坏密钥或密码符号的想法都是虚构的。
$ \ endgroup $
– tylo
15年3月30日在12:05

$ \ begingroup $
是的,为什么不将128位分解为128个“部分”。这样可以将运算减少为128次迭代,如果您非常不幸,则可以减少256次
$ \ endgroup $
–个展
15年11月27日在9:14