针对NTRU 公钥密码算法的计时分析研究

陈财森，蔡红柳，陈 平，邓柳于勤，于 茜

（1.装甲兵工程学院 科研部，北京100072；2.装甲兵工程学院 信息工程系，北京100072；3.装甲兵工程学院 基础部，北京100072）

0 引 言

密码学分析学家对NTRU［1］提出了各种各样的攻击，例如穷举攻击、碰撞攻击、多次传输攻击和基于格攻击等，但是这些攻击方式都是试图从数学的角度破解密钥，实现难度极大甚至不可行。以Kocher为代表的密码分析学家提出了一种从密码实现角度出发的破解方式，通过获取密码加解密执行过程中所泄露信息推算出密钥的攻击方式，称之为旁路攻击［3］，其中泄露的信息包括消耗的时间、功耗、电磁或故障信息等。计时攻击［4，5］是旁路攻击的一种，指攻击者通过测量密码算法执行过程中消耗的时间信息推算出密钥的一种攻击方式，由于不需要特殊的设备且不需与攻击目标接触，具有操作简单、可行性高的特点，是目前旁路攻击研究领域的热点之一。

本文以NTRU 算法为研究对象，介绍算法实现加解密的原理以及密钥参数的选择，分析算法执行的时间踪迹，对其旁路安全性进行分析。研究结果发现NTRU 算法实现过程中，基于不同的输入所调用哈希函数的次数存在差异，这些差异信息会导致执行时间的差异，从而存在泄漏密钥信息的安全威胁。首先给出针对基于哈希函数调用数目变化的计时攻击算法，然后针对一般NTRU 算法和密钥形式为f＝1＋2F 的实现算法，分别给出相应的计时攻击算法和验证算法，最后依据存在的安全漏洞给出抵御计时攻击的措施。

1 NTRU 算法及其旁路安全性分析

1.1 NTRU 算法介绍

为了便于理解NTRU 算法的旁路安全性分析，下面简单介绍算法的密钥产生、加密操作、解密操作以及算法实现原理。

1.1.1 密钥产生

与其它公钥密码算法不同，NTRU 是基于商环R ＝Z［X］／（XN－1）上运算的算法。环R 中的乘法定义为卷积“＊”（convolution multiplication）：设f，g ∈R。

那么定义如下操作

其中f＊g 中xk系数为

称f＊g是模q 的，指f，g 及f＊g中所有单项式系数均为模q的，即将f，g 及f＊g 视作R ＝Z［X］／（XN－1）的元素。可证明当q 是素数时，R 具有可逆性，即对F ∈R，存在F＊∈R 满足：F＊F＊≡1（modq）。

同时定义两种特殊类型的多项式：

最后得到NTRU 的私钥f 和g，而公钥h计算如下

1.1.2 加密操作

加密使用了两个哈希函数，表示为G 和H。实际中依据要求的安全等级，经常以多种方式使用SHA－1 或者SHA－256 （secure hash algorithms）。加密步骤如下［7］：

（1）选择加密的明文M，将其编码为βN 形式：M ∈βN ；

（2）利用哈希函数G 随机填充M，产生严格符合dr的二元多项式：r＝G（M）∈βN（dr）；

（3）计算m′，表示为：m′＝M ⊕H（r＊hmodq）。

最后获得密文e：e＝（r＊h＋m′）modq。

1.1.3 解密操作

NTRU 解密操作同样采用两个哈希函数G 和H。具体操作步骤如下：

（1）解密算法首先恢复m′：m′＝（（f＊emodq）modp）＊modp；

（2）恢复明文M：M ＝m′⊕H（e－m′modq）；

（3）最后进行验证，一旦计算出M 和m’就可以重新构造出盲化值r：r＝G（M），验证 （m’，e）是否为NTRU加密结果：e＝（r＊h＋m′）modq。

1.1.4 算法实现原理

为了更好地理解整个算法函数是如何工作的，本节介绍解密原理。我们计算的多项式a满足

由于选择的多项式p＊r＊g＋f＊m′中f，g，r，m′等系数的绝对值都很小，所以p＊r＊g＋f＊m′系数的绝对值相对于q也很小，由于q ≥p，因此可以认为p＊r＊g＋f＊m′的系数已在（1，q）之间，因而有：a ＝p＊r＊g ＋f＊m′。

