| GRAND PRIZE AT NATIONAL CONTEST "E-IDEA" FOR SOFTWARE IDEAS/PRODUCTS AT BINARY 2002, BUCHAREST-ROMANIA
HENKOS PSEUDO-RANDOM NUMBER GENERATOR
The generation of random numbers is critical to cryptographic systems. Symmetric ciphers such as DES, RC2, and RC5 all require a randomly selected encryption key. Public-key algorithms - like RSA, Diffie-Hellman, and DSA - begin with randomly generated values when generating prime numbers.
At a higher level, SSL and other cryptographic protocols use random challenges in the authentication process to foil replay attacks. But truly random numbers are difficult to come by in software-only solutions, where electrical noise and sources of hardware randomness are not available (or at least not convenient).
This poses a challenge for software developers implementing cryptography.
A pseudo-random number generator (PRNG) is a deterministic algorithm which, given a truly random binary sequence of length k, outputs a binary sequence of length l >>k which appears to be random. The input to the generator is called the seed, while the output is called a pseudorandom bit sequence.
A PRNG must have a high degree of unpredictability. Even if nearly every bit of output is known, those that are unknown should remain hard to predict.
The other component in producing good random numbers is providing a random seed. A good PRNG will produce a sequence that is sufficiently random for cryptographic operations, with one catch: it needs to be properly initialized, or "seeded". Using a bad seed is a common flaw in poorly implemented cryptographic systems.
There are two aspects to a random seed: quantity and quality. They are related. The quality of a random seed refers to the entropy of its bits. Cryptographers use the word entropy a lot, so it is worth knowing. In a system that produces the same output each time, each bit is fixed, so there is no uncertainty, or zero entropy per bit. If every possible sequence of outputs is equally likely (i.e. truly random) then there is total uncertainty, or one bit of entropy per output bit. There are precise mathematical formulas for entropy, but the short summary is the more entropy per bit, the better. Since the quality may vary, it is a good idea to account for this with quantity. Sufficient quantity makes it impractical for an attacker to exhaustively try all likely seed values.
The HENKOS generator is a new type of generator that implements an own algorithm that essentially modifies the mode of construction and utilization of pseudo-random number generators. This generator brings two new directions referring to the quantity and quality of a seed used as input:
* the seeds size is not selected from a fixed interval, there is only an inferior limitation of 192 bits meant to prevent its location using a brute-force attack, which can be whatever big, the superior limit being established according with the application where the generator will be used.
* it can be generated a sequence of pseudo-random numbers from any seed no matter its entropy, even from one whit a zero entropy which doesn't contain any information.
HENKOS generator has two distinctive parts:
1. a training module - who prepares the seed in order to become a "good seed".
2. the generation module - that produce the output pseudo-random sequence.
The verification of generated sequence for establish if it has or nor random features is made by statistic tests.
The HENKOS generator is successfully passing the most important packs of statistic tests: FIPS 140-1, FIPS 140-2 (security requirements for cryptographic modules, Commerce Department USA), ENT tests(the entropy count, chi square test, the Monte Carlo test), DIEHARD (the most "acid" pack of tests which many generators are not passing it; author dr. Marsaglia, Florida University), NIST Statistical Test Suite (tests developed at The National Institute For Standard and Technologies from USA for the pseudo-random number generators which are going to be used in the cryptographic applications).
In the development of HENKOS generator was used an algorithm of own conceive and for its implementation in the software variant it has been used the C language this one assuring a good portability of the source cod as well as for DOS/Windows and for the Linux operating system. For obtain of the two versions it has been used the Borland C compiler for DOS/Windows and the gcc compiler for Linux.
It has been done tests on samples of numbers produced by the generator of order of tens and hundred megabytes and the results up till now indicates the fact that it can be used in the cryptographic applications.
* the HENKOS generator allowed the use of a seed with a very big length, theoretical there is not a superior limitation which make it impossible to be found in order to compare with the other generators which has a limitation of seeds size.
* HENKOS may generate a pseudo-random sequence from any seed inclusive from a seed with zero entropy, thing impossible to be done by other generator. That's why this PRNG cannot generate non-random sequences if wasn't properly seeded.
* From the test result a superior speed of generating of the numbers of 276 Mbps, which shows that is faster than the existing generators. This results because the algorithm simplicity.
* The security is not sacrificed for the speed, the statistic tests confirming that the generator can be used in cryptographic applications.
* HENKOS generator might be an efficient alternative in the security applications (keys generating for the encryption algorithms) having in vision the news represented, its implementation needs very low costs.
Solutions for data security
HENKOS pseudo-random number generator doesn't need especially resources; it can be actually to work in minimal system. There is also the version for DOS/Windows as well the version for Linux. The generating speed of a sequence depends directly on of the system performances, as refer point the generator was tested on the system PII 300MHz, 32 MB RAM, DOS/Windows 98 / Linux (276.62 Mbps, for a seed of 640 bits).
Contact: Marius Oliver Gheorghita (firstname.lastname@example.org)
||Statistical tests for randomness
1. FIPS 140-1 and FIPS 140-2 (security requirements for cryptographic modules)
2. ENT pseudorandom sequence test program
3. DIEHARD battery of tests
4. NIST Statistical Test Suite for pseudorandom number generators used in cryptographic applications
Test computer: PII 300, 32MB RAM, Linux
Seed: 2584 bits
Training seed time: 2.27 s
Pseudorandom sequence: 100000000 bits
Producing sequence time: 2.62 s