Cryptography Reference
In-Depth Information
inner state to be guessed. The approach proposed by the authors suggests solving
2
2
4 linear equation systems, and checking which actually produced keystream
matches the correct one obtained, to successfully recover the key. The computational
bound of this attack technique is determined by the repeated solution of the 1
=
10
4
simultaneous equations four times, which can be achieved in minutes to hours on a
typical desktop computer.
.
8
×
14.5 An Overview of Grain, Rabbit and SNOW 3G
The landscape of the attacks to stream cipher does not end with the three attacks men-
tioned: we will now provide a quick overview of the attack techniques used to break
Grain, Rabbit and SNOW: three stream ciphers selected by either the eSTREAM
portfolio (Grain, Rabbit) or the 3GPP standard (SNOW 2.0).
Grain is a two state register stream cipher taken into consideration by the
eSTREAM project for the hardware implementation portfolio. The design of the
cipher involves a linear and a nonlinear feedback function for the two registers,
together with a nonlinear filter function to combine their contents and output the
keystream. The best classical cryptanalytic techniques have not yet obtained any
results against Grain; in [36] the authors report a successful fault attack based on a
single bit-flip in the state of the cipher, without knowledge of the flipped bit, though
requiring exact (clock-accurate) timing.
Rabbit is a stream cipher which entered both the software and the hardware port-
folio of the eSTREAM project thanks to both its reduced size and the vast amount
of white papers presented regarding its soundness with respect to a number of crypt-
analytic techniques (in particular algebraic, correlation-based and differential). In
order to break the ciphers the authors of [40] assume a quite original fault model:
the possibility of changing an ADD instruction into a XOR. This assumption allows
them to perform a kind of cryptanalysis much akin to the linear approximations of
multi-bit additions with simple XORs on the cipher and successfully recover the key
within a 2
34
time complexity.
The SNOW 2.0 cipher has been chosen as one of the standard ciphers to be
employed to encrypt 3G cellphone communication by the 3GPP committee. The
committee deemed some tweaks to be necessary and renamed the standardized cipher
SNOW 3G in order to distinguish it from the previous version.
The stream cipher has its inner state split into two parts: a shifting register with 16
32-bit wide cells and a Finite State Machine composed of three 32-bit registers. At
each clock cycle the inner state is updated by performing XORs (represented by the
⊕
symbol) and additions modulo 2
32
(
in Fig.
14.3
) on 32-bit values. In particular, the
feedback of the shifting register is obtained by adding together using XOR the value
of the third word of the register,
s
2
and the values of the other two multiplied by two
fixed values,
α
−
1
, over
Z
2
32
. In order to add a nonlinear mask to the output, a
Finite State Machine is employed to derive a 32-bit mask to be added to the first value
of the shift register, before outputting it as a part of the keystream. The nonlinearity
α
and
