Cryptology 1.2 Methods for Generating a Key Stream

a7Hzq .#5r< kÜ\as TâÆK$ ûj(Ö2 ñw%h: Úk{4R f~`z8 ¤˜Æ+Ô „&¢Dø

Here are four methods for generating the key stream. The enumeration corresponds to increasing security.

Method 1: Periodic bit sequence

A periodically repeated (longer or shorter) bit sequence serves as key. Technically this is a BELLASO (or VIGENÈRE) cipher over the alphabet F₂. The classical cryptanalytic methods for periodic polyalphabetic ciphers apply, such as period analysis or probable word.

Known or probable plaintext easily breaks periodic XOR encryption.

Method 2: Running-Text

A classical approach to generating an aperiodic key is taking an existing data stream, or file, or text, that has at least the length of the plaintext. For a bitstream cipher the key stream is a bit sequence from another source, for example the content of a CD from a certain position. The analysis uses the methods from Chapter I.5. Note that the key space is far too small as soon as the enemy knows the source of the key stream, for example the CD—linearly searching through 700 MB of data is almost effortless.

XOR encryption with running-text keys is fairly easily broken.

Method 4: True Random Sequence (One Time Pad)

The extreme choice for a key on the secure side is a true random sequence of bits as key stream. However, as we saw in Part I, this is not practicable in many situations due to the complex key management.

Method 3: Pseudorandom Sequence

For XOR encryption—as approximation to the OTP—algorithmically generated bit sequences are much more practicable. But the attacker should have no means to distinguish them from true random sequences. This is the essence of the concept of pseudorandomness, and generating pseudorandom sequences is of fundamental cryptologic relevance.

We try to mimic the ideal properties of the One Time Pad by using a pseudorandom bit sequence that is generated from a short »effective key« (or start value) by an algorithm (called pseudorandom generator) instead of a »true« random sequence. Even if we use a pseudorandom generator of lesser quality, the ciphertext resists statistical analyses. We are left with the challenge of making the cipher secure from attacks with known plaintext. The remainder of this chapter addresses this problem.

To be useful for cryptographic purposes the pseudorandom key stream must depend on parameters the attacker has no access to and that represent the cryptographic key. Such parameters might be, see the figure that extends the basic model of a pseudorandom generator:

• the initial value of the state,
• parameters the transition algorithm depends on.

The PDF of this section contains some more material.