Hot answers tagged

13

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


13

According to the paper On Lempel-Ziv Complexity of Sequences by Doganaksoy and Gologlu, A test based on Lempel-Ziv complexity was used in the NIST test suite, to test the randomness of sequences. However the test had some weaknesses. First of all, the test could only be applied to data of a specified length: $10^6$ bits. Moreover, the test used empirical ...


10

Prove resistance to differential cryptanalysis. For example, this presentation: Provable security against Impossible Differential Cryptanalysis. Or this paper: ProvableSecurity Against a Differential Attack (1995) Prove resistance to linear cryptanalysis. For example: On Measuring Resistance to Linear Cryptanalysis Run a bunch of statical tests against ...


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

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


6

A quite common way to actually prove something is building a system on already known components, and then proving the security of the composed system, given the security of the components. Most often the paper has a theorem like If the function F has property Y, then this new function G has property X. The proof then shows that if someone can attack ...


6

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


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

The most important take-away is that if you are asking this question, you are almost certainly not qualified to design a secure cryptographic primitive. Sounds harsh, but I mean it in all earnestness. You wouldn't trust someone who hadn't been to medical school to do surgery on you. Similarly, we wouldn't trust someone who doesn't already know the ...


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

Well, from your previous questions, I'm assuming that your writing a utility to brute-force decrypt a password protected file (encrypted with a certain encryption utility), and you're looking for a way to determine whether your trial decryption is plausible. Normally, when an attacker attempts to decrypt something, he has some idea about what it is (why ...


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


4

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


4

The usual assumption is that the attacker knows a full plaintext block; that's what the EFF DES-cracking machine uses. That machine knows exactly 8 consecutive plaintext bytes and the corresponding ciphertext block; it stops when it finds a matching key. Since there are 256 possible DES keys, and 264 possible 8-byte blocks, chances are high that there is ...


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

In addition, NIST Statistical Tests and Diehard Battery of Tests of Randomness are good tests.Some tests proposed here and here for stream ciphers. Passing these tests is essential but does not enough. For more information see introduction of first link. Also Provable security may be useful.


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

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.


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

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


3

Failing ENT output is a little like the length of string; elusive. So I offer an anti-answer. The following is the output from running the code below and shows a random sequence passing ENT. You'll have to use some judement to weigh output diverging from this reference test. The code executed for 1 MB, 10MB, 100MB, 1GB and 2GB random files using a decent ...


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

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


2

The rationale for no longer mandating these tests include: These tests are generally not useful against most FIPS 140-2 approved random number generators. These tests can be useful against some kind of entropy sources. These tests give frequent false positives every few thousandth block of truely random stream will fail the test. Some entropy sources are ...


2

As mentioned, most proofs of PRNG security are really proofs of a protocol that uses some underlying construct. The proofs say, "If the construct can't be broken, then the protocol that uses it can't be broken any easier than that." That makes all these proofs subject to the assumption that the underlying construct (like factoring, quadratic residuosity, ...


2

Regarding the test of unicity You could just script the test in Python (or any other language, really). The language in which you already implemented your cipher might be a good choice otherwise. Then, given the size you are talking about (256 possibilities of 16bits = 4Ko), you can basically just generate all the results in a 256-array, and check the ...


2

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


2

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.


2

My own algorithm validation for block ciphers consists of the combination of the AESAVS KAT and MCT tests from the NIST CAVP, plus the NESSIE test vector sets, plus an additional MCT of 400 key changes and 10000 inner loops (like the TDES tests). The probability of a block cipher passing all these tests but failing in production is astronomically low. Once ...



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