作者：Talosec核心组 王安，杨晓雅

摘要：我们使用侧信道分析的方式对一款开源硬件钱包进行安全性测评，这款钱包的芯片为ARM-Cortex-M4内核，内部采用椭圆曲线数字签名算法（ECDSA）进行签名，在已知源码的情况下，我们参考国内外对ECDSA算法进行侧信道攻击的多种方式，对源码进行分析，找出已经进行侧信道防护的位置、以及可能存在侧信道攻击风险的位置，并尝试借助实验来佐证我们的结论。最后，我们给出了一些侧信道防护的改进建议。我们的第二篇报告Part2会针对改进后的方案做更进一步的攻击测试。

由于本论坛只能通过文本格式输入数学公式，本报告涉及到大量数学公式，我们将分析报告作为pdf附件一并上传。

与大多数传统货币不同，比特币是一种数字货币。由于比特币不存在任何物理形状或形式，因此技术上无法存储在任何地方。交易时双方需要类似电子邮箱的“比特币钱包”和类似电子邮箱地址的“比特币地址”。和收发电子邮件一样，汇款方通过电脑或智能手机，按收款方地址将比特币直接付给对方。

比特币地址和私钥是成对出现的，他们的关系就像银行卡号和密码。比特币地址就像银行卡号一样用来记录你在该地址上存有多少比特币。你可以随意的生成比特币地址来存放比特币。每个比特币地址在生成时，都会有一个相对应的该地址的私钥被生成出来。这个私钥可以证明你对该地址上的比特币具有所有权。我们可以简单的把比特币地址理解成为银行卡号，该地址的私钥理解成为所对应银行卡号的密码。只有你在知道银行密码的情况下才能使用银行卡号上的钱。所以，对与比特币钱包来说私钥是尤为重要的。

比特币钱包按照私钥的存储方式，大致可分为热钱包和冷钱包两种，热钱包指使用时必须要保持联网状态，而冷钱包是再非联网状态下使用的，所以外界一般不能通过网络访问到其存储私钥的位置，遭受黑客攻击的可能性大大降低。在冷钱包中，硬件钱包是非常受大众青睐的一种使用。私钥保存在硬件内部的微处理器，交易在硬件钱包内部确认，即使电脑感染病毒也不会泄露密钥，安全性极高。与其他离线钱包，比如纸质冷钱包相比，其便捷性非常突出。硬件钱包可以通过USB口或蓝牙连接到电脑，点击按钮就能确认交易。

加密电子设备在运行过程中，会产生时间消耗、能量消耗或电磁辐射之类的侧信道信息泄露，而利用这些泄露对加密设备进行攻击的方法被称为侧信道攻击。侧信道攻击技术是国际密码学研究的热点方向，它能够通过物理信道直接获得密码运算的中间信息，也能够分段恢复较长的密钥，因而它比传统密码分析更容易攻击实际密码系统。所以国际主流的密码产品测评机构均把侧信道攻击的防护能力作为衡量设备或芯片安全性的主要指标，学者、黑客们可以利用侧信道攻击破解密码模块或安全产品，主要方法有能量攻击、电磁辐射攻击、故障攻击、中距离电磁与声音攻击、缓存攻击等。

硬件比特币钱包作为一种硬件设备，其在进行运算时不可避免会泄露一些侧信息，比如在进行签名运算过程中会使用到私钥，如果攻击者采集此时的能量或者电磁等侧信息，就有一定的几率得到钱包内存储的私钥。获取到私钥也就相当于完全破解了该电子钱包，所以对于比特币钱包的侧信道分析就显得尤为重要。如果无法证明一款硬件比特币钱包是抗侧信道攻击的，我们完全有理由怀疑这款钱包的安全性。

当前市面存在多种品牌硬件钱包，虽然有部分声称对侧信道攻击做过防御，但并没有公布细节，所以没有第三方的评估对其安全性不得而知。在今年的4月30日，Riscure公司公布了对keepKey的电磁脉冲故障注入实验[1]，绕过了其对PIN码的认证流程以及重置私钥步骤，可使得攻击者在没有输PIN码的状态下获取钱包私钥的权限。

我们研究侧信道分析通常会针对不同的密码算法进行研究，对于相同的算法，它在不同的硬件设备中的实现都存在着许多共性问题。由于本文研究的比特币钱包中的签名算法为ECDSA，其是基于ECC实现的，国内外对于ECC的实现已经有多年的侧信道分析积累，主要包含能量分析和故障注入两种手段，以下对这两种侧信道分析方法在ECC中的应用展开介绍。

在能量攻击方面，Coron在[2]指出可以对ECC中标量乘实现部分进行简单能量分析（Simple Power Analysis，SPA）；对于使用蒙哥马利算法实现的模幂算法，Herbst在[3]指出可以可以对该过程执行模板攻击（Template Attack，TA），攻击者可以先在一个完全可控的设备上进行多次实验，构建模板，然后在待攻击设备上多次采集加密过程中的能量消耗，与之前建立的模板匹配；在计算标量乘，也就是kP时，如果k固定，攻击者可以自由选择P，那么攻击者可以通过给定多个P的取值，让设备进行加密运算，并采集加密过程中的能量，在这种情况下可以使用相关能量分析（Correlation Power Analysis，CPA）以几个比特为单位来恢复k，这种方法在[4]中提到；在文献[5]中，作者提出一种介于SPA和CPA之间的方法——比较法，Fouque等人在[6]中指出，对于两次倍点2P和2Q，攻击者可能从能量波形上无法得出P和Q具体的值，但是可以通过比较波形得知P和Q是否相等，攻击者有机会通过比较kP和k(2P)的波形来恢复k的全部比特。另外，在P为攻击者可选的情况下，如果输入的P中含有零值（如(x,0)，或(y,0)）时，无论对P进行何种随机，P都有一个坐标值为零，在进行标量乘法时，可以利用这个零值获取密钥信息，这种方法被称之为RPA，是Goubin在[7]中提出的；零点值攻击（ZPA）[8]是RPA的扩展，RPA利用坐标值中含零的特殊点进行能量攻击，ZPA利用域运算中辅助器寄存器中值为零的点进行能量攻击。

除了能量分析，常用的侧信道分析方法还有故障注入，攻击者可以利用激光或者电磁脉冲、电源/时钟毛刺等对被攻击设备进行故障注入，使得被攻击设备的运算过程发生故障，攻击者可以通过这种方式获取自己感兴趣的输出值，具体方法读者可参考[9]。

在ECC中，主要存在三种故障注入的方法，一种是安全-错误分析（Safe-Erro Analysis），这个概念由Yen和Joy在[10][11]中提出，指出了两种安全-错误分析的攻击方法，其中C安全-错误攻击的方法是指通过诱导临时故障以判断操作是否为冗余操作。一种是由Biehl等人在[12]中提出的弱曲线为基础的攻击，攻击者通过故障注入改变曲线的参数a_6，得到阶数较小的弱曲线，这样在知道kP的情况下就可以通过遍历的方法恢复k值了。还有一种是差分故障攻击（Differential Fault Attack，DFA），也是Biehl等人在[12]中提出的，攻击者在非故障注入状态下进行一次加密并得到正确结果，再在注入故障的状态下再次进行加密并获得错误结果，比较两次的结果，可能得到某些敏感信息。

本文以素域为例介绍椭圆曲线的一些基本概念。令p>3是一个素数，a,b∈F_P，满足4a_3+27b_2≠0，由a和b定义F_P 上的椭圆曲线是方程y^2=x^3+ax+b的所有解(x,y)，x,y∈F_P，连同无穷远点(记为O)的元素组成的集合。对所有P(x,y)∈Fp，P+O=P。令P_1 (x_1,y_1)≠O，P_2 (x_2,y_2)≠O为椭圆曲线上两点，P_1≠-P_2，则P_1+P_2=P_3 (x_3,y_3)，在仿射坐标下，椭圆曲线的点加和点倍关系为：

x_3=λ^2-x_1-x_2

y_3=λ(x_1-x_3)-y_1

式中当P_1≠P_2 时，λ=(y_2-y_1)/(x_2-x_1)；当P_1=P_2 时，λ=(3x^2+a)/(2y_1)。

Q=kP是ECC的基本运算（P和Q都是椭圆曲线上的点，k为整数），称为点乘或者标量乘。其中，k为私钥；Q为公钥；P为椭圆曲线上的一个基点。已知k和P很容易求出Q；但已知P和Q很难求出k。ECC的安全性正是基于该原则。

ECDSA的参数组D=(q,FR,S,a,b,P,n,h)为需要满足一定的条件。它的密钥对也是根据参数组生成的。随机从[1,n-1]中选取一个数d, 计算Q=dG。其中，d就是私钥，而Q即为公钥。

ECDSA的签名算法如下： 

——————————————————————————————————————

算法1：ECDSA签名

输入：参数组D=(q, FR, S, a, b, P, n, h)，私钥d，消息m

输出：签名(r,s)

1：选择k∈_R [1,n-1]

2：计算kP=(x_1,y_1)，并将x_1 转换为整数(x_1 ) ̅

3：计算r=(x_1 ) ̅mod n。若r=0，跳至步骤1

4：计算e=H(m)

5：计算s=k^(-1) (e+dr)mod n。若s=0，跳至步骤1

6：Return (r,s)

——————————————————————————————————————

ECDSA的验证步骤如下：

——————————————————————————————————————

算法2：ECDSA验证

