Cryptography Reference
In-Depth Information
Let m be a parameter, such that one wants to recover exactly m out of the l
secret key bytes by solving equations and the other l−m bytes by exhaustive
key search. Let n be another parameter (m ≤ n ≤ r) of our choice, that
denotes how many equations of the form S
r
[y] = f
y
, y = 0,1,...,n− 1, in l
variables (the key bytes) are to be considered.
Let EI
τ
denote the set of all systems of τ equations that are independent.
Equivalently, EI
τ
may be thought of as the collection of the subsets of indices
{y
1
,y
2
,...,y
τ
}⊆{0,1,...,n−1},
corresponding to all systems of τ independent equations (selected from the
above system of n equations).
In general, we need to check whether each of the
n
m
systems of m equa-
tions is independent or not. The next result establishes the criteria for in-
dependence of such a system of equations and also the total number of such
systems.
Theorem 4.2.2. Let l ≥ 2 be the RC4 key length in bytes. Suppose we want
to select systems of m independent equations, 2 ≤ m ≤ l, from the n equations
of the form S
r
[y] = f
y
, 0 ≤ y ≤ n− 1, involving the permutation bytes after
round r of the KSA, m ≤ n ≤r ≤ N.
Part1. The system S
r
[y
q
] = f
y
q
, 1 ≤ q ≤ m, of m equations corresponding to
y = y
1
,y
2
,...,y
m
, is independent if and only if any one of the following
two conditions hold:
(i) y
q
mod l, 1 ≤ q ≤m, yields m distinct values, or
(ii) y
q
mod l = (l − 1), 1 ≤ q ≤ m, and there is exactly one pair
y
a
,y
b
} such that y
a
= y
b
(mod l), and all other
y
q
mod l,q = a,q = b, yields m− 2 distinct values different from
y
a
,y
b
(mod l).
∈ {y
1
,y
2
,...,y
m
Part 2. The total number of independent systems of m (≥ 2) equations is
given by
m
l−n mod l
m−x
n mod l
x
(⌊
l
⌋+ 1)
x
(⌊
l
⌋)
m−x
|EI
m
| =
x=0
m−2
n mod l
1
⌊
l
⌋+1
2
n mod l−1
x
l−n mod l−1
m−2−x
(⌊
l
⌋+1)
x
(⌊
l
⌋)
m−2−x
+
x=0
m−2
⌊
l
⌋
2
n mod l
x
(⌊
l
l−n mod l−1
1
l−n mod l−2
m−2−x
⌋+1)
x
(⌊
l
⌋)
m−2−x
,
+
x=0
u
v
where the binomial coe
cient
has the value 0, if u < v.
Proof: Part 1. First, we will show that any one of the conditions (i) and
(ii) is su
cient. Suppose that the condition (i) holds, i.e., y
q
mod l (1 ≤ q ≤
m) yields m distinct values. Then each equation involves a different key byte
as a variable, and hence the system is independent.
