一种基于探测集约减的掩码安全性验证方法

1.本发明涉及抗侧信道掩码防护领域，特别涉及一种基于探测集约减的掩码安全性验证方法，可用于验证抗侧信道掩码防护的安全性。


背景技术：

2.当今社会，密码算法和密码设备的应用十分广泛，在各个领域保护着数据的安全性。尽管密码算法有着极强的理论安全性，但在实际应用中，由于运行密码算法的密码设备会泄露敏感信息的物理特征，例如电磁辐射、声音等等。攻击者可利用这些物理信息进行差分能量分析、相关性能量分析攻击等侧信道攻击，从而将敏感信息恢复。
3.为了抵抗这类侧信道分析技术，不同的防护技术被提出，其中最有效的一项技术就是掩码技术。掩码技术基于秘密分割的门限思想，在理论上也有较强的安全性。对于复杂的密码算法，设计对应的抗侧信道掩码方案并非易事，由于设计者的疏忽，掩码方案可能仍然存在不安全之处。而手动对掩码方案中的每一个敌手可探测到的变量集合(探测集)进行手动分析是一项繁琐耗时且极易出错的任务，因此利用形式化等技术对掩码方案安全性进行自动化的验证具有重要的意义。
4.为了刻画掩码防护的安全性，不同的安全性概念被提出，其中应用最为广泛的两个安全性概念是探测安全性和强探测安全性。探测安全性可用于评估软件实现的掩码方案的安全性，敌手使用一根探针可以探测到一个变量的概率分布。相比于软件实现，掩码方案的硬件实现还需要考虑硬件电路中时钟毛刺现象的存在，因此敌手使用一根探针可以探测到一组变量的联合分布。敌手的攻击能力由其能使用的探针个数决定。敌手使用其探针所能探测到的变量集合称为探测集。对于给定掩码方案，若敌手所能探测到该掩码方案中的每一个探测集中的变量的联合分布均与秘密变量(敏感信息)统计独立，则该掩码方案是安全的。
5.为了证明掩码方案的强探测安全性，不同的技术被提出。roderick bloem等人提出了基于傅里叶展开的验证方法。该方法的原理是，若敌手所探测变量的傅里叶展开式中秘密变量集合的所有非空子集的傅里叶系数均为0，则秘密变量集合与该探测变量统计独立。由于直接计算傅里叶系数的开销较大，roderick bloem等人将傅里叶系数是否为0的问题编码为sat公式，通过sat公式是否有解来判断傅里叶系数是否为0。这种方法由于需要调用求解器，所以其开销很大。gilles barthe等人提出了基于程序语言和概率信息流分析的验证方法。该方法利用随机掩码与表达式之间存在的双射关系，将探测集中该表达式的每一处出现替换为该随机掩码。这种替换保留了掩码方案对应的掩码程序的语义，不会影响探测集中变量的联合分布。经过这种替换后，若最终探测集的表达式中不含有秘密变量，则这个探测集是安全的。这种方法效率较高，但是由于其使用嵌套的表达式，且在表达式替换不成功时会对表达式进行正则化，在验证某些复杂的掩码方案时会遇到栈溢出的问题从而无法完成验证。david knichel等人提出了基于robdd的布尔变量集合统计独立性验证方法。该方法为探测集和秘密变量集合中的每一个变量构建robdd，并利用robdd计算探测集
的任一子集和秘密变量集合的任一子集中的变量取值全部为1的概率和这两个子集中变量取值分别全部为1的概率乘积，通过验证这两个概率在不同的子集组合下总是相等来证明探测集和秘密变量集合的统计独立性。这种方法不会出现基于傅里叶展开的方法和基于程序语言和概率信息流分析的方法所出现的假阴性问题(即将安全的掩码方案判定为不安全)，但是由于其需要构建robdd，消耗的处理器和内存资源极大，存在性能不足的问题。


技术实现要素：