输入：参数组D=(q, FR, S, a, b, P, n, h)，公钥Q，消息m，签名(r,s)

输出：判断签名是否合法

1：检验r和s是否是区间[1,n-1]内的整数，若任何一个验证失败，则返回（“拒绝该签名”）

2：计算e=H(m)

3：计算w=s^(-1) mod n

4：计算u_1=ew mod n和u_2=rw mod n

5：计算X=u_1 P+u_2 Q

6：若X=∞，则返回（“拒绝该签名”）

7：将X的x坐标x_1 转换为整数(x_1 ) ̅；计算v=(x_1 ) ̅  mod n

8：若v=r，则返回（“接受该签名”）；否则，返回（“拒绝该签名”）

——————————————————————————————————————

在ECC中，用到的标量乘kP是最为耗时的，计算一般可以将k转化为二进制形式再进行运算，用到的操作主要有点加和倍点操作，具体算法如下。

——————————————————————————————————————

算法3：点加倍点操作实现标量乘

输入：点P，一个正整数k=〖(1,k_(n-2),…,k_0)〗_2

输出：[k]P

1: R[0]←P

2：For n-2 downto 0

3:           R[0]←2R[0]

4:    If k_i=1 then

5:           R[0]←R[0]+P

6：Return R[0] 

——————————————————————————————————————

Width-w NAF是使用预先计算的点的NAF的扩展。Width-w NAF表示n比特的整数d，d=∑_(i=0)^(n-1)▒〖d_w [i]2^i 〗，d_w [i]奇整数并且满足|d_w [i]|<2^(w-1)，在连续的w个元素中，最多只有一个非负值。

Width-w NAF由不同的作者在[13][14][15]中独立提出的。Solinas在[16]中提出的生成算法非常简单，我们对此进行简单描述。 

——————————————————————————————————————

算法4：传统的Width- NAF算法

输入：窗口宽度w，一个正整数d。

输出：NAF_W (d)。

1：For i=0to n

2:   If d=1mod2 then

3:          d_w [i]←dmods2^w andd←d-d_w [i]

4:   Else

5:          d_w [i]←0

6：d←d/2

2：Return d_w [n],d_w [n-1],…,d_w [0]

——————————————————————————————————————

