代数侧信道攻击的理论研究

需积分: 9 95 浏览量更新于2024-07-29 收藏 764KB PDF 举报

代数侧信道攻击分析代数侧信道攻击（Algebraic Side-Channel Attack，ASCA）是一种新的攻击方式，由Renauld、Standaert和Veyrat-Charvillon在CHES 2009上提出。这种攻击方式利用侧信道信息来实现有效的代数攻击。这种攻击方式主要基于SAT solver的使用，但缺乏理论支持。本文对代数侧信道攻击的代数阶段进行了理论研究，研究了基于Gröbner方法的更一般的代数攻击。我们发现，Gröbner基础计算的复杂度取决于一种新的代数免疫概念和密码系统的泄露信息分布。我们研究了两个常见的泄露模型：汉明权重模型和汉明距离模型。例如，在汉明权重模型中，我们发现PRESENT的替换层（resp. AES）中至少有64（resp. 130）线性关系的概率约为50%。此外，如果S-boxes被替换为满足新的代数免疫标准的函数，那么代数攻击（Gröbner和SAT）将变得不可行。在本研究的基础上，我们还推导出一个不变量，可以从给定的S-box中轻松计算出来，并提供了一个弱S-box的充分条件。这个新不变量不需要任何复杂的代数技术来定义和计算，因此对于没有高级代数知识的密码工程师来说，这可能是一个有趣的工具来拒绝弱S-boxes。代数侧信道攻击的关键是利用侧信道信息来实现代数攻击。这种攻击方式可以对密码系统造成严重的威胁，因此，研究这种攻击方式的理论基础和防御方法非常重要。本文的研究结果可以为密码系统的设计和分析提供有价值的参考。在本文中，我们还讨论了代数侧信道攻击的各种应用和防御方法。例如，我们可以使用Gröbner方法来实现代数攻击，也可以使用SAT solver来实现攻击。同时，我们还可以使用密码系统的泄露信息来防御代数侧信道攻击。本文对代数侧信道攻击的理论基础进行了深入的研究，并推导出了一些有价值的结果。这些结果可以为密码系统的设计和分析提供有价值的参考，并且可以为防御代数侧信道攻击提供有价值的方法。

J Cryptogr Eng

make reference to the algebraic immunity extended to

Boolean vectorial functions (sometimes called “graph alge-

braic immunity”). This definition slightly varies from one

article to the next. Thus, we ﬁrst remind the definition of the

algebraic immunity which we are going to use and we give

an algorithm to compute it (see [1,4,6,7,17,18,28]).

The algebraic immunity is deﬁned as the lowest degree

of algebraic relations of a Boolean vectorial function. More

formally, let B : F

→ F

be a black box and I

⊂

,...,X

, Y

,...,Y

] the ideal generated by the equa-

tions representing B and the ﬁeld equations:

=S

∪ S

Field Eq.



Deﬁnition 1 The algebraic immunity of B is deﬁned by

AI(B) = min{deg(P), P ∈ I

\ I

Field Eq.

}

Remark 1 The number of such lowest degree relations is also

an important invariant related to I

, and it is always com-

puted at the same time as the algebraic immunity.

To obtain the algebraic immunity of a black box B,we

could compute a Gröbner basis of I

with respect to a graded

order([4]):

Theorem 1 The reduced Gröbner basis G

of I

with

respect to a graded order contains a linear basis of the low-

est relations of B (i.e. the polynomials P ∈ I

such that

deg(P) = AI(B)).

Proof Every f ∈ I

is reduced to zero by a Gröbner

basis of I

. Thus, there is a polynomial g ∈ G

such that

the leading monomial LM(g) of g divides LM( f ).Aswe

have a graded monomial order, deg(g) = deg(LM(g)) and

deg( f ) = deg(LM( f )). Thus, deg(g) ≤ deg( f ) and we

prove that G

contains a linear generated family of the low-

est relations of B. Then the definition of a reduced Gröbner

basis implies that the linear generated family is a linearly

independent family. 

Example 1 The algebraic immunity of the function calculat-

ing the inverse over F

(e.g. AES S-box) equals 2. Indeed,

the inverse function is represented by a set of 39 quadratic

equations over F

([23]) as well as over F

([7]).

2.2 Algebraic immunity of S-boxes with leakage

In the previous section, the concept of algebraic immunity

is deﬁned as the lowest degree of algebraic relations of a

Boolean vectorial function. In the ASCA context, we are

looking for the lowest degree relations of B with leakage

information (e.g. Hamming weights, Hamming distances).

Therefore, we need to introduce a slightly different notion

of Algebraic Immunity to take the leakage into account. To

do so, for every value l of the leakage model, we consider

the ideal I

of F

,...,X

, Y

,...,Y

] generated by the

equations representing B, the ﬁeld equations S

Field Eq.

and by

the set of equations representing the leakage information

l, namely:

=S

∪ L

∪ S

Field Eq.

 .

From this ideal we can deﬁne this new notion of algebraic

immunity.

Deﬁnition 2 Let B be a black box and l the value of the leak-

age model L.Thealgebraic immunity with leakage, denoted

by AI

(B, l), is deﬁned by

(B, l) = min{deg(P), P ∈ I

\ I

Field Eq.

}

The number of linearly independent relations in I

with

degree AI

(B, l) will be denoted by # AI

(B, l).

Similarly to the general notion of algebraic immunity, the

relations of lowest degree can be explicitly obtained by the

computation of a Gröbner basis of I

with respect to a graded

order (see [7]).

An other important invariant related to I

is the number of

points in the associated variety V (I

),i.e.thesetofcommon

roots of the polynomials in I

. This number which depends

on the black box B and on the value l of the leakage function

L, is also linked to our algebraic immunity with leakage and

it will be denoted by N

(l):

Deﬁnition 3 N

(l) is deﬁned as the number of points of the

variety V(I

). In other words, N

(l) is equal to the cardinality

of the set {x ∈ F

s.t. L(x, B(x)) = l}

We will show in Sect.3 below that AI

(B, l) is equal to

1 in the cases of Hamming weight and Hamming distance

model. In this particular situation where AI

(B, l) is equal

to one (ie. there is at least one linear equation in the Ideal

), we prove the following relation between # AI

(B, l) and

(l):

Proposition 1 Let n be the bus size of B. If AI

(B, l) is

equal to 1 and N

(l) is non-zero then

(l) ≥ 2n + 1 − #AI

(B, l).

Proof As observed in Definition 3,wehaveN

(l) = #V (I

Since I

contains the ﬁeld polynomials, it is radical. Its vari-

ety V (I

) is a subset of F

and, from the Nullstellensatz, we

have

#V (I

) = dim



,...,X

, Y

,...,Y

]



= dim(Span(m

: α ∈ N

, m

/∈ LT( I

)))

From this set of generating monomials, we only keep the set

F of monomials which have a degree less than or equal than

one:

F ={m : deg(m) ≤ 1andm /∈ LT( I

)}

123

剩余17页未读，继续阅读

tuyunan

粉丝: 1
资源: 3

代数侧信道攻击的理论研究

Algebraic Functions

Research Progress of The Algebraic and Geometric Signal Processing

A Note on the Algebraic Immunity of the Enhanced Boolean Functions

The Bezout Number of Piecewise Algebraic Curves

Complex Analysis and Algebraic Geometry

Maximal values of generalized algebraic immunity

Invariant algebraic surfaces of the Chen system

C程序数值试验大全Solution of Linear Algebraic EquationsThe Art of Scientific Computing

Real-Time GPU Rendering of Piecewise Algebraic Surfaces

A+Weil-Foundations+Of+Algebraic+Geometry

最新资源