# 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:

• Linux: F2G Tested on Red Hat Enterprise kernel 2.6.18, Ubuntu 8.04 (64 bit), and Fedora Core 8.

• Windows Cygwin: F2G Tested on cygwin1.dll version 1.5.25.

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:
• Grain80 stream cipher [4]:

80-bit NLFSR, original version:

f79=x62+x60+x52+x45+x37+x33+x28+x21+x14+x9+x0+x63x60+x37x33+x15x9+x60x52x45+x33x28x21+x63x45x28x9+x60x52x37x33+x63x60x21x15+x63x60x52x45x37+x33x28x21x15x9+x52x45x37x33x28x21 r=0-62

Note that Grain80 uses the bit 63 of the NLFSR for producing its keystream, hence the restriction r=0-62.

Degree of parallelization x 4:

f79=x62+x60+x52+x45+x37+x33+x28+x21+x14+x9+x0+x63x60+x37x33+x15x9+x60x52x45+x33x28x21+x63x45x28x9+x60x52x37x33+x63x60x21x15+x63x60x52x45x37+x33x28x21x15x9+x52x45x37x33x28x21 r=0-66,68-70,72-74,76-78

Degree of parallelization x 8:

f79=x62+x60+x52+x45+x37+x33+x28+x21+x14+x9+x0+x63x60+x37x33+x15x9+x60x52x45+x33x28x21+x63x45x28x9+x60x52x37x33+x63x60x21x15+x63x60x52x45x37+x33x28x21x15x9+x52x45x37x33x28x21 r=0-70,72-78

• Grain128 stream cipher [4]:

128-bit NLFSR, original version:

f127= x0+x26+x56+x91+x96+x3x67+x11x13+x17x18+x27x59+x40x48+x61x65+x68x84 r=0-94

Note that Grain128 uses the bit 95 of the NLFSR for producing its keystream, hence the restriction r=0-94.

Degree of parallelization x 4:

f127= x0+x26+x56+x91+x96+x3x67+x11x13+x17x18+x27x59+x40x48+x61x65+x68x84 r=0-98,100-102,104-106,108-110,112-114,116-118,120-122,124-126

Degree of parallelization x 8:

f127= x0+x26+x56+x91+x96+x3x67+x11x13+x17x18+x27x59+x40x48+x61x65+x68x84 r=0-102,104-110,112-118,120-126

Degree of parallelization x 16:

f127= x0+x26+x56+x91+x96+x3x67+x11x13+x17x18+x27x59+x40x48+x61x65+x68x84 r=0-110,112-126

• VEST stream cipher [5]:

• 32 NLFSRs, the first 16 are of size 11-bit, the last 16 are of size 10-bit:

f10=x0+x8x9+x4+x4x10+x4x9x10+x4x8x9+x3+x3x10+x3x9x10+x3x8+x3x4+x3x4x9+x3x4x9x10+x3x4x8+x3x4x8x9+x3x4x8x9x10

f10=x0+x9+x9x10+x4+x4x9+x4x8x10+x4x8x9+x3x10+x3x8+x3x8x10+x3x8x9+x3x4x10+x3x4x9+x3x4x9x10+x3x4x8x10+x3x4x8x9+x3x4x8x9x10

f10=x0+x9x10+x4+x4x10+x4x9+x4x8x10+x4x8x9+x4x8x9x10+x3+x3x8x10+x3x8x9x10+x3x4+x3x4x10+x3x4x8+x3x4x8x9x10

f10=x0+x10+x9+x9x10+x8+x8x10+x4x10+x4x9+x4x9x10+x3+x3x9+x3x8+x3x8x9+x3x4x9+x3x4x9x10+x3x4x8+x3x4x8x9x10

f10=x0+x10+x8x10+x8x9+x4+x4x9x10+x4x8x9x10+x3+x3x10+x3x9+x3x9x10+x3x8+x3x8x10+x3x4x10+x3x4x8+x3x4x8x10+x3x4x8x9x10

f10=x0+x10+x9x10+x8x10+x8x9x10+x4x10+x4x9x10+x4x8+x4x8x9+x3x10+x3x9+x3x9x10+x3x4+x3x4x10+x3x4x9x10+x3x4x8x9+x3x4x8x9x10

f10=x0+x10+x9+x9x10+x8x10+x4+x4x10+x4x8+x3+x3x10+x3x8x10+x3x8x9+x3x8x9x10+x3x4x10+x3x4x9x10+x3x4x8+x3x4x8x9x10

