GAP (fsr) - Chapter 1: Preface

The GAP package FSR implements Feedback Shift Registers. Feedeback shift registers play an important role in stream cipher design. A well known early example of an LFSRs based stream cipher is A5/1, intended for securing GSM voice and data. A5/1 is built from three LFSRs with different periods and a stop-and-go majority function controlling their clocks. The A5/1 output is computed as XOR of outputs from all three LFSRs. A milestone in stream cipher design is the eSTREAM project [RB08], [Est], launched in 2004. All 3 hardware portfolio ciphers, Grain, MICKEY (using Galois-style feedback) and Trivium, as well as the software portfolio cipher Sosemanuk, use FSRs. The stream cipher ACORN [Wu], a CAESAR candidate [Cae], that made it to the final portfolio, is based on 6 LFSRs. Last but not least, both stream ciphers used for encryption and integrity of communications in mobile networks, Snow3G [sno] and ZUC [zuc], use LFSRs over an extension field.

Another application area for LFSRs are the cyclic redundancy codes (CRC) used in many communication and data storage devices for error-detection. The LFSRs have been used as counters in applications where the order of the sequence does not matter, for example Xilinx proposed the use of LFSR counters to address the RAM [Alf] (by now declared obsolete). Furthermore, LFSRs are used for pattern generation in built-in self testing for electronic circuits.

Less noticeable is the use of LFSRs in algorithms for finite field arithmetic. For example, a serial circuit that requires multiplication by \(x\), followed by reduction modulo the field defining polynomial, can be implemented as an LFSR with the defining polynomial as feedback [Has18].

1.1 Some basic concepts

An \(n\)-stage shift register over a finite field \(\mathcal{F}\) is an array of \(n\) registers (denoted \(S_t\), \(t=n-1, \ldots,0\)), and each stage holds a value from the underlying finite field \(\mathcal{F}\). \(n\) is also referred to as the length of the FSR. This memory array is shifted with each step \(S_t \rightarrow S_{t-1}\) for \(t=n-1, \dots,1\), and the vacant register \(S_{n-1}\) is updated with a new value obtained from the feedback function, hence the name feedback shift register (FSR). One of the stages is used to generate the output and each time the FSR is clocked. The chosen stage produces a new element \(s_i\in\mathcal{F}\). In this way, the FSR produces a sequence of elements:
\(\underline{s}=\{s_k\}= s_0,s_1,s_2,\dots\)
A simple schematic of an \(n\)-stage FSR shown in figure below produces the output sequence from stage \(S_0\).

The feedback function is a polynomial function in \(n\) variables (that correspond to the stages, i.e. variable \(x_t\) takes its value from the stage \(S_t\)):
\(f:\,\mathcal{F}^n \rightarrow \,\mathcal{F}\,\)
\(f(x_0,x_1,\dots,x_{n-1}) = \sum\limits_{\forall (i_0,i_1,\dots,i_{n-1}) \in Z_q^n}c_{i_0,i_1,\dots,i_{n-1}}x_0^{i_0} x_1^{i_1}\dots x_{n-1}^{i_{n-1}}\)
with coefficients \(c_{i_0,i_1,\dots,i_{n-1}}\in\mathcal{F}=\mathbb{F}_q\) and where \(i_t\in \mathbb{Z}_q\) and \(q\) is a prime or a prime power and \(t\in \mathbb{Z}_n\). The sum in the equation above runs over all possible monomials \( x_0^{i_0}x_1^{i_1}\dots x_{n-1}^{i_{n-1}}\).

The degree of a monomial is defined as the sum of all its powers and the degree of the polynomial as the maximum degree of all its monomials. For readability, notation \(m_{i_0,i_1,\dots,i_{n-1}}\) is introduced for monomials: \(m_{i_0,i_1,\dots,i_{n-1}}=m(x_0,x_1,\dots,x_{n-1})=x_0^{i_0}x_1^{i_1} \dots x_{n-1}^{i_{n-1}}\).

\({\rm Degree}(f(x_0,x_1,\dots,x_{n-1}))=\max\limits_{\forall (i_0,i_1,\dots,i_{n-1})\in Z_q^n} \left\{{\rm Degree}(m_{i_0,i_1,\dots,i_{n-1}})\right\}\)

Based on the degree of the feedback polynomial, distinction is made between linear (LFSR (2.2-1)) and nonlianear (NLFSR (2.3-1)) feedback shift registers. For the linear case, the degree of the feedback polynomial is 1.

At any given moment, the contents of the FSR hold \(n\) values from the underlying finite field, and can be written as a vector of length \(n\): \((s_0,s_1,\dots,s_{n-1})\in\mathcal{F}^n\). This vector is called the state of the FSR, and the state right after loading the initial state. The output sequence \(\underline{s}\) is completely determined by the feedback polynomial and the initial state.

