39

1 - How feasible is it that the chip's manufacturer can predict the output of this PRNG when it passed tests from the people applying the use of this RdRand instruction in kernels? A strong stream cipher's output is random and unpredictable to anyone not knowing the key. See where this is heading? Just because something looks random doesn't mean it's random....


33

The ISO/IEC 9899:1990 edition of the C standard contains: EXAMPLE     The following functions define a portable implementation of rand and srand. static unsigned long int next = 1; int rand(void) // RAND_MAX assumed to be 32767 { next = next * 1103515245 + 12345; return (unsigned int)(next/65536) % 32768; } void srand(unsigned int ...


30

A Pseudo Random Function is a function that is indistinguishable from a function selected at random from the set of all functions with the same domain and value set. A Pseudo Random Permutation is, similarly, a bijective function that is indistinguishable from a bijective function selected at random from the set of all bijective functions over the same ...


29

What are the criteria that make an RNG cryptographically secure? In short, a DRBG [deterministic random bit generator] is formally considered computationally secure if a computationally-limited attacker has no advantage in distinguishing it from a truly random source. What does this mean? Given a DRBG F and a truly random oracle G, let A be a probabilistic ...


21

The other answers provide very good lists of reasons not to use Twitter as an entropy source. What follows is the flip side of your question:- Why would you want to? Tweets are typically read on tablets, PCs and phones. All of those have access to hardware entropy sources that can produce oodles of truly random bits for seeding anything. The zeitgeist is ...


20

What you are suggesting is not a good idea for a general purpose random number generator. It could be meaningful for very specific use cases if you need a random number generator whose output can be verified independently by a third party. Even in those cases there are other sources of entropy which are potentially more suitable. The oldest mention of this ...


17

I have the first 40 numbers of the sequence. Is there a way to recover the seed or find the next 460 numbers in the sequence? The first thing to know is that Python's random module uses Mersenne Twister as the PRNG. That is not a cryptographically secure RNG, in fact it is easy to recover the state as long as you have enough samples. 40 numbers of the ...


15

The answer is given by Henrick is good, but I try to give a explanation with more details in security area. When you think about PRF (Pseudo Random Function), you will think that there are three elements with PRF, which is $K, X, Y$. $K$ means the key, $X$ means the message and $Y$ means the output. PRF is a function, when you give this function $K$ and $X$...


15

Have you heard of the strange story of Dual_EC_DRBG? A random number generator suggested and endorsed by the government that exhibits some very suspicious properties. http://www.schneier.com/blog/archives/2007/11/the_strange_sto.html From that article: This is how it works: There are a bunch of constants -- fixed numbers -- in the standard used to ...


15

How are you going to decide which tweet to use? Randomly? This quickly leads to a chicken / egg problem. What if the chosen tweet is one word? That would not add a lot of entropy. What if twitter is unavailable? Are you just stopping your service that relies on the entropy or are you going to continue regardless? How are you going to keep the chosen tweet ...


14

Notations: $v=u\bmod m$ means $m$ divides $u-v$ and $0\le v<m$, including if $u<0$. All variables are non-negative integers (except for the above). $a=214013$, $b=2531011$ are the LCG parameters. $X_n$ is the 31-bit state with $X_{n+1}=(a\cdot X_n+b)\bmod 2^{31}$. $R_n=\lfloor X_n/2^{16}\rfloor$ is the 15-bit output. $S_n=X_n-2^{16}\cdot R_n$ is the ...


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


14

I tried to use mostly non-jargon beyond what the question already mentioned, to keep the answer understandable. What are the criteria that make an RNG cryptographically secure? From en.wikipedia.org/wiki/CSPRNG: there may be no algorithm that predicts the next output with anything better than guessing. If you can say "50.0001% chance the next bit is ...


14

On modern CPUs, a fast Cryptographically Secure Pseudo-Random Number Generator runs sizably faster than one cycle per byte. We are talking >40Gbit/s. See numbers there. Top contenders are AES-CTR assisted by special instructions, and ARX ciphers like ChaCha. When using dedicated hardware, the true limit is moving around the generated random bits. We can ...


13

There is a black-box separation between one-way functions and collision resistant hash functions. This was proven at Eurocrypt 1998 by Dan Simon, in the paper entitled Finding collisions on a one-way street: Can secure hash functions be based on general assumptions?. Of course, this doesn't mean that it's not possible using non-black-box reductions, but no ...


12

1 - How feasible is it that the chip's manufacturer can predict the output of this PRNG when it passed tests from the people applying the use of this RdRand instruction in kernels? As nightcracker correctly stated, any strong cryptographic PRNG will produce a stream of numbers that pass statistical tests. However, the manufacturer has some constraints: ...


