A noniterative reconstruction algorithm for lfsr prng

NO.	State1	State2	Used IDs*	Used IDs	Time Elapsed*
Time Elapsed
1	f6920c40	e07c2ea	12	15	5.679	138.379
2	190c0f66	4a3883b7	14	15	8.732	121.071
3	d074e57a	5c53697f	9	15	5.083	118.334
4	f9941fda	4af71039	9	15	8.486	121.723
5	5c1b80fd	d20d8331	15	15	13.614	133.166

1. 
   columns with * means our algorithm.
   
2. 
   here unit of time elapsed: us.
   

TABLEⅡshows that our reconstruction algorithm is more efficient than iterative algorithm, which only needs about 1/10
—1/24 time of what the iterative needs. What’s more TABLE
Ⅱalso shows that our algorithm needs less IDs to reconstruct the full states in some conditions.

5. 
   CONCLUSION
   

In this paper, we have discussed and analyzed the weakness of LFSR based PRNG in detail. A reconstruction algorithm is
proposed to fully reconstruct the states of LFSRs by utilizing a sequence of IDs. Our comparative experiment shows our algorithm is more efficient and less resource-consuming than existing algorithm.
As far as we know, by the writing of this paper, there are still some DNS servers in the Internet use BIND 9.2.4 or lower version, which is very insecure. It’s strongly recommended that users update their DNS server to newer versions.

REFERENCES

1. 
   Paul Mockapetris, “Domain names — concepts and ficilities (RFC 1034),” November 1987, http://www.ietf.org/rfc/rfc1034.txt.
   
2. 
   Paul Mockapetris, “Domain names — implementation and specication (RFC 1035),” November 1987, http://www.ietf.org/rfc/rfc1035.txt.
   
3. 
   Steven M. Bellovin, “Security problems in the TCP/IP protocol suite,” Computer Communications Review, vol. 19, pp. 32-48, April 1989.
   
4. 
   Christoph Schuba, “Addressing weaknesses in the Domain Name System protocol,” Master’s thesis, Purdue University, August 1993.
   
5. 
   Derek Atkins, Rob Austein, “Threat analysis of the Domain Name System (DNS) (RFC 3833),” August 2004, http://www.ietf.org/rfc/ rfc3833.txt.
   
6. 
   J. Stewart, “DNS cache poisoning — the next generation,” LURHQ, Technical Report, January 27th, 2003.
   
7. 
   Michal Zalewski, “strange attractors and TCP/IP sequence number analysis,” RAZOR/Bindview Corporation, April 21st, 2001.
   
8. 
   Y. Kadakia, “Dan Kaminsky’s DNS cache poisoning vulnerability explained,” August 2008, http://www.yashkadakia.com/2008/08/dam- kaminskys-dns-cache-poisoning.html.
   
9. 
   Amit Klein, “BIND 9 DNS Cache Poisoning,” Technical Report, Trusteer Ltd., June 2007.
   
10. 
    TW Williams, W Daehn, M Gruetzner, “Bounds and analysis of aliasing errors in linear feedback shift registers,” IEEE Computer- Aided Design of Integrated Circuits and Systems, vol. 7, pp. 75-83, Jan. 1988.
    
11. 
    ISC, “BIND 9.2.4 source code,” http://ftp.isc.org/isc/bind9/9.2.4/ bind-9.2.4.tar.gz.
    
12. 
    Daniel J. Bernstein, “How long can an NS chain be?” December 28th, 1998. http://www.ops.ietf.org/lists/namedroppers/namedroppers.199x namedroppers./msg03692.html.
    

339

Authorized licensed use limited to: Tashkent University of Information Technologies. Downloaded on April 08,2023 at 09:33:10 UTC from IEEE Xplore. Restrictions apply.