30 de agosto de 2012

Analysis for Pseudorandomness in One-Time Keys

Seguridad de la Información y Criptografía
Homework 2

Last week we write a python program for create one-time pads for two users, and then we use one of the keys and send a encrypted message, and the other user receive that message and decrypt with the same key, and every key that we use was deleted.

In that program we use a python random function for create the one-time keys, and now we need to check if the keys are secure.

And the question is:

Are one-time pads unbreakable?
"Yes. But only if used properly. A one-time pad must be truly random data and must be kept secure in order to be unbreakable." [1]

In class we learn three characteristics of a randomness key:
  • Unpredictable.
  • Uncompressible.
  • Unreproducible.

This three characteristics can be passed with a statistical test in the random keys, there are some tests that we can use, like Monobit Test, longest run of ones in a block, non overlapping template, and more.

In my case I use two tests that I had used in the past, monobit test and frequency block test, the next link is one of my publications in this blog, where I talk about statistical tests for pseudorandomness numbers.

Statistical tests for pseudorandomness numbers

I modify my last code for one-time pads, and in this case I add the functions for check every key with the two tests.

Note: I add a hashtag in the main function in the lines that encrypt and decrypt the message, because I only want to check the result of the test.

And here is my code:

And here is an example of an execution where I only request 4 keys, and every key was checked by the two tests.

If you check my code, in the part of the monobit test I need to change a character for a binary number (0 or 1), and in the frequency blocks I change the character for an int number.

Other important thing is that in the frecuency blocks, in my runnings ever gets a 1.0, but is because is use a little length of the key, if I change for 100000, the number change, but it takes more time for check every key.

One more thing that I used for check my one-time pads, is compressing the file with the keys and view the difference of size of the original file with the compressed file, and we can know how many is the percentage of compressing.

Pay attention in keys1 with keys1.tar.gz the compression is 16.95% less than the original, and keys22 with keys22.tar.gz the compression is the same, so if I create a file with more keys the percentage of compression don't change drastically.

ramon@pavilion:~/Documents/programas/criptologia/breakonetimepad$ ls -l
total 20672
-rwxr-xr-x 1 ramon ramon     3289 Aug 30 08:02 checkontimepad.py
-rw-rw-r-- 1 ramon ramon  1001000 Aug 30 08:05 keys1
-rw-rw-r-- 1 ramon ramon   831446 Aug 30 08:07 keys1.tar.gz
-rw-rw-r-- 1 ramon ramon  1001000 Aug 30 08:05 keys2
-rw-rw-r-- 1 ramon ramon 10010000 Aug 30 03:35 keys22
-rw-rw-r-- 1 ramon ramon  8313357 Aug 30 03:35 keys22.tar.gz

The percentage of compression isn't as bad as I think, so if the compression was more than 50%, someone can attack our keys easily, but isn't the case.

References and other pages:
[1] - One-time pad
Statistical Tests for Random Number Generators

1 comentario:

  1. Nice. I think it's good that you write in English. Try also to read something (whatever) in English to get the hang on the grammar faster. 7 pts.


Nota: solo los miembros de este blog pueden publicar comentarios.