Information Technology Reference
In-Depth Information
The eciency of TMTO attacks can be improved using different approaches.
Using distinguished points approach, instead of generating fixed length chains,
the chains are terminated whenever a distinguished
x
ij
(e.g. having last
m
bits
as zero) is obtained. This improvement reduces the memory access in the online
phase, since a value is compared to the end points only if it is a distinguished
point. In [7], the idea of distinguished points is used to attack 40-bit DES and the
key is recovered in 10 seconds with a success rate of 72%. Another improvement
is to use Rainbow tables [8] where different reduction functions are utilized. In
this approach, instead of having
t
different tables, only one table of size
mt
×
t
is generated.
TMTO Attacks Against Stream Ciphers.
TMTO attacks against stream
ciphers are firstly proposed by Babbage [2] and Golic [3] independently. In the
pre-computation phase, the function
f
:
log
2
that inputs the
logN
bit state and outputs
logN
keystream bits is considered and the following table
is generated:
logN
2
F
→
F
(
S
1
,f
(
S
1
))
(
S
2
,f
(
S
2
))
.
(
S
M
,f
(
S
M
))
using
M
randomly selected initial states
S
i
. Then, the table is sorted with
complexity
O
(
MlogM
) based on the output keystream bits. Given the output
keystream of length
D
+
logN
1,
D
overlapping
logN
bit subsequences are
generated and compared to the table generated in the oine phase. It should be
noted that unlike block ciphers, the TMTO attacks against stream ciphers do
not require chosen plaintext.
In [4], Biryukov and Shamir combined the tradeoff attacks presented by Hell-
man and Babbage-Golic. Using the same
f
function, chains of length
t
are gen-
erated by assigning the output keystream as the new internal state as presented
in Fig. 2. Instead of using output size of
n
bits (internal state size), for stream
ciphers using
k
bit key and
v
bit IVs the output size is taken as
k
+
v
bits can be
used. Using this approach, it is possible to recover the key with time and mem-
ory complexity
T
=
M
=2
2
(
k
+
v
)
if
D
=2
4
(
k
+
v
)
frames are available [5]. For
IVs shorter than key (
v<k
), the stream ciphers are vulnerable to the TMTO
attack. Therefore, to avoid the attack, IV size should be at least equal to the key
size and IVs should not be used in a predictable way and the state size should
be at least the size of key plus IV.
According to [4], it is also possible to use distinguished points idea against
stream ciphers. Similar to Babbage-Golic scheme, the states and the correspond-
ing keystream with distinguished property are stored. This is especially impor-
tant in online phase where different keystream portions are compared to the
table. Since there is no need to check keystream portions that do not satisfy
the distinguishing property, this reduces the complexity of checking memory
significantly.
−