1.2 NTRU 算法的旁路安全性分析

从旁路安全性分析的角度出发，简单分析NTRU 算法执行过程可能存在的安全漏洞。由Paul Kocher提出的计时攻击主要利用密码设备运行时的时间特征，推导出私钥的一种攻击方式。类似于窃贼通过观察他人保险柜拨号盘的时间长短来猜测密钥［3］。

NTRU 算法实现过程中，由于G 函数调用SHA 的次数依赖于G 的输入，通过测量解密执行时间，攻击者可能观测到关于G 函数的输入，这样可获得关于私钥f 的泄露信息。哈希函数调用请求由信息／密文对 （m′，e）创建的随机值r的次数对于不同的信息对可能不同。每一次哈希函数调用需要的总时间也不一样，因此攻击者可尝试检测出解密密文e时调用多少次哈希函数，这样给攻击者创造了破解私钥的机会［6，7］。

2 针对一般NTRU 算法的计时攻击算法

2.1 执行时间踪迹分析

为了更好地解释计时攻击，定义了一个时间踪迹的概念。第1.2节中调用的随机值r，每次构造它都需要使用哈希调用信息对 （m′，e），针对不同的信息对调用的次数不同，因此哈希调用的时间存在差异。依据这一点差异，攻击者可能通过检测时间差异判断解密密文e过程中调用哈希函数的次数。实际上，存在一个数K，计算r时调用哈希函数的次数不是K 就是K＋1［6］。同时根据解密算法，定义对于每一个信息对 （m′，e）的输出为

定义β（m′，e）∈｛0，1｝，则当构造r（m′，e）时最多调用K 次哈希函数，则设为0，如果调用次数多于K 则为1，可以循环得到（Xim′，Xie），i＝0，1，…。最后给出时间踪迹的完整定义，它的二进制表示形式如下

时间踪迹表示对于每一个信息对 （m′，e）所请求的哈希调用次数，依据这一点，我们可以得知两对信息对具有相同时间踪迹的概率和分别调用哈希函数的次数。设P表示对于一个随机信息对 （m1’，e1）最多请求K 次哈希调用的概率，则1－P 表示其它随机信息对 （m2’，e2）最少请求K＋1次哈希函数调用的概率。如果P值足够大，那么两个信息对具有相同的时间踪迹的概率相当小。更准确的描述如下

式 （1）推导过程为：已经知道时间踪迹的二进制表示长度为N。假设P是第i个位置为0概率，1－P为第i个位置为1的概率。那么对于两个随机的时间踪迹第一个位置为相同值的概率为

如果两个时间踪迹是完全一样的话，那么它们所有位置的值都是一样的 （0或者1）。因此我们有

时间踪迹是针对NTRU 算法计时攻击时密钥的一样表现形式。

2.2 基于哈希函数调用数目变化的攻击算法

为了更好地解释计时攻击原理，假设两个角色A 和B，他们之间相互交换信息，直到其中一个人决定扮演攻击者尝试获取另外一个人的私钥，这些都是通过计时攻击方式实现的。假设B 为攻击者，他先选择一个密文集合ε，表示为一个多项式mod q的集合。同时选择一序列代表性信息M，M 包含大多数A 构造的信息，即有如下方式

此外假设A 构造的信息中包含在集合M 中的概率非常大。在开始执行攻击的有效部分之前，B 对于每一个信息对 （M，ε）构造对应的时间踪迹表。换句话说，他构造了一个可查找的二进制表

攻击从B向A 发送一些随机的e∈ε开始。一旦密文被发送，B就开始测量A 解密它的时间。主要的思想是攻击者不需要关注他伪造的密文是否在不合格检测之后被拒绝。他唯一要做的事情就是检测时间信息。通过这些时间信息，攻击者能够推测哈希函数调用的次数。换句话说，他便得知形 式 如 下 的 值m′：｛（（f＊emodq）modp）＊（f－1modp）：e∈ε｝，其中 （p＝2）。

攻击者不知道m′（e）的值，只知道β（m′（e），e）的值，用来对比从A 获取的观测值与B先前构造的存储在表中的值。为此B在时间踪迹表中需要N－1 个项。其它值在发送如下的多项式之后获得

每一个密文发送之后攻击者获得β（m′（Xie），Xie）的值，for i＝0，1，2，…，N－1。

