Two methods of generating pseudo-random bits, both in themselves very weak from a cryptographic point of view, because they are based on recurrence relations of a linear nature, are still at the root of most stream ciphers. The same simple mathematical properties that make them vulnerable to cryptanalysis at least ensure that they will generate sequences with a long period.

One is the *linear feedback shift register*,
most often used in hardware designs.

Another is the *mixed congruential pseudorandom number
generator*, usually used in software.

The first section following will deal with stream ciphers based strictly on single-bit shift registers; the second section will deal not only with linear congruential pseudorandom number generators, but with other techniques, including a byte-wide shift register.

Although one usually thinks of pseudo-random number or bit generation when one thinks of stream ciphers, the cipher produced by a rotor machine, which is a changing substitution (as opposed to a changing displacement, as produced by a Hagelin lug and pin machine) is still classed as a stream cipher. Also, even if the plaintext is modified by a simple XOR, the value used, instead of being generated by a process that feeds back only on itself, or which produces a function of a counter value, could be produced by a function of the last few bytes of plaintext or ciphertext, thus giving a cipher of the autokey type.

In general, autokey ciphers have poor error-propagation
characteristics. However, a stream cipher which uses the last few
ciphertext bytes only to determine how the next plaintext byte is to be
enciphered is called a *self-synchronizing stream cipher*, because
it can recover after an error, even if the error is a sufficiently long
burst that even the count of the number of bytes recieved is lost.

The Cipher Feedback (CFB) mode of DES is an example of this class of cipher, although in that case one would need to know the boundary between 8-byte blocks to recover.

Another, more elaborate, example would work like this:

--- | | Plaintext --- | (sub) | ---> XOR | | | (sub) | | |---> XOR | | | (sub) | | |---> XOR | | --- | (sub) | | | | |D| |---> XOR | | | | --|E|-| (sub) | | | | | | |S| |---> XOR | | | | | | --- | (sub) | | | | |---> XOR | | | | | (sub) | | | | |---> XOR | | | | | (sub) | | | | ---> XOR | | | (sub) | --- --- --- --- --- --- --- --- --- | | | | | | | | | | Ciphertext --- --- --- --- --- --- --- --- --- | | | | | | | | --------------------------- | | | |___|

in which the preceding eight bytes of ciphertext are fed back into DES encryption, and then the eight output bytes from the DES encryption are XORed to the plaintext byte, between eight byte-substitution stages (each one using a key-dependent permutation of the 256 values from 0 to 255).

This produces a highly secure cipher, but takes eight times as long as conventional DES encryption.

[Next] [Up] [Previous] [Index]

Next

Chapter Start

Skip to Next Section

Skip to Next Chapter

Table of Contents

Home Page