步骤3中的“mods2^w”为奇数d选择有符号余数类2^w，即{{〖-2〗^(w-1)+1,…,-3,-1,1,3,…,2^(w-1)-1}。 因此，我们必须预先计算点P,3P,...,(2^(w-1)-1)P，以便通过预先计算的点来表示残差数列，其具有2^(w-2) 个点。 如果步骤1.1中的d不是偶数的话，那么d_w [i]是奇数，且有|d_w [i]|<2^(w-1) 。步骤1.1之后的d总是可被2^w 整除的。因此，一旦d_w [i]=0成立，则接下来的w-1位就全为零，即 d_w [i+1]=d_w [i+2]=⋯d_w [i+1]=0。

汉明重量指的是一串符号中非零符号的个数。在二进制表示的符号串中，它是1的个数。

在芯片上，其所有的运算最终都是由芯片内部半导体逻辑状态0和1规律变化实现的。当芯片进行工作时，逻辑状态0和1的变化将在逻辑门上消耗能量，同时产生电磁辐射。根据当前半导体工艺技术（主要指CMOS工艺技术）的实现特点，密码芯片在处理逻辑状态0和逻辑状态1时会有不同的能量消耗，并产生不同强度的电磁辐射，分析者通过检测能量消耗或者电磁信号的差异便可获得逻辑0和逻辑1相关的一些侧信道信息。由于能量消耗和电磁信号通常反应同样的信息，我们以下就以能量消耗展开介绍。

在算法运行的过程中，通常会产生一些攻击者感兴趣的操作的操作数。对于不同的操作数，芯片内部逻辑门上的能量消耗通常不同。人们将这种差异归结为几种模型：汉明重量模型、汉明距离模型、零值模型等。

操作数在芯片内部的存储形式一般是二进制的，对于软件实现的算法，其操作数对应的寄存器的跳变一般是由全0或者全1跳转为该操作数的二进制表示形式，产生的能量消耗通常符合汉明重量模型。

即我们假设算法中某一时刻的能量消耗t与中间值y的汉明重量呈线性关系：

t=aHW(y)+b

若a是正数，则操作数的汉明重量越高，其能量消耗越小；操作数的汉明重量越低，其能量消耗越大。若a是负数，则反之。

我们采用Lecroy WaveRunner 104Xi-A示波器、自主研发的能量信号采集探头、Mini-Circuits 1.9MHz低通滤波器、待测开发板、USB转UART板、计算机等组件搭建了实验平台，如图1所示。

图1  测试平台实物图

我们采用串口调试助手，对芯片循环发送待签名数据，循环周期为3秒，也就是每3秒钟执行1次ECDSA签名运算。在这一过程中，我们观察示波器上的波形变化，可以发现每3秒中将会有大约1.2秒的波形较特殊，它与无指令发送时采集到的芯片空闲时刻的能耗波形有显著差别。我们以串口的发送信号为触发，在200KSa/s采样率下采集5s波形，得到如图2所示波形。

图2  整体波形

已知波形以3秒为一个周期，在起始采样点之后芯片开始处理收到的数据，所以可确定芯片签名时间大约1.2秒。由于波形起伏并不明显，我们将波形进行参数为50的平滑滤波。得到图3所示结果。在图中可以明显看出，在这5秒中进行了2次签名，第一次大约为第0秒至第1.2秒，第二次大约为第3秒至第4.2秒，在1.2秒的一次签名过程中，芯片的数据处理主要可分为5个阶段，第1阶段、第3阶段和第5阶段耗时较短（小于0.1秒），且能量消耗变化较大，第2阶段和第4阶段的时间都大约在0.5秒到0.6秒左右，耗时较长，且能量消耗变化相对较小。

图3  整体波形滤波后的波形

我们在250MS/s的采样率下更清晰地采集第1、3、5部分的波形，并且对他们进行滤波，可以得到图4中对比图。

  图4  第1、3、5阶段的波形及其滤波波形

我们对第2阶段和第4阶段同样进行更高精度的波形采集并滤波，得到图4所示结果。可以看到它们的波形都十分规律，没有较大的起伏。第2阶段的图包括了第1阶段和第3阶段作为首尾，第4阶段的图包括了第3阶段和第5阶段为首尾，方便进行观察比较。

图5  第2、4阶段的波形及其滤波波形

第2、4阶段放大来看其规律几乎完全相同，且时间基本相等。在ECDSA的签名的计算过程中，最耗时的为标量乘操作，而且标量乘操作是多次循环，非常有规律。根据程序的源码我们可以知道，整个签名过程共包括了两次标量乘操作，一次是在签名时计算kP，一次是计算公钥。由此可以推断第二阶段和第四阶段都是标量乘操作。

可以看出第1、3阶段的波形是比较相似的，可以猜测第3阶段对应了标量乘运算之后的计算s以及将签名结果进行数据填充，将转换为返回数据格式的过程。

我们在500MHz采样率下采集第2、4阶段波形，并进行放大，可以发现波形是由图6（左）中所示的直角三角形状的波形组合而成的，其频率为32MHz。我们在相同频率下采集一段空闲阶段（芯片等待上位机信号的阶段）的波形，进行同比例放大，发现空闲阶段也是由相同形状的三角形组合而成的，但是此时的频率为24MHz。直角三角形状抖动的形成原因可能是显示升压造成的，我们后续会继续分析和做相应降噪处理。

图6  第2、4阶段的波形及其滤波波形

在CRYPTO 1999上，Kocher等人提出的简单能量分析技术[4]，这种分析技术基于以下假设：对于不同操作，它的能量消耗的波型一般是不同的，在目前的芯片制造工艺下，我们认为这是成立的。

如果操作序列与攻击者感兴趣的参数或者密钥相关，攻击者完全可以通过采集一条曲线，通过分析波形的变化恢复加密过程中的操作，从而通过操作反推密钥或者相关参数。

算法5：采用二进制下传统算法实现的标量乘

输入：点P，256 比特的整数k=k_255…k_2 k_1 k_0

输出：kP

步骤：

1：Q=0

2：For j=254 downto 0

3：       Q=2Q

4：If k_j=1 then

5:          Q=Q+P

6：Return Q

——————————————————————————————————————

可以看出当k_j=1时，对应倍点和点加操作，当k_j=0时对应倍点操作。由于通常情况下整数k_j 等于0或者等于1的概率都是1/2，所以倍点操作和点加操作的比例大约是2:1，并且每个点加操作之前必定有一个倍点操作，点加操作和点加操作肯定是不相邻的。攻击者可以以此为根据区分点加和倍点，并由此反推出k的值。

在传统的Width-w NAF算法中，w为窗口长度，在计算标量乘之前将窗口值(P,2P,…,(2^w-1)P)预先保存在存储器中，执行时直接从存储器中读取这些点的值。算法先将k的二进制序列转化为Width-w NAF形式，再进行标量乘法。 

——————————————————————————————————————

算法6：采用Width-w NAF算法的标量乘

输入：k、P、w

输出：kP

预计算：

1：将k转换为width-w NAF形式，表示NAF_W (k)=∑_(i=0)^(l-1)▒〖k_i 2^i 〗 。

主运算：

1：Q←∞

2：For i=l-1 downto 1

[峰会]看雪.第八届安全开发者峰会10月23日上海龙之梦大酒店举办！