A noniterative reconstruction algorithm for lfsr prng

2012 2nd International Conference on Computer Science and Network Technology

A Noniterative Reconstruction Algorithm for LFSR PRNG

Chengxi XU, Ronggui HU, Yongyi WANG, Fan SHI

Electronic Engineering Institute (EEI) He Fei, China, 230037
Email: [e-mail]

Abstract—Pseudo Random Number Generator (PRNG) is widely used in computer software design. The famous Domain Name System (DNS) software—— BIND uses Linear Feedback Shift Register (LFSR) based PRNG algorithm to produce randomness of its transaction IDs. In recent years, DNS cache poisoning attack occurs frequently, which exploits BIND PRNG weakness, aiming at forging BIND with fake responses. In this paper, we present detailed analysis of the LFSR PRNG algorithm of BIND 9.2.4, which shows that its PRNG can be reconstructed. An effective noniterative reconstruction algorithm is proposed to fully reconstruct the internal states of the LFSRS. The algorithm is independent of the initial state of LFSR and of specific hardware platform. The experiment shows that our algorithm is more efficient than existing algorithm.


Keywords- LFSR PRNG; PRNG Weakness; PRNG Reconstruction; Noniterative Algorithm

1. 
   INTRODUCTION
   

DNS (Domain Name System) is a distributed, coherent, autonomous, hierarchical database which is mainly used for locating a host in the Internet based on a human readable name [1-2], which makes the worldwide Internet possible.
The concept of DNS cache poisoning attack has been known for over two decades. As early as in 1989, Steven M.Bellovin first described this kind of attack in [3]. In 1993, Christoph Schuba’s paper “Addressing Weaknesses in the Domain Name System Protocol” [4], pointed out several vulnerabilities, including the technique of DNS cache poisoning. More systematic analyses can be found in [5-6].
A typical flow of DNS cache poisoning can be described in four steps [7] (Fig. 1): Step 1. The attacker sends a query to cache DNS server; Step 2. If the cache server doesn’t have the answer in its cache, it will send a query to authorative DNS server who is responsible for that domain. In its query packet, there are several parameters —— a source port, which is constant in BIND 9.2.4, a 16-bit transaction ID, produced by the LFSR PRNG. These parameters are used to associate response with specific query. Only those responses come in correct source port and transaction ID are accepted; Step 3. The attacker sends carefully designed fake responses to the cache server immediately right after the cache sends the query. As long as the attacker’s fake responses reach the cache server

earlier than the authorative server’s real response and anyone of those fake responses matches all the parameters, the cache server will accept the answer and save to its caches; Step 4. When the real response reaches the cache server, the cache server will simply discard it because of it already taking an answer.

Figure 1. Typical flow of DNS cache poisoning.

As mentioned above, only the attacker has successfully guessed the right transaction ID will he have the chance to win the race. Therefore, it’s all up to the performance of BIND PRNG now. Unfortunately BIND 9.2.4 uses a weak PRNG which can be predicted [7-8]. Amit Klein proposes an iterative reconstruction algorithm in [9], which can iteratively reconstruct the full states of the LFSRs through guess and verify. It is obvious that this algorithm has to guess and verify many unnecessary paths, which can be inefficient.

In this paper, a state transition table is established to contain all the possible execution paths of the two LFSRs of the PRNG. A noniterative reconstruction algorithm is proposed based on the internal state transition table, which reconstructs the states reversely (i.e. from bottom to top). An experiment is designated to compare our algorithm to Amit Klein’s iterative algorithm.
The rest of the paper is organized as follows: SectionⅡ gives a full description and analysis of LFSR PRNG Algorithm, which establishes an internal state transition table. Section Ⅲ proposes a noniterative reconstruction algorithm to fully reconstruct the internal states of the LFSRS based on the state transition table. We validate our algorithm through experiment in Section Ⅳ and conclude in Section Ⅴ.

978-1-4673-2964-4/12/$31.00 ©2012 IEEE

336

CHANGCHUN, CHINA

2. 
   LFSR PRNG ALGORITHM ^}