Modification Attack Effects on PRNGs: Empirical Studies and Theoretical Proofs

Year 2015, Volume: 3 Issue: 1, 42 - 47, 17.01.2015

Santi Indarjani Kiki Sugeng Belawati Widjaja

https://doi.org/10.18100/ijamec.67885

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.

Keywords

pseudorandom generator, modification attack, statistical distance, entropy difference, bit pattern, occurance probability

Original Research Paper

Abstract

References

• Indarjani, S. and Widjaja, B., “Indistinguishable of AES-based PRNG against Modification Attack Based on Statistical Distance Tests and Entropy Measures,” ser. Lecture Notes on Software Engineering vol. 1, no. 3, 2013, pp. 314-318.
• Young, A. and Yung, M., Malicious Cryptography : Exposing Crypto virology, John Willey & Sons, USA, 2004.
• Uner, E., “Generating Random Numbers,” Embedded: Cracking the code to system development, 2004, available: http://www.embedded.com/ design/configurable-systems/4024972/Generating-random-numbers. .
• Sunar, B., Martin,W.J., and Stinson, D.R., "A Provably Secure True Random Number Generator with Built-In Tolerance to Active Attacks," IEEE Transactions on Computers, vol. 56, no. 1, January, 2007, pp. 109-119.
• Schneier, B., Kelsey, J., Wagner,D., and Hall, C., “Cryptanalytic Attacks on Pseudorandom Number Generators”, in Fast Software Encryption, Fifth International Workshop Proceedings, published by Springer-Verlag, March 1998, pp. 168–188.
• Goldreich, O., Foundation of Cryptography : Volume I Basic Tools, Cambridge University Press., England, 2001
• Schneier, B., Applied Cryptography, 2nd ed., John Wiley & Son, Inc., USA, 1996.
• Wang, Y., A comparison of two approaches to the randomness, Theor. Comput. Sci., Vol. 276, No. 1-2. ,2002, pp. 449-459
• Farashahi, R.R., Schoemaker, B., and Sidorenko, A., “Efficient of Pseudorandom Generators based on DDH Assumption”, in Lecture Notes in Computer Science Volume 4450, published by Springer-Verlag, Berlin, 2007, pp 426-441.
• Bose,R., Information Theory, Coding and Cryptography, Tata McGraw Hill, New Delhi, 2002
• Hoffstein, J., Pipher, J, and Silverman, J.H., An Introduction to Mathematical Cryptography, Springer Science+Business Media, LLC, New York, 2008
• NIST, NIST-Recommended Random Number Generator Based on ANSI X9.31 Appendix A.2.4 Using the 3-Key Triple DES and AES Algorithms, 2004, available : http://csrc.nist.gov/groups/STM/cavp/documents/rng/931rngext.pdf
• G.T. Becker, F. Regazzoni, C. Paar, and W.P. Burlesson, “Stealthy Dupont-level Hardware Trojan”, in CHES'13 Proceedings of the 15th international conference on Cryptographic Hardware and Embedded Systems, published by Springer-Verlag, Berlin, 2013, pp. 197-214.
• A.T. Markettos and S.W.. Moore, “The Frequency Injection Attacks on Ring-Oscillator-Based True Random Number Generator”, in Proceedings of the 11th International Workshop on Cryptographic Hardware and Embedded Systems, pp. 317 – 331, Springer-Verlag, 2009.