Skip to main content
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 ...
Squeamish Ossifrage's user avatar
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 ...
Squeamish Ossifrage's user avatar
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 ...
Squeamish Ossifrage's user avatar
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 ...
Aleph's user avatar
  • 1,876
7 votes

Plaintext for randomness evaluation of cryptographic algorithms?

If I understand you properly, you are going to test some cryptographical primitives by running them on some plaintext, and then taking the resulting ciphertext and giving it to a randomness test suite;...
poncho's user avatar
  • 148k
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 ...
Paul Uszak's user avatar
  • 15.6k
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 ...
Ella Rose's user avatar
  • 19.7k
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 ...
Luis Casillas's user avatar
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 ...
fgrieu's user avatar
  • 142k
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 (...
fgrieu's user avatar
  • 142k
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 ...
Paul Uszak's user avatar
  • 15.6k
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 ...
Future Security's user avatar
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 ...
fgrieu's user avatar
  • 142k
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,...
Bla Blaat's user avatar
  • 136
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)+\...
fgrieu's user avatar
  • 142k
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 ...
Paul Uszak's user avatar
  • 15.6k
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 ...
Squeamish Ossifrage's user avatar
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 ...
kodlu's user avatar
  • 22.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 ...
Squeamish Ossifrage's user avatar
3 votes
Accepted

What problems with "random" data would cause this result from Ent?

I've seen this before in the true random number generators I've been working on. Look at the following test. I've ent'd two jpegs, one 10 times the size of the other. A jpg is highly compressed so ...
Paul Uszak's user avatar
  • 15.6k
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, ...
fgrieu's user avatar
  • 142k
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 ...
kodlu's user avatar
  • 22.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$ (...
kodlu's user avatar
  • 22.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 ...
fgrieu's user avatar
  • 142k
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 ...
swineone's user avatar
  • 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 ...
kodlu's user avatar
  • 22.7k
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 ...
Paul Uszak's user avatar
  • 15.6k
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 ...
Paul Uszak's user avatar
  • 15.6k
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 ...
Paul Uszak's user avatar
  • 15.6k
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 ...
Squeamish Ossifrage's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible