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

9

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

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

4

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

4

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.

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

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

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

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

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.

1

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

1

I can't give an example illustrating why leakage must be non-negligible for the utility of the mechanism, but I can give a proof of why leakage must be non-negligible for the utility of the mechanism. Let $\;\; U \: = \: \left\{\langle D,D'\rangle : D,D' \text{ differ in one element}\right\} \;\;\;$. By the triangle inequality, for all $D$ and $D'$, for ...

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.

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