Ever Hear of NIST's STS?

NIST's STS?  That's the space shuttle program right... Space Transportation System?

Wait, wrong, NIST != NASA.

NIST, or the National Institute of Standards and Technology, is an organization with in the US Government, that's responsible for setting standards for technology.  They're the group that said AES (Advanced Encryption Standard) was good enough for all US Government use and blessed it as such via FIPS-197 (Federal Information Processing Standard publication #197).  Turns out that the NSA (National Security Agency, still not NASA) had a big impact on approving that standard, so either it's good enough for them, or they already had a way to break it.

The STS (Statistical Test Suite) is a PCT (Pretty Cool Tool), that hopefully wasn't somehow nerfed by the NSA too.  You (or I or someone) can use it to test the "randomness" of output from a random number generator.  I've been using it for a couple of years now; running a quasigroup based cryptosystem I invented through its paces (I'll go more into that getup in another post).  So why use the STS on a cryptosystem?  It just so has it that encrypted data should be just as good as output from a PRNG (pseudo random number generator).

It's great, because not only does it combine tests from some of it's predecessors like Diehard and bros, but it also made some decisions on how to interpret the output. So, statisticians like to create "null-hypothesis" for some reason (you can tell I'm not one), then test them.  Which results in a P-value (Great name huh?  Basically means the probability the null-hypothesis is true).  So the STS's null-hypothesis is that some data are random. I quote from the massive PDF that documents the tool:

For these tests, each P-value is the probability that a perfect random number generator would have produced a sequence less random than the sequence that was tested, given the kind of non-randomness assessed by the test. NIST-STS docs

Turns out the bar's pretty low (or so it would seem).  P-Values greater than 0.001 (0.1%) indicates success; that's the decision process that the NIST team added to the tool.  How easy is that to obtain?  Well, turns out that AES in it's lower configuration modes doesn't pass, which is good, because we can use that as a benchmark.

So, STS is PCT, but sucks too.  You can only run one file through at a time, and it generates like 1-billion files (mmu ha ha HAAA!).  So it's crap at the same time, because on most computers manufactured, like in the last decade, it uses about 10% of the CPU resources.

Thus!  I put together a script to jam random bits into the STS's "assess" program and spit out a CSV (Comma Separated Value) file.  Then created 10 identical copies of the STS distribution directory so I could MP (Multiprocess, common people keep up) my way through heating my CPU past 150 Fahrenheit.

Save the script (I called it ta.sh, I don't even remember what the T stands for, I think the A was assess) and run it like so:

 ./ta.sh 20000 my.20000.byte.assessment.csv *.random.stuff 

Results:

1. Multiple files run through the STS assess program
2. A single CSV with the results (Success score and P-Values)
3. Double clickable to Excel
4. $$PROFIT$$

Here's that script:

#!/bin/bash

testThis() {
echo "Assessing $2"
(./assess $1 \
    | grep "UNDERFLOW"
) << EOF.
0
$2
1
0
1
1
EOF.

n=`echo $2 | sed -e "s^.*/^^g"`
grep "p_value" `find experiments -name stats.txt` \
        |grep -v "RandomExcursions\|CumulativeSum\|Serial" \
        |sed  -e "s^/stats.txt^^g" -e "s#^.*/##g" \
                -e "s/:.*\(SUCCESS\|FAILURE\)/,\1/g" \
                -e "s/\t.*p_value1\?2\? = /,/g" -e "s/^/$n,/g" >> $3

grep "FORWARD\|REVERSE\|p_value" exp*/*/CumulativeSums/stats.txt \
    |sed -e "s/.*FORWARD.*/Forward/g" -e "s/.*REVERSE.*/Reverse/g" -e "s/\t.*= /,/g" \
| (
    read t
    read s
    echo "$n,CumulativeSums-$t,$s" >> $3
    read t
    read s
    echo "$n,CumulativeSums-$t,$s" >> $3
)
grep p_value exp*/Alg*/Ser*/stats.txt \
    | sed -e "s/\(SUCCESS\|FAILURE\)\t.*p_value\(.\) = /\2,\1,/g" \
            -e "s/^/$n,Serial/g" >> $3
}

CAPTURE=$1
SIZE=$2
while [ "$3" != "" ]; do
    for i in $3; do
        testThis $SIZE $i $CAPTURE
    done
    shift
done