# Tag Info

16

You don't want to use something like the Mersenne Twister for gambling. It is not cryptographically secure. Given a small amount of output, it is relatively straightforward to compute all future outputs. These algorithms are designed for things like Monte-Carlo simulations and things of that ilk. A better option is to select a 128-bit key at random and ...

14

"PRNG" means "Pseudorandom Number Generator" which means that a sequence of numbers (bits, bytes...) is produced from an algorithm which looks random, but is in fact deterministic (the sequence is generated from some unknown internal state), hence pseudorandom. Such pseudorandomness can be cryptographically secure, or not. It is cryptographically secure if ...

14

No, that would not be a true RNG, because these physics engines would just repeat the exact same calculation and thus repeat the whole sequence of random numbers - like a PRNG. The starting conditions are the seed of this PRNG. Dice are truly random in the real world. Well, are they? If we ignore quantum effects, we could measure all relevant values of the ...

13

A simple way to imagine the effect of the hash function is a truncation. A "good" hash function ought to behave like a random oracle. If your source has entropy $s$ bits, then this means that the source somehow assumes $2^s$ possible values. When processed with a random oracle with an $n$-bit output, you force the $2^s$ input values into $2^n$ possible ...

11

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

With a 64-bit known polynomial, future output of an LFSR can be trivially predicted from the last 64 bits output. Even if the 64-bit polynomial is unknown, the last 128 bits are enough, using the Berlekamp–Massey algorithm. Thus indeed, the LFSR-based PRNG in the hardware described in a section 27 of the document linked to in question, with some additional ...

8

Use any DRBG (deterministic random bit generator) in the NIST FIPS (the NIST 800-90 publication series). Except... don't use Dual EC DRBG, which has serious problems and is likely to be withdrawn. Use any DRBG in that standard other than Dual EC DRBG. Or, hash the seed with SHA256, then use AES256 in counter mode to generate output. Either of those will ...

8

The key difference between the two is that a random number generator used for cryptographic purposes has to stand up to an attacker. When you use random numbers in statistics, the main thing you care about is that the output sequence "looks random." What that means in practice is that it passes a bunch of statistical tests, showing that the distribution of ...

8

The key element in the definition of a PRG is the observer (aka distinguisher, algorithm, test, etc) that the PRG is supposed to fool. A statistical PRG fools a specific set of observers, whereas a cryptographic PRG fools all efficient observers. This strong definition is essential for cryptography:: The only assumption the designer should make about the ...

7

There is some relationship between the two notions, but a CSPRNG is designed to be computationally secure (secure against adversaries with bounded computation time), whereas a randomness extractor is required to be information-theoretically secure (unconditionally secure against adversaries with unbounded computation time). So, they're different primitives. ...

6

Quoting Poncho's answer: Well, the chief vulnerability is that if an attacker is given a large enough sample of Mersenne Twister output, he can then predict future (and past) outputs. This is a gross violation of the properties that a cryptographically secure random number generator is supposed to have (where you're supposed to not even be able to tell ...

6

It fails to be a cryptographically-strong PRNG because it is predictable: given some outputs, you can predict the next outputs. For instance, if you observe the outputs at offsets 0, 1, and 4096, you can predict what the output will be at offset 4097. What it's missing: it's not that it's missing some little tweak (just change line 7 to use addition ...

6

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

As Paŭlo Ebermann already mentioned in his comments, SHA3 can indeed be used as a pseudo-random number generator. The paper "Sponge-based pseudo-random number generators" talks about just that and it also describes a clean and efficient way to construct a re-seedable PRNG with a (Keccak) sponge function. What you'll get is a PRNG based on a cryptographic ...

5

Any result of a dice-throwing simulation in a physics engine is determined by its initial state prior to starting the simulation. Accordingly, the same initial state will always result in the same die surface coming up. To obtain a quantity of $N_{output}$ random output bits of randomness quality $Q_{output}$ from this simulation would require seeding with ...

5

A statistical PRNG is intended to not exhibit any statistical abnormalities. That is, an "adversary" who applies statistical analysis to the generated output should not be able to see a significant difference to the properties one expects from a uniformly distributed random source. For performance reasons, most statistical PRNGs are based on simple ...

