*******************************************
* 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)
* 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)
