[SC] 3. One time pad pseudo-randomness tests

For this week, we had to test our one time pad keys generator.

The goal is to ensure that our generator produces enough pseudorandom keys.

To achieve that goal we need to satisfy the next requirements

- The pseudorandom numbers should be enough uniformly distributed

- The generation must be unpredictable and unreproducible.

- The keys must be uncompressible.

We must also ensure that our generator does not cause any kind of pattern.

Tomada de http://www.random.org/analysis/

In the image, we can see how the pseudorandom number generator of the function rand() from PHP have a high periodicy and the pattern thats causes a pattern, this is a very big vulnerability because, with the enough computing power, any pseudorandom generated key can be broken.

If we fulfill the requirements we can ensure that our keys are unbreakable.

Tests

To tests my pseudorandom  keys, I perform the following tests:

• Uniformity of pseudorandom integers
• Uniformity of zeros and ones
• Frequency Monobit Test
• Frequency Block Test
• Compression test

Results

1. Uniformity of pseudorandom integers.

For this tests first I generate a new set of keys, the one-time-pad to test is conformed by a set of 100 keys with length 100 each one, that means that I produce 10000 pseudorandom numbers in a range from 0 to 126, then, I store them in a matrix (only for storage, nothing special). Then, I pass the matrix to a function that calculates the frequency of each number in the range 0 to 126.

Then, with the frequencies calculated I proceed to plot them in a graph. This is the result

We can see that the integers are semi uniform, sometimes there are some high levels of recurrence, sometimes are low levels of recurrence. This is only the first part, later we can tests if really the pseudorandom keys are really random.

2. Uniformity of zeros and ones.

After calculate the frequency of each integer, I proceed to tests the uniformity of zeros and ones, so, first I need to convert my key in a long binary string, for that I followed the rule:

if(number >= 0 and number <=63) then number = 0

if(number >=64 and number <=126) then number = 1

With this method now my key matrix is a binary matrix, now I counted the amount of ones and zeros in each key and then I plot a graph with the results.

The graph looks like the previous one, we can see that the amount of ones and zeros is also semi uniform, so, we can conclude that maybe the numbers that form each key are pseudorandom.

For more confiability, I perform 2 officially tests for pseudorandom generators.

3. Frequency Monobit.

"The focus of this test is the proportion of zeroes and ones for the entire sequence. The purpose of this test is to determine whether the number of ones and zeros in a sequence are approximately the same as would be expected for a truly random sequence. The test assesses the closeness of the fraction of ones to 1/2, that is, the number of ones and zeros in a sequence should be about the same. 
Note that if a generator fails this test then the likelihood of other tests failing is high."

Tomado de  http://www.random.org/analysis/Analysis2005.pdf

The parameter of this test is only n , the length of the key (list of ones and zeros, length 100), I pass all the matrix as parameter and I perform the tests 100 times (100 keys).

This is the results of the tests:

.......

The pictures are croped, at the final, the tests shows the amount of passed tests and failed tests.

We can conclude that our one time pad is suspicious to be a real pseudorandom keys because the 93% of the monobit tests was passed.

4. Frequency Block.

"The focus of this test is the proportion of ones within M-bit blocks. The purpose of this test is to determine whether the frequency of ones in an M-bit block is approximately M/2, as would be expected under the assumption of randomness. 
Note that for block size M=1, this test degenerates to the Frequency (Monobit) test. 
The parameters of the tests are the length of each block (M), the length of the bit string (n),  the sequence of bits as generated by the RNG or PRNG being tested (ε). ε ≥ n. 
If the computed P-value is <0.01, then conclude that the sequence is non-random. Otherwise, conclude that the sequence is random. "

Tomado de  http://www.random.org/analysis/Analysis2005.pdf

Also, I pass all the matrix as parameter and I perform the tests 100 times (100 keys, each keys of lenght 100 with block length of  "key length / 10").

The results:

 ......

With the two tests performed we can conclude that, according to the results of the tests, our one time pad meet the requirements to be a real random keys because the 90% of the frequency block tests was passed.

Summary:

90% of the frequency block tests was passed.

93% of the monobit tests was passed.

5. Compression test.

This is an extra tests that only to measures the compression ratio of the keys, so first we take the keys matrix and pass it as parameter to the function, then, reads each key and convert it to a string, next we apply the zlib.compress() to compress the key with a level of compression of 6 (default). Then I perform a summatory of the lenght of each keys (compressed and decompressed) and finally I compare the size of all the keys compressed and decompressed.

The result was:

If I try to compress the ones-zeros matrix, the result was:

We have a little contradiction here, because, our randomness tests conclude that the keys was real random keys, but, the compression ratio is almost 50%

5. Conclusion.

I think that the keys in the tested one time pad are real random keys, because the graphs shows that the numbers are generated almost uniformly, also, we pass the official test of randomness.

I think that the compression tests failed because the file is too small, maybe generating a long enough file the result will be better.

6. Code.





Referencias

• http://www.random.org/analysis/Analysis2005.pdf
• Google Docs | Statistical Testing Slides
• Google Docs | RNG Test Slides