Effects of Inadequate Randomness in Information Security
Víctor Emanuel Ríos Martínez
Víctor Emanuel Ríos Martínez
Introduction
Randomness is a noun derived from the adjective random, The American Heritage Dictionary of the English Language defines random as “having no specific pattern, purpose or objective” or “related to an event in which all outcomes are equally likely”. The probability of a coin landing heads up or tails up is equal. Also a die has unpredictable outcomes.
Randomness is a noun derived from the adjective random, The American Heritage Dictionary of the English Language defines random as “having no specific pattern, purpose or objective” or “related to an event in which all outcomes are equally likely”. The probability of a coin landing heads up or tails up is equal. Also a die has unpredictable outcomes.
In cryptography, the use of true randomness is necessary so that intruders were not able to hack the cipher texts and decrypt it. In computer science some algorithms use random numbers to outperform the process, such as genetic algorithms and other heuristics.
The true random number generators (TRNG) use physical parameters, such as the photoelectric effect or quantum phenomena, in order to produce truly randomized sequences of numbers, thus the use of an TRNG is too expensive. The pseudo random number generators (PRNG) are deterministic algorithms that generates numbers seeming randomness.
The Pseudo Random Number Generators
Programming languages include a pseudo random number generator. The generator of the C programming language always returns the same numbers unless the programmer selects a seed to change the sequence of numbers but it is common to use the library time.h to get the seed based on the time. If someone else chooses the same seed, the pseudo random numbers generated will be exactly the same.
The main deterministic algorithms used to produce sequences of pseudo random numbers are the congruential and the Fibonacci generators. [1]
Linear congruential generators (LCG)
Xi = (A * Xi-1 + B) mod M
These generators were first proposed in 1949 by D. H. Lehmer. Given a seed X0, a multiplier A and a modulus M, these generators yield a cycled sequence which is called period. M is a very large prime number and determines the maximum length of the period.
Lagged Fibonacci generators (LFG)
Xi = Xi-P ⊙ Xi-Q
⊙ is any binary operator, such as addition, multiplication or the bitwise XOR and P > Q. Instead of 0 and 1, the Fibonacci sequence begins with two large starting numbers.
George Marsaglia and Arif Zaman have created two new number theoretic generators based on the Fibonacci sequence, called add-with-carry and subtract-with-borrow generators.[2] The add-with-carry method consists in carrying a bit. As in the Fibonacci sequence, the next number is produced by summing the two previous numbers. If the result is 10 or more, then 1 is carried and the right-most digit is taken as the new number. The next new number will be obtained by summing the two previous numbers and the bit carried.
The statistical tests are used to prove the trust in the sequences, that is to prove the randomness. The frequency test, the series test and the Kolmogorov test are used for this purpose.
Costs in information security
Nowadays, Internet has changed the way to do transactions. Internet has become an important and strategical way for promoting and selling products and services. The banks and the organizations use credit cards and bank account numbers so that the transactions can be done. Furthermore, the identity of every user is recorded in all the databases in which the user has signed up. The identity theft is a growing problem, the idea of the concept is quite simply: one person taking the identity of another person. This is done for many reasons, typically for economic gain, for example obtaining credit cards or even driver's licenses in the victim's name. [3]
The Pseudo Random Number Generators
Programming languages include a pseudo random number generator. The generator of the C programming language always returns the same numbers unless the programmer selects a seed to change the sequence of numbers but it is common to use the library time.h to get the seed based on the time. If someone else chooses the same seed, the pseudo random numbers generated will be exactly the same.
The main deterministic algorithms used to produce sequences of pseudo random numbers are the congruential and the Fibonacci generators. [1]
Linear congruential generators (LCG)
Xi = (A * Xi-1 + B) mod M
These generators were first proposed in 1949 by D. H. Lehmer. Given a seed X0, a multiplier A and a modulus M, these generators yield a cycled sequence which is called period. M is a very large prime number and determines the maximum length of the period.
Lagged Fibonacci generators (LFG)
Xi = Xi-P ⊙ Xi-Q
⊙ is any binary operator, such as addition, multiplication or the bitwise XOR and P > Q. Instead of 0 and 1, the Fibonacci sequence begins with two large starting numbers.
George Marsaglia and Arif Zaman have created two new number theoretic generators based on the Fibonacci sequence, called add-with-carry and subtract-with-borrow generators.[2] The add-with-carry method consists in carrying a bit. As in the Fibonacci sequence, the next number is produced by summing the two previous numbers. If the result is 10 or more, then 1 is carried and the right-most digit is taken as the new number. The next new number will be obtained by summing the two previous numbers and the bit carried.
The statistical tests are used to prove the trust in the sequences, that is to prove the randomness. The frequency test, the series test and the Kolmogorov test are used for this purpose.
Costs in information security
Nowadays, Internet has changed the way to do transactions. Internet has become an important and strategical way for promoting and selling products and services. The banks and the organizations use credit cards and bank account numbers so that the transactions can be done. Furthermore, the identity of every user is recorded in all the databases in which the user has signed up. The identity theft is a growing problem, the idea of the concept is quite simply: one person taking the identity of another person. This is done for many reasons, typically for economic gain, for example obtaining credit cards or even driver's licenses in the victim's name. [3]
Information security is important due to the damages and costs that can be generated if such information is revealed. Information about the clients or the users of a web platform such as bank account numbers, the physical resources of an organization, the financial statements and any other valuable asset must be safeguarded to protect the customers, the business and also the reputation of the company. [4]
The use of inadequate random number generators makes a system vulnerable. However, in many cases, companies or governments have used pseudo random number generators as if it were truly random, originating security problems and causing economic loss.
The cryptographic systems provides security to the processes that must be protected and the randomness is very related to this systems. A cryptographic system use keys to safeguard the information. The strength of a key depends on the randomness of the number generator, it hinge on the statistical quality of the pseudo random number generator. [5] It is more difficult to hack a key if the process of creation cannot be reproduced, that is the key is unreproducible, not as in the rand function of C. Also, a key must be incompressible and unpredictable because those properties will reveal a pattern and that would be great for the hackers. Due to this pattern, the attackers can obtain some parts of the key hacking only some blocks of it and, as a result, the time of hacking it by brute force will reduce. The large of the key will not guarantee the security of the cryptographic system, but if the key is truly random then the attackers will have to be very patient to obtain it. Thus the randomness of the key with a good implementation of an encryption algorithm provides the most powerful security system.
It's important to prove the security of a system attacking it ourselves. Companies, sometimes, offer prizes to people who can find a security risk in their systems because by this way they can assure the reliability of the services that they promote.
Conclusions
In information security, the cryptographic systems protect the most valuable resources of a company, and the cryptographic systems requires the randomness to make the most secure passwords in order that even a virtuoso hacker could not break the system.
There are a lot of problems that demand a big quantity of pseudo random numbers, so the new methods for obtaining it must be improved. The Marsaglia and Zaman's methods are an example of the new classes of generators and some of them still need to show their capacity to produce long periods.
References
[1] Coddington, Paul D. and Sung-Hoon Ko, “Techniques for Empirical Testing of Parallel Random Number Generators”, 1998.
[2] Bennett, Deborah J.. “Randomness”, Harvard University Press, 1998.
[3] Eastomm, Chuck. “Computer security fundamentals”, Pearson, 2011.
[4] T. R. Peltier, J. Peltier and J. Blackley. “Information security fundamentals”, Auerbach Publications, 2005.
[5] K. Marton, A. Suciu, C. Sacarea and O. Cret. “Generation and testing of random numbers for cryptographic applications”, The Publishing House of the Romanian Academy, 2012
[1] Coddington, Paul D. and Sung-Hoon Ko, “Techniques for Empirical Testing of Parallel Random Number Generators”, 1998.
[2] Bennett, Deborah J.. “Randomness”, Harvard University Press, 1998.
[3] Eastomm, Chuck. “Computer security fundamentals”, Pearson, 2011.
[4] T. R. Peltier, J. Peltier and J. Blackley. “Information security fundamentals”, Auerbach Publications, 2005.
[5] K. Marton, A. Suciu, C. Sacarea and O. Cret. “Generation and testing of random numbers for cryptographic applications”, The Publishing House of the Romanian Academy, 2012