随机选取一项m′（Xie），由于得知m′（e）是均等的，给出m′（Xie）的适合表达式

因为所有Xi为0 或者1，把Xi移到公式的前面得：Xi＊（（f＊emodq）modp）＊（f－1modp），即Xim′（e）。

B 现在拥有（m′（e），e）的时间踪迹T（m′（e），e）。下一步要做的工作就是在先前构造的列表中寻找与之匹配概率较大的项。B 获取两个多项式e m′和A 解密e时获得第二个 多 项 式 m′。这 里 攻 击 者 只 需 要 计 算 m′＊f ≡（f＊emodq）modp，其中e和m′是已知的。

攻击者如何获取A 的密钥：私钥f 将依赖于e的特殊形式，例如，如果ε 得元素只是包含非常少的非零系数，那么等式m′＊f ≡（f＊emodq）modp 可能给出涉及f 系数与非零系数之间间隔的信息。接下来描述一个特殊集合ε，当密钥f形式为f ＝1＋2F 时，将导致实际的哈希函数计时攻击。

3 针对密钥形式为f＝1＋2F 的攻击算法

3.1 高精度计时技术

由于NTRU 算法执行速度快，运行时所需要的时钟周期数小，因此其它噪声对其真实执行时间的影响系数大，需要精度高的测量技术。系统定时器 （包括读取测量值所需要的时间在内）提供大约5 ms的精度，这对应500 Hz系统的2000多个脉冲。在高精度测量时，系统定时器是不适合的，这里需要用到Pentium 系统的处理器具有的时间戳计数器，执行RDSTC 指令，通过测量CPU 的时间周期来表示执行时间［9］。由于系统运行存在系统本身以及其它进程的干扰，影响测量执行时间的精确度，可以采用多次测量取平均值的方法。

另外为了克服二度运行的问题，能够得到精确的测量结果，需要多次测量执行时间。需要注意一点，每次运行必须是在相近的条件与相近的环境下执行的。但是这些条件和环境在现实中是无法满足的。磁盘高速缓存、CPU 的Cache、转换后被缓冲区 （TLB）与分支变化使得时间的测量复杂化，因为程序的重复运行极大地降低了运行时间。由于访问Cache时，会发生命中和失效两种情况，其中前者的访问时间会比后者的访问时间短，尽管时间差异不多，但是对于需要精确测量执行时间时，这仍然是不可忽略的。TLB同样类似的问题。最终我们利用文献 ［10］的建议，对多次测量的样本量进行排序，再取中间的1／3值的平均值，作为算法的执行时间。

3.2 攻击算法

从第1节中我们已经了解到在大多数情况下，参数p的值为2，这意味着q是奇数，也就是说私钥f具有如下的形式［8］：f＝1＋2F，对于一些二进制多项式F∈βN（dF）。

（1）首先选择一个值δ；

（2）设ε＝｛ei＝λ＋λXi：1≤i≤（N－1／2）｝且M ＝βN（0＜d ≤δ）；

（3）重新计算并保存所有的时间踪迹T（m′，e）；

（4）向A 发送Xjei，j＝0，1，…，N－1，并计算解密时间，确定时间踪迹T（m′（ei），ei）；

（5）查找候选值；

（6）通过结果值m′（ei）重构F。

我们还要从步骤 （2）找出m′（e）的可能值，因此分析A 的 解 密 过 程，得 知A 首 先 计 算［6］

因此对于a的第j个系数具有如下的形式

在执行a mod 2之后我们获得0或1的值，由于λ和q都是奇数，在约简步骤之后我们得到

那么可以更明确地定义m′（ei）为

这样就产生了关于F的部分信息

3.3 密钥验证

初始集合ε相对小的话可以减少重复计算。确认一个时间踪迹与攻击者数据库中的ei是高概率匹配的。但是如果发现时间踪迹是唯一的，那么B 可能需要检验它实际上已经确认的正确的ei。为此我们注意到如果把ei＝λ＋λXi解密为m′，那么设变换的形式为＝（λ＋2）＋λXi，or λ＋λXi，or…。