In case of \(q=2\), \(\mathcal{F}=\mathbb{F}_2\), function \(f\) is a boolean function and the FSR produces a binary sequence. In all other cases, the sequence is referred to as a \(q\)-arry sequence.

To keep the chapter short, details will be omitted and the reader can refer to a number of sources such as [GG05],[CG12], [LN97].

1.2 Overview

The FSR package allows creation, initialization and running of FSRs, and can compute some of their properties, such as length or internal state size. A third object called FILFUN, short for ``filtering function'' was added. A filtering function is simply a multivariate function. Because of the similarities between filtering functions and NLFSR feedbacks, the FILFUN is created as an FSR object, which allows the reuse of most NLFSR methods (see [ZAG18] for details). The core functionality is organized into four basic parts:

The category of FSR objects is defined, and the FSRs can be created as LFSRs, NLFSRs or FILFUNs. They are created through a function call with various possibilities for the arguments, and will return an object with five components, and some (case specific) attributes and properties. Only the values that can change during the FSRs lifetime are implemented as components:

Initial state is kept as a component because we want the ability to reload and run the same FSR without creating a new instance. Field init is empty when the FSR is created and is updated when its loaded. The component state is updated with each FSR step. Field numsteps keeps track of the FRS: when created its set to -1, when loaded to 0, and then increments with each step. It is used for coding purposes to prevent an attempt of running an empty FRS and to stop the FRS once a certain threshold is reached, preventing it from looping indefinitely. The basis field holds the current basis used for representation of elements and can be chained when needed. The field sym is only set to true when symbolic computation is performed. The first example of symbolic FSR is shown in the example for LoadFSR (2.1-7).
Please note that there is no concept of shifting and updating of the state for the FILFUNs: the components init and state are loaded with same initial state, which is then used to evaluate the multivariate function, i.e. compute the ``feedback''. The computed value is the output of the FILFUN. Furthermore, state and numsteps are not updated.
The behavior of an FSR is captured with three methods:

StepFSR comes in two versions, and both are inherited by the RunFSR as well:

The external step and run are implemented because of their common use in cryptography.
Remainder of the FSR package consists of helper functions (for example to compute the degree of the feedback polynomial), writing functions (for example to print out a sequence of LFSR steps including the state changes to a *.txt file or directly as *.tex file) and drawing functions (generating the tikz for *.tex) as is shown in figure below.

1.3 Symbolic FSR

When the FSR package is loaded, two sets of global variables are created as finite field indeterminates and bound, namely \(x_0, \dots, x_{199}\) and \(s_0,\dots,s_{199}\). The \(x_k\) indeterminates are intended for the entry of the multivariate polynomials used to define the FSR objects. Given 200 indeterminates, e.g. a 200 stage NLFSR can be created. The \(s_k\) indeterminates are intended for symbolic computation with the FSRs: we create the FSR normally, but then load with initial state containing the indeterminates \(s_k\), which we call symbols. Then, the FSR can be run to obtain the symbollic sequence. The symbolic sequence allows for additional analysis, e.g. for finding the degree of the sequence elements or for finding the symbolic period of the sequence. Below is a simple explample of an NLFSR loaded with symbolic initial state and run for 10 steps.

   
 gap> K := GF(2);; f := x_0*x_1+x_2;; nl := NLFSR(K, f, 3);
 < empty NLFSR of length 3 over GF(2),
  given by MultivarPoly = x_0*x_1+x_2>
 gap> ist := [s_2, s_1, s_0];; seq:=  RunFSR(nl,ist,10);
 [ s_0, s_1, s_2, s_0*s_1+s_2, s_0*s_1+s_1*s_2+s_2, s_0*s_1*s_2+s_0*s_1+s_1*s_2,
   s_2, s_0*s_1+s_2, s_0*s_1+s_1*s_2+s_2, s_0*s_1*s_2+s_0*s_1+s_1*s_2, s_2 ]

NOTE: if the mixed symbols/FFE list is to be used in LoadFSR (2.1-7), LoadStepFSR (2.1-10) and RunFSR (2.1-11)) in place of ist or elmvec, the list must be multiplied with One(s_0), e.g.:

  
  gap> ist := [s_2, s_1, Z(2)^0]*One(s_0);; seq:=  RunFSR(nl,ist,10);
  [ Z(2)^0, s_1, s_2, s_1+s_2, s_1*s_2+s_1+s_2, s_1, s_2, s_1+s_2,
    s_1*s_2+s_1+s_2, s_1, s_2 ]

1 Preface

1.1 Some basic concepts

1.2 Overview

1.3 Symbolic FSR