[转]基于“旁路攻击”的AES256破解实践
12112017/07/31无线电 IP:四川
按:本文原标题《没有绝对安全的系统:写在AES 256破解之后》,转载自阿里聚安全博客,作者cyxu。论坛编辑没有对文章进行学术检验,不代表编辑的观点,仅供参考。

AES 256被破解了?

对于TLNR(Too Long, Not Read)的读者来说,先把答案放在这:是的,但也不尽然。

事件回顾如下:前几日在互联网上转发的一条题为“AES 256加密被破 一套1500元设备5分钟内搞定”的新闻引起了各界的关注。新闻在国内各大媒体转载,热门评论里不乏各种被高赞但实际上并不正确的说法:有说是字典攻击无线信号,和破解AES是两回事的,也有所是根据无线电特性来攻击的,和AES没关系的。还有想搞个大新闻的媒体直接说是路由器被破解,甚至还说成了5分钟破解任何WiFi密码的,唯恐天下不乱。

实际上这次的破解来自Fox-IT [1],确实攻击了AES算法本身,利用了电磁辐射泄露的信息,可以实现无线攻击(隔墙有耳)。这样的攻击形式称为旁路攻击(Side Channel Attack),在学术界和工业界已经研究了20多年,是一种较为系统完善的攻击方法,此次攻破AES256的方法是利用电磁旁路信号来完成差分功耗分析(DPA),获取了密钥。从介绍本身来看,是一个很不错的工作,但不是AES首次被破解,AES 128早就可以用类似的方式破解,AES 256在DPA看来,和前者没有本质差异,在实验室中早已破解。当然也做不到5分钟破解任何WiFi密码。原因是SCA需要一定的物理条件,目前AES算法本身还是安全的,不必惊慌过度。

背景知识

以AES为例,AES是高级加密标准Advanced Encryption Standard的缩写,是美国联邦政府采用的一种分组加密标准,也是目前分组密码实际上的工业标准。AES广泛使用在各个领域(当然包括WiFi的加密过程),实际上目前主流的处理器中广泛包含了AES的硬件加速器(低至售价几美元的STM32中有CRYP [2],高至售价上千美元的Intel CPU中有AES-NI [3])。对于这样一个成熟的密码学标准,密码算法本身设计的十分完善,传统的差分分析,线性分析等方法基本上不能在有限复杂度内完成,AES在理论上是安全的。但是正如本文标题描述的那样,即便有绝对安全的算法,也做不到绝对安全的系统。唯物辩证法中有联系的普遍性和多样性原理,现代密码系统在设计上理论安全,并不能替代密码系统的实现安全性。攻击者可以在不干扰密码芯片运行的前提下,观测时间,功耗,电磁辐射等旁路泄露,然后结合算法的实现进行密钥还原,实现所谓的旁路攻击。对于旁路攻击的防御,涉及到密码算法实现安全性这一范畴,很显然,这次攻击成功的AES 256,表明实现安全性的研究还有很长的路要走。

这里简要介绍一下AES算法。AES算法包含了多个轮,每一轮(除了最后一轮)中,都有4个步骤[4][5]:
(1)AddRoundKey—矩阵中的每一个字节都与该次回合密钥(round key)做XOR运算;每个子密钥由密钥生成方案产生。
(2)SubBytes—通过一个非线性的替换函数,用查找表的方式把每个字节替换成对应的字节。
(3)ShiftRows—将矩阵中的每个横列进行循环式移位。
(4)MixColumns—为了充分混合矩阵中各个直行的操作。这个步骤使用线性转换来混合每内联的四个字节。最后一个加密循环中省略MixColumns步骤,而以另一个AddRoundKey取代。

