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

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

Date: Wed, 19 Oct 2005 16:55:41 GMT

Joseph Ashwood wrote:
[...]
> Near the end of the computation you have:
> /* count the number of bits, create a p-value, blah blah */
>
> count = num_bits(test_data, sizeof(test_data));
>
> testval = (count - ((double)sizeof(test_data)*4)) * 2;
>
> sobs = fabs(testval) / sqrtl(sizeof(test_data));
Big bad bug: ^^^^^^^^^^^^^^^^^

Wanted the bits, counted the bytes.

Joe, was this bug in Ikcl's original code?

> f = sobs / sqrt2;
>
> pval = erfc(f);

For tests on one or several blocks, use the exact binomial;
the code above uses the normal approximation. As Mike Amling
pointed out, in this experiment we need only calculate the
interesting values once, so we can handle reasonably large
sizes with the exact distribution.

If you do need the normal approximation, re-write the code
above to not suck so much. Maybe like:

    n_trials = sizeof(test_data) * 8;
    /* Assume binomial distribution with p = q = 0.5. */
    expected = n_trials * 0.5;
    variance = n_trials * 0.5 * 0.5;
    stdev = sqrtl(variance);
    z_score = fabs(count - expected) / stdev;
    pval = erfc(z_score / sqrt2); 

-- 
--Bryan

Relevant Pages