CN1640051B - 使具有秘密密钥的电子密码装置安全的方法 - Google Patents

Abstract

本发明的一个目的是用秘密或私有密钥，对密码电子装置或系统的所有n个值，消除“n阶DPA”攻击带来的风险。根据本发明的方法涉及一种用于使用密码计算过程的电子系统的安全方法，该密码计算过程使用秘密密钥。本方法包括为所述过程屏蔽至少一个临界函数的输入或输出中的中间结果。

Description

使具有秘密密钥的电子密码装置安全的方法

技术领域

本发明涉及一种用于使涉及密码算法的电子装置安全的方法，该密码算法使用秘密密钥。更精确地说，该方法旨在实现该算法的一种方案，该方案不易被一些类型的物理攻击—称为“高阶微分功率分析”破坏—试图通过研究该电子装置在计算运行过程中的耗电量来得到关于秘密密钥的信息。

背景技术

这里考虑的密码算法使用秘密密钥来根据输入信息计算输出信息；这可以是编码、解码、签名、签名检验、鉴权或者非抵赖(non-repudiation)运算。这些算法使得攻击者即使知道输入和输出，实际上也不可能演绎地推论出关于秘密密钥本身的任何信息。

因此，这是一个比传统上由“秘密密钥算法”或“对称算法”表达式指定的类别更大类别的问题。特别地，在本专利申请中描述的任何方法也适用于公开密钥算法或非对称算法，这些算法实际上有两个密钥：一个是公开的，另一个是私有的，不公开的，后一种私有密钥就是下文所述的攻击目标。

“功率分析”类型的攻击起源于一个事实，即在进行运算时，实际上除了输入和输出的简单释放，攻击者还需要得到其他信息，例如微控制器的耗电量或电路产生的电磁辐射。

微分耗电量分析是称为“微分功率分析(DPA)”的攻击类别的原理，通过用同一个密钥对许多计算所作的耗电量记录进行统计分析，能够获得关于该电子装置中包含的秘密密钥的信息。

在最简单的攻击，即称作“一阶DPA”或简称为“DPA”中，当没有可能的混淆时，攻击者记录当前的消耗信号并计算该信号在每一时刻的各个统计特性。这里我们考虑称为“高阶微分功率分析”，简称为HO-DPA的攻击，一般为“一阶DPA”的攻击：攻击者当前计算在几个不同时刻取出的耗电量的联合统计特性。更确切地说，一个n阶DPA攻击考虑消耗信号的n个值，对应于在密码算法的计算过程中出现的n个不同的中间值。攻击检测到的中间值在下文中将称为临界信息。

作为非限制的例子，考虑DES算法(数据加密标准)的情况，在1994年的FIPS PUB 46-2，“数据加密标准”中对此进行了说明，上面提到的文档在此引入作为参考。

DES算法运行16个步骤，即16轮(见图2)。在16轮的每一轮中，进行一个32位的变换f。变换f使用从6位到4位的8个非线性变换，在一个称为代替盒(S-box)(图2中的S)的表中编码每个变换。

在DES上的二阶DPA攻击可以执行如下步骤：

第一步，在第一轮为1000次DES计算进行消耗测量。将E[1]，...，E[1000]记录为这1000次计算的输入值。将C[1]，...，C[1000]记录为进行这些计算时测得的耗电量的1000个相应曲线。

第二步，我们假设计算中出现两个位(为临界信息)，其值分别为b₁和b₂，并且使得等于在第一轮从第一个代替盒中输出的第一输出位的值b。这里，指定为逐位“异或”函数。假设对应b₁的耗电量曲线点和对应b₂的耗电量曲线点之间的时间间隔为δ。则另一个曲线C_δ[i]与每个曲线C[i](其中i为等于1，2，...，1000的连续整数)相关，曲线C_δ[i]等于C[i]与通过沿X轴转换δ值从C[i]得到的曲线之间的差值。1000个C_δ[i]曲线的平均值CM曲线也可计算出来。

第三步，容易看出b只依赖于秘密密钥的6位。攻击者对这6位进行推测。他根据那6位和E[i]计算出期望的b的理论值。这样就允许将1000个输入E[1]，...，E[1000]分为两类：导致b＝0的输入和导致b＝1的输入。

第四步，对与第一类(或第二类)，即，b＝0(或b＝1)，的输入有关的C_δ[i]曲线的CM’(或CM”)平均值进行计算。如果CM’和CM”显示出很大的差别，就认为为该密钥中的6位取的值，以及对δ值的选择都是正确的。如果CM’和CM”显示没有大的差别，从统计的意义上说，即，没有差别明显地高于测量噪声的典型偏移量，则对该6位的另一种选择重新启动第二步。如果对该6位密钥的选择都是无效的，则以另外一个δ选择值重新启动步骤3和4。

