# Tag Info

12

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

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

9

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

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

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

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

5

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.

5

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

5

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

4

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

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

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

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

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

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

2

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.

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

1

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

1

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

1

As $n$ events cant be represented as $2^n$ number, we can have a function $F(n)$, which gives 0 if NIST suite for given bit sequence represented by $n$ fails to satisfy and gives 1 if n looks like random. Question is what is sum $F(n)$ over all $n$? A statistical randomness test generally (and in the case of the NIST suite) returns a $p$-value ...

1

NIST has a lot of information on testing random number generators at http://csrc.nist.gov/groups/ST/toolkit/rng/index.html that might be of value to you.

1

I am not a complexity theorist, but I believe this fits the requirements. The best known algorithms for factoring are superpolynomial time algorithm so they are not polynomial time. An example of something th superpolynomial time algorithm could distinguish are outputs from the Blum-Blum-Shub PRNG.

1

If the sequences are supposed to be perfectly random, you may want to take a look at e.g. the NIST statistical test suite. However, you should be aware that statistical tests don't prove or really even estimate entropy. They are just a sanity check that tells you whether the numbers look random. Non cryptographic PRNGs that are completely predictable can ...

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