* INTRODUCTION TO SHIFT REGISTERS *

*******************************************

As discussed in my paper "Beginner's Stream Cipher Design Notes"

(http://www.inforeading.com/articles/art.php?info_mode=showone&id=98), perhaps

the most important aspect of a stream cipher is the stream of psuedo-random bits

with which the plaintext is combined: the keystream. One of the most commonly

used technologies used for pseudo-random number generation is the feedback

register. This paper concerns itself with the basics behind shift register

operation and design. It is the work of an amateur enthusiast, and should not

be taken as an authoritative work.

THE SHIFT REGISTER

Shift registers are one of the most commonly used devices for generating a

stream of psuedo random bits. A shift register is really nothing more than a

sequence of bits, which is continually shifted one bit to the right. The

rightmost bit is discarded, and the new leftmost bit is replaced by a function

of the other bits. The act of shifting the register is known as "clocking"

and the function used to produce the new bits the "feedback function". The

output of the register at each clock is usually the rightmost bit, but any of

the register's bits will suffice.

___________

----|Bitwise_XOR|

| _|_______|_____

|--->| x | x | x | x |---> OUTPUT

---------------

The diagram above shows a simple four bit register, in which the first and third

bits are XORed together to supply the new bit. If the register were initialized

with 1010, the output would be as follows:

Initial: 1010

After first clocking: 0101

After second clocking: 0010

After third clocking: 1001

After fourth clocking: 1100

After fifth clocking: 1110...

The output of the register is the string of rightmost bits, ie; 010100

LINEAR FEEDBACK SHIFT REGISTERS (LFSRs)

LFSRs are shift registers in which the feedback function is simply the XOR of

two or more other bits in the register. These are the simplest variety of

shift register. Like all shift registers, LFSRs are periodic; that is, they

will eventually begin to repeat themselves. This should be obvious when the

structure of a register is considered: As soon as the register occupies a

state which it has previously occupied (ie; one all the register's bits are

in a pattern identical to one they formed before), then the feedback function

will produce the same new bit as last time and the entire process will loop.

Since there are two to the power of n possible states for an n bit register,

the maximum period for a LFSR is given as 2^n - 1. The one is subtracted

since any LFSR initialized with a string of 0s will produce an infinite string

of 0s as output - not particularly usefull as a keystream.

Not all LFSRs will produce a bit stream of this maximum period, though.

Registers, which do this, are called maximal-period LFSRs, and their output

streams are called m-streams. Whether or not an LFSR will produce an m-stream

depends on which bits are XORed to produce the new bit. Bits, which are used

in the XOR are said to be "tapped". The mathematical theory to predict which

bits must be tapped for a certain sized register to produce an m-stream is

based on primitive polynomials, and is beyond the scope of this document. A

table of m-stream producing tap sequences for registers from 1 to 151 bits

long is provided in Bruce Schneier's "Applied Cryptography".

NON-LINEAR FEEDBACK SHIFT REGISTERS (NFSRs)

Shift registers, which use anything other than the XOR operator in the feedback

function is known as Non-linear Feedback Shift Registers. Any operation

requiring two bits can be used in a shift register's feedback function, and as

suck NFSRs can be very elaborate in their design. The result of this,

however, is that mathematical theory for analyzing NFSRs doesn't exist, which

is a strong contrast to LFSRs, for which there is an abundance of theory.

While the unavailability of theory is advantageous in that it makes

cryptanalysis of stream ciphers based on NFSRs difficult, it is a double

edged sword in that there isn't any way of be certain how secure an NFSR is or

how it will act. The periods of NFSRs are often less than are expected, and

other problems exist which make NFSRs impractical for use in stream ciphers.

FEEDBACK WITH CARRY SHIFT REGISTERS (FCSRs)

Feedback with carry shift registers utilize a carry register, which provides

the new bit for the shift register and is continually updated with input from

the register at each clock. A common example is the sum mod 2 FCSR, in which

the carry register is filled with the sum of the shift register bits, mod 2.

Modulus addition, such as that described above, is a form of addition whereby

the result can only have a maximum value, in this case 1. To demonstrate,

consider 3 + 5, mod 6:

After 1 is added to 3, the result is 4. This is less than 6, so we continue.

After 2 is added to 3, the result is 5. This is less than 6, so we continue.

After 3 is added to 3, the result is 6, which is our maximum. So the next

addition is done to zero instead. The fourth addition then gives us one,

and the fifth and final addition gives us 2. To try and summarize, the

running total of a modulus addition "wraps" back to zero whenever it exceeds

the maximum. As such, the sum mod 2 that is contained in the carry register

is only every 1 or 0. The new bit in the sum mod 2 FCSR is the content of the

carry register, and at each clock the contents of the register is divided by 2.

FCSR theory is still relatively new, and so not much work has been done. To

my knowledge, there do not exist any major stream ciphers which utilize them

for keystream generation, however some simple implementations are suggested

in Applied Cryptography. For now though, these remain rather untested and

should not be used for important security purposes.

COMBINING REGISTERS (CASCADES)

While a single shift register is adequate to produce a stream of pseudo-random

bits, it is a common practice to combine multiple registers together. Such

constructions are known as cascades. Cascades can combine registers in a

number of ways:

* The output of one register may be used as the new bit source of a second

register. Any number of registers could be combined in this way

* The output of two registers which function independently of one another may

be combined, say by XORing the two outputs together.

* The state of one register could be used to control the clocking of other

registers. For example, in a three register system, the first register may

clock continuously as per usual, but the second register clocks only when

the first outputs a 0. The third register clocks if the first outputs a 1.

The whole system outputs either the second or third register's output,

depending on the first register's state. These systems are called "Stop and

Go Generators".

Many variations of these methods, and some others not discussed, exist. It is

far beyond the scope of this paper to provide a description of all the various

cascade systems. See Applied Cryptography for such information - the Gollmann

Generator should be particularly noted.

SUMMARY

Shift registers, and LFSRs in particular, are a common method of pseudo-random

number generation, and at least a basic understanding of their functionality

is strongly recommended for those wishing to tinker with stream cipher design.

Shift registers are implemented much faster in hardware than software, making

them particularly useful for embedded cryptographic applications. Ciphers of

note which employ shift registers include A5, the stream cipher used to

encrypt GSM phone signals, XPD (aka KPD), a stream cipher designed by the

Hughes Aircraft Corp for use in military radios and the like, Nanoteq, a

cipher used by the South African police to encrypt fax transmissions, and

Rambuutan, a hardware only cipher chip designed by the British GCHQ.

comments on, as well as additions or corrections to this document are welcome.

(thenine@trinity.sa.edu.au)