3.1.1 Analysis Without InputWhen the input is set to zero, the mixing function is equivalent to an LFSR over GF(2^32) with
feedback polynomial Q(X) = α^3*(P(X) − 1) + 1, where α is the primitive element of GF(2^32)
corresponding to X defined by the CRC-32-IEEE 802.3 polynomial, and P(X) depends on the
size of the pool:
input pool: P(X) = X^128 + X^103 + X^76 + X^51 + X^25 + X + 1
output pool: P(X) = X^32 + X^26 + X^20 + X^14 + X^7 + X + 1.
The multiplication by α^3 is done by a lookup table, called twist-table in the source code.
The actual system slightly differs from what is stated in the comments of the source code.
First, the design of the mixing function is claimed to rely on a Twisted Generalized Feedback
Shift Register (TGFSR) as defined in [MK92]. However, TGFSRs are LFSRs on binary words
with a trinomial feedback polynomial whereas the mixing function uses a heptanomial. The
case of general polynomials on finite fields is treated in standard literature, such as [LN97].
Moreover, the maximal period, that is the primitivity of the feedback polynomial, seems to
have been ill understood, as the comments mention the primitivity for polynomials on GF(2),
whereas the primitivity must be checked on GF(232). This confusion is also repeated in [GPR06,
Definition 2.2].
Finally, the polynomial Q(X) = α^3*(P(X) − 1) + 1 is not primitive over GF(2^32), nor is it
even irreducible. Thus, the resulting LFSR does not achieve maximal period. The period is less
than 2^(92∗32) − 1, rather than the maximal value of 2^(128∗32) − 1, for the input pool,
and less than 2^(26∗32)−1 instead of 2^32∗32 − 1 for the output pool.
We do not believe these reduced periods can lead to practical attacks. However, Q(X) can be
made irreducible by changing just one feedback position:
input pool: P(X) = X^128 + X^104 + X^76 + X^51 + X^25 + X + 1
output pool: P(X) = X^32 + X^26 + X^19 + X^14 + X^7 + X + 1.
These modified polynomials have periods of (2^128∗32−1)/3 and (2^32∗32−1)/3, respectively.
A primitive polynomial can be easily achieved by using (α^i)*(P(X)−1)+1 with gcd(i,2^32−1) = 1,
for example for i = 1,2,4,7, . . ., and an adequate polynomial P(X). This would change the size
of the twist-table to 2^i elements. For instance, α^2*(X^32+X^26+X^23+X^14+X^7+X)+1 is primitive.
All these computations can be made using computational algebra systems like magma [BCP97].