A noniterative reconstruction algorithm for lfsr prng

^{state1^ state2  curid}




^state1'  (state1  1)^ tap1

_state2'  state2  2

^_state1' ^ state2'  nxtid

 (state2  1)(state2  2)  nxtid^ (curid  1)^ tap1

From the above equation, we can calculate some possible values for state2 and we can verify these values and eliminate wrong values using the next IDs. There are three more situations regardless the impact of higher unknown bits:

• 
  LSB(state2) = 10, LSB(state1) = *1:
  

^{state1^ state2  curid}




^state1'  (state1  1)^ tap1
_state2'  (state2  2)^ tap2
^_state1' ^ state2'  nxtid
 (state2  1)(state2  2)  nxtid^ (curid  1)^ tap1^ tap2

• 
  LSB(state1) = 00, LSB(state2) = *1:
  

^{state1^ state2  curid}




^state1'  state1  2

_state2'  (state2  1)^ tap2

^_state1' ^ state2'  nxtid

 (state1  1)(state1  2)  nxtid^ (curid  1)^ tap2

• 
  LSB(state1) = 10, LSB(state2) = *1:
  

^{state1^ state2  curid}




^state11  (state1  2)^ tap1
_state21  (state2  1)^ tap2
^_state11^ state21  nxtid
 (state1  1)(state1  2)  nxtid^ (curid  1)^ tap2^ tap1
Second, because of the advance of LFSR is reversible, if the later states is known, we can just try the opposite operation of the ID generation by utilizing TABLEⅠand verify these states with previous ID.
Third, since we know the lower 16-bit states of the first ID before doing this, our main task is to obtain the higher 16 bits of the sates. Assume all the higher 16 bits are all exposed in the next states, the LFSR should right shift 16 bits, whereas, the way how the LFSR advances is determined by the least two significant bits which are already known. So the lower 16-bit states can be used to infer when the higher 16 bits completely appear in the states.

338

4. 
   EXPERIMENTS
   

Our algorithm is implemented in Visual C++ 6.0 on Lenovo M7150 with Pentium Dual-Core 2.80GHz and Windows XP SP3. The source data of the experiment come from the log file of BIND 9.2.4, which consists of 691 continuous transaction IDs.
Because every advance of LFSR at least right shifts one bit, two bits at most, 8-16 transaction IDs are needed to fully reconstruct the states of the PRNG. It is validated in the experiment.
In this Experiment, five sequences of transaction IDs are randomly chosen, each consisting of 15 consecutive transaction IDs. And then compare our reconstruction algorithm to Amit Klein’s iterative reconstruction algorithm. Here is the result:

TABLE II. EXPERIMENT RESULT