Modification Attack Effects on PRNGs: Empirical Studies and Theoretical Proofs

Abstract

Random sequence as a critical part in a security system should be garranted as random that should be secure from any attacks. Modification attack is one of possible attacks on random generator in order to make the generator function mislead or the output random sequences bias. From previous research, it was shown that 1-bit modification attack has effects on the randomness property of AES-based PRNG outputs under advantage ε = 0.00001 based on statistical distance test and entropy difference test.  In this paper, we propose the extended research on some other PRNGs i.e. Rabbit, Dragon, ANSI X9.17 and ANSI X9.31 under the same scenario with intensity of modification (1-bit to 3-bits) per block.  From the experiment results we found that the modification attack already has effects on the four algorithms under advantage ε = 0.001 with intensity 3-bits per block. Even on PRNG X9.17, the attack effect is already significant for all intensity. The effect is getting more significant for all four algorithms under advantage ε = 0.0001 for all intensity. It is showed that PRNG ANSI X9.17 is weaker against the modification attack than the other three algorithms. From theoretical approach based on occurrance probability of an m-bit pattern in the sequence after the attack, we got two results.  First, the modification attack will have no effect on the probability distribution of each m-bit pattern as long as the modified bits are balance. So it is possible that the randomness property of the target sequence still hold after the attack. Second, if the bits modified are not balanced then it caused the unbalanced of the probability distribution of the m-bit patterns that could make the randomness of the target sequence bias.  Based on the two results, we concluded that the modification attack is potential to reduce the randomness property of the output sequences of a random or pseudorandom generator.