f10=x0+x10+x9+x8x9+x8x9x10+x4+x4x9x10+x3+x3x9+x3x8x9+x3x8x9x10+x3x4+x3x4x9+x3x4x9x10+x3x4x8x9x10

f10=x0+x9x10+x8x9+x8x9x10+x4+x4x9x10+x3+x3x9+x3x9x10+x3x4+x3x4x10+x3x4x9+x3x4x8+x3x4x8x9+x3x4x8x9x10

f10=x0+x9x10+x8+x8x9+x4+x4x10+x4x9+x4x9x10+x4x8+x3x10+x3x8x10+x3x8x9x10+x3x4x10+x3x4x9+x3x4x8+x3x4x8x9+x3x4x8x9x10

f10=x0+x10+x9x10+x8x9+x8x9x10+x4x8+x4x8x10+x4x8x9x10+x3+x3x8x10+x3x8x9+x3x4+x3x4x9+x3x4x8x10+x3x4x8x9+x3x4x8x9x10

f10=x0+x9x10+x8+x8x10+x4x9+x4x8x9+x3x9x10+x3x8+x3x8x10+x3x8x9+x3x8x9x10+x3x4+x3x4x9+x3x4x8x9+x3x4x8x9x10

f10=x0+x10+x9x10+x8x9x10+x4x10+x4x9+x4x8x9+x4x8x9x10+x3+x3x9+x3x8x10+x3x8x9+x3x8x9x10+x3x4x10+x3x4x8+x3x4x8x10+x3x4x8x9x10

f10=x0+x9+x9x10+x8+x8x10+x8x9x10+x4+x4x10+x4x8x10+x4x8x9+x4x8x9x10+x3x10+x3x8x9x10+x3x4x10+x3x4x8+x3x4x8x9+x3x4x8x9x10

f10=x0+x10+x9x10+x8x10+x8x9x10+x4x9+x3+x3x9+x3x9x10+x3x8+x3x8x9+x3x8x9x10+x3x4x10+x3x4x9+x3x4x8+x3x4x8x9+x3x4x8x9x10

f10=x0+x10+x9+x9x10+x8+x4x9+x4x8+x4x8x9x10+x3x10+x3x9x10+x3x8x9+x3x8x9x10+x3x4x9+x3x4x9x10+x3x4x8x10+x3x4x8x9+x3x4x8x9x10

f9=x0+x9+x7+x7x9+x7x8+x3+x3x9+x3x7x8+x2+x2x9+x2x8+x2x7x9+x2x7x8+x2x7x8x9+x2x3x8+x2x3x7+x2x3x7x8x9

f9=x0+x8+x8x9+x7+x7x8+x3x9+x3x7+x3x7x8+x2x9+x2x8+x2x7x9+x2x7x8+x2x3x9+x2x3x8+x2x3x7x8x9

f9=x0+x9+x8+x8x9+x7x8+x3+x3x9+x3x8x9+x3x7x8+x2+x2x8+x2x3x8+x2x3x7+x2x3x7x8+x2x3x7x8x9

f9=x0+x8+x8x9+x7x9+x7x8x9+x3+x3x9+x3x8+x3x8x9+x2x9+x2x8+x2x7x9+x2x7x8+x2x3+x2x3x9+x2x3x7x9+x2x3x7x8x9

f9=x0+x8x9+x7+x7x9+x7x8+x7x8x9+x3+x3x8+x3x7+x2x8+x2x8x9+x2x7+x2x7x8x9+x2x3x9+x2x3x8+x2x3x7x8+x2x3x7x8x9

f9=x0+x8x9+x7x8+x7x8x9+x3x9+x3x8+x3x8x9+x3x7+x3x7x9+x2x9+x2x8x9+x2x7+x2x7x9+x2x3x8x9+x2x3x7+x2x3x7x9+x2x3x7x8x9

f9=x0+x8+x8x9+x7+x7x8x9+x3+x3x7+x3x7x9+x2+x2x8+x2x7x9+x2x7x8+x2x3x8x9+x2x3x7+x2x3x7x9+x2x3x7x8+x2x3x7x8x9

f9=x0+x9+x8+x7x8+x7x8x9+x3x9+x3x8x9+x3x7+x3x7x8x9+x2x9+x2x8+x2x8x9+x2x7x8+x2x7x8x9+x2x3x7x9+x2x3x7x8+x2x3x7x8x9

