advice sought on key/data histogram analysis of rijndael/128 and serpent

hiya,

i have a bit of a problem and am endeavouring to track down whether
it's my tests that are at fault. ha ha, of course there are no
problems with rijndael or serpent so it must be my use of gnuplot
or my code.

see: http://lkcl.net/crypto/key_as_data.tgz.

convenient build requirements: gcc and gnuplot.
(anything else you're on your own).

the basic premise of the test i am performing is to pick an initial
key with only one bit set, to encrypt some input data, to XOR in one
bit
into the output, then to use the output as the KEY for the next
encrypt,
repeat the process N times.

the outputs from this process i am chaining together and performing a
simple bit-count and statistical test to produce a p-value: the code
is ripped wholesale from STS, using erfc().

the STS bit-count test documentation notes two things: firstly, that
you shouldn't attempt to test less than 100 bits (okay - so that means
that if testing a 128-bit block cipher, we can test 1 block. hooray).
secondly, that a p-value of less than 0.01 indicates a bit of a problem
with your data. _especially_ if you end up with large numbers of <0.01
p-values.

this process i repeat 128x128 times - for initial keys with bit 0 set
all the way through to bit 127 (assuming a 128-bit cipher) and XORing
in one bit all the way from 0 to 127...

and _that_ process i repeat say 256, 512, 2560 times, with different
input
data.

i then build up a histogram, using the key bit-index and the data
bit-index,
of the number of times that the p-values "fail" - i.e. fall below 0.01.

i then use gnuplot in weird and wonderful ways to plot these histograms
in 3D.

i make three plots: one as you might expect: the key-bit-index as x,
the
data-bit-index as y, and the "bit-bucket" - number of p-value fails -
as z.
the other two are where i treat the "bit-bucket" as x, and make the
key-bit-index
and data-bit-index y/z and z/y respectively.

the results show patterns, where if everything was hunky-dory, there
would
be none. even plotting the raw data instead of creating histograms
from
it, and rotating the graph at some speed very clearly shows up what
look
like diffraction / interference patterns.

i initially started with rijndael-128, and was sufficiently puzzled by
the irregularities - or more specifically i should say regularities -
to try using serpent as a baseline, and found that serpent had even
worse
regular patterning than rijndael-128.

could somebody _please_ go over this code, and my use of gnuplot, and
point
out what i have done wrong.

for example: is the problem that i start off in each case with an
initial
key containing only one bit set?

am i just not generating enough test results? (yes, when i was
developing
an encryption algorithm i bought 8 AMD2000+ machines and ran NIST's STS
program on literally gigabytes of output for sometimes days on end, for
several months, fine-tuning the algorithm, so i do know how important
it is to test properly for randomness.)

i am beginning to understand that the "odd" graphs - where the
histogram
data is treated as the x-axis (and is therefore sorted) will show only
a
few data points at the extremes, such that the graphs cannot be
considered
reliable - but even with histogram values in the tens of thousands,
regularities still showed up.

overnight, i just ran a 5-hour run to take 256000*128*128*5 samples: at
the
extreme ends of the histogram spectrum - bars of size 421500 and bars
of
size 426000 - there are clear lines indicating correlations between key
bits around 90, 100, 16, 24... i think they're key bits: i can't
remember
which way round i did the plots :)

i'm placing the jpeg gnuplot window captures here:

http://lkcl.net/crypto/rjd.key.5.256000.jpeg
http://lkcl.net/crypto/rjd.data.5.256000.jpeg

advice much appreciated.

l.
Received on Mon Oct 17 20:48:35 2005