5

For a random function you'd expect all outputs to be different if you generate fewer than $2^{n/2}$ blocks (birthday problem). Thus PRPs and PRFs are indistinguishable unless you observe about $2^{n/2}$, at which point you'd expect collisions using the PRF but not using the PRP. For a 128 bit cipher this is a lot of data, so we generally don't care about ...

5

We, for the most part, don't bother with elliptic curve-based pseudorandom generators. DUAL_EC_DRBG was shoehorned into a NIST standard that also included a block cipher generator, CTR_DRBG, and two hash-based ones—Hash_DRBG and HMAC_DRBG—that are actually used in the field. Number-theoretic generators, which include Blum-Blum-Shub, DUAL_EC_DRBG, and ...

4

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

4

It is a little unclear, how you transformed all your numbers... e.g. how did you interpret your decimal numbers "as binary" and "create a bitmap"? Then you look at the binary representation and guess what.... and they are just the numbers 0-9 in binary and added on an static number (no idea where that came from). Things to consider: Of course the numbers ...

4

First, on the difference between perfect security and semantic security. Both definitions concern confidentiality, so let us first define what confidentiality means. Note first that an adversary as some a priori knowledge of the message. We can capture that by e.g. having the adversary choose two messages and then flipping a fair coin to decide which one to ...

4

This is not secure. There is a distinguishing attack that involves about $2^{41}$ invocations of the interface. Define $f(x) = \text{MSB}_{80}(x) \oplus \text{LSB}_{80}(x)$. Consider applying the following operation, which I'll call "Leap": Call Read. Call the result $d$. Call Update $(0 \, || \, d)$ (i.e., call Update passing the 160-bit value ...

4

Yes. This paper on nist.gov gives five such PRNGs. Three of them are based on hash functions and two of them are based on block ciphers.

3

I'd rather add this as a comment. Alas, I lack the reputation for that. I'm a programmer, not a cryptography expert, but for some strange reason I like to lurk here regardless. The cryptography aspect aside (others are much better at that) I'd like to focus on the programming perspective, and why your reasoning is wrong. First of all: lurking here taught ...

3

You need a CSPRNG. And yes, a good CSPRNG should mix some new random data in the pool (reseed) periodically. Here are a few options: SecureRandom in Java RNGCryptoServiceProvider in .Net openssl_random_pseudo_bytes() or mcrypt_create_iv() in PHP RAND_bytes() from OpenSSL /dev/urandom on some Unix-like systems

3

Does anyone have a reliable source for this? Well, you are asking about the definition of a CSPRNG, and whether this second criteria is a necessary part. Well, it comes down the to exact definition of the term 'CSPRNG'. If we define a CSPRNG as something that generates output which is indistinguishable from random (your first criteria), then a ...

3

Some CSPRNGs accept a constant width seed. That means they could only be used as randomness extractors for that input size; no less, no more. For example, AES-128 CTR_DRBG CSPRNG (from 800-90A) would only accept 256 bits of seed for the key and initial vector in total. Further, if the input is not fully random (as you'd expect with a randomness extractor), ...

3

For randomness extraction, in some cases, you could use alternatives to hash functions. However, mostly hash (or hmac) is preferable, because hash and hmac are very good in extracting randomness. RFC 5869 describes HKDF, HMAC-based extract-and-expand key derivation function, with randomness extraction and expansion phase. NIST has made equivalent standard ...

3

The best answer is almost certainly to use a cryptographic hash. Your reason for avoiding a cryptographic hash makes no sense to me. Your problem does not explain the motivation for your question, but I suspect you've fallen prey to the XY problem (see also here). You haven't told us what you're ultimately trying to accomplish, but I suspect the right ...

3

If nothing else, it makes the output of the pool irrecoverable. One of Fortuna's goals is to make prior Fortuna outputs safe from a compromise (the discovery of all of Fortuna's current data by an adversary). If the pool continued on without a reset, with little or no entropy added before the compromise took place, the adversary could more easily calculate ...

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