AES流程图
1.jpg
接下来留意2个数字,2^256(2的256次方)和8192。2^256是整个密钥空间,这是一个相当大的数字,表明如果要一个一个猜密钥,需要这么多次才能确保猜对,这个数太大了,所以没法猜,暴力破解不可取。
但如果是猜8192次呢,这个数字对于计算机来说就完全可以接受了。怎么猜才能在8192次中猜对呢。信息论告诉我们,必须有额外的信息输入。简言之就是分治的思想:一个一个猜。256 bits的密钥,也就是32个Bytes,如果逐字节猜,每个字节有256种可能,32个字节需要256*32 = 8192次猜测就可以了。

而芯片工作受限于位宽和算法实现,是不会一次完成整个256bits密钥的处理的,正如饭要一口一口吃,数据也是逐字节处理的,这就给我们我们逐字节猜提供了实现依据。

本次旁路分析依然按惯例关注其中的非线性环节SubBytes。所谓的非线性替换函数,在实现中就是一个查表操作。查表操作的输出(S-box output)是攻击点。当然算法的优化会合并一些操作以提高运算速度,这里攻击者可以偷着乐。原因是虽然优化需要做大量的工作,但实际上,最终结果还是查表,查较大的表和较小的表,在旁路攻击中没有实质的区别。AES 128和256的区别也是轮数,密钥长度的区别,查表操作本身是没有本质变化的(划重点)。

接下来用一张关系图来说明各要素的关联。
2.jpg
AES的输入是密钥和明文,对于攻击者来说,明文已知,密钥未知,也是分析目标。

接下来初始密钥和明文会进行一个异或操作(首次AddRoundKey),得到的值,作为查表索引输入,进行查表操作,注意到查表的数据是和密钥和明文的异或有关的。而明文已知,查找表本身固定已知,异或运算又是简单的可逆运算,所以可以认为查表的输出和密钥有关。查表操作在现代计算机体系结构中是一次访存操作,那么,地址和数据都会出现在总线上。如果能知道总线上是什么数据,就可以简单的反推出密钥。接下来考虑总线是什么?低频上看是导线,射频上看是天线,对于安全分析人员来说,天线都是个好东西。高速数字电路的信号翻转,包含了丰富的频谱分量,会辐射到芯片外部。理论上能准确探测到这样的辐射,就能完成攻击了,so easy。

当然,在实践中,呵呵。

问题一方面出在测量精度上。实际上我们并不能如此高精度地测量电磁辐射。我们可以测量的是电磁辐射的相对高低。例如1根导线上信号翻转和8根导线上信号一起翻转,就有明显的信号强度差异。这里涉及到一个术语称为泄露模型(model of leakage),描述泄露的情况。这次攻击使用了Hamming distance模型,也就是说信号跳变程度是可以观测的,这在电磁旁路分析中也是较为常见的建模方式。

问题另一方面出在信噪比。(即便用上雅鲁藏布江的水电),环境中始终有大量的干扰,提高信号质量的方式是多次测量,然后通过相关性分析的方法提取统计上的最大相关性。

还有一些问题限于篇幅这里不展开,反正DPA都很巧妙地解决了:
(1)首先输入一个明文,在加密过程中,明文会和密钥的第i个字节异或,输入到查找表中查表,查表结果会出现在总线上,然后产生电磁辐射。这个过程是真实物理发生的,在此期间使用硬件记录这个电磁辐射。
(2)分析软件模拟计算过程(1),当然因为不知道密钥的第i个字节具体数值,每一种可能都要算,利用泄露模型计算256个模拟的电磁辐射相对值。
(3)变换不同的明文重复(1)和(2)的过程,得到N次结果。一共有N个实际测量值和N*256个计算值。
(4)使用相关性分析的方法,比对这256种猜测中,和实际测量值相关性最大的猜测值,就是实际上密钥的第i个字节真实值。
(5)重复(1)到(4),分别猜测32个密钥字节,得到完整密钥。

