Cryptography Reference
In-Depth Information
To attack DSC, Nohl, Tews, and Weinmann used the following approach: If
DSC would be regularly clocked, one could easily recover the secret key. Of
course DSC is not regularly clocked, but the probability that register R1 has
been clocked
i
times, R2 has been clocked
j
times, and R3 has been clocked
k
times when the
l
th bit of output is produced is:
p
i,j,k,l
=
2
−
(40+
l
)3
40 +
l
40 +
l
40 +
l
i
−
(80 + 2
l
)
j
−
(80 + 2
l
)
k
−
(80 + 2
l
)
Let
s
=
x
(
i
)
1
,
0
,x
(
i
)
1
,
1
,x
(
j
)
2
,
0
,x
(
j
)
2
,
1
,x
(
k
)
3
,
0
,x
(
k
)
3
,
1
be the six bits of registers R1, R2, and
R3, which contributes to the keystream generated by DSC at this moment. To
eliminate some variables we may write
x
(
i
+1)
1
,
0
instead of
x
(
i
)
1
,
1
because the bit is
simply shifted with the next clock.
x
(
j
+1)
2
,
0
=
x
(
j
)
2
,
1
and
x
(
k
+1)
=
x
(
k
)
3
,
1
also holds.
Let
z
l
be the bit of output produced by DSC and
z
l−
1
be the previous bit of
output which is now stored in the memory bit of the output combiner. Because
s
is just a linear combination of key and IV bits, we may split it into a key and
IV part
s
=
s
key
+
s
iv
. The linear combination of the IV part
s
iv
is known by
the attacker for every keystream and the recovery of
s
key
would reveal 6 bit of
information about the secret key. If
3
,
0
(
s, z
l−
1
)=
z
l
holds for a value of
s
,it
can bee seen as an indication that
s
key
=
s
+
s
iv
for a higher probability than
guessing (
64
).
To execute the attack, a clocking interval C = [102
,
137] of length 35 was
chosen. This leads to 35
3
= 42875 possible combinations for the number of clocks
i, j, k
for the registers R1, R2, and R3 which reveal information about the state
variables
x
(102)
O
{
1
,
2
,
3
},
0
...x
(138)
{
1
,
2
,
3
},
0
. For every choice
i, j, k
of clocking combinations
in this interval a frequency table for the 2
6
= 64 choices for the key-part
key
of
s
is used. For every consecutive pair of bits
z
l
,z
l−
1
from the keystream where
the clocking combination has a none negligible probability and for every choice
of
s
,
1
p
=
l
(
s, z
l−
1
)=
z
l
]+
1
2
p
i,j,k,l
∗
[
O
−
p
i,j,k,l
l
is computed and ln
p
1
−p
is added to the frequency table entry
s
key
=
s
+
s
iv
.
Instead of representing the equations in the frequency table directly as linear
combinations of key-bits, a short form is used where all equations have the
form
x
(
·
)
{
},
0
=
{
0
,
1
}
. Every entry in the frequency table contains six of those
1
,
2
,
3
equations.
After all keystreams have been analyzed, we take every variable
v
and examine
all frequency tables which contain equations of the form
v
=
b
i
,b
i
∈{
0
,
1
}
.We
=
i
(2
b
i
−
take the top-voted entry from these tables and compute
p
v
1)
∗
p
i
where
p
i
is the number of votes for the top voted entry in the table. If
p
v
is
negative, we assume that
v
= 0 holds, 1 otherwise.
In total there are 36
∗
3 = 108 different equations. All of them are sorted
according to
. The original attack suggests using the topmost equations (for
example 30 equations) to build an equation system of the form
Ak
=
b
for the key
|
p
v
|
Search WWH ::
Custom Search