A noniterative reconstruction algorithm for lfsr prng

}

1. 
   Algorithm Description
   

Linear Feedback Shift Register (LFSR) is one of the commonly used in stream cipher technologies, whose feedback function is a simple XOR of certain bits in the register [10]. An n-bit LFSR can generate 2^n-1 bit long pseudo-random sequence before repeating.
The BIND 9.2.4 PRNG is implemented in file "/lib/isc/lfsr.c" [11], which can be concluded in two steps: Step
1. Initializing the PRNG. qid_allocate() (located in the "/lib/dns/dispatch.c") calls isc_lfsr_init() at startup, initializing the two "lfsr" variable; Step 2. Generating transaction ID. dns_randomid() (located in "/lib/dns/dispatch.c") calls isc_lfsr_generate32() to obtain a 32-bit pseudo-random bit, and uses its least-significant 16 bits as transaction ID for each query.
The internal states of the LFSR based PRNG include two 32-bit lfsr variables. When called in isc_lfsr_generate32, their values change as the mutual feedback linear shift register. Here are the codes:
static dns_messageid_t dns_randomid(dns_qid_t *qid)
{
id = isc_lfsr_generate32(&qid->qid_lfsr1, &qid->qid_lfsr2); return (dns_messageid_t)(id & 0xFFFF);
}
isc_uint32_t isc_lfsr_generate32(isc_lfsr_t *lfsr1, isc_lfsr_t *lfsr2)
{
isc_uint32_t state1, state2, skip1, skip2; skip1 = lfsr1->state & 0x01;
skip2 = lfsr2->state & 0x01;
state1 = lfsr_skipgenerate(lfsr1, skip2); state2 = lfsr_skipgenerate(lfsr2, skip1); return (state1 ^ state2);
In words, the algorithm can be described as follows:

• 
  LFSR PRNG Algorithm：
  

Step 1. Test each LFSR’s Least Significant Bit (LSB), and conduct “cross-skip” for the two LFSRs, and return the XOR of each LFSR’s new state. Take least significant 16-bits as a transaction ID. The so-called “cross-skip” means that if LSBs of the two LFSRs are (0, 1) respectively, then LFSR1 will skip for 1 time and LFSR2 will not skip.
Step 2. For each LFSR, if it skips one time, it will execute Step 3 for twice; if it skip 0 time, it will execute Step 3 for once.
Step 3. Test the LFSR is current state, if its LSB equals 1, its new state is the XOR of current state shifting 1 bit to right and a constant value——tap; if its LSB equals 0, its new state is the current state shifting 1 bit to the right.

2. 
   Algorithm Analysis
   

It is important to note that the two LFSRs’ states will never be 0 in the above algorithm, because the initial seeding ensures that the initial state in each LFSR is never 0. And since both LFSR reversible, it can be easily seen that neither LFSR’s state can get the value 0.
It can be easily seen from Fig. 2 that if the LSB of the two states are identical (i.e., both are 0 or 1), the LSB of the transaction ID generated by the two states’ LSB is 0, too. An observation that plays an important role later is as following: When the transaction ID least significant bit is 0, it means that in the next step, the two LFSRs will advance in the same way.

}
static inline isc_uint32_t lfsr_skipgenerate(isc_lfsr_t *lfsr, unsigned int skip)
{

while (skip--) (void)lfsr_generate(lfsr); (void)lfsr_generate(lfsr);
return (lfsr->state);
}
static inline isc_uint32_t lfsr_generate(isc_lfsr_t *lfsr)
{
if (lfsr->state & 0x01) {
lfsr->state = (lfsr->state >> 1) ^ lfsr->tap;
}
else {
Figure 2. Relationship between ID and states

And what’s if the transaction ID least significant bit is 1? It means that in the next step, there may be two situations: (1). Both LFSRs will advance in the same way (i.e., two bits); (2). One will advance one bit and the other two bits. So, it becomes difficult to predict the next value of transaction ID.

But more clues can be get if we see into the least two significant bits of each LFSR’s state. If we regard the LSBs of the state1 and state2 as a two-tuple, according to the code of the PRNG algorithm, a state transition table identifying the actions of each situation can be established.

lfsr->state >>= 1;
337