第五步，用“异或”出自第二个代替盒的两个位重复执行步骤2，3和4，然后是第三个代替盒，...，直到第八个代替盒。最后可以如此得到秘密密钥的48位。

第六步，通过全面搜索可以找到8个剩余位。

理论上，n阶DPA既不需要了解每条指令的各自耗电量，也不需要了解每条指令的时间位置。这同样适用于当估计到攻击者知道一些算法输出以及相应的消耗曲线时。这仅仅基于以下的基本假设：

在算法计算过程中出现一组n个中间变量，如知道的几个密钥位，实际上少于32位，使得能判断两个输入以及两个输出对这n个变量的已知函数是否得到相同的值。

使用代替盒的所有算法，例如DES，潜在地容易受到“高阶DPA”的攻击，作为常见的实施例模式，包括那些设计成对抗“一阶DPA”攻击的模式，通常保持在上面提到的假设下。

实际上，计算装置还需要找到(通过全面搜索或了解其它信息，例如密码算法实施例的细节)对应于所考虑的n个变量的消耗曲线点之间的时间间隔。

本发明的一个目的是对所有组合的所有n个值，或带秘密或私有密钥的密码电子系统消除“n阶DPA”攻击带来的任何风险。

本发明的另一个目的是为密码电子系统给予保护，如上面提到的假设不再被验证，即，没有一组n个中间变量的已知函数依赖于对秘密或私有密钥的容易得到的子集的了解，因此“高阶DPA”攻击不起作用。

发明内容

本发明涉及一种用于包括处理器和存储器的电子系统的安全方法，该电子系统使用秘密密钥实现存储在存储器中的密码计算过程，该方法的特征在于，包括屏蔽用处理器执行的所述过程的至少一个临界函数的输入或输出中间结果，使得临界函数分别在输出给予或在输入接收未屏蔽的中间结果。

附图说明

通过参考附图阅读下面的对根据本发明的方法实施例以及作为非限制例子给出的适用于本实施例的电子系统的实施方式的描述，将了解本发明其它目的、优点和特征，其中：

图1a和1b示出了根据本发明的方法的两种类型的替换函数；

图2示出了典型的DES算法的一轮；

图3a至3e示出了适用于根据本发明的方法的DES算法的每种类型的可能的轮；

图4是适用于根据本发明的方法的DES算法的自动执行图。

具体实施方式

根据本发明的方法的目的在于保护使用带秘密密钥的密码计算过程的电子系统，例如板上系统，如芯片卡。该电子系统包括一个处理器和一个存储器。密码计算过程结合到存储器中，例如所述系统的ROM类型存储器。所述系统的处理器使用存储在存储器的秘密区域的秘密密钥执行该计算过程，例如E2PROM类型的存储器。

根据本发明的方法包括屏蔽中间结果，该中间结果构成在计算过程中得到的作为函数的输入或输出的临界信息，该函数此后称为临界函数。

本方法用一个作“同样的”计算但是输入或输出数据被修改的替换函数替换临界函数。

如图1a和1b所示，进行n位到m位计算(通过一连串基本运算的计算，查表...)的任何f函数被一个新函数p代替，函数p由函数f与另一个函数g(从n’位到n位)(图1a)或函数h(从m位到m’位)(图1b)组成，函数g在函数f之前执行，函数h在函数f之后执行；因此，本方法在计算中用(g→f)或(f→h)替换了f。

根据所示的例子，g和h是“异或”形式的数据屏蔽运算。函数p占用输入被g屏蔽的数据或输出h被屏蔽的数据。

本说明书中的词“mask(屏蔽)”意思是用一个不公开的函数(内部的，卡的使用者不知道的)，例如一个使用未知数的函数，进行变换。

在计算过程中屏蔽第一临界函数出现在用函数h输出中；在计算过程中屏蔽最后一个临界函数出现在用函数g输入中。以这种方式，计算过程在输入中接收并在输出中给予未屏蔽的数据：对外界来说屏蔽是清楚的。一个想对系统进行DPA类型攻击的人不知道产生可探测信息的中间结果被屏蔽，因此在不了解原因的情况下他不可能从结果中得出任何结论。

应注意，函数g的输入数据(和函数h的输出数据)的尺寸不必与函数f的尺寸相同。

本发明有两方面：变换计算过程本身(如何包含一个修正函数)以及修正函数的计算模式(例如，如果它基本上是一个表的入口，则建立新表的方法)。