f9=x0+x8+x8x9+x7x9+x7x8+x3+x3x8+x3x8x9+x3x7+x3x7x9+x3x7x8x9+x2x8x9+x2x7+x2x3+x2x3x8+x2x3x8x9+x2x3x7x8x9

f9=x0+x9+x7x9+x7x8+x3+x3x8+x3x7+x3x7x9+x3x7x8+x3x7x8x9+x2x9+x2x8x9+x2x3+x2x3x8+x2x3x8x9+x2x3x7x8+x2x3x7x8x9

f9=x0+x7+x3x8+x3x7+x3x7x9+x3x7x8x9+x2+x2x8+x2x7+x2x7x9+x2x7x8x9+x2x3x9+x2x3x8+x2x3x8x9+x2x3x7x9+x2x3x7x8+x2x3x7x8x9

f9=x0+x9+x8x9+x7+x7x8x9+x3x8x9+x3x7x9+x2x8+x2x8x9+x2x7+x2x7x8x9+x2x3+x2x3x8+x2x3x7x9+x2x3x7x8x9

f9=x0+x9+x7+x7x8x9+x3x8x9+x3x7+x3x7x9+x3x7x8+x2+x2x9+x2x8x9+x2x7+x2x7x8+x2x3+x2x3x7+x2x3x7x8+x2x3x7x8x9

f9=x0+x9+x7+x7x8+x7x8x9+x3+x3x7+x3x7x9+x3x7x8x9+x2+x2x9+x2x8x9+x2x7x9+x2x3x8+x2x3x7x8x9

f9=x0+x9+x8+x7+x3+x3x9+x3x8x9+x3x7x9+x3x7x8x9+x2x8+x2x7+x2x7x9+x2x7x8+x2x7x8x9+x2x3+x2x3

f9=x0+x9+x8+x8x9+x7x9+x7x8+x7x8x9+x3x9+x3x7x9+x2+x2x7x9+x2x7x8+x2x7x8x9+x2x3+x2x3x7+x2x3x7x8+x2x3x7x8x9

• Achterbahn-128/80 stream cipher [6]:

• 13 NLFSRs of sizes 21-33:

f21=x0+x2+x3+x4+x5+x6+x8+x11+x15+x1x11+x2x11+x2x12+x4x6+x4x7+x5x6+x1x2x11+x1x2x12+x1x9x11+x9x10x11+x1x2x6x13+x1x2x9x11+x1x2x9x12+x2x9x10x11+x2x9x10x12+x1x2x6x9x13+x2x6x9x10x13

f22=x0+x1+x5+x6+x8+x13+x15+x1x3+x1x7+x1x13+x4x12+x5x11+x6x12+x7x9+x1x11x14+x1x4x11x14+x1x7x11x14+x1x4x10x11x14+x1x7x9x11x14+x1x10x11x12x14

f23=x0+x4+x5+x13+x16+x1x6+x1x7+x4x6+x5x11+x7x9+x8x11+x12x14+x1x5x9x15+x1x9x10x15+x1x3x9x11x1+x1x5x9x11x15+x1x8x9x11x15+x1x9x10x11x15

f24=x0+x2+x3+x6+x8+x12+x18+x1x11+x1x15+x2x13+x4x13+x6x15+x12x13+x13x14+x2x5x6+x2x5x14+x2x6x7+x2x7x14+x5x6x7+x5x7x14+x1x2x5x15+x1x2x7x15+x1x5x7x15+x2x5x6x15+x2x5x9x14+x2x5x9x16+x2x6x7x15+x2x7x9x14+x2x7x9x16+x5x6x7x15+x5x7x9x14+x5x7x9x16

f25=x0+x6+x11+x20+x1x5+x3x5+x4x12+x5x14+x6x16+x7x16+x8x15+x8x17+x15x17+x2x3x14+x2x5x14+x5x8x15+x5x8x17+x5x12x13+x5x12x14+x5x15x17+x2x3x8x15+x2x3x8x17+x2x3x12x13+x2x3x12x14+x2x3x15x17+x2x5x8x15+x2x5x8x17+x2x5x12x13+x2x5x12x14+x2x5x15x17

f26=x0+x4+x5+x15+x16+x17+x21+x2x4+x2x18+x3x6+x4x13+x12x13+x3x4x10+x3x4x15+x3x10x14+x3x14x15+x4x10x15+x10x14x15+x3x4x10x13+x3x4x13x15+x3x7x10x11+x3x7x10x14+x3x7x11x15+x3x7x14x15+x3x10x12x13+x3x12x13x15+x4x10x13x15+x7x10x11x15+x7x10x14x15+x10x12x13x15

