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

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

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

1.1. 研究背景和意义

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

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

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

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

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

1.2. 国内外研究现状

当前市面存在多种品牌硬件钱包，虽然有部分声称对侧信道攻击做过防御，但并没有公布细节，所以没有第三方的评估对其安全性不得而知。在今年的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]中提出的，攻击者在非故障注入状态下进行一次加密并得到正确结果，再在注入故障的状态下再次进行加密并获得错误结果，比较两次的结果，可能得到某些敏感信息。

2.1. 椭圆曲线加密

本文以素域为例介绍椭圆曲线的一些基本概念。令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的安全性正是基于该原则。

2.2. ECDSA

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，则返回（“接受该签名”）；否则，返回（“拒绝该签名”）

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

2.3. 标量乘算法

在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] 

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

2.4. Width-w NAF算法

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。

2.5. 能量分析攻击与汉明重量模型

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

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

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

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

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

t=aHW(y)+b

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

3.1. 平台搭建

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

图1  测试平台实物图

3.2. 初步观测

我们采用串口调试助手，对芯片循环发送待签名数据，循环周期为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阶段的波形及其滤波波形

4.1. 简单能量分析介绍

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

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

4.2. 理论分析

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

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

算法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的值。

4.2.2. 采用Width-w NAF算法实现的标量乘

在传统的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

3：        Q=2Q

4：If k_i≠0 then

5：        Q←Q+P 

6： Return Q

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

在Width-w NAF算法中，当存在连续4个0以上的情况时，NAF_W (k)表示中存在超过w个连续的0。在这种情况下，攻击者通过波形可以恢复出k的一部分数值。

4.2.3. 抗简单能量分析的改进Width-w NAF算法设计

在Talosec钱包的设计中，根据文献[17]提出的方案对Width-w NAF算法进行改进，以窗口为4为单位，对k进行分组，每组数据组成的一个4比特二进制数作为数组u的一个元素，若u[i]为0，则将u[i]赋值为1 ̅…1 ̅(此处数值表示有误，如想了解请查看附件中的正确表示，详细解释可参考文献[17])，且在u[i+1]减去相应数值。这种方法可以保证在使用根据这种方法构造出的NAF数制表示的k在计算标量乘时为固定操作，即每计算4个倍点，计算一个点加操作。以此避免简单能量分析的攻击。

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

算法7：抗SPA的width- NAF算法

输入：w,d

输出：d_w [n],d_w [n-1],…,d_w [0]。

1：For i = 0 to ⌈n/w⌉

2：        u[i] ←d mod 2^w 

3：        If u[i]= 0…0 then

4：               u[i]←1 ̅…1 ̅  and d←d+2^w 。

5：        d←d-u[i], d←d/2

6：        d_w [iw]=u[i],d_w [iw+1]=…=d_w [iw+w-1]=0。

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

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

然后我们使用Width-w NAF计算标量乘法，该算法与采用传统Width-w NAF算法的标量乘算法完全相同。

4.2.4. 抗简单能量分析的改进Width-w NAF算法实现

Talosec钱包的标量乘算法模块采用4.2.3节介绍的改进的Width-w NAF算法实现，其中w为4，对于一个256比特的k，理论上采用64层循环，每个循环内在雅可比坐标系下实现4次倍点操作和1次点加操作，处理4比特的数据。由于该流程的每一步均为固定操作，并未泄露任何和操作数有关的信息，所以即使攻击者可从波形上区分出点加、倍点操作，该标量乘算法理论上能够抵抗简单能量分析。

查看在雅可比坐标系下的倍点操作和点加操作的实现，可以对比发现它们的不同，点加操作明显要比倍点操作要复杂。

体现到波形上，如果能通过分析观察得到标量乘部分的波形，应该能够通过数据处理分析区分出倍点和点加两种不同的操作，理论上来讲倍点操作应该消耗的能量较少，点加操作消耗的能量较多，并且每隔4个倍点应该有一个点加。

4.3. 实验分析

根据分析可以得出在大约0.6秒时结束标量乘算法，我们在10MSa/s采样率下采集1秒波形，得到图7所示波形。

图7  包含标量乘部分的波形

我们对波形分别进行参数为2000、5000、10000的平滑滤波，并进行波形的部分放大，分别得到图8、图9、图10所示结果。

图8  滤波参数为2000的标量乘部分的波形

图9  滤波参数为5000的标量乘部分的波形

图10  滤波参数为10000的标量乘部分的波形

