Abstract: Many models have been designed for generating pseudo random numbers and there is the potentiality to design more. Among the mentioned generators, a few of them are applied in cryptography. Thus, there is an inevitable need among researchers and users for evaluating the generators. A variety of criteria are used for evaluation which have more or less or neutral importance depending on the way the generators are applied. Accordingly, some reliable sources pay attention to the particular criterion while overlooking others. In the present study, in addition to enumerating all of the popular criteria, there has been an attempt to classify them in the form of a general model. At the end, some suggestions are presented for the foremost priority in using and applying the criteria. With implementing this pattern all the criterions have been considered and on the other hand the probability of second type error will be reduced. Also, observance of the sequence of criterions would cause saving in time and costs.
INTRODUCTION
Random numbers are applied in several sciences such as simulation, modeling, computer sciences, statistical sampling and cryptography. With the expansion of network communications and unauthorized accessibility to the exchanged information, the development of research seems necessary. Random numbers play such a key role in cryptography that it seems impossible to consider a cryptography program without using random numbers (Kang, 2005). Using insecure random numbers in cryptographic systems leads to the insecurity of the whole system. Thus, evaluating the generators and not using insecure generators is a significant step in achieving secure cryptographic systems.
In the following, some applications of random numbers in cryptography are mentioned:
| • | Message and session keys for symmetric ciphers, such as triple-DES or Blowfish |
| • | Seeds which usually produce mathematical values, such as prime numbers in RSA or ElGamal |
| • | Salts to combining with the passwords which cancel the program for guessing the passwords in offline mode |
| • | Initialization vectors for chaining modes |
| • | Random values for special requests from digital signature schemes, such as DSA |
| • | Random challenges in authentication protocols, such as Kerberos |
| • | Nonces for protocols, to ensure that different runs of the same protocol are unique; e.g., SET and SSL (Kelsey et al., 1999) |
Generating true random numbers based on physical sources by computers is time consuming and costly. The production speed is usually low in these generators, thus, pseudo random number generators are used which are able change a short sequence of random numbers into a long sequence of numbers in a way that appear to be random. "Indistinguishable from truly random sequence" and "unpredictability to an adversary with limited computational resources" are two main requirements for output of pseudo random number generators (Kang, 2005).
Confirming the fact that a generator is really pseudo random is difficult but one can reject that a generator is pseudo random by statistical tests and the mentioned essentials. Therefore, success in a statistical test can be regarded as a criterion for identifying suitable generators.
Given that the method for distinguishing between output sequences of generators and true random sequences is called attack (Kelsey et al., 1998), an appropriate generator has to be resistant to identifiable attack. Then, resistance against identified attacks is another criterion for identifying an appropriate generator. Other factors such as speed, long sequence can be used as a criterion for identifying a good generator.
Patidar et al. (2009) run NIST (3 level) and DIEHARD tests for their generators based on formed chaos standard mappings in. They took this as the only criterion for analyzing generators (Patidar and Sud, 2009). Orue et al. (2010) proposed a generator based on Fibonacci mapping and evaluated that in terms of speed, easy implementation, long period and success in statistical tests. Gayakwad and Ranbir (2012) proposed a useful pseudo random number generator for processing image. They evaluated the generator with criterion such as speed, easy implementation, Monobit and serial tests and other NIST tests.
Akhshani et al. (2014) for pseudo random number generator based on quantum chaos mapping applied 4 famous souit of statistical tests, DIEHARD, ENT, NIST and U0I. They also considered speed and easy implementation criterions.
Reyad and Kotulski (2015) presented a generator that is combination of elliptic curves and chaos mapping and for its evaluation, they investigated only 5 statistical tests addition to speed and long period criterions.
In this study, there is an attempt to present all the criteria proposed by researchers in cryptography as an applicable evaluative model so that one can evaluate his/her generator or other generators without referring to several sources. Then they can use the criteria based on the priority we proposed.
James (1990) enumerated the criteria for a suitable generator as long period, uniform distribution, repeatability, having disjoint subsequences and portability. Kelsey et al. (1999) proposed the comprehensive classification of several attacks on the generator. Kelsey et al. (1998) suggested four criteria as resistance against attacks, efficiency, the capacity for reseeding and resistance against disavowal. Given the significant role of chaos mapping designing pseudo random number generators, paying attention to essentials of chaos based systems proposed by Gonzalo and Li (2006) would be necessary. Statistical packages are a set of statistical tests which, in designers’ perspective, can be a criterion for the suitability of generators if they are not rejected. Applying programs such as DIEHARD in reference (Marsaglia, 1996), ENT in reference (Walker, 2008), U0I in reference (L'Ecuyer and Simard, 2007) and NIST in reference (Rukhin et al., 2010) are available. Babaei and Farhadi (2011) suggested that the essentials for a pseudo random number generator are uniform distribution, independence, the long period and unpredictability and offered the use of U0I package for examining these essentials (Babaei and Farhadi, 2011). Yang and Xiao-Jun (2012) applied autocorrelation and NIST tests for the suggestive generators based on empirical distribution of data. Furthermore, they examined the analysis of the key space and sensitivity and speed analysis (Yang and Xiao-Jun, 2012). Francois et al. (2013) applied the NIST tests for three types of output sequences and made a correlation analysis for three subsequences and examined the security analysis for the size of the key space, key sensitivity and key selection. Then, they studied the resistance against guess-and- determine attacks (Francois et al., 2013). Ilyas et al. (2013) applied for a suggestive generator the NIST package in deeper level which was a uniform distribution on p-value (Ilyas et al., 2013). Stoyanov and Kordov (2014) applied three testing packages namely, DIEHARD, ENT and NIST on a large number of a generator based on chaos. Then, he examined the portion of successful sequences (Stoyanov and Kordov, 2014). Wang and Nicol (2015) showing the weak points of NIST package with respect to indicating nonrandom generators as random, suggested that there should be tests based on statistical distances such as iterated logarithm for decreasing type two error (Wang and Nicol, 2015). Hamdi et al. (2015) proposed the criteria for long sequences and uniform distributions for generators and examined the speed and resistance analysis against differential attacks. Moreover, the NIST tests were applied in several output sequences and the results were compared based on the ratio of success in AES algorithm (Hamdi et al., 2015).
It should be noted that, according to the current trend, in order to evaluate the suggestive generators, only a few criteria can be considered to accept a generator while the same generator may be rejected if evaluated by other criteria. In this study, considering other criteria proposed in the literature and based on the experiences of the authors, a model is proposed which has a general perspective toward evaluating random number generators. Observing this model causes increase in security level of generators and thus, increase in security of cryptographic systems.
MATERIALS AND METHODS
General definition and concepts: As a basic definition of pseudo random number generators, it is necessary, first, to elaborate on the definition of indistinguishability of two ensembles (Goldreich, 2004).
Definitions 1: Two ensembles {Xn}n∈N, {Yn}n∈N are called indistinguishable in polynomial-time when we have for each probabilistic polynomial-time algorithm A and each polynomial p and all sufficiently large n,s:
| (1) |
Ensemble {Xn}n∈N would be pseudo random if {Xn}n∈N and {Un}n∈N be indistinguishable, which Un shows that the random variables have uniform distribution on binary sequence set with the length of n.
Definition 2: Deterministic polynomial-time algorithm G are called pseudo random number generator if the two conditions will be met (Goldreich, 2004):
| • | The function l exists that l(n)>n;∀n∈N and for each s∈{0,1}*, we will have: |G(s)| = l(|s|), where s is called seed |
| • | Ensemble {G(Un)n∈N} be pseudo random |
Definition 3: Ensemble {Xn}n∈N is called unpredictable in polynomial-time, if for each probabilistic polynomial-time algorithm A and each polynomial p and all sufficiently large n,s (Goldreich, 2004):
| (2) |
The above definitions are not practically possible since all the algorithms should be confirmed. In the following definitions there seems to be a good association between pseudo random number generators and statistical tests (Goldreich et al., 1986).
Definition 4: It is said that a pseudo random number generator to pass all the polynomial-time statistical tests if no polynomial-time algorithm can correctly distinguish between an output sequence of a generator and the truly random sequence with the same length with probability significantly greater than
In other words, the output of the generator and the truly random sequence with the same length are computational indistinguishable.
In reference (Goldreich et al., 1986), it is confirmed a generator can be successful in an unpredictable next bit if and only if becomes successful in all polynomial-time statistical tests.
Lack of success of a generator in any statistical test could be a reason for rejecting that generator. Although the success of a generator in all of the existing tests could be regarded as a strength point, however, it cannot be considered as a reason for their being pseudo number.
Evaluating model for pseudo random number generators: In this section, a model for evaluating pseudo random number generator will be proposed. Investigating theoretical underpinnings and common methods researches applied during recent years leads to a conclusion that for general evaluation of a pseudo random number generator, actions must be done in three dimensions. In fact, a suitable generator should have the following features:
| • | In applying statistical tests on generators, the random and independence assumption of the output should not be rejected |
| • | Being resistant against identifiable and appropriate attacks |
| • | Being acceptable with respect to applying and security issues |
Accordingly, three subsections will be proposed.
Statistical tests: We can determine whether an output sequence is nonrandom, however, we cannot confirm that a sequence is random. In statistical tests, we can decide with a determined measurable probability about whether a generator produces random sequence. Null hypothesis suggests that the output of a generator is random, that is, it follows independently uniform distribution or i.i.d. Type one error occurs in a case that we reject the random sequence α = P (rejected H0|H0 true). According to sample observations, p-value will be calculated and if p-value<α, the null hypothesis will be rejected and otherwise, the hypothesis will be accepted. The success of a generator lies in the fact that the H0 will be accepted. Statistical tests could be conducted in three levels. The first level selects an output sequence from the generator and the test will be conducted on it. The second level considers m sequences which have n number of bits as sample of output generators and each test will be conducted on all of sequences. Given that m independent test are conducted in α level, H0i shows random assumption of ith sequence. Random variable Bernoulli Xi will be 1 when H0i is accepted. Thus, the variable:
has polynomial distribution with m and 1-α parameters, when each H0i is true. Now, if we indicate the probability of acceptance of the generator with γ = P(Xi = 1), then the variable:
has polynomial distribution with m and γ parameters. Now, for second test, the hypothesis H0: γ≥1-α has to be tested in a significant α* level. The test statistic, if the null hypothesis is true, has normal limiting distribution and is shown as following:
| (3) |
Null hypothesis will be rejected if p value<α* and otherwise, we can accept that the generator is pseudo random.
The acceptance region for this test shows the minimum acceptable ratio for sequences:
| (4) |
For example, in examining m = 1000 sequences for α = 0.01, if the second level test for α* = 0.0001 was applied, we should have at least 979 sequences to accept the fact that the generator was pseudo random.
The third level is based on the following lemma.
Lemma 1: If a test statistic were continuous, p value as a random variable has uniform distribution on [0,1], if the primary hypothesis is true.
Proof: Let a∈(0,1) because of continuity in test statistic T, ta number will be:
Now, if we show the random variable p value with p, two inequality p≤a and T≤ta indicate the rejection of H0 with the probability of a, so they are equivalent. Pr(T≤ta) = Pr(P≤ta) = a, so according to last equality and uniform distribution function, problem has been proofed.
With regards to lemma 1, we can conduct the first level of test for several times and consider p-value as a random sample of p. Then, by using goodness of fit tests such as Kolmogorov-Smirnov test and Chi-squared test, we examine the establishment of uniform distribution for p.
It should be noted that for conducting statistical tests, there are identified packages with different capacities and applications. Examining all of these packages we could find out that the package which belongs to NIST is more appropriate than others. Provided that the package has the essential standards, we can introduce a sequence which is obviously nonrandom in a sense that passes all the tests successfully (Wang and Nicol, 2015). The iterated logarithm test which is based on the Law of the Iterated Logarithm (LIL) is a tool for reducing the potential type two errors. In fact, a generator which is confirmed by this test, it will be less likely to produce nonrandom sequences. This test is called the fourth level for statistical tests.
Iterated logarithmic test: Two famous limit theorems about binary sequences are central limit theorem and law of the iterated logarithm. A number of NIST tests are based on central limit theorem but the law of the iterated logarithm has never been used in any tests.
Definition 5: It is said that the sequence ξ does not pass the weak LIL-(α,N*) test successfully if for any n∈N we have:
| (5) |
Where:
and ξ[i] is the i-th bit of ξ. Further, α∈(0,0.25) and N*⊆N.
Common attacks on pseudo random number generators: Generally, a pseudo random number generator involves an unpredictable input called seed value and a secret state "S". The pseudo random number generator starts with a random state and has to process many seeds to reach a secure state S. The output should be produced which an attacker S cannot guess. Moreover, the generator should be able to change its secret state by repeatedly processing inputs (seed). Figure 1 describes the pseudo random number generators (Kelsey et al., 1998).
One of the features that makes the use of pseudo random number generators in cryptography distinguished from others is identifying the attacks on these generators and examining the resistance against them. In an overall view, attack is defined as any method of distinguishing between pseudo random number generator outputs and truly random outputs (Kelsey et al., 1998). Nevertheless any attempt in achieving the following goals can be regarded as an attack:
| • | To learn about the output |
| • | Getting information with respect to input and output |
| • | To manipulate the output |
| Fig. 1: | PRNG model (Kelsey et al., 1998) |
Based on the above definition, a wide range of attacks are identified. The following classification is done based on the common identified attacks (Kelsey et al., 1998).
Direct cryptanalytic attack: When an attacker can directly distinguish between output sequences of generator and truly random number sequences, a direct cryptanalytic attack has occurred. Distinguishing attack is regarded as this type of attack. A large number of generators apply cryptographic primitives such as hash functions or block ciphers in order to prevent such attacks.
Input-based attacks: When the attacker can observe the input or manipulate (control) it, an input-based attack occurs. The goal of the attacker is to reduce the number of outputs in such a way to make it easy to guess them. In order to prevent this type of attack, it is better to transform the inputs with an enumerator into a hash function, before transferring them to the generator. The guess-and-determine and differential attacks are considered as this type of attack.
State compromise extension attacks: When the attacker is able to recover unknown pseudo random number generator outputs from before S was compromised, this attack occurs. The attacker tries to develop this knowledge to further points in time and to previous or future output. This attack usually occurs when the generator starts with insecure mode such as the primary which has all the elements zero or the selection of seed was from a set available to the attacker. In order to resist against this attack, enough care must be taken for selecting seed. Meet-in-the-middle attacks are considered as this type of attack.
Other criteria: In this section, we discussed the criteria which are not examined in statistical test and cannot be regarded as attacks except for one.
Speed: The expression ‘it is easy to design a secure but very slow cipher’ (Alvarez and Li, 2006) is well known in cryptography. Thus, attention to speed in evaluating the generators is something common. Speed becomes significant in proportions because factors such as the structure of CPU, the memory capacity, platform, optimum coding and programming language affect the speed. For chaos-based generators, the expected speed should not be slower than 10 Mbps on a 1 GHz-CPU.
Effective implementation: The expression "It is quite easy to design a secure but very large cipher" (Gonzalo and Li, 2006) is common in cryptography. Thus in evaluating generators, it is required that we pay attention to the fact that it is better to have a simpler generator and less need to hardware and software equipments.
Key space: In designing generators, usually it is possible to call the used seeds or initial vectors as "key". In current conditions the size of key space for resisting against brute-force attacks should be at least 2128. The bigness of the size of key space is necessary but not enough because, in cryptographic perspective, the keys should not be strong and correlated (Francois et al., 2013).
Key sensitivity: The sensitivity on the key is an essential doer for chaos-based generators. The key sensitivity can be calculated by correlation the outputs which are the result of seeds that are close to each other. Insignificance of correlation shows high sensitivity. If the test was rejected, then the correctness of the null hypothesis could be questioned, that is, the generator is not pseudo random.
Suggested priorities: Applying a variety of criteria is a strength point for the model of evaluating pseudo random number generators. However, it should be noted that not caring about appropriate priorities could lead to waste of time and deviation from the main goal.
Thus, the priorities are empirically suggested by comprehensively examining the research conducted on studying the association and correlation of criteria.
In the following model, if the generator can meet the condition in each level, goes to next level. Otherwise, evaluation procedure is stopped and the generator is recognized inappropriate for cryptography points. However, it should be noted that inappropriate recognized generators may be used for certain applications in special cases.
First step
Speed: The speed of production should be measured for the evaluating generator. If the calculated speed was more than the criterion mentioned by Alvarez and Li( 2006), we could continue the evaluation, otherwise, we will reject the generator.
Second step
Resistance against the brute-force attack: We measure the size of the key space and if the criterion were more than 2128, we go to the next step in evaluation and, otherwise, the generator will be rejected.
Third step
Implementation of statistical tests in the first level NIST: Given to the fact that in some tests the number of elements under evaluation should be 106, thus, we produce a sequence with the minimum number of 106 members of the generator and then implement the first level NIST on the sequence. If random assumption were not rejected with any of the tests, we go to the next step in evaluation, otherwise, we reject the generator.
Fourth step
Examining the sensitivity: In order to examine the sensitivity of the generator to the key and initial values, close seeds are selected and we get the output. Then, the correlation of output sequences will be calculated. Insignificance of correlation between the outputs means that the sensitivity is to the key is high and the generator will be accepted. Then we go for evaluation to the next step. In the case of significant correlation between the generators, the generator will be rejected.
Fifth step
Examining the resistance against attacks: Given to the mentioned attacks in Kelsey et al. (1998) and the structure of the generator, the resistance against the attacks will be examined and in the case of success, each generator is rejected. Is the generator were resistant against the known attacks, we go to the next step in evaluation.
Sixth step
Implementing statistical tests second level NIST: A large number of sequences of generator were selected as a random sample and these tests will be conducted independently. The ratio of the accepted sequences is compared by Eq. 4. If for all the NIST tests our ratio was bigger, the generator is accepted and we go to the next step in evaluation.
Seventh step
Implementing statistical tests the third level NIST: A large number of sequences are selected from the generator as samples and each test will be independently conducted on them. For each test a sequence of p value is calculated. Uniform distribution of random variable p is tested and we can reject the generator if it was rejected.
Eighth step
Implementing the low of iterated logarithm test: Running this test is applied in following stages (Wang and Nicol, 2015):
| • | Select testing points such as n = 2t+26 that t = 0, 1,..., 8 |
| • | Generate m≥10000 sequences and put them in |
| • | Compare the distance between |
Also, for calculating distance this statement, root-mean-square deviation, can be used:
| (6) |
As Fig. 2 shows, this pattern neither puts the attack criteria like many recourses (Kelsey et al., 1998, 1999), nor pays no attention to attack like many other recourses (Reyad and Kotulski, 2015; Babaei and Farhadi, 2011; Ilyas et al., 2013; Hamdi et al., 2015). Also, about statistical tests intended by all the researchers, our proposed model completes recourses perspectives only deal with tests (Patidar and Sud, 2009; Ilyas et al., 2013; Hamdi et al., 2015).
| Fig. 2: | PRNGs evaluation pattern |
Furthermore, the recourses that only have noted first level of tests can have a precise evaluation too (Walker, 2008; Babaei and Farhadi, 2011; Ilyas et al., 2013), so this pattern completes their evaluation. Because of inappropriate generators that success in all 3 levels, as mentioned in recourse (Wang and Nicol, 2015), implementing iterated logarithm test is an important step for reducing second type error probability that our proposed pattern has focused on it.
RESULTS AND DISCUSSION
First in this section, we presented how generators stop or pass steps of the pattern with considering various generators. Then a generator will be proposed that can pass most of the steps.
Examples for some steps: For first step 3 generators are evaluated and results are shown in following table (Table 1). As it is presented in Table 1, Yang’s generator does not have acceptable speed. So, it is rejected and there is no need to run other steps.
For second step some generators are evaluated and the results shown in Table 2. As it is indicated in Table 2, first and second generators are rejected because of their small size of key space (complexity) and there is no need to continue pattern for them.
For third step sensitivity of generators are evaluated and results are shown in Table 3. As it is shown in this table, second generator can’t pass this step and there is no need to run the other steps.
For sixth and seventh step, BBS generator can be used which passes the sixth step successfully but stops at seventh step. It is indicated about some NIST tests in following table (Table 4).
For eighth step some generators have been evaluated and just 2 generators could pass the LIL test successfully. Table 5, indicates results for this step.
Introducing a good generator: Francois and Defour (2013) proposed a pseudo random generator with using 3 logistic mapping chaos in 2013.
| Table 1: | Table speed for speed check |
| Table 2: | Complexity for brute force attack |
| Table 3: | Result of NIST test on the sequences obtained from the two generators |
| Table 4: | Status for proportion of passing and distribution pattern |
| Table 5: | Law of the iterated logarithm testing results |
| LIL: Law of the iterated logarithm (Wang and Nicol, 2015) | |
The main idea of their PRBG is to combine several chaotic logistic maps and carefully arrange them in the same algorithm in order to increase the security level. It generates a block of 32 random bits per iteration using the following three logistic maps:
| (7) |
| (8) |
| (9) |
The evaluation pattern is as follows:
Step 1: The speed performance analysis is achieved on a personal computer with Intel(R) Core(TM) 2 Duo CPU P7350 at 2:00 GHz. The algorithm is implemented using GCC on Fedora release 16 (Verne). Speed of this generator is 44.1120 Mbit/s and indeed the generator could pass this level successfully.
Step 2: It is generally accepted that a key space of size larger than 2128 is computationally secure against such attack. In this case, the size of the key space is around 2173, which clearly allows resisting the brute force-attack.
Step 3: Output of this generator is used as random sample in the first level of NIST and no test is not rejected. Indeed the generator could pass this level successfully.
Step 4: About 15000 output sequences with close seed are generated for analyzing sensitivity. Correlation coefficient indicated that this generator is sensitive to seed and initial value and passes the forth level.
Step 5: Resistance against differential attack and Brute-force attack and guess-and-determine attack is approved, so it passes fifth step.
Step 6 and 7: Proportion of successful sequences in NIST test showed that the generator was successful in passing of sixth step. Also, the hypothesis of distribution uniformity of p values based on observed sequences is accepted. This means that the generator passes seventh step (Francois and Defour, 2013).
CONCLUSION
Evaluating the pseudo random number generators is essential which needs enough attention. There are a variety of criteria which are examined holistically in this study. Our suggested model in three issues of statistical tests, resistance against attacks and security implementing considerations are emphasized. An extensive discussion was conducted on three statistical tests. A comprehensive classification for different types of attacks on pseudo random number generators was proposed. We examined issues related to security and implementing considerations. Some priorities for applying these models are proposed which can lead to good guideline for one who is trying to evaluate the generators. With following all steps of this pattern, while a comprehensive evaluation, the probability of accepting improper generators will be reduced.