以上就是电磁/功耗差分分析的主要流程(通俗版)。由于密码芯片在加密过程中,是逐字节处理的,而处理每个字节的时候,都会有电磁信息的泄露,给了攻击者逐字节猜测的机会,从而可以在前文提到的8192次猜测中完成破解。实际分析中,还会遇到很多的困难,接下来看看Fox-IT的专家是怎么完成这次攻击的。

实战
以下是Fox-IT的专家给出的攻击流程。
3.jpg
首先使用射频采集设备采集目标芯片的电磁辐射,混频量化后存储到分析计算机中。分析计算机首先对采集的信号进行预处理后,使用上述DPA的方式得出密钥。

攻击的目标硬件为来自Microsemi的SmartFusion2,这是一个混合了ARM和FPGA的SoC。攻击针对的是ARM部分,一个Cortex-M3的内核。目标软件是来自OpenSSL [6]的AES 256实现。虽然SoC是一个混合芯片,但是只是用了ARM部分,Cortex-M3是很经典的ARM core,软件上也是OpenSSL的标准实现,可以认为这样的攻击很具有代表性。

SmartFusion2 SoC FPGA 结构[7]
4.png
接下来看看信号链部分。
首先是天线。理论上,设计天线是一个非常严谨且套路很深的活,比如下图只是冰山一角(图片来自网络)。
4.jpg
回到实践中,下图是本次攻击中使用的天线。
5.jpg
就是一根电缆外加胶带“随意”制作的环状天线。
攻击场景如下:
6.jpg
绿色的PCB是目标板,环状天线悬空固定在芯片上方,信号通过了外部的放大器和带通滤波器,这些都是标准的工业器件,价格也不贵。
比较有意思的是采集设备,通常时域采集可以使用示波器,或者专用的数据记录仪,再不济也得用个USRP之类的软件无线电设备。Fox-IT的专家一开始自然也是这么考虑的。
7.jpg
图中左边是专用的数据记录仪,傻大粗,价格倒是很美丽。中间是USRP板子,这个板子的性能够用,价格也是一般的研究机构或者个人可以承受了。有趣的部分在图中右边,这个标识为RTLSDR的USB小玩意玩无线电的小伙伴一定不陌生。实际上国内也有卖,价格只需要几十到上百人民币。本次研究表明,这么一个入门级的小东西已经完全可以用来完成攻击。
8.jpg
上图就是用上述硬件观测到的AES模式,可以清晰地看到I/O操作之间的AES加密流程,包括Key Schedule过程和14轮的操作,都是清晰可见。

接下来是分析过程,这方面,文献[1]中并没有详细介绍。但是DPA是一个比较标准的套路,他们也使用了业界标杆级的软件Riscure's Inspector,因为可以结合笔者的经验来谈一谈。
首先是信号预处理,这部分主要包括数字滤波,复信号转为实信号,当然也包括重采样,截取等步骤。还有一个比较重要的过程是不同traces之间的对齐,比较简单的方法是使用滑动窗和相关性分析的方法,使得所有traces能够精确对准。

接下来就是真正的DPA了,这在Inspector软件中有标准的模块,反而不需要自己实现。不过也有一些技巧,文献[1]中就提到了一个。为了快速验证采集到的电磁信号和设备功耗有直接关联,以及采集的位置是否正确。使用输入的明文(或输出的密文)和采集的trace做一次相关性分析,并验证泄露模型是否有效。
9.jpg
这条相关性曲线说明了数据和信号之间确实有相关性的点,即确实可以从采集的信号中检测到数据。
接下来就是猜测密钥了,下图中相关性最高的猜测就是正确的密钥。实验表明SmartFusion2中,泄露来自AHB,这是符合预期的。因为AHB连接了Cortex-M3和片上RAM,查表操作就是M3内核访问RAM的一个操作。相比于简单的MCU,这里还要考虑cache的影响,对于指令cache,使用Hamming distance模型即可,而SmartFusion2为了和FPGA模块连接,考虑到数据一致性而没有设置数据cache,这也算是简化了攻击者的工作。
10.jpg
以上操作在几厘米之内探测电磁信号就完成了整个攻击过程,硬件成本小于200欧元(约1500人民币)。实际上这些硬件在国内购买的话,完全可能低于1000元。
在软件方面,Inspector是商业软件,需要支付授权费用。好在核心算法早已是公开的,可以自己编写,也可以使用便宜的解决方案,所以这方面的费用不计在总价内也是可以理解的。