观察图8和图9的滤波结果，对滤波后的波形进行放大，可以通过观察得到每四个起伏较小的波形后面跟随一个起伏更大的波形。根据统计，在滤波之后两个较大尖峰之间，共有252个起伏更小尖峰，63个起伏更大尖峰，估计起伏较大的尖峰为点加操作，这与之前我们分析代码得到的4个倍点跟随1个点加的结论完全相符。

根据分析，我们可以得到以下结论：

（1）攻击者可以通过放大、滤波等手段从波形上区分出点加和倍点。

（2）由于该钱包中标量乘kP的实现采用了固定窗口的标量乘算法，即使攻击者能够区分出点加和倍点，它天然可有效抵抗SPA分析。

5.1. 相关能量分析介绍

相关能量分析是Brier等人在CHES 2004上提出的[18]。通常来讲，相同操作的操作数不同，对应的能量也不同。攻击者在已知算法的情况下，如果能够多次驱动被攻击设备进行加密，并且和密钥进行运算的操作数每次都不同且已知的情况下，攻击者可以通过对采集到的波形进行统计分析的方法进行密钥恢复。

人们将波形的归结为几种模型：汉明重量模型、汉明距离模型、零值模型等。在软件实现的情况下，波形通常符合汉明重量模型，有关汉明重量模型的介绍我们已经在2.5中给出介绍。我们下面以汉明重量为例简单介绍一下相关能量分析的方法。

在相关能量分析中，攻击者会对波形点t和中间值汉明重量HW(y)进行相关性检测，所用公式如下：

ρ=(cov(t, HW(y)))/(σ_t σ_(HW(y)) )=(E[(t-t ̅)(HW(y)-(HW(y)) ̅)])/(σ_t σ_(HW(y)) ).

该公式的数学意义为：若两个向量之间趋向于完全正相关，则ρ趋向于1；若负相关，则ρ趋向于-1；若不相关，则ρ趋向于0。

在做相关能量分析时，通常有两个步骤，第一步采集对应敏感中间值不同的多条波形，第二步通过猜测密钥的方式进行密钥恢复。

对于我们采集到的加密过程中的波形来说，只有一部分是真正和我们需要的敏感中间值有相关性的，对于测评者来说，在密钥已知的情况下，可以通过中间值泄露分析的方法快速定位泄露位置。对于攻击者来说，如果能有一台可写密钥的与待攻击设备完全相同的设备，也可以通过中间值泄露分析的方法定位泄露位置，在已知泄露已知的情况下可以大幅减少进行密钥恢复阶段的计算量。

5.1.1. 相关能量分析的波形采集

攻击者随机选取N个明文{P_1,P_2,…,P_N}，加密M次，同时采集到M条波形。将采集到的包含进行敏感中间值运算的波形段记录下来。我们将M条波形记作{T_1,T_2,…,T_M}，其中每个条波上有N个点，可以将其即做一个M行N列的波形矩阵，矩阵的第i行第j列的点t_ij 就表示第i条波形在第j时刻的能耗为t_ij 。

5.1.2. 已知密钥条件下的中间值泄露分析

我们知道必定存在一个时刻j，它对应的第j列波形{t_1j,t_2j,…,t_Mj}与M个明文加密过程中敏感中间值y的汉明重量{〖HW(y〗_1),HW(y_2),…,HW(y_M)}之间存在显著的相关性。通过遍历j(1<j<N)，计算{t_1j,t_2j,…,t_Mj}和{〖HW(y〗_1),HW(y_2),…,HW(y_M)}的相关系数，可以得到N个相关系数，在这N个相关系中，应该有一个时刻的相关系数，明显高于其他时刻。这个时刻应该是在做和敏感中间值相关的运算。

5.1.3. 未知密钥条件下采用相关能量分析进行密钥恢复

（1）敏感中间值位置已知的情况

我们记泄露位置为j。首先猜测k=0，用猜测的k与已知的M个明文计算出猜测的中间值y，以及它们的汉明重量，命名为{HW(〖y^'〗_1 ),HW(〖y^'〗_2 ),…,HW(〖y^'〗_M )}。随后计算{HW(〖y^'〗_1 ),HW(〖y^'〗_2 ),…,HW(〖y^'〗_M )}与{t_1j,t_2j,…,t_Mj,}之间的相关系数ρ_0，作为正确密钥与错误密钥之间的区分器。