或者确实有许多多项式λ1＋λ2Xi，系数为λ1和λ2甚至整数接近于q／4并且满足λ1＋λ2＞q／2。B因此选择其中一个可能的，计算解密原始ei获得m′相应的时间踪迹T（m′，），然后重新提交重新计算时间踪迹。如果测量的结果和计算的时间踪迹匹配的话，那么他已经确认猜测m′。否则的话需要对做进一步的调整。

4 防御措施

从上文我们已经了解计时攻击是如何泄露NTRU 算法的私钥信息的，同时也知道这种攻击方式是基于对于不同的密文，可能需要调用不同次数的哈希函数的事实。尽管我们已经给出针对形式为f＝1＋2F的私钥的攻击算法，理论上可以假设对于大多数的密钥存在类似的攻击方式。

在掌握NTRU 实现算法计时攻击漏洞的基础上，给出相应的防御措施。攻击的漏洞是基于不同的密文解密时调用哈希函数的次数不一样。这里可以假设哈希函数调用的最大次数为Kmax，这种情况下一个随机密文需要少于Kmax次哈希调用，设为k次，使其再执行Kmax－k额外哈希函数调用。这种方式使得对于所有的密文调用哈希函数的次数一样，从而可以避免此类攻击。不过此种方式会降低算法的执行效率。另外一种方式是填充操作，将填充系数与哈希函数调用次数相混合，使其填充的每个位影响哈希调用次数的每个位。因为填充必须仔细考虑并顾及安全级别，例如有80位填充80位的安全，因此增加安全级别同时需要增加填充位。

5 结束语

本文介绍了NTRU 公钥密码算法加解密的工作原理，分析其算法基于简单的多项式乘法运算，与其它公钥密码算法相比较，具有较高的执行效率；同时对NTRU 算法的实现安全性进行了分析，指出其存在遭受计时分析的安全漏洞，结合旁路攻击的基本概念和原理，通过研究发现由于算法实现过程中由于哈希函数调用次数的不同会导致时间差异，给攻击者提供了攻击的可能性。分析了NTRU 算法实现的时间踪迹，给出针对一般NTRU 的计时攻击算法以及针对具体密钥形式为f＝1＋2F 的攻击算法。最后给出两种抵御计时攻击的措施，主要是基于消除哈希函数调用次数对输入值的依赖关系。

［1］Hermans J，Vercauteren F，Preneel B.Speed records for NTRU ［M］.Berlin：Springer Berlin Heidelberg，2010：73－88.

［2］Li J，Pan Y，Liu M，et al.An efficient broadcast attack against NTRU ［C］／／Proceedings of the 7th ACM Symposium on Information，Computer and Communications Security，2012：22－23.

［3］Venkateswarlu S，Teja G S，Deepa G M，et al.Breaking cryptosystem’s through cache based timing side channel attack［J］.International Journal of Dvanced Research in Computer Science and Software Engineering，2013，3 （5）：82－86.

［4］Chen C S，Wang T，Tian J J.Improving timing attack on RSA－CRT via error detection and correction strategy ［J］.In－formation Sciences，2013，232：464－474.

［5］Chen C S，Wang T，Kou Y Z，et al.Improvement of tracedriven I－cache timing attack on the RSA algorithm ［J］.Journal of Systems and Software，2013，86 （1）：100－107.

［6］Kamal A A，Youssef A M.A scan－based side channel attack on the NTRU encrypt cryptosystem ［C］／／Seventh International Conference on Toulouse：Reliability and Security.IEEE，2012：402－409.

［7］Zheng X，Wang A，Wei W.First－order collision attack on protected NTRU cryptosystem ［J］.Microprocessors and Microsystems，2013，37 （6）：601－609.

［8］Lei X，Liao X.NTRU－KE：A lattice－based public key exchange protocol ［J］.IACR Cryptology ePrint Archive，2013：718.

［9］Demme J，Martin R，Waksman A，et al.Side－channel vulnerability factor：A metric for measuring information leakage［J］.ACM SIGARCH Computer Architecture News，2012，40（3）：106－117.

［10］CHEN Caisen，WANG Tao，GUO Shize，et al.Research on trace drive instruction cache timing attack on RSA ［J］.Journal of Software，2013，24 （7）：1683－1694 （in Chinese）.［陈财森，王韬，郭世泽，等.RSA 踪迹驱动指令Cache 计时攻击研究 ［J］.软件学报，2013，24 （7）：1683－1694.］