# 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

I'll assume that the objective is to assert if the distribution of the $f'_i/n'$ is sufficiently similar with the distribution of the $f_i/n$ to support that a substitution cipher (including Caesar cipher) with the same permutation table and same frequency of plaintext characters could be used in both case. If $n \gg n'$, $f_i \gg 5$ and $f'... 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 By discarding values 252 to 255, you effectively avoid introducing any new bias; the generic method is expressed in many places, e.g. this article (page 3). To generate random values between$0$and$d-1$(inclusive) from a PRNG which produces bit, you do the following: Choose an integer$r$such that$2^r \geq d$. Obtain a$r$-bit word$x$from the PRNG. ... 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$...

6

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, ...

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

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

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

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 ...

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 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

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 ...

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 linearity of certain ...

4

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 ...

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

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

Well, for one, SHA-2 (either SHA-256 or SHA-512) doesn't have a 'keyspace'; that's because it doesn't have a key. SHA-2 takes an arbitrary bitstring is input, and generates an output; while there are limits on how long the bitstring can be, those limits are so huge ($2^{64}-1$ bits for SHA-256, $2^{128}-1$ bits for SHA-512), those limits can in practice be ...

3

On the first glance, this base 36 key stream looks at least as secure as RC4 itself - you are simply discarding some of the output, and not introducing any bias. Note that there are some general weaknesses with in the start of the output of RC4, which means that it is normally recommended to discard the first 1000 or so bytes after initialization (I have to ...

3

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 ...

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