|
Karl-Uwe Frank
|
Feb 23 2017, 11:18 AM
Post #1
|
- Posts:
- 639
- Group:
- Members
- Member
- #3,502
- Joined:
- July 11, 2011
|
Yet another tiny and simple program to visualise the randomness of binary files written in Java.
http://www.freecx.co.uk/crypto/cryptanalysis/Random-Visualisation/GreyPlotRandomFile.java
Essentially it just define a new image based on the file size or a given byte offset - similar to the previously posted Python program - and read in the given file byte per byte, place a pixel based on the integer of the byte value at a sequential position. The calculated image will then be resized to 512 x 512 pixel and this resulting image will be saved at the same location as the binary file.
Surprisingly this simple routine reveal even more precise if the PRNG which generated the random binary file is biased.
For example if we again check the binary file http://www.freecx.co.uk/crypto/cryptanalysis/Random-Visualisation/2D-Example-Binary-Files/badRNG_4MB.bin
the resulting image show a clearly visible pattern that indicate a massive bias http://www.freecx.co.uk/crypto/cryptanalysis/Random-Visualisation/2D-Example-Binary-Files/badRNG_4MB.bin_rnd.jpg
The same holds for the following image which reveal a massive pattern as well http://www.freecx.co.uk/crypto/cryptanalysis/Random-Visualisation/2D-Example-Binary-Files/permpolyprng_4MB.bin_rnd.jpg
which ist based on the binary file http://www.freecx.co.uk/crypto/cryptanalysis/Random-Visualisation/2D-Example-Binary-Files/permpolyprng_4MB.bin
and of course the extreme pattern in http://www.freecx.co.uk/crypto/cryptanalysis/Random-Visualisation/2D-Example-Binary-Files/zero_4MB.bin.crystalline_rnd.jpg
based on the binary file http://www.freecx.co.uk/crypto/cryptanalysis/Random-Visualisation/2D-Example-Binary-Files/zero_4MB.bin.crystalline
All of these binary files fail other tests for randomness, like Rabbit/Alphabit or the Qualcomm bias test.
Now I would like to highlight how the test behave on checking a JPEG, a PDF and a text file. First let's look at the result of the JPEG file http://www.freecx.co.uk/crypto/cryptanalysis/Random-Visualisation/2D-Example-Binary-Files/Krak_des_Chevalier.jpg_262144_rnd.jpg
based on this image http://www.freecx.co.uk/crypto/cryptanalysis/Random-Visualisation/2D-Example-Binary-Files/Krak_des_Chevalier.jpg
Surprisingly it looks quite random even if we would expect to see some pattern. A test with ENT give us this result
- Code:
-
*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=* Entropy[space]=[space]7.978943[space]bits[space]per[space]byte.
Optimum[space]compression[space]would[space]reduce[space]the[space]size of[space]this[space]313196[space]byte[space]file[space]by[space]0[space]percent.
Chi[space]square[space]distribution[space]for[space]313196[space]samples[space]is[space]8933.78,[space]and[space]randomly would[space]exceed[space]this[space]value[space]less[space]than[space]0.01[space]percent[space]of[space]the[space]times.
Arithmetic[space]mean[space]value[space]of[space]data[space]bytes[space]is[space]128.1416[space](127.5[space]=[space]random). Monte[space]Carlo[space]value[space]for[space]Pi[space]is[space]3.118297285[space](error[space]0.74[space]percent). Serial[space]correlation[space]coefficient[space]is[space]0.017011[space](totally[space]uncorrelated[space]=[space]0.0).
Only the Chi square indicate that the binary is not as random as expected in comparison with the greyscale image.
The Rabbit/Alphabit test however reveal that the binary is far from being random.
- Code:
-
============================================== 313196[space]byte[space]for[space]testing
========[space]Running[space]Rabbit[space]Test[space]=========
=========[space]Summary[space]results[space]of[space]Rabbit[space]=========
[space]Version:[space][space][space][space][space][space][space][space][space][space]TestU01[space]1.2.3 [space]File:[space][space][space][space][space][space][space][space][space][space][space][space][space]2D-Example-Binary-Files/Krak_des_Chevalier.jpg [space]Number[space]of[space]bits:[space][space][space]313184 [space]Number[space]of[space]statistics:[space][space]38 [space]Total[space]CPU[space]time:[space][space][space]00:00:00.63 [space]The[space]following[space]tests[space]gave[space]p-values[space]outside[space][0.001,[space]0.9990]: [space](eps[space][space]means[space]a[space]value[space]<[space]1.0e-300): [space](eps1[space]means[space]a[space]value[space]<[space]1.0e-15):
[space][space][space][space][space][space][space]Test[space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space]p-value [space]---------------------------------------------- [space][space]1[space][space]MultinomialBitsOver[space][space][space][space][space][space][space][space][space][space][space][space][space][space]eps[space][space] [space][space]2[space][space]ClosePairsBitMatch,[space]t[space]=[space]2[space][space][space][space][space][space]2.6e-71 [space][space]3[space][space]ClosePairsBitMatch,[space]t[space]=[space]4[space][space][space][space][space]1.4e-149 [space][space]4[space][space]AppearanceSpacings[space][space][space][space][space][space][space][space][space][space][space][space][space]1[space]-[space]eps1 [space][space]6[space][space]LempelZiv[space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space]1[space]-[space]eps1 [space][space]8[space][space]Fourier3[space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space]4.1e-11 [space]10[space][space]PeriodsInStrings[space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space]9.1e-6 [space]11[space][space]HammingWeight[space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space]eps[space][space] [space]12[space][space]HammingCorr,[space]L[space]=[space]32[space][space][space][space][space][space][space][space][space][space][space][space][space][space]eps[space][space] [space]13[space][space]HammingCorr,[space]L[space]=[space]64[space][space][space][space][space][space][space][space][space][space][space][space][space][space]eps[space][space] [space]14[space][space]HammingCorr,[space]L[space]=[space]128[space][space][space][space][space][space][space][space][space][space][space][space][space]eps[space][space] [space]15[space][space]HammingIndep,[space]L[space]=[space]16[space][space][space][space][space][space][space][space][space][space][space][space]7.4e-6 [space]18[space][space]AutoCor[space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space]1[space]-[space][space]1.8e-5 [space]20[space][space]Run[space]of[space]bits[space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space]eps[space][space] [space]24[space][space]RandomWalk1[space]H[space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space]3.9e-8 [space]24[space][space]RandomWalk1[space]M[space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space]2.5e-6 [space]25[space][space]RandomWalk1[space]H[space](L[space]=[space]1024)[space][space][space][space][space][space][space][space]2.6e-8 [space]26[space][space]RandomWalk1[space]H[space](L[space]=[space]10016)[space][space][space][space][space][space][space]4.2e-7 [space]---------------------------------------------- [space]All[space]other[space]tests[space]were[space]passed
*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*
========[space]Running[space]Alphabit[space]Test[space]========
=========[space]Summary[space]results[space]of[space]Alphabit[space]=========
[space]Version:[space][space][space][space][space][space][space][space][space][space]TestU01[space]1.2.3 [space]File:[space][space][space][space][space][space][space][space][space][space][space][space][space]2D-Example-Binary-Files/Krak_des_Chevalier.jpg [space]Number[space]of[space]bits:[space][space][space]313184 [space]Number[space]of[space]statistics:[space][space]17 [space]Total[space]CPU[space]time:[space][space][space]00:00:00.03 [space]The[space]following[space]tests[space]gave[space]p-values[space]outside[space][0.001,[space]0.9990]: [space](eps[space][space]means[space]a[space]value[space]<[space]1.0e-300): [space](eps1[space]means[space]a[space]value[space]<[space]1.0e-15):
[space][space][space][space][space][space][space]Test[space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space]p-value [space]---------------------------------------------- [space][space]1[space][space]MultinomialBitsOver,[space]L[space]=[space]2[space][space][space][space][space][space][space]eps[space][space] [space][space]2[space][space]MultinomialBitsOver,[space]L[space]=[space]4[space][space][space][space][space][space][space]eps[space][space] [space][space]3[space][space]MultinomialBitsOver,[space]L[space]=[space]8[space][space][space][space][space][space][space]eps[space][space] [space][space]4[space][space]MultinomialBitsOver,[space]L[space]=[space]16[space][space][space][space][space][space]eps[space][space] [space][space]5[space][space]HammingIndep,[space]L[space]=[space]16[space][space][space][space][space][space][space][space][space][space][space][space]7.4e-6 [space][space]7[space][space]HammingCorr,[space]L[space]=[space]32[space][space][space][space][space][space][space][space][space][space][space][space][space][space]eps[space][space] [space][space]8[space][space]RandomWalk1[space]H[space](L[space]=[space]64)[space][space][space][space][space][space][space][space][space]8.4e-14 [space][space]8[space][space]RandomWalk1[space]M[space](L[space]=[space]64)[space][space][space][space][space][space][space][space][space][space]1.3e-7 [space][space]8[space][space]RandomWalk1[space]J[space](L[space]=[space]64)[space][space][space][space][space][space][space][space][space][space]7.9e-6 [space][space]9[space][space]RandomWalk1[space]H[space](L[space]=[space]320)[space][space][space][space][space][space][space][space][space]5.0e-4 [space][space]9[space][space]RandomWalk1[space]M[space](L[space]=[space]320)[space][space][space][space][space][space][space][space][space]2.5e-4 [space]---------------------------------------------- [space]All[space]other[space]tests[space]were[space]passed
Because of the fact that the visualisation tool just collect byte sequentially as they appear in the binary file without any further calculation for potential bias we can not expect it to be a one-and-only tool to rely on in regards of finding bias.
A JPEG file has somehow a random structure that the simple visualisation function displays. The ENT test explains this if we look at the Arithmetic mean, the Monte Carlo value for Pi and the Serial correlation coefficient. So we can't expect this visualisation tool to find the far more detailed results like the Rabbit/Alphabit test.
So let's take a look at two more structured files and check them with the randomness visualisation function.
First we visualise a PDF file like this one http://www.freecx.co.uk/crypto/cryptanalysis/Random-Visualisation/2D-Example-Binary-Files/Attack%20on%20Broadcast%20RC4%20Revisited%20.pdf
(which I have downloaded from here http://fse2011.mat.dtu.dk/slides/Attack%20on%20Broadcast%20RC4%20Revisited%20.pdf)
The randomoness image clearly show that this is a non-random file http://www.freecx.co.uk/crypto/cryptanalysis/Random-Visualisation/2D-Example-Binary-Files/Attack%20on%20Broadcast%20RC4%20Revisited%20.pdf_1048576_rnd.jpg
Secondly we check this huge text file http://www.freecx.co.uk/crypto/cryptanalysis/Random-Visualisation/2D-Example-Binary-Files/big.txt
and again the resulting image indicate that it is a non-random file http://www.freecx.co.uk/crypto/cryptanalysis/Random-Visualisation/2D-Example-Binary-Files/big.txt_5308416_rnd.jpg
As a conclusion I like to say that even if the randomness visualisation tool is that extremely simple, still it could be part of a test series because it is able to indicate a binary file generated by a biased PRNG, as the three examples at in the beginning of this post explain.
All binary files and resulting test images can be found over here
http://www.freecx.co.uk/crypto/cryptanalysis/Random-Visualisation/2D-Example-Binary-Files/
Cheers, Karl-Uwe
|