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

From: Joseph Ashwood (ashwood_at_msn.com)
Date: 10/22/05

  • Next message: Joseph Ashwood: "Re: Encryption newbie - Same length encrypted result" 
    Date: Sat, 22 Oct 2005 00:25:46 GMT

    "Bryan Olson" <fakeaddress@nowhere.org> wrote in message
    news:G0f6f.5368$q%.4108@newssvr12.news.prodigy.com...
    > Joseph Ashwood wrote:
    > > "Bryan Olson" wrote:
    > >
    > >>Joseph Ashwood wrote:
    > >>> [...] The numbers look to very quickly
    > >>>converge, I've got a graph of the first 9000 or so entries, at 1 block
    > >>>intervals. The maximum setBits/totalBits starts at 70.83% and drops to
    > >>>51.12%, the minimum 36.67% to 48.93%, and average 53.31% to 50.01% so
    > >>>it
    > >>>still has quite a few statistical anomalies to work out, at 20626, the
    > >>>numbers move to; max 70.83% - 51.12%, min 35.00%- 48.91%, and average
    > >>>53.28%-50.01%. Interestingly, although the rounding error hides it, the
    > >>>final average actually rose from 50.006... to 50.0098, probably just a
    > >>>statistical anomaly, I do expect these to over time approach the
    > >>>perfect
    > >>>numbers of 100, 0, 50.
    >
    > >>You lost me. Are readers supposed to be able to tell what the numbers
    > >>mean?
    > >
    > >
    > > Sorry, it was late. That's the percentage of set bits; maximum,
    > minimum, and
    > > average.
    >
    > I'm still missing something. A maximum that starts high and
    > drops doesn't conform to my idea of what a maximum is. Can
    > you explain out how you generate the block and how you
    > take the counts?

    Sorry again. The counts are from sample lengths starting at 16-bytes,
    extending to 4096-bytes. The critical code looks like:

    count = 0;
    for(i = 0; i < numBlocks; i++)
    {
        count+=count_bits(outputBlock)
        fullcounts[i] = count;
    }
    ........

    The csv generation process is:
    for(int i = 0; i < numBlocks; i++)
    {
        System.out.print(fullcounts[i]+",");
    }
    System.out.println("");

    I'm willing to share the entire source code if you'd like it, at 53KB it's
    not that large. It currently generates 2 files each 32769 lines of csv, one
    of the straight counts (with a sample size header) and the second the
    percent of bits set. The straight count csv is about 840MB, the percentage
    one is ~2.4GB. I will also warn you that these files take a long time to
    load in OpenOffice, in 1.1.5 it was on the order of half an hour to get the
    graph I was looking at, in 2.0 it's 5-10 minutes, I would expect that MS
    Office is in the 5-10 minutes range as well.

    > As Paul Rubin pointed out, related-key issues could cause
    > non-random-like statistics, but I'd be surprised if a simple test
    > could distinguish AES from a random cipher.

    I don't see any evidence that this distinguishes it from random, in fact I
    see the opposite. I see it behaving very much like a random function should
    under this test. The average converges very quickly towards 50%, the minimum
    converges very quickly toward the expected minimum for the sample size, the
    maximum converges very quickly towards the maximum expected for the sample
    size. I only published the max and min per sample size because they are more
    meaningful. The only meaningful information that I can see coming from this
    is if the cycle length is notably different from expected, but this test
    doesn't appear to give any indications about those statistics.
                    Joe

  • Next message: Joseph Ashwood: "Re: Encryption newbie - Same length encrypted result"