局限性
通过梳理整个攻击流程,我们可以总结出这类旁路攻击的先决条件,也是它的局限性所在。
(1)必须完全可以控制目标设备,给它输入不同的明文,控制其完成加密操作。
(2)必须可以接近到目标设备,因为要测量设备的物理属性(电磁特征),究竟距离多近需要看现场的电磁环境。
(3)必须熟悉目标设备使用的算法和实现细节。算法本身比较容易确认,实现细节很多设备不会公开源代码,但是密码学算法通常有若干标准实现,不难猜测确定。

要完成攻击攻击,条件(1)是基础,所以不用担心邻居家可以只通过旁路攻击来破解你家的路由器了。
条件(2)主要看距离要多近,这里有一些深入的研究。
前文使用的手工制作的环状天线,工作距离只有若干厘米,稍远一点就淹没在噪声里了。
11.jpg
于是(早已坐不住的)天线工程师制造了下图的PCB天线,它的性能好很多,可惜为了降低尺(jia)寸(ge),它的工作频率是400MHz。而SmarFusion2只能最高工作到142MHz。既然是研究,不如换个目标设备(就是这么任性),比如Xilinx的Pynq board就可以稳稳地跑在400MHz。实践表明,依然可以用RTL-SDR完成攻击。这次攻击可以在30厘米内完成,但是不要忘了需要采集400k条traces,而且是在一定电磁屏蔽的环境下完成的。

PCB天线
12.jpg
使用急救毯包裹的攻击环境
13.jpg
最后再冲击一下1米的距离,这需要在理想条件下完成。
首先,测试在微波暗室中进行,尽可能地排除了干扰信号。天线方面使用了盘锥天线,并保证了测量子系统和加密子系统之间的电气隔离。1米的距离很艰难的达到了,使用了240万条traces。这个理想实验证明了,在足够好的条件下,1米的攻击距离是完全可行的。
14.jpg
防御
旁路攻击之所以可以生效,主要在于密码设备泄露的旁路信息和操作的数据有关联性。在算法实现上,可以通过掩码(masking)或者隐藏(hiding)的方式来消除这种关联性。这方面的具体细节本文不再展开。在密码学算法这一领域,对于一般的应用或者系统开发者,是不推荐自己造轮子的。特别是不可以认为自己略懂密码学的算法,就去修改它们,一个简单的小修改,可能会破坏理论安全性和实现安全性,这些都不是普通的开发者可以做好的事情,还是用成熟的轮子最为靠谱。

以SmartFusion 2为例,完全可以不使用OpenSSL的算法实现,而使用带有保护的实现,例如Microsemi官方提供的FPGA实现。在电路级别上,功耗平衡等技术也可以从一定程度上解决这类泄露,使用专有的硬件来完成密码学操作,就可以很好地防御这类攻击了。

参考文献
[1] XXXXXXXXXXXXXXXXXXXXXX/en/insights/blogs/blog/tempest-attacks-aes/
[2] XXXXXXXXXXXXXXXXX/zh/embedded-software/XXXXXXXXXXXXXXXXXml
[3] XXXXXXXXXXXXXXXXXXXXX/content/www/us/en/architecture-and-technology/advanced-encryption-standard--aes-/XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXml
[4] XXXXXXXXXXXXXXXXXXXXXXXX/wiki/Advanced_Encryption_Standard
[5] Pub N F. 197: Advanced encryption standard (AES)[J]. Federal information processing standards publication, 2001, 197(441): 0311.
[6] XXXXXXXXXXXXXXXXXXXXXXX/
[7] XXXXXXXXXXXXXXXXXXXXXXXXX/products/fpga-soc/soc-fpga/smartfusion2
[8] Mangard S, Oswald E, Popp T. Power analysis attacks: Revealing the secrets of smart cards[M]. Springer Science & Business Media, 2008.
来自:电子信息 / 无线电
4
已屏蔽 原因:{{ notice.reason }}已屏蔽
{{notice.noticeContent}}
~~空空如也
RodTech
7年5个月前 IP:广东
837432
应该重新学习语文,侮辱了“破解”。。。

