Cryptography Reference
In-Depth Information
standard for encryption. In fact, KASUMI is a version of a block cipher named
MISTY1 running in a Counter mode and is employed to encrypt streams of data in
cellphone communications.
The two main parts of a stream cipher are the state-transition function, which,
given an old state, computes a new state, and a filter, which, given the actual state,
produces the output. The output of a stream cipher is a random-looking stream of bits
(or digits) which are typically XORed with a plaintext resulting in a ciphertext. Thus
stream ciphers can be viewed as a computational analogy of a one-time pad cipher,
replacing a long, perfectly random, secret key with a short secret “seed” from which a
stream of bits is generated pseudorandomly. For practical purposes it is fundamental
that the pseudorandom stream be computationally indistinguishable from a stream
of truly random bits.
Many stream ciphers are still based on Feedback Shift Registers (FSRs), where
these registers are combined in a variety of ways: LFSR with nonlinear filters, irregu-
lar stepping functions, nonlinear feedback functions, irregular decimation/shrinking
and any kind of nonlinear transform. (L)FSR-based ciphers are up to this day the
main workhorses when there is a need to encrypt large quantities of fast streaming
data. A number of secret military hardware-oriented ciphers belong to this group,
as do“civil” ciphers E0 (Bluetooth), designed for a short-range LAN, and one of
the most widely used (by the virtue of being included in the GSM cipher suite for
ensuring over-the-air privacy protection) ciphers A5/1.
A new, popular modern trend uses parts of block cipher-like rounds mixed with
LFSR-like structures; an example of such ciphers is MUGI [417], which has been
recommended by the Japanese e-government initiative CRYPTREC. In [50] this
approach has been generalized by turning any standard block cipher into a stream
cipher by a combination of an appropriate mode and a “leak extraction” phase, i.e.
outputting some parts of the internal state of a cipher at certain rounds, thus increasing
the rate at which the keystream is produced.
A champion in simplicity and robustness of modern stream ciphers, RC4 is based
on a 256-byte permutation table, somewhat similar to an S-Box, where a state tran-
sition function makes a pseudorandom swap of two elements of the table. The value
of one of the indices of the swapped elements is sequentially incremented and thus
is known, while the value of the other is computed as a sum of the previous value
and a result of a lookup in the table with the first index. RC4 with a 128-bit key is
a defacto Internet standard and is also recommended by the CRYPTREC initiative.
One of the finalists of the EU-funded network of excellence ECRYPT's competition
eSTREAM, HC-128 has a similar internal structure, but it uses a much larger state
made of two 512
32-bit word tables with rather complex state transition functions
and a nonlinear output filter.
We refer readers to [133] for a journey to a fascinating world of modern stream
ciphers, their making and breaking. In this chapter we will concentrate on so-called
fault attacks, i.e. attacks based on the simple discovery that by injecting faults in hard-
ware during execution of cryptographic algorithms, one can get privileged informa-
tion from within the encryption process, information which otherwise would have
been hidden from an attacker who is trying to analyze a cipher based only on its
×
