Hot answers tagged

20

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


18

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


15

We simply strive for crypto that's as close as possible to ideal. Indistinguishably is the strongest property we can demand from a PRNG/streamcipher. It's hard to predict which non ideal properties will lead to problems at some point in the future. For example the non ideal properties that lead to padding oracles, BEAST, CRIME or the RC4 biases were known ...


14

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


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

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


12

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


10

Many stream ciphers work by transforming a short key (and optionally a nonce) into a long key-stream that's xor-ed into the plaintext to produce the ciphertext, which is exactly the construction you're proposing. Wikipedia calls these Synchronous stream ciphers. Most popular stream ciphers fall into this category, including block ciphers operated in CTR or ...


9

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

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


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

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


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

Your idea of using a hash function to expand your seed is a reasonable one. If you want a standardized method of doing so, try HKDF from RFC 5869. Specifically, I'd suggest something like the following: PRK = HKDF-Extract("custom salt value", P) output[i] = HKDF-Expand(PRK, string(i), 256/8) where "custom salt value" is a unique string identifying your ...


7

One of the key properties we want out of PRNGs is that they produce results that follow a desired probability distribution. Nearly all of the time we want our PRNGs to produce data with uniform distribution—all of the possible output values should have equal probability. So let's assume that we are given a seq sequence whose values are samples drawn from a ...


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

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

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

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

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

X9.31-based PRNGs as used in current practice (including in the Botan library) tend to be extensions of the generator of ANSI X9.31-1998 appendix A.2.4 (which designated purpose is as a submodule of a prime generator for RSA keys). This really is the PRNG of ANSI X9.17-1985 Appendix C (which designated purpose is generating DES keys), also described in ...


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


5

A PRNG has an internal finite state. The value of that state determines all subsequent outputs; that's the point of the PRNG being a deterministic engine. Whenever the PRNG produces a new output element, its internal state evolves into a new value. Since the internal state is finite in size, it is a mathematical certainty that the PRNG, at some points, ...


5

Answering your question If an attacker have access to a copy of my users database table containing each salt and the related salted password, I can't understand how a CSPRNG would be more secure than a SHA12 hashed UUID. Can someone elaborate? I’m not sure if you only have read the question “Cryptographically Secure Pseudo-Random Number Generator in Qt/...


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

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


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

Using a stream cipher for mass generation of "random" bytes is a fairly good solution, however the risk is loosing Forward Secrecy at some point. The trick then is re-keying the cipher often enough, and having a good source of random data with which to rekey your cipher. See Fortuna.



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