October 8, 2013 at 10:40Looking for a crypto-resistant PRNG
Hi% username%!
In today's post, we will talk about the cryptographic stability of pseudo random number generators (PRNGs).
To begin with, we will determine what is a crypto-resistant PRNG (KSGPSCH).
The HRCSSC shall satisfy the “next bit test”. The meaning of the test is as follows: there should not be a polynomial algorithm that, knowing the first k bits of a random sequence, will be able to predict k + 1 bits with a probability of more than 50%.Wikipedia
Perhaps some readers have used PRNGs such as linear feedback shift registers (RSLOS) or Mersenne’s beloved by many programmers. I will try to show that both of these methods, despite very good statistical properties and large periods, do not correspond to the above definition and cannot be considered cryptographically strong, and I will also offer, as an alternative, two very reliable PRNGs.
Linear Feedback Shift Register
Often it was seen how this method was proposed to be used for cryptographic purposes, therefore, in fact, we will begin with it. Generators of this kind consist of a shift register and a feedback function.
Each PRNSS PRNS is associated with a specific polynomial that characterizes the length of the register and the feedback function. For example, the
following register corresponds to a polynomial : The 
degree of the polynomial determines the length of the register, nonzero members describe which register elements constitute the tap sequence.
If the polynomial forming the tap sequence is irreducible modulo 2, then the period of the sequence generated by the register will be maximum and is calculated by the formula
.Before starting work, an arbitrary sequence of bits, called the initial state, is entered into the register. After that, each clock cycle of the generator returns 1 bit, which looks completely random.
RSLOS per se are good PRNGs, but since the bits received with their help have a linear connection, using RSLOS for cryptographic purposes is unreasonable.
If an attacker receives a sequence of bits of length n generated using RSLOS, he can load these bits into the register and scroll back to get the initial state. Knowing the initial state will give him access to all the sequences generated earlier and generated in the future.
It might be a good idea to hide case information. Then, even after receiving a sequence of length n, the attacker will not be able to take steps to open the initial state.
But this situation is easily solved using the Berlekamp – Massey algorithm. This algorithm makes it possible to open the polynomial associated with RSLOS. To do this, it is enough to have a sequence generated by the register with a length of only 2n.
The algorithm is quite simple to implement:
public int[] BerlekampMassey(int[] array)
{
int N = array.Length;
int[] b = new int[N];
int[] c = new int[N];
int[] t = new int[N];
b[0] = 1;
c[0] = 1;
int l = 0;
int m = -1;
for (int n = 0; n < N; n++)
{
int d = 0;
for (int i = 0; i <= l; i++)
{
d ^= c[i] * array[n - i];
}
if (d == 1)
{
Array.Copy(c, 0, t, 0, N);
int N_M = (n-m);
for (int j = 0; j < N - N_M; j++)
{
c[N_M + j] ^= b[j];
}
if (l <= n / 2)
{
l = n + 1 - l;
m = n;
Array.Copy(t, 0, b, 0, N);
}
}
}
return c;
}
The input receives a sequence of bits generated using RSLOS. A polynomial characterizing the feedback scheme is returned as a result.
Of course, RSLOS can be combined in cascades for a more cryptographic PRCH. This idea is used in some stream ciphers. However, many generators based on this method are vulnerable to the so-called correlation attacks. I gave some details about this type of attack in my recent post Security of GSM networks: data encryption . Here I will only say that with the help of a correlation attack, an attacker, having the sequence of the generated PRNG, is able to restore the initial value and gain access to all values generated in the future.
Mersenne Whirlwind
Much more interesting in my opinion is the PRNG, called the Mersenne Whirlwind. There are several options for the algorithm.We will consider only the most commonly used MT19937. We briefly describe this algorithm.
The Mersenne vortex consists of two parts: RSLOS and quenching.
The shift register consists of 624 elements, each 32 bits long. Initialization of the initial state is described by the function:
function initialize_generator(int seed) {
index := 0
MT[0] := seed
for i from 1 to 623 { // loop over each other element
MT[i] := last 32 bits of(1812433253 * (MT[i-1] xor (right shift by 30 bits(MT[i-1]))) + i) // 0x6c078965
}
}
At the input of the initialization function, a certain seed value is supplied, with the help of which the entire register is filled.
At the first and each subsequent 624th step, the internal state of the register is mixed:
function generate_numbers() {
for i from 0 to 623 {
int y := (MT[i] & 0x80000000) // bit 31 (32nd bit) of MT[i]
+ (MT[(i+1) mod 624] & 0x7fffffff) // bits 0-30 (first 31 bits) of MT[...]
MT[i] := MT[(i + 397) mod 624] xor (right shift by 1 bit(y))
if (y mod 2) != 0 { // y is odd
MT[i] := MT[i] xor (2567483615) // 0x9908b0df
}
}
}
At each step, the algorithm returns the following number from the current state of the register and produces the so-called "hardening":
function extract_number() {
if index == 0 {
generate_numbers()
}
int y := MT[index]
//закалка
y := y xor (right shift by 11 bits(y))
y := y xor (left shift by 7 bits(y) and (2636928640)) // 0x9d2c5680
y := y xor (left shift by 15 bits(y) and (4022730752)) // 0xefc60000
y := y xor (right shift by 18 bits(y))
index := (index + 1) mod 624
return y
}
In order to gain access to the internal state of the algorithm, the attacker just needs to get a sequence of 624 numbers.
All you need to do is return the numbers generated by the algorithm to the state in which they were before the "hardening" stage. To do this, you need to do all the steps of hardening in the opposite direction. For example, consider the last step of quenching:
y := y ^ (y >>> 18)Let's see what happens with binary data when performing this operation:
y 10110111010111100111111111111111010
y >>> 18 00000000000000000010110111010111100111111001110010
y ^ (y >>> 18) 10110111010111111011010011101001011011
As you can see, the first 18 bits of the result and the original number are the same. In order to restore the remaining 14 bits, we need to do the following:
result ^ (result >>> 18) Acting in a similar way for all the steps of the hardening stage, we get an element of the initial state of the PRNG:
private uint reverse(uint output)
{
uint tempout = output >> 18;
output = output ^ tempout;
tempout = output << 15;
output = (uint)(output ^ (tempout & 4022730752));
uint a = output << 7;
uint b = (uint)(output ^ (a & 2636928640));
uint c = b << 7;
uint d = (uint)(output ^ (c & 2636928640));
uint e = d << 7;
uint f = (uint)(output ^ (e & 2636928640));
uint g = f << 7;
uint h = (uint)(output ^ (g & 2636928640));
uint i = h << 7;
uint tempfinal = (uint)(output ^ (i & 2636928640));
uint k = tempfinal >> 11;
uint l = (uint)(tempfinal ^ k);
uint m = (uint)l >> 11;
uint final = (uint)(tempfinal ^ m);
return final;
}
As I noted above, if the attacker has 624 numbers generated using the Mersenne Vortex, this is enough to restore the entire internal state and predict with 100% probability all the numbers generated in the subsequent one.
Cryptographic PRSP
As an alternative, I want to offer two very reliable methods.
Blum - Blum - Shub Algorithm
This generator is based on the complexity of solving the problem of factorization of large numbers.
The algorithm generates a sequence of pseudo-random bits and consists of the following steps:
- Generate two large primes p, q such that p = q = 3 mod 4.
- Calculate M = p * q.
- Take a large number x 0 , coprime to M.
- At each step of generating the sequence, the number x i + 1 = x i 2 mod M.
- As the result, the last bit of the number x i is returned .
To date, this algorithm is perhaps the most reliable PRNG. To open the initial state or guess the next element of the pseudo-random sequence, the attacker must know the numbers p and q.
The BBS generator has only one drawback - this is an extremely low speed. To increase productivity at each step of generation, it is possible to return instead of one, log (log M) bit. This will increase the speed without reducing cryptographic strength.
CTR encryption mode
A faster, but equally reliable way to obtain a pseudo-random sequence is the CTR block cipher encryption mode, in other words, counter mode. As an encryption function, you can use any strong block cipher, for example, AES.
An encryption key and a 128-bit data block consisting of a random bit string and a counter are fed to the input of the encryption function. At each step, the counter is incremented by one, thereby guaranteeing a non-repeating sequence of blocks. The generated sequence consists of encrypted blocks. In order to predict the next element of the generated sequence, the attacker needs to open the encryption key, i.e. the task is reduced to breaking the block cipher used in the scheme.
Conclusion
First of all, I wanted to demonstrate the cryptographic unreliability of such well-established PRNGs as linear feedback registers and Mersenne Whirlwind.
Both of these algorithms are favorably distinguished by a high speed of work. They generate truly good sequences that are statistically indistinguishable from random ones. But, unfortunately, when it comes to cryptography this is often not enough and it is necessary to use slower, but much more secure methods.