以下描述说明本发明的DES算法的一个应用。首先，示出第一个简化易懂的例子，便于接下来研究由此第一个例子直接产生的各种改进。

根据本发明的方法分别解决了两个问题：

怎样安排使用修正的代替盒的DES，以及

怎样构成这些代替盒。

下面参考图2，3a至3e和图4说明在第一个简化例子中安排使用修正的代替盒的DES。

首先考虑的是DES的第i轮(图2)。修正典型的DES的代替盒以处理屏蔽数据。然后考虑有32位的任意值的α。定义两个新函数，48位到32位变换的S’₁和S’₂为：

S’₁(x)＝S(x xor E(α))           对任何32位的x

S’₂(x)＝S(x)xor P^-1(α)           对任何32位的x

然后定义两个函数f’_1，Ki和f’_2，Ki，它们类似于函数f_Ki，但是使用S’₁和S’₂盒代替了S盒。

这两个新函数允许f’_1，Ki通过一个以非屏蔽值开始的α得到一个屏蔽值，对于f’_2，Ki执行相反运算。

图3a至3e示出通过使用屏蔽值，或不通过α和各个盒(S_Ki，S’_1，Ki或S’_2，Ki)得到的DES(A至E)的每一轮的所有图表。为了更清楚说明，用虚线表示屏蔽数据，而用实线表示非屏蔽数据(正常数据)。

图4示出可能得到的整个轮顺序，用符号表示为自动执行。如前所述，为了以非屏蔽数据离开和到达，起始状态是A或B，而结束状态是A或E。

因此可能用序列IP-BCDCDCEBCDCDCDCE-IP^-1执行一个完整的DES(16轮)。从消息M开始，该方法能得到一个常见密码(用序列IP-AAAAAAAAAAAAAAAA-IP^-1得到的密码)，该密码进出没有暴露。

有许多有效的组合；一些组合甚至使得能用这些被屏蔽的轮之间的正常轮(A型)屏蔽第一轮和最后一轮；例如：IP-BCEAAAAAAAAAABCE-IP^-1。

根据本发明的改进，用基于这些轮的不同掩码屏蔽数据。采用上面使用的轮符号(A，B，C，D和E)，加上一个下标(α，β，γ，...)，以符号表示在屏蔽中使用的32位掩码。由此可以看出，在上面的简化例子中B轮写作B_α。还应注意，A轮不需要用掩码值作下标，因为不涉及掩码。在这样的一般化例子中，根据以下序列实现DES：

IP-B_αC_αD_αC_αD_αC_αE_αB_βC_βD_βC_βD_βC_βD_βC_βE_β-IP^-1

以这种方式，这些轮，特别是对攻击敏感的第一和最后一轮，被独立的掩码保护。

为了实现上面提到的计算，有必要建立S，S’_1，α，S’_2，α，S’_1，β，S’_2，β类型的代替盒。

根据本发明在本方法中使用的各种修正的代替盒是基于下面的公式以安全的方式生成的：

S’_1，α(X)＝S(x xor E(α))

S’_1，β(X)＝S(x xor E(β))

S’_2，α(X)＝S(x)xor P^-1(α)

S’_2，β(X)＝S(x)xor P^-1(β)

所述公式根据下面给出的基本运算被划分：

提取一个随机值(如α，β...)；置换秘密值的位(如E(α)，P^-1(β)...)；

执行一个值(如p^-1(α))与对应于代替盒的常见值(输入或输出)的数值表的异或运算；

基于下面的算法选取一个n位的随机值(对于DES，n＝32)。

使用本方法的系统包括一张n个8位字节的表“t”，和一个8位字节的称为“rand”的未知数据源。该算法的执行如下所示：

For i from 0 to n-1：t[i]：＝rand ％2

For i from 0 to m-1：permute t[rand％n]and t[rand％n]

其中m是一个基本上大于等于n的数。

“％”是模运算或者整个除法的余数。

需要的结果是表t中包含的一连串的n位。

根据第一方案，本系统包括一个n/4个8位字节的表t。

For i between 0 and n/4-1：t[i]：＝rand

For i between 0 and m：Permute t[rand％(n/4)]against t[rand％(n/4)]

其中m是一个基本上大于n/4的数。

结果是表t中每一个n/48位字节中的头四位的链接。

根据第二方案，根据第一方案使用n/2，n/3，n/8或任何n的分量再次做该算法。

根据第三方案，不是以随机方式交换数据组(case)，而是随机选择一个数据组，并与一个随机值的异或运算相加。

将来自一个秘密值的n位置换为m位(在DES情况下：在置换p^-1(β)中：n＝48且m＝32)，在置换E(α)中：n＝m＝32)基于以下算法。