6.本发明的目的是，针对给定掩码方案，给出敌手通过探针探测到的探测集的约减方法，通过将这个探测集约减为空集，证明该探测集是安全的。若敌手所能探测到的所有探测集均可被约减为空集，则给定的掩码方案是安全的。本发明的方法是一种新的掩码安全性验证方法，能够高效地验证较为复杂的抗侧信道掩码方案的安全性。
7.实现上述目的的本发明的技术方案为，一种基于探测集约减的掩码安全性验证方法，该方法流程如图1所示，包括如下步骤：
8.1)对于给定包含若干门的硬件掩码方案，将其解析为有向无环图g。掩码方案中的门包括输入门、中间门和输出门。按是否为线性，中间门可分为线性门(异或门、同或门、非门、寄存器等)和非线性门(与门、或门、与非门、或非门等)。按照操作数的个数，可将中间门分为一元门(非门、寄存器等)和二元门(与门、或门、与非门、或非门、异或门、同或门等)。解析的过程为：将掩码方案中的每个门对应到图g的一个顶点n。具体而言，将掩码方案的输入门对应到图g中一个入度为0，出度可为任意值的顶点n；将输出门对应到图g中一个入度为1，出度为0的顶点n；将一元门对应到图g中一个入度为1，出度可为任意值的顶点n；将二元门对应到图g中一个入度为2，出度可为任意值的顶点n。一元门、输出门对应顶点n的入边指向其操作数对应的顶点n.lft；二元门对应顶点n的两条入边分别指向两个操作数对应的顶点n.lft和n.rgt。
9.2)计算图g中每个顶点n的辅助数据结构，即支持集、单路达掩码集合、完美掩码集合和探测集，分别用supp(n),unq(n),perf(n),on表示。根据输入是否为掩码电路敏感信息的分享值，输入门可分为分享门和随机门。以下行文中，\表示集合的差集运算，∪表示集合的并集运算，∩表示集合的交集运算，{
·
}表示由括号内的元素
·
构成的集合，表示空集，s∈s表示s是集合s的一个元素。掩码方案将敏感信息x分割为d+1(d≥1)个分享值x1,
…
,x
d+1
，分别对应到有向无环图中的d+1个顶点这d+1个顶点中第j个顶点对应辅助数据结构计算方式为：当1≤j≤d时，当j＝d+1时，分享值x
d+1
对应的顶点对应辅助数据结构计算方式为对应辅助数据结构计算方式为随机门对应于一个随机数r，在有向无环图中对应的顶点n的辅助数据结构的计算方式为supp(n)＝unq(n)＝perf(n)＝on＝{r}。一元门和输出门对应顶点n的辅助数据结构计算方式为supp(n)＝supp(n.lft)，unq(n)＝unq(n.lft)，perf(n)＝perf(n.lft)和on＝o
n.lft
。二元门对应顶点n的支持集和单路达掩码集合的计算方式为supp(n)＝supp(n.ltf)∪supp(n.rgt)，unq(n)＝(unq(n.lft)∪unq(n.rgt))\(unq(n.lft)∩unq(n.rgt))。二元线性门对应顶点n的完美掩码集合计算方
式为pref(n)＝pref(n.lft)∪perf(n.rgt)∩unq(n)，二元非线性门对应顶点n的完美掩码集合计算方式为二元门对应顶点n的探测集计算方式为：若n.lft和n.rgt对应的门均为寄存器，则on＝{n.lft}∪{n.rgt}；若n.lft和n.rgt对应的门都不为寄存器，则on＝o
n.lft
∪o
n.rgt
；若n.lft对应的门为寄存器，n.rgt对应的门不是寄存器，则on＝{n.ltf}∪o
n.rgt
；若n.lft对应的门不是寄存器，n.rgt对应的门为寄存器，则on＝o
n.lft
∪{n.rgt}。{n.lft}表示由顶点n.lft组成的集合；{n.rgt}表示由顶点n.rgt组成的集合。
10.3)按字典序从g中所有可能的d个顶点的组合中选取一个之前未被选取的d阶顶点组合nd(d为正整数)，nd包含顶点n1,
…
,nd，计算d阶探测集(其中表示nd中的第j个顶点对应的探测集)并进行步骤4)的检测。若g中不存在未被选取的d个顶点的组合，则给定的掩码方案是安全的，退出步骤。每一次都从g中的所有顶点中选取d个不同的顶点作为一个组合，并要求每次选取的组合与之前选过的组合不同。
11.4)若由步骤3)、5)、6)进入本步骤的探测集(等)为空集，进入步骤3)。若由步骤3)、5)、6)进入本步骤的探测集不为空集，则将其重命名为并根据变量的掩码情况将变量分为两两之间不共享掩码的若干子集即(其中表示不相交的集合的并集运算)，且对任意1《i≠j《t，有成立。从i＝1到t，计算的第i个探测子集(设包含p个顶点，分别用n1,
…
,n
p
表示)的完美掩码集合(设包含q个随机数，分别用r1,
…
,rq表示)。根据计算完美掩码矩阵若rj∈perf(nk)，则否则
12.5)从i＝1到t，若第i个子集不满足条件(rank()表示括号内矩阵的秩)和条件当1≤j≤p时,秩)和条件当1≤j≤p时,(其中perf(nj)表示第j个顶点nj的完美掩码集合；表示中除nj外其他顶点nk(1≤k≤q且j≠k)的支持集supp(nk)与完美掩码集合perf(nk)的差集的并集；表示中除外的其他探测子集中的顶点n对应的支持集supp(n)的并集)，则不服从独立均匀分布。若不可扩展则给定的掩码方案可能存在安全性问题，输出可能存在泄漏的d阶顶点组合nd，退出步骤。若该子集可扩展，则按拓扑序由大到小的顺序依次选取探测子集中的顶点nj(1≤j≤p)，若与交集不为空，则将扩展得到探测集并进入步骤4)对探测集进行约减。若1≤j≤p时，与交集为空，则将扩展得到探测集并进入步骤4)对探测集进行约减。
13.6)从i＝1到t，若第i个子集满足条件和条件当1≤j≤p时,(解释同步骤5))，则
服从独立均匀分布。从中删除得到探测集并进入步骤4)对探测集进行约减。
14.本发明的技术方案具有以下优点：
15.本发明可根据探测集的完美掩码矩阵高效判断某个探测集是否安全，相比于使用smt、robdd、sat等技术的方法，本方法的效率非常高，例如，对于aes加密算法的1阶dom掩码方案，1阶cms掩码方案，本方法的效率是使用robdd的方法的数千倍；可有效检测公开文献中不安全的掩码方案的泄露，例如本方法可以检测到2013年fse会议中发现的不安全掩码方案中的泄露点。
附图说明
16.图1为本发明的流程图。
17.图2为aes加密算法的1阶dom掩码算法片段数据流图。
具体实施方式
18.下面结合附图对本发明进行进一步详细描述，所举实例只用于解释本发明，并非用于限定本发明的范围。
19.首先以aes加密算法的1阶dom掩码方案中的片段(如下所示)为例介绍本发明中完美掩码矩阵的构造。
20.21.该掩码方案中，秘密变量为a,b,c,d,e,f,g,h，满足a＝a0+a1,b＝b0+b1,
…
,h＝h0+h1。为方便理解，上面所示的掩码方案，可转化为图1所示的数据流图，该数据流图为有向无环图。其中线性操作(异或、同或)用圆形表示，非线性操作使用方形表示，随机数使用红色圆形表示，秘密值的分量使用双圆形表示，随机数和秘密值的分量都存在寄存器中，存储中间变量的其他寄存器使用菱形表示。在强探测模型下，敌手若探测寄存器节点n
326
，则能获取与其相连的上一级寄存器集合中的探测变量的联合分布。在本实例中，敌手可探测到节点集合为由图2可知，其中n
19
的完美掩码为r0，未被其他探测变量使用，故将探测集划分为两个子集和和其中的完美掩码矩阵为(1)，秩为1，等于变量个数，故服从独立均匀分布，可从中删除。因此接下来对进行约减。
22.中的8个探测变量可表示为
[0023][0024]
为了确定每个节点的完美掩码，将a1,b1,c1,d1,e1,f1,g1,h1用a0,b0,c0,d0,e0,f0,g0,h0和a,b,c,d,e,f,g,h表示，即
[0025][0026]n19
的完美掩码为{r0}，n
56
的掩码为{h0}，n
78
的掩码为{b0,c0,g0,h0}，以此类推。此时根据每个节点的掩码情况以矩阵表示：
[0027][0028]
其中数字矩阵即为完美掩码矩阵计算得到完美掩码矩阵的秩为8，等于探测
集中的变量个数，因而是独立同分布的，从而是安全的。
[0029]
下面以第二个实例说明扩展规则的使用以及该方法如何检测泄露。该实例为2013年fse会议中jean-sebastien coron等人发现的一个有缺陷的二阶掩码方案。该方案涉及如下变量：其中a为秘密变量，且a＝a0+a1+a2；利用两个随机数r0,r1对a进行重掩码得到3个新的掩码分量b0＝a0+r0+r1,b1＝a1+r0,b2＝a2+r1；而敌手的探测变量集合为{n1＝a0+r0,n2＝a2∧b1}。易知n1的完美掩码为{a0,r0}，n2的完美掩码为从而完美掩码矩阵的秩为1，故需要将节点n2扩展为{a2,b1}，得到扩展后的探测变量集合{n0＝a0+r0,n1＝a2,n2＝b1＝a1+r0}。以矩阵表示，即
[0030][0031]
数字矩阵即为完美掩码矩阵。该矩阵是二元域上的矩阵，计算可得到其秩为2，小于探测变量的个数，因此该掩码方案可能存在泄露。
[0032]
尽管为说明目的公开了本发明的具体实施例，其目的在于帮助理解本发明的内容并据以实施，本领域的技术人员可以理解：在不脱离本发明及所附的权利要求的精神和范围内，各种替换、变化和修改都是可能的。因此，本发明不应局限于最佳实施例所公开的内容，本发明要求保护的范围以权利要求书界定的范围为准。

