暴力解决一切?破解AES也是妄想!

文章转载自DPDK与SPDK开源社区

什么是AES?

AES是美国国家标准与技术研究院(National Institute of Standards and Technology,NIST)于2001年发布的高级加密标准(Advanced Encryption Standard)的简称,旨在取代DES(Data Encryption Standard,高级加密标准)成为新一代的分组加密标准,现已广泛应用于各个领域。

随着密码破译技术的发展和计算机运算水平的提高,使用56位密钥的DES算法已无法满足当今数据加密安全性的要求,一种安全性更高的加密标准亟待提出,最终NIST选择了分组长度为128位的Rijndael算法作为AES算法。AES和DES同为对称分组加密算法,都使用相同的密钥加密数据和解密数据。相比于DES算法密钥长度为56位,AES的密钥长度可以为128位、192位和256位,根据加解密密钥长度的不同,AES算法可分为AES-128、AES192和AES-256三种。AES加解密的算法结构如下图所示[2]。

图1. AES加解密的算法结构[2]

什么是暴力攻击?

暴力攻击又称为穷举攻击,即依次穷举每一个可能的密钥进行解密运算,直至找出正确的密钥,成功破解密码算法平均需要遍历一半的密钥空间。下表给出了AES和DES算法基于不同长度密钥所对应的暴力攻击的平均时间[2]。随着密钥长度的增加,密钥空间的密钥个数相应增加,DES和AES抗暴力攻击的能力也随之增强。

表1. 穷尽密钥搜索所需的平均时间[2]
随着计算机运算能力的日益增强,56位密钥的DES在暴力攻击下的安全性变得十分脆弱。为保证数据安全保密,可以采用新一代的AES算法,密钥个数大大增多足以对抗暴力攻击。然而全新的算法设计也意味着先前针对DES算法的软件开发和硬件设施不再适用,为保护已有的软硬件投资,也可使用多个密钥对数据进行多次DES加密(例如使用三个密钥的三重DES),变相地增加了密钥长度,从而保证了隐私数据的安全性。

破解AES算法需要多长时间?

以AES-128算法为例,平均需要尝试2^127 ≈ 1.7*10^38个128bit的随机数作为密钥进行加解密运算,方能找到正确的密钥。

常言道,“天下武功,唯快不破”;反之,天下密码,快必可破。问题是,那得有多快?我们知道,比特币网络在全球范围内调用了非常庞大的硬件资源以达到极高的运算效率,每秒钟操作的Hash运算(SHA-256)可高达2.5644*10^19次。虽然AES和SHA-256算法并不相同,运算量也有所差异,但我们不妨近似地用该数据估算全球人民众志成城破解AES算法所需要的时间。

假设AES的运算效率为2.564410^19 ≈ 2^64.4753次/秒,则进行2^127次AES运算所需要的时间为:
2^127 / 2^64.4753 ≈ 2^62.5247秒 ≈ 6.6345
10^18 秒 ≈ 1.8429 10^15 小时 ≈ 7.6789 10^13 天 ≈ 2.104 * 10^11年 ≈ 210,400,000,000 年

210,400,000,000 年又是多久呢?通俗地说就是2104亿年。可2104亿年又是什么概念呢?自大爆炸一刻起,宇宙他老人家如今已是138亿岁的高龄了,然而和2104亿年一比,立马也就只能算个学龄前儿童了。2104/138 ≈ 15.2464(倍)

太阳还剩大约50亿年的寿命,宇宙也并非永生不灭。想要看到AES破解成功的那一天?想要一鼓作气活他15个宇宙年龄?想要活过太阳赶超宇宙?管你怎么佛系养生,管你怎么保温杯里泡枸杞,即便向天再借五百个五百年,结果也只能是AES破解从开始到放弃。

破解AES算法需要花多少钱?

继续借用比特币网络以类比,据统计每秒进行1G次 hash运算消耗的电量约为0.237J,破解AES平均需要进行2^127次AES运算,总共需要消耗的电量约为:
(2^127 / 10^9) (0.237 10^-3) / 3600 ≈ 1.1201 * 10^22 kWh

国内一般工商业用电的电价约为0.77元/千瓦时,暴力破解AES需要花费的电费约为:
0.77 1.1201 10^22 ≈ 8.625 10^21 元 = 8.625 10^13 亿元≈ 1.368 * 10^13 亿美元

2017年我国GDP为827122亿元,全球GDP也不足一百万亿美元,远远小于破解AES的电费开销。
8.625 10^13 / 827122 ≈ 1.043 10^8 年
1.368 10^13 / 1000000 = 1.368 10^7年

