# Tag Info

14

We currently have no way to prove that a specific PRNG is cryptographically secure. In fact, we currently cannot prove that there exists a cryptographically secure PRNG (!). If you scale back the requirement from "mathematical proof" to "something we generally accept", there's still no way for an automated test to verify that a specific output is ...

8

I think that you missed a pivotal point in the concept, which is the small blocks that are used to compose a secure PRF (or PRP), i.e. when you permute one bit, you actually change the value of the small block of that bit, i.e. the whole small-block is effected and thus prepared to be confused in the next round, this way you will reach a confusion of the ...

8

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 on known-answer tests, confirm round-trips on randomized inputs, etc. None of this involves statistical tests, since the point is to implement a specific ...

7

Knowledgeable crypto practitioners do not calculate $\pi$ using a Monte Carlo method to determine if a series of numbers are random. The test alluded to in the question is a general-purpose¹ randomness test for random number generators with output a real number expected to be uniform of the range $[0\dots1[$. The test consists of drawing pairs $(x,y)$, and ...

7

The NIST special publication 800-90 series (NIST SP 800-90A, NIST SP 800-90B and NIST SP 800-90C) contain a set of PRNGs and tests for cryptographically secure PRNGs. Unfortunatelly, right now (13/10/2013) the NIST website is down, however you can find copies of the NIST statistical test suite via Google at sites like this one.

7

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 Carter and Wegman's research program on universal hash families (paywall-free), though their first use in cryptography for one-time authenticators, by Gilbert, ...

7

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 intrinsically not something you can test by looking at its outputs. What you can do is write a decision procedure that will, with some probability, return a ...

6

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; your question is "what plaintext should I use? If I pick a random plaintext, then the test results might reflect the randomness of the plaintext, and no ...

6

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 meaningful general discussion here because different tests consider completely different aspects of the stochastic process of output bits. In general, indeed, the $... 5 I'm not certain but aren't there ways to evaluate a given sequence as random with some given satisfied error? Given n bits, how many "truly random" sequences/numbers can be constructed? If you define "truly random" as meaning prior to generating the sequence, that each bit has an independent 50% chance of being 0 or 1, then all$2^n$bit strings are equally ... 5 Q1: Why are these tests stroked out? These tests are stroked out on pages 57-58 of the current FIPS 140-2 because they are no longer part of the current FIPS 140-2 standard, since Change Notice 2 of 2002 December third, where these pages belong. My guess for the rationale of removing these tests is that It was realized that the very principle of ... 5 How to prove the security of the PRNG? My best advice would be to start with a statistical test suite like the one NIST describes in "A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications" (PDF). It’s a battery of statistical tests to detect non-randomness in binary sequences constructed using random number ... 5 The best that can be done for a PRNG is to reduce the problem of distinguishing its outputs from random (or predicting them) to some believed-to-be-hard problem. A PRNG based on AES in counter mode can be proven to be as secure as AES in some sense. Similarly a PRNG based on a HMAC-SHA256 can be shown to be as secure as HMAC-SHA256. There are PRNGs based ... 5 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 necessarily correct: "Substitution" is actually just a function application to the state; The implementation often utilizes a memoized function, but you can ... 5 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 disprove the claim that your generator is random; they cannot prove it. So you really need, in addition, an independent argument for why your generator's output ... 5 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 of the test, and TestU01 has several tests (as test suites do). If in doubt, use both methods. Should any valid test consistently fail more than predicted by ... 4 I searched the web, and finally (I think) I got: In page 47, 48 of this thesis, it is mentioned that - To detect a bias of$p(1+q)$(where$p$is the probability for an Uniform Random event), we need roughly$\dfrac{1}{pq^2}$samples. 4 Like fkraiem's answer points out, passing a statistical test does not prove a PRNG is cryptographically random, or even statistically random with regard to other tests. In the case of RC4 the biases are most prominent in the beginning of the keystream. To borrow a useful illustration from Vanhoef and Piessens' "All Your Biases Belong To Us: Breaking RC4 in ... 4 Statistical tests have no value to evaluate randomness in a cryptographic sense, because an attacker is not required to use any specific test. The fact that a stream passes some set of predetermined tests tells you nothing about how it fares against tests which are not in the set. 4 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, if you would really want to) is not different for numbers that are used with S-boxes compared to any other numbers. "Also how i calculate the non ... 4 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 matter for the tests how long the individual values (4-byte) were before? Yes for both. The fact that others may have obtained (and removed) randomness from the ... 4 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 uniform samples then tests should pass the resulting byte stream. It doesn't matter how the bits are rearranged as long as order doesn't depend on the value of those ... 4 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 (with a significant advantage, by a program that can actually be run). Thus it's a failure of a PRNG, and a capital offense for a CSPRNG, if it does not pass all ... 3 I've read that a good RNG will have a range of p-values that follows a uniform distribution; values between 0 and 1 should happen with about equal probability. Why should that be so? It comes straight from the definition of p-values. The p-value indicates the probability you'd get at least that skewed a result if the source is truly random. So you expect a ... 3 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 can't be compressed much further, and incompressibility is one of the definitions of random. It has however, some non random bytes such as control structures ... 3 PRNGs are a difficult and hot topic. Some tests can be found here: What tests can I do to ensure my PRNG is working correctly? But they do not tell you (or others) if your PRNG is really secure. A PRNG must be build in a way, that a third party is not able to "calculate" former or upcoming PRNG output based on some random data from the PRNG. 3 The short answer is: given$n$bits,$2^n$“truly random”$n$-bit sequences can be constructed — all of them. Randomness is not a property of a number, nor a property of a sequence of numbers. It's a property of the method that was used to generate that number or sequence. Or, as fgrieu puts it What matters to entropy is what the sequence could be, not ... 3 Typically, the output of format-preserving encryption is easily distinguishable from a random bitstream, precisely because the ciphertexts conform to some non-random format. Thus, you cannot use standard statistical tests on them, at least not directly. If the format of your FPE scheme is flexible enough, you may be able to test some aspects of it by ... 3 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 unbiased binary source, the run length distribution is geometric, which in a finite length segment should follow the profile given in R2, due to the law of ... 3 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 converges to a normal distribution—specifically, for fixed$p$, as$n \to \infty\$, $$\operatorname{Binom}(n, p) \to \mathcal N\bigl(np, np(1 - p)\bigr),$$ or, more ...

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