在说明的例子中，希望将标记n位“in”的表置换成标记m位“m”的表；该系统包括一张含有m个值的“temp(临时)”表(每个情况可包含值n-1)。

在临时表中建立一个数字0，1，2，...，m-2，m-1的置换。

For i from 0 to m-1：out[V[temp[i]]]：＝in[temp[i]]

实际上，以随机方式逐位进行置换是一个问题。

根据第一方案，置换不是逐位进行，而是每次置换k位，所有置换都是以随机方式。

根据第二方案，也可以在表V和/或在输入表和/或输出表中加上伪(dummy)值。因此，如果8位字节用于存储一个位，则可以使用未知数填满其它的“空”位。

异或运算的实施例包括将一个n位的值(如P^-1(α))加到m个值的表t中。

在输出表的8位字节上以及在这些8位字节的位上同样可以以随机方式执行运算。

根据一种方案，也可以在α的位和表t中加上伪值。

根据本发明的方法，在没有用密钥建立代替盒时，使用一个非公开的函数进行屏蔽。当计算过程运行时，不使用掩码。因此，根据本发明的方法能保护电子系统抵抗使用甚至不了解的掩码的任何攻击。

应该强调的是，可以使用任何其它类型的提取和置换来建立修正的代替盒。

另外，基于所述的三种运算建立代替盒可以通过任何其它类型的形式实现，特别是与本说明书中列举的专用于DES的代替盒不同的另一种形式。

Claims (6)

1.一种用于使用密码计算过程的电子系统的安全方法，该密码计算过程使用秘密密钥，该方法的特征在于，包括利用一个修正的代替盒屏蔽所述过程的至少一个临界函数的输入或输出中的中间结果，使得该临界函数分别在输出中给予或在输入中接收未屏蔽的中间结果，其特征还在于，包括一个用于替代所述过程的临界函数的替换函数，该替换函数执行同样的计算但在输入或输出中结果被屏蔽，其中，基于以下运算建立对于输入结果被屏蔽的替换函数：

利用使用者不知道的内部屏蔽函数的屏蔽运算；

与临界函数执行相同计算、但使用已被执行了所述屏蔽函数的结果的运算。

2.根据权利要求1的方法，其特征在于，包括以随机方式顺序排列屏蔽函数的运算。

3.一种用于使用密码计算过程的电子系统的安全方法，该密码计算过程使用秘密密钥，该方法的特征在于，包括利用一个修正的代替盒屏蔽所述过程的至少一个临界函数的输入或输出中的中间结果，使得该临界函数分别在输出中给予或在输入中接收未屏蔽的中间结果，其特征还在于，包括一个用于替代所述过程的临界函数的替换函数，该替换函数执行同样的计算但在输入或输出中结果被屏蔽，其中，基于以下运算建立在输出中数据被屏蔽的替换函数：

与临界函数执行相同计算但结果将被屏蔽的运算；

利用使用者不知道的内部屏蔽函数的屏蔽运算。

4.根据权利要求3的方法，其特征在于，包括以随机方式顺序排列屏蔽函数的运算。

5.一种电子系统，包括用于存储使用秘密密钥的密码计算过程的装置，用于执行所述计算过程的装置，该电子系统的特征在于包括由修正的代替盒组成的、用于屏蔽所述过程的至少一个临界函数的输入或输出中的中间结果使得临界函数分别在输出中给予或在输入中接收未屏蔽的中间结果的装置，其特征还在于，包括一个用于替代所述过程的临界函数的替换函数，该替换函数执行同样的计算但在输入或输出中结果被屏蔽，其中，基于以下运算建立对于输入结果被屏蔽的替换函数：

利用使用者不知道的内部屏蔽函数的屏蔽运算；

与临界函数执行相同计算、但使用已被执行了所述屏蔽函数的结果的运算。

6.一种电子系统，包括用于存储使用秘密密钥的密码计算过程的装置，用于执行所述计算过程的装置，该电子系统的特征在于包括由修正的代替盒组成的、用于屏蔽所述过程的至少一个临界函数的输入或输出中的中间结果使得临界函数分别在输出中给予或在输入中接收未屏蔽的中间结果的装置，其特征还在于，包括一个用于替代所述过程的临界函数的替换函数，该替换函数执行同样的计算但在输入或输出中结果被屏蔽，其中，基于以下运算建立在输出中数据被屏蔽的替换函数：

与临界函数执行相同计算但结果将被屏蔽的运算；

利用使用者不知道的内部屏蔽函数的屏蔽运算。

Images