Upper bounds of maximum values of average differential and linear characteristic probabilities of feistel cipher with adder modulo 2^m
The paper discusses the Feistel cipher with a block size of n = 2m, where the addition of a round key and a part of an incoming massage in each round is carried out modulo 2^m. In order to evaluate the security of such a cipher against differential and linear cryptanalyses, the new parameters of c...
Збережено в:
| Дата: | 2006 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | English |
| Опубліковано: |
Інститут математики НАН України
2006
|
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/4438 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Upper bounds of maximum values of average differential and linear characteristic probabilities of feistel cipher with adder modulo 2^m / A. Alekseychuk, L. Kovalchuk // Theory of Stochastic Processes. — 2006. — Т. 12 (28), № 1-2. — С. 20–32. — Бібліогр.: 12 назв.— англ. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-4438 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-44382009-11-11T12:00:30Z Upper bounds of maximum values of average differential and linear characteristic probabilities of feistel cipher with adder modulo 2^m Alekseychuk, A. Kovalchuk, L. The paper discusses the Feistel cipher with a block size of n = 2m, where the addition of a round key and a part of an incoming massage in each round is carried out modulo 2^m. In order to evaluate the security of such a cipher against differential and linear cryptanalyses, the new parameters of cipher s-boxes are introduced. The upper bounds of maximum average differential and linear probabilities of one round encryption transformation and the upper bounds of maximum average differential and linear characteristics probabilities of the whole cipher are obtained. The practical security of the cipher GOST (with independent and equiprobable random round keys) against differential and linear cryptanalysis is also evaluated. To the authors’ mind, the obtained results allow one to expand the basic statements concerning the practical security of Markov (Feistel and SPN) ciphers against conventionally differential and linear attacks to a cipher of the type under study. 2006 Article Upper bounds of maximum values of average differential and linear characteristic probabilities of feistel cipher with adder modulo 2^m / A. Alekseychuk, L. Kovalchuk // Theory of Stochastic Processes. — 2006. — Т. 12 (28), № 1-2. — С. 20–32. — Бібліогр.: 12 назв.— англ. 0321-3900 http://dspace.nbuv.gov.ua/handle/123456789/4438 519.21 en Інститут математики НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| description |
The paper discusses the Feistel cipher with a block size of n = 2m, where the addition
of a round key and a part of an incoming massage in each round is carried out
modulo 2^m. In order to evaluate the security of such a cipher against differential and linear cryptanalyses, the new parameters of cipher s-boxes are introduced. The upper bounds of maximum average differential and linear probabilities of one round
encryption transformation and the upper bounds of maximum average differential and
linear characteristics probabilities of the whole cipher are obtained. The practical
security of the cipher GOST (with independent and equiprobable random round keys) against differential and linear cryptanalysis is also evaluated. To the authors’ mind, the obtained results allow one to expand the basic statements concerning the practical security of Markov (Feistel and SPN) ciphers against conventionally differential and
linear attacks to a cipher of the type under study. |
| format |
Article |
| author |
Alekseychuk, A. Kovalchuk, L. |
| spellingShingle |
Alekseychuk, A. Kovalchuk, L. Upper bounds of maximum values of average differential and linear characteristic probabilities of feistel cipher with adder modulo 2^m |
| author_facet |
Alekseychuk, A. Kovalchuk, L. |
| author_sort |
Alekseychuk, A. |
| title |
Upper bounds of maximum values of average differential and linear characteristic probabilities of feistel cipher with adder modulo 2^m |
| title_short |
Upper bounds of maximum values of average differential and linear characteristic probabilities of feistel cipher with adder modulo 2^m |
| title_full |
Upper bounds of maximum values of average differential and linear characteristic probabilities of feistel cipher with adder modulo 2^m |
| title_fullStr |
Upper bounds of maximum values of average differential and linear characteristic probabilities of feistel cipher with adder modulo 2^m |
| title_full_unstemmed |
Upper bounds of maximum values of average differential and linear characteristic probabilities of feistel cipher with adder modulo 2^m |
| title_sort |
upper bounds of maximum values of average differential and linear characteristic probabilities of feistel cipher with adder modulo 2^m |
| publisher |
Інститут математики НАН України |
| publishDate |
2006 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/4438 |
| citation_txt |
Upper bounds of maximum values of average differential and linear characteristic probabilities of feistel cipher with adder modulo 2^m / A. Alekseychuk, L. Kovalchuk // Theory of Stochastic Processes. — 2006. — Т. 12 (28), № 1-2. — С. 20–32. — Бібліогр.: 12 назв.— англ. |
| work_keys_str_mv |
AT alekseychuka upperboundsofmaximumvaluesofaveragedifferentialandlinearcharacteristicprobabilitiesoffeistelcipherwithaddermodulo2m AT kovalchukl upperboundsofmaximumvaluesofaveragedifferentialandlinearcharacteristicprobabilitiesoffeistelcipherwithaddermodulo2m |
| first_indexed |
2025-07-02T07:41:00Z |
| last_indexed |
2025-07-02T07:41:00Z |
| _version_ |
1836520110845591552 |
| fulltext |
Theory of Stochastic Processes
Vol. 12 (28), no. 1–2, 2006, pp. 20–32
UDC 519.21
A. ALEKSEYCHUK AND L. KOVALCHUK
UPPER BOUNDS OF MAXIMUM VALUES OF AVERAGE
DIFFERENTIAL AND LINEAR CHARACTERISTIC PROBABILITIES
OF FEISTEL CIPHER WITH ADDER MODULO 2m
The paper discusses the Feistel cipher with a block size of n = 2m, where the addition
of a round key and a part of an incoming massage in each round is carried out
modulo 2m. In order to evaluate the security of such a cipher against differential
and linear cryptanalyses, the new parameters of cipher s-boxes are introduced. The
upper bounds of maximum average differential and linear probabilities of one round
encryption transformation and the upper bounds of maximum average differential and
linear characteristics probabilities of the whole cipher are obtained. The practical
security of the cipher GOST (with independent and equiprobable random round keys)
against differential and linear cryptanalysis is also evaluated. To the authors’ mind,
the obtained results allow one to expand the basic statements concerning the practical
security of Markov (Feistel and SPN) ciphers against conventionally differential and
linear attacks to a cipher of the type under study.
1. Introduction
Differential [1], [2] and linear cryptanalyses [3] are considered as the most powerful
statistical techniques of the block cipher cryptographic analysis. The quite developed
theory of differential and linear cryptanalysis of Markov block ciphers1 [2] exists nowa-
days, techniques of their security estimations against differential and linear attacks are
worked out, general techniques of design of SPN-ciphers and Markov Feistel ciphers that
are practically secure against such attacks are well known. The literature devoted to this
topic includes dozens of published manuscripts. Let’s mention here review [4] and papers
[5]–[7], where one can find a detailed bibliography.
In spite of the progress of mathematical foundations for differential and linear crypt-
analyses, we have to admit that today there is no general theory of analysis and security
proofs against the above-mentioned attacks of non-Markov block ciphers. This is caused
by the analytical difficulties accompanying the investigations of the non-Markov block
cipher security and by the lack of a new adequate mathematical procedure taking into
account a specific structure of such ciphers.
The paper studies the analytical upper bounds of the maximum average differential
and linear characteristic probabilities of a (non-Markov) Feistel cipher with a key adder
modulo 2m. The well-known example of such a cipher is GOST 28147-89 (hereafter
GOST) [8]. The expressions for the obtained upper bounds include new parameters
of the cipher s-boxes. These parameters are different from the classical measures (the
maximum differential and the maximum linear probabilities of s-boxes) of the Markov
2000 AMS Mathematics Subject Classification. Primary 60C05, 94A60.
Key words and phrases. Feistel cipher, addition modulo 2m, differential cryptanalysis, linear crypt-
analysis, GOST.
1Hereafter the Markov block cipher is considered as a Markov cipher as to operation ⊕ of a bitwise
Boolean addition in a set of binary vectors
20
UPPER BOUNDS OF MAXIMUM VALUES OF AVERAGE DIFFERENTIAL . . . 21
cipher security against differential and linear cryptanalyses. It is shown that there exist s-
boxes (length of 4), for which the maximum average differential probabilities of the round
transformation of a cipher with the adder modulo 2m are less than the maximum average
differential probabilities of the round transformation of the corresponding Markov Feistel
cipher with arbitrary chosen s-boxes.
The structure of the paper is as follows. Some definitions are introduced in Section 2,
the exact task is stated, and the main results (Theorems 1, 2) are described in Section 3,
their proofs are presented in Section 4. Section 5 depicts an application of Theorem 2
to the estimation of the average differential and linear probabilities of the GOST cipher
modification by independent and equiprobable random round keys. Particular examples
of cipher s-boxes are described, for which the maximum values of the average linear
and differential characteristic probabilities of a 30-round cipher do not exceed 2−40 and
2−46.4, respectively. Finally, Section 6 discusses the results obtained and the future
investigations.
2. Main Notations
Let l be an arbitrary natural number. We denote Vl as a set of Boolean vectors with
length l and SVl as a symmetric group on Vl. For any α = (α1 . . . αl), β = (β1 . . . βl) ∈ Vl,
we define αβ = α1β1 ⊕ . . . ⊕ αlβl, α ⊕ β = (α1 ⊕ β1, . . . α1 ⊕ β1).
Below, an arbitrary vector (x1, . . . , xl) ∈ Vl is identified with an integer number
x = 2l−1x1 + . . . + 20xl . The symbol x
l
+ y is used for the sum modulo 2l of two binary
integer numbers corresponding to vectors x, y ∈ Vl. We also use the notation x + y
instead of x
l
+ y if it doesn’t cause the confusion, and the value l is defined from the
context (from the condition x, y ∈ Vl).
For any x, y ∈ Vl, we denote, by ν(x, y), the previous carry bit into the most significant
(l-th) digit in the sum of two binary numbers x and y in the ring Z.
Let g ∈ SVl , then
(1) gk(x) = g(x + k), x ∈ Vl,
(2) Cg(α, β) = 2−l
∑
x∈Vl
(−1)αg(x)⊕βx,
(3) Dg(α, β) = 2−l|{x ∈ Vl : g(x ⊕ α) ⊕ g(x) = β}|,
(4) d(g)(α, β) = 2−l
∑
k∈Vl
Dgk
(α, β),
(5) l(g)(α, β) = 2−l
∑
k∈Vl
(Cgk
(β, α))2,
(6) Λ(g)(α, β) = 2−l
∑
k∈Vl
⎛
⎝2−l
∑
a∈{0,1}
∣∣∣∣∣∣2−l
∑
x∈Vl:ν(x, k)=a
(−1)βg(x+k)⊕αx
∣∣∣∣∣∣
⎞
⎠
2
,
Δ(g)(α, β) = 2−2l×
(7) × max
(a1, a2)∈V2
⎧⎨
⎩
∑
(x, k)∈Vl×Vl
δ (g((x ⊕ α) + k + a1) ⊕ g(x + k + a2), β)
⎫⎬
⎭ ,
22 A. ALEKSEYCHUK AND L. KOVALCHUK
where δ(·, ·) is the Kronecker delta, δ(u, v) = 1 if u = v, otherwise δ(u, v) = 0.
From Eqs. (1)–(7), we obtain directly the following relations:
(8) d(g)(α, 0) = l(g)(α, 0) = Δ(g)(α, 0) = Λ(g)(α, 0) = δ(α, 0),
(9) d(g)(0, β) = l(g)(0, β) = Δ(g)(0, β) = Λ(g)(0, β) = δ(0, β),
(10) 0 ≤ d(g)(α, β) ≤ Δ(g)(α, β) ≤ 1,
(11) 0 ≤ l(g)(α, β) ≤ Λ(g)(α, β) ≤ 1,
for any g ∈ SVl , α, β ∈ Vl.
3. Problem Statement and Main Results
Let’s consider an r-round Feistel cipher � with the set of plaintexts (ciphertexts) Vn,
where n = 2m, m ≥ 2, the set of round keys K = Vn, and the encryption function
F : Vn × Kr → Vn. A transformation F (λ) of the plaintext x ∈ Vn into the ciphertext
y ∈ Vn with the key λ = (k(1), . . . , k(r)) ∈ Kr is a composition of r round encryption
transformations f (k(1)), . . . , f (k(r)) defined by the key λ:
(12) y = F (λ)(x) = (f (k(r)) ◦ . . . ◦ f (k(1)))(x), x ∈ Vn.
We assume that the encryption transformation f (k) (k ∈ Vm) in each round from 1 to
r takes the form
(13) f (k)(x) = f (k)(u, v) = (v, u ⊕ ϕ(v + k)),
where x = (u, v) is the input of this round, u, v ∈ Vm, ϕ ∈ SVm , and the + sym-
bol (according to our agreement) denotes a sum modulo 2m of m-digit binary integer
numbers.
Assume that m = pt, p, t ∈ N, and a substitution ϕ takes the form
(14) ϕ(z) = A
(
s(p−1)(z(p−1)), . . . , s(0)(z(0))
)T
, z =
(
z(p−1), . . . , z(0)
)
∈ Vm,
where z(j) ∈ Vt, s(j) ∈ SVt for any j = 0, p − 1, and A is an invertible matrix of order m
over the field GF(2).
The mapping ϕ is called a round function, and the substitutions s(j) (j = 0, p− 1 )
are called s-boxes of a cipher �.
Below, a differential (linear) characteristic of the cipher � is considered as an arbitrary
sequence Ω = (ω0, ω1 . . . , ωr) of non-zero Boolean vectors ω0, ω1 . . . , ωr ∈ Vn.
We assume that the key λ = (k(1), . . . , k(r)) of the cipher � is a random element with
the equiprobable distribution on the set Kr. Let us consider the formal products
(15) EDP (Ω)
def
=
r∏
i=1
(
2−m
∑
k∈Vm
Df(k)(ωi−1, ωi)
)
,
(16) ELP (Ω)
def
=
r∏
i=1
(
2−m
∑
k∈Vm
(
Cf(k)(ωi, ωi−1)
)2)
.
We call them as the average differential characteristic probability Ω and the average linear
characteristic probability Ω of a block cipher �. Then
(17) MD(�) = max
(Ω)
{EDP (Ω)} ,
UPPER BOUNDS OF MAXIMUM VALUES OF AVERAGE DIFFERENTIAL . . . 23
(18) ML(�) = max
(Ω)
{ELP (Ω)} .
Notice that these definitions of the average probabilities EDP (Ω), ELP (Ω) actually
coincide with the definitions of the same notations for Markov block ciphers [9]. In
this case, the parameter upper bounds of (17), (18) are the standard values character-
izing the practical security of (Markov) block ciphers against conventionally differential
cryptanalysis and linear cryptanalysis, respectively [1], [3], [7], [9]–[11].
The paper solves the problem of obtaining the upper bounds of expressions (17), (18)
for any Feistel cipher � defined by expressions (12)–(14) in terms of certain parameters
depending on the cipher s-boxes.
The following theorem plays a central role in obtaining the defined upper bounds.
Theorem 1. Let t, m ∈ N, t ≤ m−1, ψ(1) and ψ(2) are substitutions on the sets Vt and
Vm−t, respectively. We define the substitution ψ ∈ SVm assuming that
(19) ψ(x2, x1) =
(
ψ(2)(x2), ψ(1)(x1)
)
, x1 ∈ Vt, x2 ∈ Vm−t.
Then, for any α = (α2, α1), β = (β2, β1), where α1, β1 ∈ Vt, α2, β2 ∈ Vm−t, the following
inequalities hold:
(20) d(ψ)(α, β) ≤ d(ψ(l))(α1, β1)Δ(ψ(2))(α2, β2),
(21) l(ψ)(α, β) ≤ Λ(ψ(l))(α1, β1) l(ψ
(2))(α2, β2).
The following result arises directly from Theorem 1 and relations (10), (11).
Corollary 1. Let ϕ be a substitution (4), α = (α(p−1), . . . , α(0)),
β = (β(p−1), . . . , β(0)), where α(j), β(j) ∈ Vt, j = 0, p− 1. Then
(22) d(ϕ)(α, AβT ) ≤
p−1∏
j=0
Δ(sj)(α(j), β(j)), l(ϕ)(α, βA−1) ≤
p−1∏
j=0
Λ(sj)(α(j), β(j)).
The following theorem states the upper bounds of (17), (18), depending only on the
s-boxes of the cipher � and the number of rounds r.
Theorem 2. Let � be a Feistel cipher defined by expressions (12)–(14). Then the fol-
lowing relations hold for the maximum average differential and maximum average linear
characteristic probabilities of the cipher �:
(23) MD(�) ≤ Δ(�) 2r
3
, ML(�) ≤ Λ(�) 2r
3
,
where
(24) Δ(�) = max
{
Δ(s(j))(α, β) : α, β ∈ Vt \ {0}, j = 0, p − 1
}
,
(25) Λ(�) = max
{
Λ(s(j))(α, β) : α, β ∈ Vt \ {0}, j = 0, p − 1
}
.
Notice that, for the Markov Feistel cipher with bijective round function ϕ, rela-
tions similar to (23) were obtained earlier in [11] (with the parameters Ds(j)(α, β) and
(Cs(j) (α, β))2 instead of Δ(�) and Λ(�) , respectively, α, β ∈ Vt \ {0}, ⊃= 0, p − 1).
24 A. ALEKSEYCHUK AND L. KOVALCHUK
4. Proofs of Theorems
4.1. Proof of Theorem 1. We make some preliminary remarks. For any vector
z ∈ Vm, we define z1 and z2 as the sub-vectors of z including its t least significant bits
and m− t most significant bits, respectively. The vector z will take the form z = (z2, z1).
Let x = (x2, x1), k = (k2, k1), where x1, k1 ∈ Vt, x2, k2 ∈ Vm−t. We consider the
integer numbers x = x1 + 2tx2 and k = k1 + 2tk2 corresponding to the above-mentioned
Boolean vectors. Notice that x1, k1 ∈ 0, 2t − 1, x2, k2 ∈ 0, 2m−t − 1.
The following equality holds:
(26) x
m
+ k = (x1
t
+ k1) + 2t(x2
m−t
+ k2
m−t
+ ν(x1, k1)).
Here, ν(x1, k1) is a previous carry bit to the most significant (t-th) digit in the sum of
the numbers x1 and k1 in the ring Z.
Let us prove inequality (20). Applying the formulas (1), (3), (4), (19), and (26), we
obtain the following chain of relations:
d(ψ)(α, β) = 2−m
∑
k∈Vm
(
2−m
∑
x∈Vm
δ (ψk(x ⊕ α) ⊕ ψk(x), β)
)
=
(27) = 2−2m
∑
x1,k1∈Vt
δ
(
ψ(1)((x1 ⊕ α1) + k1) ⊕ ψ(1)(x1 + k1), β1
)
×
×
∑
x2,k2∈Vm−t
δ
(
ψ(2)((x2 ⊕ α2) + k2 + ν(x1 ⊕ α1, k1)) ⊕ ψ(2)(x2 + k2 + ν(x1, k1)), β2
)
.
For any a1, a2 ∈ {0, 1}, k1 ∈ Vt, k2 ∈ Vm−t, we assume
uk1(a1, a2) = 2−2t
∑
x1∈Vt:
ν(x1⊕α1,k1)=a1,
ν(x1,k1)=a2
δ
(
ψ(1)((x1 ⊕ α1) + k1) ⊕ ψ(1)(x1 + k1), β1
)
,
νk2(a1, a2) = 2−2(m−t)
∑
x2∈Vm−t
δ
(
ψ(2)((x2 ⊕ α2) + k2 + a1) ⊕ ψ(2)(x2 + k2 + a2), β2
)
.
Then, using (27), we obtain
d(ψ)(α, β) =
∑
k1∈Vt,
k2∈Vm−t
∑
(a1,a2)∈V2
uk1(a1, a2) νk2(a1, a2) ≤
(28) ≤
⎛
⎝ ∑
k1∈Vt
∑
(a1,a2)∈V2
uk1(a1, a2)
⎞
⎠
⎛
⎝ max
(a1,a2)∈V2
⎧⎨
⎩
∑
k2∈Vm−t
νk2(a1, a2)
⎫⎬
⎭
⎞
⎠ .
Notice that, according to formulas (1), (4), and (7),
∑
k1∈Vt
∑
(a1,a2)∈V2
uk1(a1, a2) = 2−t
∑
k1∈Vt
(
2−t
∑
x1∈Vt
δ
(
ψ(1)((x1 ⊕ α1) + k1)⊕
(29) ⊕ψ(1)(x1 + k1), β1
))
= d(ψ(1))(α1, β1),
UPPER BOUNDS OF MAXIMUM VALUES OF AVERAGE DIFFERENTIAL . . . 25
(30) max
(a1,a2)∈V2
⎧⎨
⎩
∑
k2∈Vm−t
νk2(a1, a2)
⎫⎬
⎭ = Δ(ψ(2))(α2, β2).
So, on the basis of relations (28)–(30), inequality (20) is proved.
Now we prove inequality (21).
Let us denote χ(a) = (−1)a, where a ∈ {0, 1}. We obtain the upper bound of the
quantity
(31) |Cψk
(β, α)| = 2−m
∣∣∣∣∣
∑
x∈Vm
χ(βψ(x + k) ⊕ αx)
∣∣∣∣∣
for a fixed k = (k1, k2), where k1 ∈ Vt, k2 ∈ Vm−t. Applying formula (26), we can write
down quantity (31) in the following form:
|Cψk
(β, α)| =
= 2−m
∣∣∣∣∣∣∣
∑
x1∈Vt,
x2∈Vm−t
χ
(
β1ψ
(1)(x1 + k1) ⊕ α1x1 ⊕ β2ψ
(2)(x2 + k2 + ν(x1, k1)) ⊕ α2x2
)∣∣∣∣∣∣∣ =
(32) = 2−m
∣∣∣∣∣
∑
a∈{0,1}
∑
x1∈Vt,
ν(x1,k1)=a
χ
(
β1ψ
(1)(x1 + k1) ⊕ α1x1
)
×
×
∑
x2∈Vm−t
χ
(
β2ψ
(2)(x2 + k2 + a) ⊕ α2x2
)∣∣∣∣∣.
For any a ∈ {0, 1}, k1 ∈ Vt, k2 ∈ Vm−t, we assume
uk1(a) = 2−t
∑
x1∈Vt,
ν(x1,k1)=a
χ
(
β1ψ
(1)(x1 + k1) ⊕ α1x1
)
, uk1 = |uk1(0)| + |uk1(1)|,
νk2(a) = 2−(m−t)
∑
x2∈Vm−t
χ
(
β2ψ
(2)(x2 + k2 + a) ⊕ α2x2
)
Then, on the basis of (32), we have
|Cψk
(β, α)| =
∣∣∣∣∣∣
∑
a∈{0,1}
uk1(a)νk2(a)
∣∣∣∣∣∣ ≤
∑
a∈{0,1}
|uk1(a)||νk2(a)|.
So taking the convexity down of the function x �→ x2 into account, we obtain the relations
|Cψk
(β, α)|2 ≤ (uk1(a))2
( |uk1(0)|
uk1
|νk2(0)| + |uk1(1)|
uk1
|νk2(1)|
)2
≤
(33) ≤ (uk1(a))2
( |uk1(0)|
uk1
|νk2(0)|2 +
|uk1(1)|
uk1
|νk2(1)|2
)2
=
= uk1(a)
(|uk1(0)||νk2(0)|2 + |uk1(1)||νk2(1)|2) .
Hence, on the basis of (5) and (33), we have
l(ψ)(α, β) = 2−m
∑
k∈Vm
(Cψk
(β, α))2 ≤ 2−m
∑
k1∈Vt,
k2∈Vm−t
uk1
∑
a∈{0,1}
|uk1(a)||νk2(a)|2 =
26 A. ALEKSEYCHUK AND L. KOVALCHUK
(34) = 2−t
∑
k1∈Vt
uk1
∑
a∈{0,1}
|uk1(a)|
⎛
⎝2−(m−l)
∑
k2∈Vm−t
|νk2(a)|2
⎞
⎠ .
Now notice that, for any a ∈ {0, 1},
2−(m−l)
∑
k2∈Vm−t
|νk2(a)|2 =
= 2−(m−l)
∑
k2∈Vm−t
⎛
⎝2−(m−l)
∑
x2∈Vm−t
χ
(
β2ψ
(2)(x2 + k2 + a) ⊕ α2x2
)⎞⎠
2
.
Substituting the variable k
′
2 = k2 +a in the right-hand side of the last equality, we obtain
2−(m−l)
∑
k2∈Vm−t
|νk2(a)|2 =
= 2−(m−l)
∑
k
′
2∈Vm−t
⎛
⎝2−(m−l)
∑
x2∈Vm−t
χ
(
β2ψ
(2)(x2 + k
′
2) ⊕ α2x2
)⎞⎠
2
=
= 2−(m−l)
∑
k2∈Vm−t
(
C
ψ
(2)
k2
(β2, α2)
)2
= l(ψ
(2))(α2, β2).
Then we get
l(ψ)(α, β) ≤ 2−t
∑
k1∈Vt
uk1
⎛
⎝ ∑
a∈{0,1}
|uk1(a)|
⎞
⎠ l(ψ
(2))(α2, β2) =
= Δ(ψ(1))(α1, β1) l(ψ
(2))(α2, β2),
from the previous equality, by applying (34) and (6), which completes the proof of The-
orem 1.
4.2. Proof of Theorem 2. Let Ω = (ω0, ω1, . . . , ωr) and Ω
′
= (ω
′
0, ω
′
1, . . . , ω
′
r) be
arbitrary differential and linear characteristics of a cipher �, respectively. Without any
restriction, we assume that
(35) EDP (Ω)
= ELP (Ω
′
)
= 0
and show that, in this case,
(36) EDP (Ω) ≤ Δ(�) 2r
3
(37) ELP (Ω
′
) ≤ Λ(�) 2r
3
,
where Δ(�), Λ(�) are defined by formulas (24), (25), respectively.
Now let us prove some auxiliary statements.
UPPER BOUNDS OF MAXIMUM VALUES OF AVERAGE DIFFERENTIAL . . . 27
Lemma 1. Under condition (35), there exist sequences (α0, α1, . . . , αr+1),
(β0, β1, . . . , βr+1) of the m-dimensional Boolean vectors such that
(38) EDP (Ω) =
∏
i∈N(Ω)
d(ϕ)(αi, αi−1 ⊕ αi+1),
(39) (αi, αi+1)
= (0, 0), i ∈ 0, r,
(40) ELP (Ω
′
) =
∏
i∈N(Ω′ )
l(ϕ)(βi−1 ⊕ βi+1, βi),
(41) (βi, βi+1)
= (0, 0), i ∈ 0, r,
where
(42) N(Ω) = {1, 2, . . . , r} \ {i ∈ 0, r : (αi, αi−1 ⊕ αi+1) = (0, 0)},
(43) N(Ω
′
) = {1, 2, . . . , r} \ {i ∈ 0, r : (βi−1 ⊕ βi+1, βi) = (0, 0)}.
In this case, the following inequality holds:
(44) |N(Ω)| ≥
⌊
2r
3
⌋
, |N(Ω
′
)| ≥
⌊
2r
3
⌋
.
Proof. Let Ω = (ω0, ω1, . . . , ωr), ωi = (αi, γi)
= (0, 0), where αi, γi ∈ Vm, i ∈ 0, r. Using
formulas (3), (13), it’s easy to check that, for any k ∈ Vm, i ∈ 1, r, the following equality
holds:
(45) Df(k)(ωi−1, ωi) = δ(γi−1, αi)Dϕk(γi−1; αi−1 ⊕ γi).
Let αr+1 = γr. Substituting (45) in (15) and taking (35) into account, we obtain
γi = αi+1, i ∈ 0, r; in particular, equalities (39) hold. Notice that
EDP (Ω) =
r∏
i=1
(
2−m
∑
k∈Vm
Dϕk(αi, αi−1 ⊕ αi+1)
)
.
This relation and formulas (4), (8), and (42) yield equality (38).
The proof of (40), (41) is similar, with the use of formulas (2), (5), (8), (13), (16), and
(43).
Now we prove the validity of inequality (44). Let N0(Ω) = {1, 2, . . . , r} \ N(Ω). For
any i ∈ 1, r,
(46) (i ∈ N0(Ω)) ⇒
((
(i + 1 ≤ r) ⇒ (i + 1 ∈ N(Ω))
)
&
&
(
(i + 2 ∈ N(Ω)) ⇒ (i + 2 ∈ N(Ω))
))
.
Then |N0(Ω)| ≤ ⌈
r
3
⌉
, which directly implies the first inequality in (44). The second
inequality has a similar proof.
Now we conclude that implication (46) is true. Let i ∈ 1, r and (αi, αi−1 ⊕ αi+1) =
= (0, 0). Then, applying (39), we have αi+1
= 0 and, consequently, αi+2 = αi⊕ ⊕αi+2
=
0, because, otherwise, we obtain EDP (Ω) = 0 on the basis of (8) and (38), which
contradicts condition (35).
28 A. ALEKSEYCHUK AND L. KOVALCHUK
So we have
((αi, αi−1 ⊕ αi+1) = (0, 0)) ⇒ ((αi+1, αi ⊕ αi+2)
= (0, 0)) , if i + 1 ≤ r,
((αi, αi−1 ⊕ αi+1) = (0, 0)) ⇒ ((αi+2, αi+1 ⊕ αi+3)
= (0, 0)) , if i + 2 ≤ r,
and Lemma 1 is completely proved.
Lemma 2. Let ϕ be a substitution of the form (14),
α = (α(p−1), . . . , α(0)), β = (β(p−1), . . . , β(0)) ∈ Vm \ {0},
where α(j), β(j) ∈ Vt, j ∈ 0, p − 1. Then
(47) (d(ϕ)(α, AβT )
= 0) ⇒ (∃i ∈ 0, p − 1 : (α(i)
= 0)&(β(i)
= 0)),
(48) (l(ϕ)(α, βA−1)
= 0) ⇒ (∃i ∈ 0, p − 1 : (α(i)
= 0)&(β(i)
= 0)).
L. et us assume that implication (47) is invalid. Suppose
i1 = min{j ∈ 0, p− 1 : α(i)
= 0)}, i2 = min{j ∈ 0, p− 1 : β(i)
= 0)}.
We assume that i1 > i2 and consider the substitutions
ψ(x) = A−1ϕ(x), x = (x(p−1), . . . , x(0)),
ψ(1)(x1) = (s(i1−1)(x(i1−1)), . . . , s(0)(x(0))), x1 = (x(i1−1), . . . , x(0)),
ψ(2)(x2) = (s(p−1)(x(p−1)), . . . , s(i1)(x(i1))), x2 = (x(p−1), . . . , x(i1)),
where x(j) ∈ Vt, j ∈ 0, p− 1.
Notice that, according to inequality (20),
(49) d(ϕ)(α, AβT ) = d(ψ)(α, β) ≤ d(ψ(1))(α1, β1) Δ(ψ(2))(α2, β2)
The following relations hold by the definitions of values i1, i2:
α = (α(i1−1), . . . , α(0)) = 0, β = (β(i1−1), . . . , β(0))
= 0,
which implies d(ψ(1))(α1, β1) = 0 [see (8)]. Then, using (49), we obtain d(ϕ)(α, AβT ) = 0,
which contradicts the condition of implication (47).
So the case i1 > i2 is impossible. In the same way, we can show that i1 ≥ i2. So
i1 = i2, which yields the validity of implication (47). The proof of implication (48) is
similar, with the use of inequality (21).
The lemma is completely proved.
To complete the proof of Theorem 2, we use expressions (38) and (40). Let us show
that each factor d(ϕ)(αi, αi−1 ⊕ αi+1), i ∈ N(Ω) on the right-hand side of equality (38)
does not exceed Δ(�). In view of the first inequality (44), this allows us to directly get
estimation (36).
Notice that, on the basis of relations (35), (42) for any i ∈ N(Ω), α
def
= α1
= 0,
AβT def
= αi−1 ⊕ αi+1
= 0. According to Corollary 1 of Theorem 1,
(50) d(ϕ)(α, AβT ) ≤
p−1∏
j=0
Δ(sj)(α(j), β(j)).
In addition, using Lemma 2, we obtain that there are j ∈ 0, p − 1 such that α(j)
=
0, β(j)
= 0. Consequently, Δ(sj)(α(j), β(j)) ≤ Δ(�) and, on the basis of (50),
d(ϕ)(αi, αi−1 ⊕ αi+1) ≤ Δ(�)
UPPER BOUNDS OF MAXIMUM VALUES OF AVERAGE DIFFERENTIAL . . . 29
for any i ∈ N(Ω), what had to be proved. The validity of inequality (37) can be proved
in the same way.
So Theorem 2 is completely proved.
5. Estimations of Maximum Average Linear and Differential
Characteristic Probabilities of GOST Modification
As an example of the application of the obtained results, we consider a modification
of the block cipher GOST, where round keys are chosen independently and equiprobably
from Vm.
It’s known [8] that GOST is a 32-round Feistel cipher with the block size n = 64,
whose round encryption transformations and round function are defined by formulas
(13) and (14), respectively. In our notations, m = 32, t = 4, p = 8, and the matrix A
in expression (14) is substitutional (it corresponds to the left cyclic shift to 11 positions
on the set V32). It’s also known that the s-boxes of GOST are its key parameters and,
generally speaking, can be arbitrary substitutions belonging to the symmetric group SV4 .
According to inequalities (23), the upper bounds of the maxima of the average dif-
ferential and linear characteristic probabilities of the (modified) GOST depend on the
parameters
Δ(s) = max{Δ(s)(α, β) : α, β ∈ V4 \ {0}},
Λ(s) = max{Λ(s)(α, β) : α, β ∈ V4 \ {0}},
where Δ(s)(α, β) and Λ(s)(α, β) are defined by formulas (6) and (7), and a substitution
s passes through the set of s-boxes of the given cipher.
Tables 1 and 2 demonstrate the results of statistical estimations for the parameters
Δ(s), Λ(s) (as functions of the random and equiprobable substitution s ∈ SV4), respec-
tively. As we can see in Table 1, the value of Δ(s) is between 0.151 and 0.200 for 7536
substitutions s out of 100000, generated randomly, independently and equiprobable on
set V4. Similarly, the value of Λ(s) is between 0.201 and 0.250 for 1591 substitutions
s out of 100000 ones generated under the same conditions (see Table 2). Notice that,
during our calculations, we cannot find any substitution s ∈ SV4 with the Λ(s) ≤ 0.250
property.
In Table 3, we have the examples of substitutions with small values of the parameters
Δ0 and Λ0. The results of Theorem 2 demonstrate that, in the case where modified GOST
cipher s-boxes are chosen from Table 3, the maximum average linear and differential
characteristic probabilities of the 30-round GOST cipher do not exceed (0.2)20 ≈ 2−46.4
and (0.25)20 = 2−40, respectively.
The estimations obtained didn’t allow us to make any exact conclusions about the
security of the cipher ΓOCT 28147-89 against differential or linear attacks. But, to our
mind, the general methods of construction of similar estimations on the basis of Theorems
1 and 2 are the first steps towards the mathematically strict proof of the condition for
the practical security of GOST against differential and linear cryptanalyses.
6. Discussion of Results and Future Investigations
Theorem 1 and Corollary 1 allow us to define the way of the construction of a substan-
tial theory of the security evaluation of block ciphers described by relations (12)–(14)
against a differential (linear) cryptanalysis in a similar way as to the well-known theory of
estimation and proof of the security of Markov Feistel ciphers against differential (linear)
attacks (see [7], [9]–[11] and references therein).
Let us put the described cipher � in correspondence to the Markov block cipher �⊕.
Their single difference consists in that the encryption transformation f
(k)
⊕ (k ∈ Vm)
30 A. ALEKSEYCHUK AND L. KOVALCHUK
Table 1. Statistical estimation of the Δ(s) parameter
distribution (for 100000 substitutions s ∈ SV4)
Interval of Number of Interval of Number of
values Δ0 substitutions valuesΔ0 substitutions
0.000− 0.050 0 0.501− 0.550 0
0.051− 0.100 0 0.551− 0.600 0
0.101− 0.150 0 0.601− 0.650 0
0.151− 0.200 7536 0.651− 0.700 0
0.201− 0.250 58633 0.701− 0.750 0
0.251− 0.300 26410 0.751− 0.800 0
0.301− 0.350 6424 0.801− 0.850 0
0.351− 0.400 893 0.851− 0.900 0
0.401− 0.450 104 0.901− 0.950 0
0.451− 0.500 0 0.951− 1.000 0
Table 2. Statistical estimation of the Λ(s) parameter
distribution (for 100000 substitutions s ∈ SV4)
Interval of Number of Interval of Number of
values Λ0 substitutions valuesΛ0 substitutions
0.000− 0.050 0 0.501− 0.550 396
0.051− 0.100 0 0.551− 0.600 14561
0.101− 0.150 0 0.601− 0.650 418
0.151− 0.200 0 0.651− 0.700 0
0.201− 0.250 1591 0.701− 0.750 0
0.251− 0.300 40450 0.751− 0.800 0
0.301− 0.350 32049 0.801− 0.850 0
0.351− 0.400 7850 0.851− 0.900 0
0.401− 0.450 1693 0.901− 0.950 0
0.451− 0.500 761 0.951− 1.000 231
Table 3. Examples of the substitution with small values
of parameters Δ0 and Λ0
Substitutions ∈ SV4 Δ(s) Λ(s)
11, 2, 1, 14, 0, 7, 15, 4, 8, 9, 6, 12, 5, 13, 3, 10 0.179688 0.250000
7, 3, 8, 14, 2, 5, 1, 13, 15, 10, 9, 12, 4, 6, 11, 0 0.187500 0.250000
1, 8, 2, 9, 14, 5, 0, 13, 7, 4, 12, 3, 10, 6, 15, 11 0.187500 0.250000
3, 15, 12, 6, 8, 4, 1, 5, 13, 9, 14, 2, 11, 7, 0, 10 0.187500 0.250000
7, 11, 13, 0, 8, 2, 14, 15, 4, 10, 1, 3, 5, 12, 6, 9 0.187500 0.250000
14, 0, 4, 7, 9, 1, 12, 10, 13, 2, 3, 6, 11, 8, 15, 5 0.195312 0.250000
14, 4, 11, 3, 1, 6, 7, 8, 10, 12, 2, 9, 13, 0, 5, 15 0.195312 0.250000
5, 15, 2, 7, 13, 3, 12, 0, 6, 10, 14, 1, 9, 8, 11, 4 0.195312 0.250000
1, 0, 14, 10, 2, 8, 12, 3, 15, 7, 11, 5, 13, 6, 4, 9 0.195312 0.250000
11, 8, 6, 10, 13, 14, 1, 0, 4, 12, 5, 7, 3, 15, 9, 2 0.195312 0.250000
UPPER BOUNDS OF MAXIMUM VALUES OF AVERAGE DIFFERENTIAL . . . 31
contains ⊕ instead of + in (13):
(51) f
(k)
⊕ (u, v) = (v, u ⊕ ϕ(v ⊕ k)), u, v ∈ Vm
Applying equalities (2), (3), and (14), it’s easy to see that the expressions for the
average differential probability
(ω0, ω1) = ((α0, α), (α, α0 ⊕ AβT ))
and the linear probability
(ω
′
0, ω
′
1) = ((βA−1, β0), (α ⊕ β0, βA−1))
of the random transformation f
(k)
⊕ , where α0, β0 ∈ Vm,
α = (α(p−1), . . . , α(0)), β = (β(p−1), . . . , β(0)), α(j), β(j) ∈ Vt, j ∈ 0, p− 1,
take the forms
(52) 2−m
∑
k∈Vm
D
f
(k)
⊕
(ω0, ω1) = Dϕ(α, AβT ) =
p−1∏
j=0
Ds(j) (α(j), β(j)),
(53) 2−m
∑
k∈Vm
(
C
f
(k)
⊕
(ω
′
1, ω
′
0)
)2
=
(
Cϕ(βA−1, α)
)2
=
p−1∏
j=0
(
Cs(j) (β(j), α(j))
)2
,
respectively.
On the other hand, on the basis of formulas (22), (38), and (40), we obtain
(54) 2−m
∑
k∈Vm
Df(k)(ω0, ω1) = d(ϕ)(α, AβT ) ≤
p−1∏
j=0
Δ(sj)(α(j), β(j)),
(55) 2−m
∑
k∈Vm
(
Cf(k)(ω
′
1, ω
′
0)
)2
= l(ϕ)(α, βA−1) ≤
p−1∏
j=0
Λ(sj)(α(j), β(j)).
As we can see from relations (52) and (54) [also (53) and (55)], the differential (linear)
properties of the round encryption transformations of ciphers �⊕ and � have similar
analytical descriptions in terms of some parameters of their s-boxes.
To our mind, the similarity mentioned above allows us to expand the existing tech-
niques for the practical security estimation of Markov Feistel ciphers against differential
and linear cryptanalyses [with round transformations (51)] to a non-Markov cipher class
[with round transformations (13)]. The above can be also applied to SPN-ciphers and
their ”2m modulo” modifications. In particular, using the well-known active s-box count-
ing technique [7], it’s possible to make estimations (17), (18) depending on the matrix A
from (14) and more accurate.
It is worth comparing the parameter values
Δt
def
= min
s∈SVt
max
{
Δ(s)(α, β) : α, β ∈ Vt \ {0}
}
,
Dt
def
= min
s∈SVt
max {Ds(α, β) : α, β ∈ Vt \ {0}}
and, respectively,
Λt
def
= min
s∈SVt
max
{
Λ(s)(α, β) : α, β ∈ Vt \ {0}
}
,
32 A. ALEKSEYCHUK AND L. KOVALCHUK
Ct
def
= min
s∈SVt
max
{
Cs(α, β)2 : α, β ∈ Vt \ {0}
}
that characterize the differential and linear probabilities of the best � and �⊕ cipher
s-boxes.
It is well known [12] that, at t = 4, C4 = D4 = 0.25. On the other hand, according to
the data in Table 3, Λ4 ≤ 0.25, Δ4 ≤ 0.18. So, at least at t = 4, the sets of s-boxes of the
cipher � exist, for which the maximum average differential probability of the one-round
encryption transformation is less than the maximum average differential probability of
the one-round encryption transformation of the cipher �⊕ with arbitrary determined
s-boxes [see relations (52) and (54)]. The problem of the calculation of exact values of
Δt and Λt isn’t solved still.
Finally, we have to remark that the important task for the future investigations is the
extension of Theorem 1 to a wider class of group operations applied for the definitions
of differential and linear approximations of the block cipher transformations. We can
include the addition modulo 2m into natural operations of the same type.
Acknowledgement
The authors would like to thank Victor Bezditny and Sergey Ignatenko for their help
in the statistical estimation with PC of the results described in Section 5 of this paper.
Bibliography
1. Biham E., Shamir A., Differential cryptanalysis of DES-like cryptosystems, J. of Cryptology 4
(1991), no. 1, 3–72.
2. Lai X., Massey J.L., Murphy S., Markov ciphers and differential cryptanalysis, Advances in
Cryptology - EUROCRYPT’91, Proceedings, Springer, 1991, pp. 17–38.
3. Matsui M., Linear cryptanalysis methods for DES cipher, Advances in Cryptology - EURO-
CRYPT’93, Proceedings, Springer, 1994, pp. 386 – 397.
4. Biryukov A., Block ciphers and stream ciphers: the state of the art, http://eprint.iacr.org/
2004/094.
5. Vaudenay S., Decorrelation: a theory for block cipher security, J. of Cryptology 16 (2003),
no. 4, 249–286.
6. Daemen J., Rijmen V., Statistics of correlation and differentials in block ciphers,
http://eprint.iacr.org/ 2005/212.
7. Kanda M., Practical security evaluation against differential and linear cryptanalyses for Feistel
ciphers with SPN round function, Selected Areas in Cryptography. - SAC 2000, Proceedings
(2001), Springer Verlag, 324–338.
8. Gosudarstvennyi Standart 28147-89. Cryptographic Protection for Data Processing Systems,
Government Committee of the USSR for Standarts (1989).
9. Vaudenay S., On the security of CS-cipher, Fast Software Encryption. - FSE’99, Proceedings,
Springer, 1999, pp. 260–274.
10. Knudsen L.R., Practically secure Feistel cipher, Fast Software Encryption. - FSE’94, Proceed-
ings, Springer, 1994, pp. 211–221.
11. Kanda M., Takashima Y., Matsumoto T., et al., A strategy for constructing fast round func-
tions with practical security against differential and linear cryptanalysis, Selected Areas in
Cryptography. - SAC 1998, Proceedings, Springer, 1999, pp. 264–279.
12. Canteaut A., Cryptographic functions and design criteria for block ciphers, INDOCRYPT’2001,
Proceedings, Springer, 2001, pp. 1–16.
|