F2G

F2G is a software tool implementing the algorithm presented in [1]. F2G transforms an NLFSR in the Fibonacci configuration into an equivalent NLFSR in the Galois configuration [2], [3]. Usually, an NLFSR can be transformed in many different ways. F2G attempts to maximize the throughput by finding a Galois NLFSR with the shortest critical path. Since it is based on a heuristic, its solution is not always optimal.

F2G reads in the feedback function of a Fibonacci NLFSR, converts it to the Galois configuration, prints out the set of feedback functions of the resulting equivalent Galois NLFSR, and estimates the increase in throughput. We assume that the bits of NLFSRs are labeled from n-1 to 0 where 0 is the output of the register.

F2G binaries are available for the following platforms:

The source code of F2G is available here.

To run F2G in Linux or Windows Cygwin, use the command:
./f2g
You will be asked to enter the feedback function of a Fibonacci NLFSR specified in an algebraic normal form (XOR-sum of products). For example, a 24-bit Fibonacci NLFSR may be specified as:

f23=x0+x3+x5+x9+x15+x17+x23+x1x4+x3x7+x2x4x6

It is also possible to restrict the transformation by listing the state bits which are not allowed to have a feedback in the Galois configuration. For example the input line of type:

f23=x0+x3+x5+x9+x15+x17+x23+x1x4+x3x7+x2x4x6 r=0-14,16,22

restricts the bits from 0 to 14, as well as the bits 16 and 22.

Such a restriction can be used to allow for different degrees of parallelization of the Galois NLFSR. If the state bits are not used for at least 2k iterations after they have been modified, then up to 2k iterations can be computed at once, provided that the circuits implementing feedback functions are duplicated k times. Thus, the clock frequency can be divided by a factor of k without affecting the throughput.

Another reason for adding a restriction might be the case when some state bits of the Fibonacci NLFSR are used for producing the keystream. In i is the largest of such bits, then in order to guarantee that the Galois NLFSR's bits from 0 to i follow the same sequences as the corresponding Fibonacci NLFSR's bits, we need to add the restriction r=0-(i-1).

TEST INPUTS

You can use the following NLFSRs from the stream ciphers Grain80/128 [4], VEST [5], Achterbahn-128/80 [6] and [7] to test F2G:

REFERENCES:

[1] "An Algorithm for Constructing a Fastest Galois NLFSR Generating a Given Sequence", J.-M.,Chabloz, S. Mansouri, E. Dubrova, in Sequences and Their Applications (SETA'2010), Eds. C. Carlet and A. Pott., LNCS 6338, 2010, pp. 41-55.

[2] "A Transformation from the Fibonacci to the Galois NLFSRs", E. Dubrova, IEEE Transactions on Information Theory, vol. 55, no. 11, 2009, pp. 5263-5271.

[3] "Finding Matching Initial States for Equivalent NLFSRs in the Fibonacci and the Galois Configurations", E. Dubrova, IEEE Transactions on Information Theory, vol. 56, no. 6, 2010, pp. 2961-2967.

[4] "The Grain Family of Stream Ciphers", M. Hell , T. Johansson, A. Maximov, W. Meier, in New Stream Cipher Designs: The eSTREAM Finalists, Eds. M. Robshaw and O. Billet, LNCS 4986, Springer-Verlag, 2008, pp. 179-190.

[5] "A Presentation on VEST Hardware Performance, Chip Area Measurements, Power Consumption Estimates and Benchmarking in Relation to the AES, SHA-256 and SHA-512", B. Gittins, H. A. Landman, S. O'Neil, R. Kelson, Cryptology ePrint Archive, Report 2005/415, 2005, http://eprint.iacr.org/.

[6] "Achterbahn-128/80: Design and Analysis", B. M. Gammel and R. Göttfert, O. Kniffler, Workshop Record of The State of the Art of Stream Ciphers (SASC'2007), 2007, pp. 152-165.

[7] "An NLFSR-based stream cipher", B. M. Gammel and R. Göttfert, O. Kniffler, Proceedings of IEEE International Symposium on Circuits and Systems (ISCAS'2006), 2006, pp. 4-8.

CONTACT PERSON:

Elena Dubrova
Department of Electronics, Computer and Software
School of Information and Communication Technology
dubrova@kth.se