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

From: Bryan Olson (fakeaddress_at_nowhere.org)
Date: 10/25/05 

Date: Tue, 25 Oct 2005 01:05:44 GMT

lkcl wrote:
> well for KEYED_PRNG(k) i'm using AES (again).

Well, that's part of what I asked for.

> i don't believe it matters what the input is, as long
> as it is unique (for all values of k).
>
> regarding p <= 0.01 - i realise that this may offend
> people who wish to be mathematically rigorous.

How about people who want to get things right instead of
wrong?

> i am _merely_ using p_value - the function - to
> guage how to group the data together (by
> number of bits in the output).
>
> at some point, once i have worked through a few
> more steps, i will come back and go "hmm, i
> _really_ need to have a more accurate statistical
> analysis handle on this: what was that p_value()
> function doing? hmmm...".

Here's an idea: don't say things like "p-value", "correlation",
or "differential analysis", unless you know what they mean.

> i should say this, however: remember that the
> p_value() function is measuring _very_ small
> block sizes (128 bits, 256 bits...).

That's why I recomended the exact binomial rather than using the
normal distribution to approximate it:

   http://groups.google.com/group/sci.crypt/msg/2478e3cf0004896b

You can compute them with the code I included in:

   http://groups.google.com/group/sci.crypt/msg/acdda09918f21189

[...]
> i mention this because it's a similar thing: quantisation
> is occurring - in this case due to the very small block
> size.

I already calculated the effect of this quantization.

     Given 128 random independent bits, to reach p <= .01 we need
     78 or more set bits. The actual p-value associated with 78
     set bits is 0.008335, so the probability of reaching the 1%
     significance level for a random block is noticeably less
     than 1%.

You seem to be using a two-tailed test, which comes out a bit
different, and there happens to be a criterion that falls very
close to p=0.01. Given 128 random (0.5 chance either way)
independent bits:

     Probability(max(set_bits, clear_bits) >= 79) = 0.01009 

-- 
--Bryan
Loading