随后，猜测k=1，计算得到ρ_1；猜测k=2，计算得到ρ_2；以此类推，直到计算出ρ_255 。

若某个k猜错了，则由它计算出来的{HW(〖y^'〗_1 ),HW(〖y^'〗_2 ),…,HW(〖y^'〗_1000 )}必为杂乱无章的随机数，故ρ_k 必接近于0。反之，若某个k猜对了，则由它计算出来的{HW(〖y^'〗_1 ),HW(〖y^'〗_2 ),…,HW(〖y^'〗_1000 )}必等于{HW(y_1 ),HW(y_2 ),…,HW(y_1000)}，故ρ_k 必定显著远离于0。因此，最为凸显、或者说离0最远的ρ_k 所对应的k即为正确密钥。

（2）敏感中间值位置未知的情况

对于敏感中间值位置未知的情况，对于每种密钥猜测k，分析者需要对j个点分别计算一个ρ_k，从而形成一条相关系数曲线，我们记作rho_k 。若某条相关系数曲线rho_k 在某处较其它曲线有非常明显的凸显，则意味着它对应的密钥k为正确密钥。

5.2. 针对待测芯片的理论分析

在这一节中，我们对ECDSA的整个计算过程中可能存在CPA分析的步骤的代码进行分析，并找到设计漏洞。

5.2.1. 标量乘步骤的CPA分析

在针对标量乘运算kP开展攻击的过程中，若攻击者可以恢复k，那么在计算s=k^(-1) (e+dr)modq一步时，k^(-1) 相当于已知，在s、k^(-1) 、e、q均已知的情况下，攻击者很容易恢复得到私钥d的值。查看标量乘部分的代码，可以看到在代码中k的生成有两种标准的，通过分析我们得到，在该芯片中标量乘步骤可抗CPA分析，主要有以下原因：

对于k为完全随机的情况：k的生成采用硬件随机数发生器实现，每条波形采用的k不同，且攻击者无法自由选定P的值，这也就决定了攻击者不能通过采集不同P对应的曲线来恢复k。

对于采用RFC6979标准生成确定性k的情况：查看代码可以发现使用雅可比坐标计算点加和倍点，攻击者通过固定密钥和消息来固定k，如果雅可比坐标系采用固定的z，若理论上可能会泄露本次签名中k的信息。在实现代码中我们看到坐标轴z的生成是完全随机的，且采用硬件随机数发生器实现，这相当于运算过程中所有与坐标值x和y有关的中间值完全被掩码了，因此攻击者无法在这种情况下通过侧信道的方式得到任何有效信息。

5.2.2. 计算签名值kP步骤的CPA分析

使用ECDSA算法进行签名的过程中，需要计算签名s，在这一步中用到了私钥d，是计算其与签名结果的一个元素r的乘积，在这一步骤中，参与计算的是固定不变的私钥d，和每次变化且已知的签名值r。一个已知可变数与一个固定未知数做运算，这在理论上做CPA分析是可行的。

我们可以看到代码对256比特大数的定义如图11所示，两个256比特大数的乘法定义如图12所示。可发现代码中并未对两个256位大数的乘法进行防护。我们可以驱动钱包做多次签名并采集能量波形，对采集到的波形做相关能量分析。

图11  256比特大数的存储格式

图12  256比特大数乘法的计算方法

在密钥已知的情况下，我们对其进行中间值泄露分析。根据算法的具体实现方法以及待测设备处理器的位数，我们确定敏感中间值位数为32比特，共17个，即以res数组的元素为单位进行分析。

对于参与运算的数值，我们可以根据钱包签名返回值得到签名值r，同时在厂商处获取私钥d，并根据程序中提供的数据转换方式将十六进制表示形式转换为实际运算时采用的大数表示形式。

5.3. 实验分析

根据分析可以得到d×r待分析步骤在整体波形上对应的区间，我们在10MS/s的采样率下采集2万条相应区间的波形，图13为其中一条波形。

图13  d×r步骤对应的波形

我们可以如图14所示列出多条波形，可以看出波形的基本形状是对齐的。

图14  多条波形对比

选中波形的一个小区间进行放大，可以得到图15所示的对比图。

图15  多条波形对比的放大图

可以看出在波形上具有如图所示类似于三角形（大）形状的噪声，并且该噪声并未对齐，且上下浮动较大，会对波形产生较大影响。对于SPA来说，可以通过滤波的方式对去掉该噪声的影响，但是由于CPA分析的操作数耗时极短，且信号大小和三角状噪声相比是比较小的，所以如果滤波过度将直接滤掉我们需要的信号。

