21-08-2012, 02:33 PM
Stream Ciphers
1Stream Ciphers.pdf (Size: 568.06 KB / Downloads: 310)
Introduction
Stream Ciphers vs. Block Ciphers
Symmetric cryptography is split into block ciphers and stream ciphers, which are
easy to distinguish. Figure 2.2 depicts the operational differences between stream
(Fig. 2.2a) and block (Fig. 2.2b) ciphers when we want to encrypt b bits at a time,
where b is the width of the block cipher.
Stream ciphers encrypt bits individually. This is achieved by adding a bit from
a key stream to a plaintext bit. There are synchronous stream ciphers where
the key stream depends only on the key, and asynchronous ones where the key
stream also depends on the ciphertext. If the dotted line in Fig. 2.3 is present,
the stream cipher is an asynchronous one. Most practical stream ciphers are synchronous
ones and Sect. 2.3 of this chapter will deal with them. An example of
an asynchronous stream cipher is the cipher feedback (CFB) mode introduced in
Sect. 5.1.4.
Why Is Modulo 2 Addition a Good Encryption Function?
A mathematical explanation for this is given in the context of the One-Time Pad in
Sect. 2.2.2. However, it is worth having a closer look at addition modulo 2. If we do
arithmetic modulo 2, the only possible values are 0 and 1 (because if you divide by
2, the only possible remainders are 0 and 1). Thus, we can treat arithmetic modulo
2 as Boolean functions such as AND gates, OR gates, NAND gates, etc. Let’s look
at the truth table for modulo 2 addition:
This should look familiar to most readers: It is the truth table of the exclusive-OR,
also called XOR, gate. This is in important fact: Modulo 2 addition is equivalent to the XOR operation. The XOR operation plays a major role in modern cryptography
and will be used many times in the remainder of this book.
The question now is, why is the XOR operation so useful, as opposed to, for
instance, the AND operation? Let’s assume we want to encrypt the plaintext bit
xi = 0.
What Exactly Is the Nature of the Key Stream?
It turns out that the generation of the values si, which are called the key stream, is
the central issue for the security of stream ciphers. In fact, the security of a stream
cipher completely depends on the key stream. The key stream bits si are not the key
bits themselves. So, how do we get the key stream? Generating the key stream is
pretty much what stream ciphers are about. This is a major topic and is discussed
later in this chapter. However, we can already guess that a central requirement for
the key stream bits should be that they appear like a random sequence to an attacker.
Otherwise, an attacker Oscar could guess the bits and do the decryption by himself.
Hence, we first need to learn more about random numbers.
Historical Remark Stream ciphers were invented in 1917 by Gilbert Vernam, even
though they were not called stream ciphers back at that time. He built an electromechanical
machine which automatically encrypted teletypewriter communication.
The plaintext was fed into the machine as one paper tape, and the key stream
as a second tape. This was the first time that encryption and transmission was automated
in one machine. Vernam studied electrical engineering at Worcester Polytechnic
Institute (WPI) in Massachusetts where, by coincidence, one of the authors
of this book was a professor in the 1990s. Stream ciphers are sometimes referred to
as Vernam ciphers. Occasionally, one-time pads are also called Vernam ciphers. For
further reading on Vernam’s machine, the book by Kahn [97] is recommended.
Random Numbers and an Unbreakable Stream Cipher
Random Number Generators
As we saw in the previous section, the actual encryption and decryption of stream
ciphers is extremely simple. The security of stream ciphers hinges entirely on a
“suitable” key stream s0, s1, s2, . . .. Since randomness plays a major role, we will first
learn about the three types of random number generators (RNG) that are important
for us.
True Random Number Generators (TRNG)
True random number generators (TRNGs) are characterized by the fact that their
output cannot be reproduced. For instance, if we flip a coin 100 times and record the
resulting sequence of 100 bits, it will be virtually impossible for anyone on Earth
to generate the same 100 bit sequence. The chance of success is 1/2100, which is
an extremely small probability. TRNGs are based on physical processes. Examples
include coin flipping, rolling of dice, semiconductor noise, clock jitter in digital
circuits and radioactive decay. In cryptography, TRNGs are often needed for generating
session keys, which are then distributed between Alice and Bob, and for other
purposes.
1Stream Ciphers.pdf (Size: 568.06 KB / Downloads: 310)
Introduction
Stream Ciphers vs. Block Ciphers
Symmetric cryptography is split into block ciphers and stream ciphers, which are
easy to distinguish. Figure 2.2 depicts the operational differences between stream
(Fig. 2.2a) and block (Fig. 2.2b) ciphers when we want to encrypt b bits at a time,
where b is the width of the block cipher.
Stream ciphers encrypt bits individually. This is achieved by adding a bit from
a key stream to a plaintext bit. There are synchronous stream ciphers where
the key stream depends only on the key, and asynchronous ones where the key
stream also depends on the ciphertext. If the dotted line in Fig. 2.3 is present,
the stream cipher is an asynchronous one. Most practical stream ciphers are synchronous
ones and Sect. 2.3 of this chapter will deal with them. An example of
an asynchronous stream cipher is the cipher feedback (CFB) mode introduced in
Sect. 5.1.4.
Why Is Modulo 2 Addition a Good Encryption Function?
A mathematical explanation for this is given in the context of the One-Time Pad in
Sect. 2.2.2. However, it is worth having a closer look at addition modulo 2. If we do
arithmetic modulo 2, the only possible values are 0 and 1 (because if you divide by
2, the only possible remainders are 0 and 1). Thus, we can treat arithmetic modulo
2 as Boolean functions such as AND gates, OR gates, NAND gates, etc. Let’s look
at the truth table for modulo 2 addition:
This should look familiar to most readers: It is the truth table of the exclusive-OR,
also called XOR, gate. This is in important fact: Modulo 2 addition is equivalent to the XOR operation. The XOR operation plays a major role in modern cryptography
and will be used many times in the remainder of this book.
The question now is, why is the XOR operation so useful, as opposed to, for
instance, the AND operation? Let’s assume we want to encrypt the plaintext bit
xi = 0.
What Exactly Is the Nature of the Key Stream?
It turns out that the generation of the values si, which are called the key stream, is
the central issue for the security of stream ciphers. In fact, the security of a stream
cipher completely depends on the key stream. The key stream bits si are not the key
bits themselves. So, how do we get the key stream? Generating the key stream is
pretty much what stream ciphers are about. This is a major topic and is discussed
later in this chapter. However, we can already guess that a central requirement for
the key stream bits should be that they appear like a random sequence to an attacker.
Otherwise, an attacker Oscar could guess the bits and do the decryption by himself.
Hence, we first need to learn more about random numbers.
Historical Remark Stream ciphers were invented in 1917 by Gilbert Vernam, even
though they were not called stream ciphers back at that time. He built an electromechanical
machine which automatically encrypted teletypewriter communication.
The plaintext was fed into the machine as one paper tape, and the key stream
as a second tape. This was the first time that encryption and transmission was automated
in one machine. Vernam studied electrical engineering at Worcester Polytechnic
Institute (WPI) in Massachusetts where, by coincidence, one of the authors
of this book was a professor in the 1990s. Stream ciphers are sometimes referred to
as Vernam ciphers. Occasionally, one-time pads are also called Vernam ciphers. For
further reading on Vernam’s machine, the book by Kahn [97] is recommended.
Random Numbers and an Unbreakable Stream Cipher
Random Number Generators
As we saw in the previous section, the actual encryption and decryption of stream
ciphers is extremely simple. The security of stream ciphers hinges entirely on a
“suitable” key stream s0, s1, s2, . . .. Since randomness plays a major role, we will first
learn about the three types of random number generators (RNG) that are important
for us.
True Random Number Generators (TRNG)
True random number generators (TRNGs) are characterized by the fact that their
output cannot be reproduced. For instance, if we flip a coin 100 times and record the
resulting sequence of 100 bits, it will be virtually impossible for anyone on Earth
to generate the same 100 bit sequence. The chance of success is 1/2100, which is
an extremely small probability. TRNGs are based on physical processes. Examples
include coin flipping, rolling of dice, semiconductor noise, clock jitter in digital
circuits and radioactive decay. In cryptography, TRNGs are often needed for generating
session keys, which are then distributed between Alice and Bob, and for other
purposes.