Tuesday, March 25, 2014

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 of breaking 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?  Turns 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 test from some of it's predecessors like Diehard and bros, but it also made some decisions on how to interpret the output. So, turns statisticians like to create "null-hypothesis" for some reason (you can tell I'm not one), then test them.  So that results in the 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 a the same time and 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

Monday, March 24, 2014

Post # 1

Hey everyone, this is the first post.  In our blog, we'll focus on novel tasks in Microsoft SharePoint and ASP.NET development that we think are pretty cool.