12

The problem with questions that ask for “the fastest” is, that such questions always raise the counter-question: compared to what exactly? Also, your question doesn’t specify if you mean cryptographically secure physical random number generators, or any physical random number generator. Anyway… 400 Mbps doesn’t really come anywhere near the word “fastest”. ...


11

I am the designer of the random number generator that is behind the Intel RdRand instruction. How feasible is it that the chip's manufacturer can predict the output of this PRNG when it passed tests from the people applying the use of this RdRand instruction in kernels? It isn't. We cannot. It passes the tests because it is a cryptographically ...


11

...wouldn't key still get repeated every few hours or so - i.e. you come to the end of the PRG(K)... This is where you are mistaken. Modern cryptographic PRGs simply do no repeat within any conceivable time frame. That is, starting from a seed, a well-constructed PRG (and this is true even when they are not so well constructed, like RC4) will simply never "...


11

A TRNG is never used instead of a CSPRNG. They serve different purposes. A TRNG is used to seed a CSPRNG. A CSPRNG alone isn't enough to generate random data since it's reproducible. A hardware entropy source alone isn't enough to generate random data because all entropy sources have biases. For any purpose that's related to security or cryptography, a ...


11

Python uses a Mersenne twister PRNG, and though it is not secure it does have a large state. You have here 40 numbers, the first one gives you 1 bit and each subsequent number has an extra bit for a total of 800 bits. This is significantly smaller then the internal state of the MT-19937. This page explains how to find the internal state of python's PRNG: ...


10

Multi-prime RSA (also known as RSA-MP) is supported by PKCS#1v2. This standard supports a public key $(n,e)$ where the modulus $n$ is the product of $u≥2$ distinct odd primes: $n=\prod_{i=1}^u{r_i}$, with $1<e<n$ and $\gcd(r_i-1,e)=1$ (implying $e$ odd). The private exponent $d$ is such that $1<d<n$, and $e⋅d≡1\pmod{\operatorname{lcm}_{i=1}^u(r_i-...


10

Please bear in mind that this information is all secondhand. I have not looked closely at the original drafts of Hash DRBG (although you might find a draft that's early enough if you peruse the FOIA results in [1]). However, during conversations with folks at NIST I was told that there were certain weaknesses in early drafts of Hash DRBG that were very ...


10

The seed of a pseudorandom number generator — whether cryptographically secure of not — is the initial input that defines the pseudorandom sequence of outputs generated from it. It's not really a term that's specific to cryptography, except insofar as there's a considerable amount of overlap between pseudorandom number generation and ...


10

No test is needed to stay clear from srand for cryptographic purposes, including when a pseudo-random generator is thought. The definition of srand is enough to disqualify it. That definition states: void srand(unsigned int seed); The srand function uses the argument as a seed for a new sequence of pseudo-random numbers to be returned by subsequent ...


10

Actually, this case is a misapplied test. rand() is defined to generate numbers between 0 and RAND_MAX, which is a compiler-defined constant which is positive as an int. That means that the range of possible results $[0..RAND\_MAX]$ is strictly smaller than the range of results you are writing $[0..UINT\_MAX]$. For example, if you are on a machine with 32 ...


9

All modern microprocessor Smart Card ICs contain a physical True RNG, generally followed by conditioning using a hardware de-biaser (such as Van Neumann's) or/and deterministic Pseudo-RNG of some kind that make the TRNG output more indistinguishable from random. Independently, a Smart Card could contain a (Cryptographically Secure) Pseudo-RNG. The later is ...


9

$s_i = s_{i-1}\cdot(N + 1) + 1 = s_{i-1} \cdot N + s_{i-1} + 1$ but $s_{i-1} \cdot N = 0 \pmod N$, so $s_i = s_{i-1} + 1 \pmod N$ which means you can discover the next number to be generated just looking to the current one...


9

Trying to distinguish a synchronous stream cipher from a CSPRNG seems to me a bit like trying to distinguish ice from frozen water. Any secure stream cipher is a CSPRNG, and any CSPRNG can be used as a stream cipher. Insofar as there is any difference, it mostly comes down to intended purpose and API design. A typical CSPRNG API might take an initial seed ...


9

Yes you can. Suppose that you have a pseudorandom generator that, on some seed $s$, outputs $n$ pseudorandom bits, where $n$ is even. Then on a uniformly random input seed $s$, prg$(s) = r$ can be written $r_1 + 2^{n/2}r_2$, with $(r_1,r_2) \in (\{0,1\}^{n/2})^2$. I claim that both $r_1$ and $r_2$ are computationally indistinguishable from uniformly random ...


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