sca在国外 早已风靡,defcon一类很多人做电源攻击的kit,无线的比较少,一般设备没有效果,稍作屏蔽snr就不够了
引用
评论
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论
bg8npk
7年5个月前 IP:四川
837438
如果磨片,上探针台的话,是不是难度更一步降低。。。。。。

要想减低这种泄露,理论上把MCU的工作电压进一步降低是不是就可以了。。
引用
评论
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论
RodTech
7年5个月前 IP:广东
837439
引用 bg8npk:
如果磨片,上探针台的话,是不是难度更一步降低。。。。。。

要想减低这种泄露,理论上把MCU的工作电压进一步降低是不是就可以了。。
降低信息泄露,从程序上做掩饰即可,不一定要降低实际频谱泄露。
上探针台。。一般不太可操作,首先把顶上盖子融掉同时保住脚,虽然可行但是很难,然后有些芯片顶层有防护,看不到实际的功能部分,还有些机子比如pos鸡有anti temper的外壳,打开壳子,分离电路板,拆开屏蔽罩,都会触发一些销毁机制。。。
引用
评论
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论
tangler
7年3个月前 IP:四川
839457
引用 bg8npk:
如果磨片,上探针台的话,是不是难度更一步降低。。。。。。

要想减低这种泄露,理论上把MCU的工作电压进一步降低是不是就可以了。。
降低MCU电压起码对stm32没鸟用。就算降到2.5V,内核电压还是1.2V…降低泄露不如加密的时候顺便跑点别的无关的东西,打散频谱…
引用
评论
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论

想参与大家的讨论?现在就 登录 或者 注册

所属专业
所属分类
上级专业
同级专业
1211
进士 学者 机友 笔友
文章
409
回复
1208
学术分
33
2005/08/31注册,6天21时前活动

科创消防局

主体类型:个人
所属领域:无
认证方式:手机号
IP归属地:未同步
文件下载
加载中...
{{errorInfo}}
{{downloadWarning}}
你在 {{downloadTime}} 下载过当前文件。
文件名称:{{resource.defaultFile.name}}
下载次数:{{resource.hits}}
上传用户:{{uploader.username}}
所需积分:{{costScores}},{{holdScores}}下载当前附件免费{{description}}
积分不足,去充值
文件已丢失

当前账号的附件下载数量限制如下:
时段 个数
{{f.startingTime}}点 - {{f.endTime}}点 {{f.fileCount}}
视频暂不能访问,请登录试试
仅供内部学术交流或培训使用,请先保存到本地。本内容不代表科创观点,未经原作者同意,请勿转载。
音频暂不能访问,请登录试试
支持的图片格式:jpg, jpeg, png
插入公式
评论控制
加载中...
文号:{{pid}}
投诉或举报
加载中...
{{tip}}
请选择违规类型:
{{reason.type}}

空空如也

加载中...
详情
详情
推送到专栏从专栏移除
设为匿名取消匿名
查看作者
回复
只看作者
加入收藏取消收藏
收藏
取消收藏
折叠回复
置顶取消置顶
评学术分
鼓励
设为精选取消精选
管理提醒
编辑
通过审核
评论控制
退修或删除
历史版本
违规记录
投诉或举报
加入黑名单移除黑名单
查看IP
{{format('YYYY/MM/DD HH:mm:ss', toc)}}