如果想要消除该噪声的影响，可以考虑先将噪声进行低通滤波，然后使用原始波形减去滤波后的波形，以尽量消除影响。在图16中，上图为原始波形，中图为多层小参数低通滤波的结果，下图为上图减去中图的到的波形。

图16  消除三角状噪声的影响

我们对图16中的三条波形进行横向放大，得到图17所示结果。可以看出我们可以基本消除掉规律的三角形噪声的影响，得到去噪后的波形。

图17  消除三角状噪声的影响的放大图

利用前面分析的中间值，我们对d×r进行泄露分析，可以得到图18所示的分析结果。

图18  d×r最低字节的中间值泄露分析结果

可以看到从始至终做中间值泄露分析得到的相关性的绝对值没有较大的波动，我们对此给出以下结论和猜测：

（1）采用CPA方法对d×r运算进行攻击实验，未恢复出有效信息。

（2）CPA无法恢复有效信息，并不意味着安全，因为此处理论上存在一阶信息泄露，即d×r中，d为固定未知密钥，r为可变已知签名值，二者相乘的过程未加入有效的抗侧信道攻击防护机制，因而理论上不抵抗一阶CPA攻击。我们猜测恢复不出有效信息可能是由于噪声过大。

关于噪声过大问题，要在此处进行一阶CPA攻击的实验验证，需要在此处进行下列修改：

（1）提高加密速度，使得测评过程所需时间更短，可采集更多波形进行分析。

（2）去掉三角形的噪声干扰。

（3）修改电路板，只采集芯片的能量消耗。

以上几点讨论主要聚焦于能量波形信噪比太低的问题，这是因为我们已经将波形经过了信号放大和1.9MHz低通滤波，但效果仍然不理想。如果上述3条难以实现，我们可以考虑换一个思路来讨论：我们建议在后面的工作中直接采集100万条波形并进行分析，如果100万条波形仍然无法得到明显信息泄露的话，我们就可以认为该产品是安全的。但是由于签名速度过慢，这个实验需要一定的时间。

除了简单能量分析和相关能量分析之外，其它侧信道分析方式对本钱包进行攻击的可能性给出理论分析：

（1）参考在[3]中作者提到的针对蒙哥马利阶梯算法的模板攻击，攻击者理论上也可对在k固定的情况下对标量乘步骤进行模板攻击。但钱包程序在使用雅可比坐标进行运算时用了随机化z坐标的对策，故可避免这种攻击。

（2）在使用改进的Width-w NAF算法实现标量乘时，由于钱包程序对分组值为0的情况进行了优化，故可以抵抗安全错误（safe-error）攻击。

（3）理论上，kP运算不能抵抗一类将点kP打到别的曲线上的故障攻击，这类故障攻击包括前面介绍的ZPA、RPA、弱曲线攻击等。当攻击者利用这些攻击方法恢复k后，即可通过推导计算出密钥d。

（1）在不考虑电路设计的情况下，我们对d×r步骤的实现过程理论分析，是存在CPA分析的可能的。我们在此给出改进方案：

由于

                                  s=k^(-1) (e+dr)modn

                                    =k^(-1) e+k^(-1) (dr)modn

                                    =k^(-1) e+(k^(-1) d)rmodn

在代码实现中，该钱包已经对k进行随机化，即在原始值上乘了一个完全随机的数值randk，所以我们可以先将完全随机且未知的k^(-1) 与私钥d相乘，再将其结果（这个结果也是随机且未知的）与签名值r相乘，由此避免计算d×r这一步骤，以消除CPA分析的理论可能性。

（2）对kP进行运算结束后，需要验证点kP是否还在当前的椭圆曲线上，以避免攻击者采用ZPA、RPA、弱曲线攻击等故障攻击来恢复k值。在不考虑效率的情况下，我们强烈建议采用蒙哥马利阶梯算法，或计算2遍kP的方法，来验证kP计算过程中是否发生了故障。

国际上现有理论研究表明，采用改进的Width-w NAF算法实现的标量乘算法可以抗SPA攻击。同时项目也采用了随机化策略对模版和安全错误攻击进行防御，但仍然存在CPA和故障攻击的可能。在我们的建议下Talosec项目组已经对这些可能受攻击的算法点进行了改进，同时也在协议级别对整个安全流程做了加固，我们会在Part2对这些改进后的算法和协议进行进一步的测试和分析。尽请期待。

