Statistical signifiance of uniform random generator I'm writing an implementation of Fortuna, and have implemented the core PRNG / DRBG which should produce a uniform distribution.
I've run a variety of statistical random test suites over the output (Dieharder, TestU01, 
RaBiGeTe, PractRand) and there were enough border-line results that I'm slightly worried something is wrong.
My question is: statisticly, should I be worried by the results below? Are they acceptable from a statistical point of view if I'm expecting a uniform distribution?
The following tests have p less than 0.001 or more than 0.999:


*

*PractRand test [Low1/8]FPF-14+6/16:(3,14-0): p = 0.99929 (or 1-7.1e-4 on the raw results) (link)

*RaBiGeTe_MT test Short blk 4_16: p = 0.0008 (link)

*RaBiGeTe_MT test DFT 1: p = 0.0005 (link)

*Test U01 test LongestHeadRun: p = 0.00075 (results link, test definition - p127)


For reference, PractRand produced 267 results, RaBiGeTe ~350, and TestU01 160.
Link to blog post with full details of random tests
For those who may not know, Fortuna defines its CPRNG as AES in counter mode. That is, the output is produced by encrypting a 16 byte counter (incremented after every encryption operation). 
I'm concerned because given the author of Fortuna (Schneier) and use of the most popular block cypher in existence (AES), I was expecting all the test to pass with flying colours.
And all the test suites picked something up, not just one.
(And, being primarily a coder, I don't fully understand what the very small / large p results in these tests actually mean).
 A: I'm not too familiar with RaBiGeTe_MT or TestU01, but all of your PractRand results are "normal". I will make the observation that you have not let PractRand run anywhere near long enough to uncover any systemic issues in a 128-bit RNG. Even a 128-bit MCG (which has well known statistical flaws) passes the default 32 TB of PractRand testing. Such generators are simply too big to fail. At the other extreme a generator with 32 bits of state would be too small to pass, because it could generate no more than 16 GB of data before starting to repeat. So to answer your questions in the context of PractRand:
statisticly, should I be worried by the results below?
No, there is nothing to worry about as PractRand says all of your results are "normal" (ie. indistinguishable from random), but you would also need to let the testing run significantly longer to uncover systemic issues. I would expect a 128-bit CSPRNG to pass 32 TB of PractRand testing with flying colours, and a failure would most likely indicate either a "bad" seed value or an implementation issue.
Are they acceptable from a statistical point of view if I'm expecting a uniform distribution?
You should not be expecting a uniform distribution, because truly random data does not have a uniform distribution. Any generator which does have a uniform distribution will fail statistical tests long before reaching it's full period because it will be obvious that it could not be a random distribution. For a uniform 128-bit generator, each 128-bit value can only be generated once per period, whereas with truly random data we would start expecting to see some duplicate values once enough numbers have been generated. Imagine you had a die where you had to roll each of the six numbers before you saw a repeat, or a coin that could not have multiple heads or tails in a row. You would not believe that it was truly random unless you saw some duplicates within a reasonable time frame.
The way that this is generally handled with RNGs is to output a number that is smaller than the state size. It is typical to see a 64-bit generator outputting 32-bit numbers, and see a 32-bit generator outputting 16-bit numbers. This solves the issue of too much uniformity to a degree, because with an n-bit uniform generator, you will see each value exactly to 2 ^ (n/2) times per period. Once you get far enough into the generator's period though, there comes a point where you would expect to see a particular value more than 2 ^ (n/2) times, and it is past this point where statistical tests will start to fail. I understand this is not an issue with Fortuna as reseeding takes place long before you get far enough into the underlying PRNG's period.