f27=x0+x3+x4+x15+x25+x1x3+x1x8+x1x12+x6x17+x10x13+x10x17+x13x14+x5x10x11x18+x2x5x11x16x18+x2x5x11x17x18+x5x10x11x13x18+x5x11x13x14x18+x5x11x16x17x18

f28=x0+x1+x5+x20+x25+x1x2+x2x17+x4x12+x10x15+x10x18+x14x16+x16x20+x7x9x18x19+x7x9x10x15x19+x7x9x10x18x19+x1x2x7x9x13x19

f29=x0+x2+x10+x11+x17+x18+x21+x24+x1x4+x8x21+x10x21+x13x19+x6x15x19+x8x9x18+x13x14x16+x13x14x19+x13x15x19+x6x14x15x16+x6x14x15x19+x8x9x18x19+x13x14x15x16+x13x14x15x19+x8x9x14x16x18+x8x9x14x18x19

f30=x0+x1+x7+x10+x12+x18+x28+x2x8+x4x7+x4x18+x10x12+x10x19+x10x22+x14x22+x3x5x7+x3x7x8+x5x7x8+x1x3x5x9+x1x3x5x21+x1x3x8x9+x1x3x8x21+x1x5x8x9+x1x5x8x21+x3x4x5x7+x3x4x5x18+x3x4x7x8+x3x4x8x18+x3x5x9x21+x3x8x9x21+x4x5x7x8+x4x5x8x18+x5x8x9x21

f31=x0+x2+x5+x6+x15+x17+x18+x20+x25+x8x18+x8x20+x12x21+x14x19+x17x21+x20x22+x4x12x22+x4x19x22+x7x20x21+x8x18x22+x8x20x22+x12x19x22+x20x21x22+x4x7x12x21+x4x7x19x21+x4x12x21x22+x4x19x21x22+x7x8x18x21+x7x8x20x21+x7x12x19x21+x8x18x21x22+x8x20x21x22+x12x19x21x22

f32=x0+x3+x17+x22+x28+x2x13+x5x19+x7x19+x8x12+x8x13+x13x15+x2x12x13+x7x8x12+x7x8x14+x8x12x13+x2x7x12x13+x2x7x13x14+x4x11x12x24+x7x8x12x13+x7x8x13x14+x4x7x11x12x24+x4x7x11x14x24

f33=x0+x2+x7+x9+x10+x15+x23+x25+x30+x8x15+x12x16+x13x15+x13x25+x1x8x14+x1x8x18+x8x12x16+x8x14x18+x8x15x16+x8x15x17+x15x17x24+x1x8x14x17+x1x8x17x18+x1x14x17x24+x1x17x18x24+x8x12x16x17+x8x14x17x18+x8x15x16x17+x12x16x17x24+x14x17x18x24+x15x16x17x24

• The stream cipher from [7]:

Ten NLFSRs of sizes 22-29, 31 and 32 bits:

f21=x0+x5+x6+x17+x10+x11+x12+x13+x17+x20+x2x7+x4x14+x8x9+x10x11+x1x4x11+x1x4x13x14

f22=x0+x6+x7+x9+x11+x12+x14+x15+x17+x19+x21+x1x4+x2x7+x5x9+x6x10+x2x4x8+x1x3x5x10+x4x11x12x13

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

f24=x0+x1+x3+x5+x6+x7+x9+x12+x14+x15+x17+x18+x22+x1x6+x4x13+x8x16+x12x15+x5x11x14+x1x4x11x15+x2x5x8x10

f25=x0+x1+x2+x4+x5+x8+x9+x13+x14+x21+x25+x1x6+x2x8+x7x8x10

f26=x0+x2+x3+x4+x8+x9+x10+x13+x18+x19+x23+x2x10+x6x11+x5x6x10

f27=x0+x1+x2+x7+x15+x17+x19+x20+x22+x27+x9x17+x10x18+x11x14+x12x13+x5x14x19+x6x10x12+x6x9x17x18+x10x12x19x20

f28=x0+x4+x5+x6+x9+x10+x11+x16+x18+x22+x25+x1x2+x3x10+x5x8x10

f30=x0+x3+x5+x7+x10+x16+x17+x18+x19+x20+x21+x24+x30+x5x15+x11x18+x16x22+x17x21+x1x2x19+x1x12x14x17+x2x5x13x20

f31=x0+x2+x6+x7+x12+x17+x20+x27+x30+x3x9+x12x15+x4x5x16

#### 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