泱泱大国举全国之财力,勤俭节约一亿余年方能筹集破解AES的用电费用;普天之下集全球之资金,埋头苦干上数千万年才可还清破解AES的电力债务。以上仅仅是用电量这一项开销,还未算及硬件设施、人力物力、资源成本、环境因素等等,若一并考虑,用度金额更是遥不可及。

安全攻击、密码破译大多是因为“有利可图”,什么样的机密才值得斥如此巨资去窥探?这么耗时耗力,不如直接绑架密码管理员;如此费心费钱,不如想法收买密码管理员。

量子计算机,AES算法的终结?

量子计算机的横空出世,便衍生出来诸多对现代算法密码的怀疑和担忧,是不是现如今盛行的密码算法都已不再安全了?诚然,学术界已严格论证了量子计算机的计算优势,例如大因子分解问题和离散对数问题等,相比于电子计算机,量子计算机的确能够带来指数级的运算速度的提高,非对称密码体系中的RSA算法和椭圆曲线算法可在较短的时间内被破解。

然而,量子计算机并非对所有运算问题都有如此可观的提速。对于对称加密体系中AES-128算法而言,假设电子计算机需要2^128个时间单位方能破解,利用量子计算机则只需要2^64个时间单位即可破解。以此类推,量子计算机暴力攻击AES-256算法的难度和电子计算机暴力破解AES-128算法的难度是一样的。虽然AES-128算法的安全性对于量子计算机已很难保证了,但仅仅通过增加密钥长度就可以克服这一问题,例如使用AES-256算法,前面已经论述过电子计算机穷举攻击AES-128算法是无能为力的,同理,量子计算机暴力破解AES-256也是鞭长莫及。

隔墙有耳——侧信道攻击

光明正大地硬碰硬是破解不了AES算法了,旁门左道的方法不妨也试一试。

侧信道攻击(side channel attack, SCA),又称旁路攻击、旁道攻击、边信道攻击,是指通过窃取电子设备实现加解密算法时泄露的旁路信息从而攻击密码系统的方法,例如通过分析密码系统的计算时间、功率消耗、电磁辐射和声音情况等“听译”密钥破解密码。与传统的通过数学手段的密码分析不同,SCA并不直接攻击已证明运算安全的密码算法本身,而采取了一种“曲线救国”的方式攻击密码算法的实现技术,破解密码系统的效果更为显著。好比想知道一个人在家中是在洗衣服还是看电视,我们并不需要撬开门锁进入屋子一探究竟,直接通过观察室外的水表和电表便可推测出来,SCA正是这样一种绕开门锁的窥探方法。

侧信道攻击是目前针对AES密码系统唯一成功的攻击,但实际上该攻击并不仅仅对AES有效,很多其他的密码系统也同样有侧信道攻击的安全隐患。AES算法本身是足够安全了,只可惜栽在了算法实现上,“不怕神一样的对手,就怕猪一样的队友”,大抵说的就是这种情况吧。

侧信道攻击之所以可行主要在于电子密码设备泄露的时间、功率、电磁辐射等旁路信息和设备所运算的数据具有一定的关联性。在硬件电路层面,可以通过功耗平衡等技术减弱这种关联性;从软件算法实现层面,则可通过“掩码”或“隐藏”等牺牲一定运算效率的方法以混淆攻击者的视听,从而保证密码算法的安全性。

总结

在规范了AES密码系统实现的情况下,对于当前电子计算机和量子计算机的运算能力,除非在数学上有重大突破,AES密码算法仍是不可破解的。一旦哪一天,上述提前被打破,那也不必担心,必会有新的密码系统抓起接力棒,继续捍卫数据的隐私安全。

参考文献
[1] Standard, NIST-FIPS. “Announcing the advanced encryption standard (AES).” Federal Information Processing Standards Publication 197 (2001): 1-51.
[2] Stallings, William. Cryptography and network security: principles and practice. Pearson Education India, 2003.
[3] Advanced Encryption Standard, Wikipedia
[4] Bitcoin Energy Consumption, Digiconomist
[5] Chen, Lily, et al. Report on post-quantum cryptography. US Department of Commerce, National Institute of Standards and Technology, 2016.
[6] Side-channel attack, Wikipedia


  • 本站原创文章仅代表作者观点,不代表SDNLAB立场。所有原创内容版权均属SDNLAB,欢迎大家转发分享。但未经授权,严禁任何媒体(平面媒体、网络媒体、自媒体等)以及微信公众号复制、转载、摘编或以其他方式进行使用,转载须注明来自 SDNLAB并附上本文链接。 本站中所有编译类文章仅用于学习和交流目的,编译工作遵照 CC 协议,如果有侵犯到您权益的地方,请及时联系我们。
  • 本文链接https://www.sdnlab.com/21145.html
分享到:
相关文章
条评论

登录后才可以评论

SDNLAB君 发表于18-07-20
1