技术特征：
1.一种基于探测集约减的掩码安全性验证方法，其步骤包括：1)对于给定包含若干门的硬件掩码方案，将其解析为有向无环图g；2)计算有向无环图g中每个顶点n的辅助数据结构，即支持集supp(n)、单路达掩码集合unq(n)、完美掩码集合perf(n)和探测集o
n
；3)按字典序不重复地选取给定掩码方案对应的有向无环图g中的d个顶点组成的集合n
d
＝{n1,
…
,n
d
}，计算d阶探测集并进行步骤4)；若g中不存在未被选取的d个顶点的组合，则判定给定的掩码方案是安全的，该掩码防护方案通过安全性验证；为表示n
d
中的第j个顶点对应的探测集；4)若当前给定探测集为空集，则原d阶探测集是安全的，进入步骤3)；将当前的探测集命名为并根据变量的掩码情况将变量分为两两之间不共享掩码的若干子集并计算各子集的完美掩码矩阵然后进行步骤5)；5)从i＝1到i＝t，若第i个子集不服从均匀分布且可扩展，则将探测集扩展为探测集并进入步骤4)对探测集进行操作；若不服从均匀分布且不可扩展，则判定给定的掩码方案可能存在安全性问题，输出可能存在泄漏的d阶顶点集合n
d
，结束验证；若第i个子集服从均匀分布，则将子集从中删除得到并进入步骤4)对探测集进行操作。2.根据权利要求1所述的方法，其特征在于，所述硬件掩码方案将敏感信息x分割为d+1个分享值x
j
；d≥1，1≤j≤d+1；且所述硬件掩码方案包含若干输入门、中间门和输出门；根据输入是否为掩码电路敏感信息的分享值，输入门可分为分享门和随机门；按是否为线性，掩码方案中的中间门可分为线性门和非线性门；按照操作数的个数，将中间门分为一元门和二元门。3.根据权利要求2所述的方法，其特征在于，将所述硬件掩码方案解析为有向无环图g的过程为：将硬件掩码方案的输入门对应到图g中一个入度为0，出度可为任意值的顶点n；将输出门对应到有向无环图g中一个入度为1，出度为0的顶点n；将一元门对应到有向无环图g中一个入度为1，出度可为任意值的顶点n；将二元门对应到有向无环图g中一个入度为2，出度可为任意值的顶点n；一元门、输出门对应顶点n的入边指向其操作数对应的顶点n.lft；二元门对应顶点n的两条入边分别指向两个操作数对应的顶点n.lft和n.rgt。4.根据权利要求3所述的方法，其特征在于，所述敏感信息x的d+1个分享值在有向无环图中对应的d+1个顶点每一顶点的辅助数据结构计算方式为：当1≤j≤d时，当j＝d+1时，随机门r在有向无环图中对应的顶点n的辅助数据结构的计算方式为supp(n)＝unq(n)＝perf(n)＝o
n
＝{r}；一元门和输出门对应顶点n的辅助数据结构计算方式为supp(n)＝supp(n.lft)，unq(n)＝unq(n.lft)，perf(n)＝perf(n.lft)和o
n
＝o
n.lft
；二元门对应顶点n的支持集和单路达掩码集合的计算方式为supp(n)＝supp(n.ltf)∪supp(n.rgt)，unq(n)＝(unq(n.lft)∪
unq(n.rgt))\(unq(n.lft)∩unq(n.rgt))；二元线性门对应顶点n的完美掩码集合计算方式为perf(n)＝perf(n.lft)∪perf(n.rgt)∩unq(n)，二元非线性门对应顶点n的完美掩码集合计算方式为二元门对应顶点n的探测集计算方式为：若n.lft和n.rgt对应的门均为寄存器，则o
n
＝{n.lft}∪{n.rgt}；若n.lft和n.rgt对应的门都不为寄存器，则o
n
＝o
n.lft
∪o
n.rgt
；若n.lft对应的门为寄存器，n.rgt对应的门不是寄存器，则o
n
＝{n.lf}∪o
n.rgt
；若n.lft对应的门不是寄存器，n.rgt对应的门为寄存器，则o
n
＝o
n.lft
∪{n.rgt}。5.根据权利要求1所述的方法，其特征在于，步骤4)所述子集的完美掩码矩阵的计算方式为：1)计算第i个探测子集的完美掩码集合的完美掩码集合2)根据计算完美掩码矩阵若r
j
∈perf(n
k
)，则完美掩码矩阵的第j行第k列的元素否则6.根据权利要求1所述的方法，其特征在于，若所述子集满足下述条件1)、2)时，则服从独立均匀分布，否则不服从独立均匀分布；1)当1≤j≤p时，2)7.根据权利要求1所述的方法，其特征在于，若步骤5)所述子集满足则不可扩展，否则可扩展。8.根据权利要求1所述的方法，其特征在于，步骤5)所述子集扩展为的过程为：按拓扑序由大到小的顺序依次选取探测子集中的顶点n
j
，1≤j≤p；若与交集不为空，则将扩展得到探测集若1≤j≤p时，与交集为空，则将扩展得到探测集9.一种服务器，其特征在于，包括存储器和处理器，所述存储器存储计算机程序，所述计算机程序被配置为由所述处理器执行，所述计算机程序包括用于执行权利要求1至8任一所述方法中各步骤的指令。10.一种计算机可读存储介质，其上存储有计算机程序，其特征在于，所述计算机程序被处理器执行时实现权利要求1至8任一所述方法的步骤。

技术总结
本发明公开了一种基于探测集约减的掩码安全性验证方法，其步骤为：1)将给定掩码防护方案解析为有向无环图G，并计算图G中每个顶点n的辅助数据结构；2)按字典序不重复地选取图G中的d个顶点组成的集合N


技术研发人员：周锋 陈华 范丽敏 姚富 曹伟琼
受保护的技术使用者：中国科学院软件研究所
技术研发日：2023.04.27
技术公布日：2023/8/6