[1] Riscure. Glitching the KeepKey hardware wallet.

https://www.riscure.com/blog/glitching-the-keepkey-hardware-wallet/, 2019.

[2] Coron, J.: Resistance against Differential Power Analysis for Elliptic Curve Cryptosystems. In: Koc, C¸ K., Paar, C. (eds.) CHES 1999. LNCS, vol. 1717, pp. 292–302. Springer, Heidelberg (1999)

[3] Medwed, M., Oswald, E.: Template Attacks on ECDSA. In: Chung, K.-I., Sohn, K., Yung, M. (eds.) WISA 2008. LNCS, vol. 5379, pp. 14–27. Springer, Heidelberg (2009)

[4] Kocher, P.C., Jaffe, J., Jun, B.: Differential Power Analysis. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 388–397. Springer, Heidelberg (1999)

[5] Homma, N., Miyamoto, A., Aoki, T., Satoh, A., Shamir, A.: Collision-based power analysis of modular exponentiation using chosen-message pairs. In: Oswald, E., Rohatgi, P. (eds.) CHES 2008. LNCS, vol. 5154, pp. 15–29. Springer, Heidelberg (2008)

[6] Fouque, P.-A., Valette, F.: The Doubling Attack – Why Upwards Is Better than Downwards. In: Walter, C.D., Koc, C, K., Paar, C. (eds.) CHES 2003. LNCS, vol. 2779, pp. 269–280. Springer, Heidelberg (2003)

[7] Goubin, L.: A Refined Power-Analysis Attack on Elliptic Curve Cryptosystems. In: Desmedt, Y.G. (ed.) PKC 2003. LNCS, vol. 2567, pp. 199–210. Springer, Heidelberg (2002)

[8] Akishita, T., Takagi, T.: Zero-Value Point Attacks Elliptic Curve Cryptosystem. In: Boyd, C., Mao, W. (eds.) ISC 2003. LNCS, vol. 2851, pp. 218–233. Springer, Heidelberg (2003)

[9] Kmmerling, O., Kuhn, M.G.: Design principles for tamper-resistant smartcard. processors. In: USENIX Workshop on Smartcard Technology – SmartCard 1999, pp. 9–20 (1999)

[10] Yen, S.M., Joye, M.: Checking Before Output Not Be Enough Against Fault-Based Cryptanalysis. IEEE Trans. Computers 49(9), 967–970 (2000)

[11] Joye, M., Yen, S.-M.: The Montgomery Powering Ladder. In: Kaliski Jr., B.S., Koc¸, C¸ K., Paar, C. (eds.) CHES 2002. LNCS, vol. 2523, pp. 291–302. Springer, Heidelberg (2003)

[12] Biehl, I., Meyer, B., Mu¨ller, V.: Differential Fault Attacks on Elliptic Curve Cryp- tosystems. In: Bellare, M. (ed.) CRYPTO 2000. LNCS, vol. 1880, pp. 131–146. Springer, Heidelberg (2000)

[13] K. Koyama and Y. Tsuruoka, Speeding Up Elliptic Curve Cryptosystems using a Signed Binary Windows Method, Advances in Cryptology - CRYPTO ’92, LNCS740, pp.345-357(1992)

[14] Atsuko Miyaji, Takatoshi Ono, Henri Cohen, Efficient elliptic curve ex- ponentiation, Information and Communication Security (ICICS 1997), pp.282-291 (1997)

[15] I. Blake, G. Seroussi, and N. Smart, Elliptic Curves in Cryptography, Cam- bridge University Press (1999)

[16] Solinas, J. A., Efficient Arithmetic on Koblitz Curves, Design, Codes and Cryptography, 19, 195-249(2000)

[17] Okeya,K., Takagi,T., The Width-w NAF Method Provides Small Memory and Fast Elliptic Scalar Multiplications Secure against Side Channel Attacks,

CT-RSA 2003, LNCS 2612, pp. 328–343, Springer-Verlag Berlin Heidelberg 2003.

[18] E. Brier, C. Clavier, F. Olivier. Correlation Power Analysis with a Leakage Model. CHES 2004, LNCS, vol. 3156, pp. 16-29, Springer, Heidelberg (2004)

[招聘]苏州极光无限公司！——高薪招聘逆向、移动、漏洞挖掘工程师！

最后于 2小时前 被LunaYoung编辑 ，原因：