8
votes
Randomness Testing
There is no such thing as randomness of a sequence (or of a permutation, or of a string, etc.). There is only randomness of a process for choosing sequences (permutations, strings, etc.), which is ...
- 49.5k
8
votes
Statistical Tests for Pseudorandom Functions
Nobody uses generic statistical tests to verify correctness of encryption algorithms.
To verify correctness of an implementation, engineers write proofs of correctness for their code, tr running it ...
- 49.5k
7
votes
Accepted
Estimated entropy per bit given P-value of a statistical test, and number of bits tested?
Firstly, the way (if at all) the "$P$-value" depends on $H$ depends (of course) on the statistical test that is being used. For each test, the result will be different and I cannot really give a ...
- 1,886
7
votes
Accepted
Is there are a metric based on collisions to compare bad hash functions?
There are a few standard quantities related to families of hash functions $H_k\colon \{0,1\}^m \to \{0,1\}^h$ for a uniform random key $k$. You might call them metrics. They came to prominence in ...
- 49.5k
7
votes
Which test suit is better to say if PRNG is CSPRNG:TestU01 or NIST?
Please don't.
TestU01 or NIST?
Neither. Trust what they say on the xoshiro256+ website. A CSPRNG is not defined by it's speed. It's defined by security against ...
- 15.7k
6
votes
Shannon confusion and diffusion concept
I find the terms "confusion" and "diffusion" to be slightly nebulous and can lead to over-simplifications.
Confusion
For example, saying that "substitution" is responsible for "confusion" is not ...
- 19.9k
5
votes
Tests to distinguish between PRNG and a CSPRNG
What are the tests which a regular PRNG would fail but a CSPRNG would succeed?
The goal of a PRNG, and the duty of a CSPRNG, is to have an output that can't be distinguished from true randomness (...
- 146k
5
votes
Accepted
Is it possible to test 15-bit PRNG with the library TestU01?
It can be taken groups of 32 samples of 15 bits, and turned each into 15 samples of 32 bits, either by transposition, or concatenation then splitting.
The best of the two method depends on the nature ...
- 146k
5
votes
Accepted
Quality test for an hardware source of randomness
NIST has a statistical test suite for testing (pseudo) random number generators. There are a number of other suites as well, such as Diehard, Dieharder, and TestU01.
But all these tests can do is ...
- 14.7k
5
votes
How to compute the dataset size required by dieharder tests?
I'll be so bold as to say that no one knows for sure how much data you really need. There is no guidance on the homepage, the manpage and this thread from Duke is equally unspecific. Anecdotal ...
- 15.7k
4
votes
How can I calculate non-linearity of an s-box element wise?
I'm not sure if I fully understand your question.
"tell me how to trasform the s-box which is in binary form into decimal form?": Changing numbers between binary and hexadecimal (or decimal,...
- 136
4
votes
Is it correct to concatenate (pseudo-)random byte values before testing them with the NIST suite or tools like dieharder?
Thousands of bytes isn't nearly enough samples for any powerful statistical test. The fewer samples you have the less sensitive a given test can be.
If you concatenate statistically independent ...
- 3,333
4
votes
Is it correct to concatenate (pseudo-)random byte values before testing them with the NIST suite or tools like dieharder?
Is it valid to just concatenate the thousands of 4-byte values so that I end up with one very long byte (n * 1000 * 4 byte) stream which I then feed into these tools?
Is it correct that it doesn't ...
- 146k
4
votes
Accepted
How many $k$-bit words of a random bitstring are we expected to extract before all $2^k$ possible words occur?
This known as the coupon collector's problem, with the number of coupons replaced by $2^k$ and $k$ is the number of independent bits drawn ($k=4$ in the question's example).
It's expected $(k\log(2)+\...
- 146k
3
votes
Accepted
Interpretation of certain results of NIST Test Suite
Randomness is pesky, and can wax and wane between samples. That's why there is no one specific categorical test that can validate an IID sequence. You need to statistically combine several (perhaps ...
- 15.7k
3
votes
How to make a hypothesis test for a simple statistical test for a certain RNG?
The number of one bits in a sequence of iid Bernoulli trials won't be normal: it will be binomial. But you have the right intuition that, as the number of bits grows, the binomial distribution ...
- 49.5k
3
votes
Golomb's Randomness postulates
They make sense as a starting point, for pseudorandomness.
R1. This is a strict balancedness condition, the difference is 1, in case $N$ is odd and zero is impossible.
R2. If you have an i.i.d. and ...
- 23.7k
3
votes
Interpretation of (NIST) Non Overlapping Template Matching Test
First, Fisher's method is a way to combine several independent statistical tests with known distributions under the null hypothesis into a single statistical test with a known distribution under the ...
- 49.5k
3
votes
Why does the NIST Runs Test include a Frequency Test?
The Monobit test checks the frequency of 0 and 1 over the whole sequence tested. The Frequency test does that on $M$ sub-blocks, ...
- 146k
3
votes
Accepted
Frequency Monobits Test
Since the test uses $X_k=\pm 1$ as its symbols, it is statistically based on the idea of a simple random walk with unknown bias (if $p=1/2$ then the bias is zero).
By the Central Limit Theorem, for an ...
- 23.7k
3
votes
Accepted
Walsh-Hadamard transform in randomness testing
You need to read about WHT. It is just a fourier transform obtained for $\pm 1$ valued sequences. A fourier transform is usually normalized in different ways. Some authors like to divide by $2^n$ (...
- 23.7k
3
votes
Use of PRNG's vulnerability for attacking a cryptographic system
a PRNG which fails some of NIST tests (FFT, ApproximateEntropy and Serial)
Assuming other tests pass, that fact taken in isolation has no practical consequence for most applications, which really are ...
- 146k
3
votes
Accepted
Statistical differences between ciphertexts generated by AES in ECB vs CBC mode?
I believe if you impose the restriction that there are no duplicate blocks, then the answer should be: no, you can't distinguish between them. If you were able to do so then I believe that would lead ...
- 880
2
votes
Accepted
NIST random test suite choosing bitstream length and count
Look for the document "NIST Randomness Testing SP800-22b.pdf" (or more recent updates if available) in the NIST website.
My guess is that your sequences are way too short (32 bits long) and no kind ...
- 23.7k
2
votes
Accepted
Explanation of the EPC Gen2 randomness standard's first rule
All is revealed in the last paragraph of that section, repeated below:-
A cryptographic suite defines RNG requirements and randomness criteria for cryptographic operations. These requirements and ...
- 15.7k
2
votes
Is it possible to test 15-bit PRNG with the library TestU01?
This one?
Generators of this form are called linear congruential generators. You can test them but by inspection you can see that it will fail a serious randomness test quite spectacularly. 32 bit ...
- 15.7k
2
votes
How to actually compute the statistical distance?
Prove your method correct.
Factor your code into a nondeterministic uniform bit sampler and deterministic logic.
You can use the full suite of standard software testing techniques for to test ...
- 49.5k
2
votes
How can the 'randomness' of a finite sample of binary keys from a finite key space be estimated?
There are a few things to notice here:
any tested sequence is finite by definition, we cannot run tests on infinite sequences;
the size of the output is interesting, but if it is sufficiently random ...
- 94.5k
2
votes
Sequence test for an image cipher
It's simple. Lena is 512 x 512 pixels with a bit depth of 8. So you simply export the raw image to a file that will be exactly 262,144 bytes long. It's critical that you export or save the image as ...
- 15.7k
2
votes
How to compute the dataset size required by dieharder tests?
In order to get a precise, hopefully definitive answer we can count the number of rewinds for each test. I generated a 1KiB file that was used as an input.
After some source code investigation, ...
- 453
Only top scored, non community-wiki answers of a minimum length are eligible