Cryptography Reference
In-Depth Information
against the alternative hypothesis
1
N
,
K = K,P(E
y
1
,y
2
= e | H
1
) =
H
1
:
0 ≤e ≤ N −1.
The optimum decision rule is given by the Neyman-Pearson Lemma [31] as
follows: select H
0
if M(S
N
, K) > T; otherwise, select H
1
, where
log
(N −1)p
y
1
,y
2
1−p
y
1
,y
2
M(S
N
, K)
=
δ(e
y
1
,y
2
)
−1≤y
1
<y
2
≤N−1
1
if e = 0;
and
δ(e)
=
0
otherwise.
According to [83], the implementation requires (
l(l+1)
2
−1)N + 1 memory and
l(l+1)
2
N
l
table look-ups. The false positive and negative rates depend on the
threshold T.
The above idea can be extended to a bit-level decision-making process,
assuming that N is a power of 2. In this case, one needs to test the null
hypothesis
H
0
: K = K mod 2
r
,
against the alternative hypothesis
H
1
: K = K mod 2
r
,
where
p
y
1
,y
2
for e = 0;
P(E
y
1
,y
2
= e mod 2
r
| H
0
)
=
1−p
y
1
,y
2
2
r
−1
for 1 ≤ e ≤ 2
r
−1,
1
2
r
,
P(E
y
1
,y
2
= e mod 2
r
| H
1
)
0 ≤e ≤ 2
r
−1, and
=
N −2
r
2
r
(N −1)
(1 −p
y
1
,y
2
).
p
y
1
,y
2
= p
y
1
,y
2
+
The measure for comparison against the threshold T is given by
log
(2
r
−1)p
y
1
,y
2
1−p
y
1
,y
2
M
r
(S
N
, K) =
δ(e
y
1
,y
2
mod 2
r
).
−1≤y
1
<y
2
≤N−1
The key recovery technique is to search over all 2
l
possible values of the r-th
LSB of the key bytes, 1 ≤ r ≤ 8, assuming that the first (r−1) LSBs of the key
bytes are known, and choose only N
r
out of them with the highest correlation
measure M
r
(S
N
, K). The complexity of this tree-based search algorithm can
R−2
i
be shown to be 2
l
(1 +
N
j
), where R = ⌈log
2
N⌉.
i=0
j=0
