# Tag Info

35

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

17

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

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

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

11

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

9

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

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

7

There is no such method. The only reliable way to "fix" a backdoored RNG is to mix its output with another, secure RNG. Specifically, let's consider a backdoor similar to that described by Becker et al. (2013), which essentially transforms the Intel TRNG into a deterministic PRNG using AES in OFB mode, with a 32-bit initial seed (occasionally reseeded) and ...

7

Both determinism and non-determinism are useful. The question is which one you use for which purpose. Determinism is generally useful for expanding a short secret to a long one. For example, you may keep a short random secret and use it to generate a long keystream that you can XOR against messages for encryption and decryption (such as described in the RFC ...

7

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

7

This allows for an easy distinguishing attack: Let $R\colon\;\{0,1\}^n\to\{0,1\}^m$ denote a pseudo-random generator, that is, if $x$ and $y$ are uniformly distributed random variables in $\{0,1\}^n$ resp. $\{0,1\}^m$, there is no polynomial-time algorithm that distinguishes $R(x)$ from $y$ with non-negligible probability. Let ...

7

I've read about the possibility of inverting the Mersenne Twister after 624 numbers of output. 624 matches the state size of my implementation of the Twister. Coincidence? If the generator only output 623 numbers, i.e. less than the state size, might inversion still be possible with really clever maths? Or is this mathematically and logically impossible? ...

6

Presuming this documentation is correct, the answer is no, these numbers are not cryptographically secure. The Random class uses a linear congruential formula with a 48 bit seed. For most purposes it is not enough even if you only require 48 bit security. Given a fairly low number of outputs from a LCG, it is possible to derive the seed, even if only a few ...

6

In the example you linked, the current time (specifically, a value representing the number of seconds elapsed since Jan 1, 1970 UTC) is used as the seed. If an attacker knows which year you generated your key, then that leaves only about 2^25 possible values for the seed --- and therefore only about 2^25 possible values for your key. At this point, he can ...

6

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

5

The modulus 77 leads to a short period.

5

Dedicated stream ciphers typically are, or at least can be, somewhat faster than constructions based on block ciphers. (If they weren't, there would be no point in using them, since a block cipher can do everything a dedicated stream cipher can.) What you gain in speed (and possibly code size), however, you lose in versatility: A block cipher (in CTR / ...

5

This answer has been updated a lot, again, after being accepted. I now base my analysis on simple functional equivalent source code to the deterministic PRNG used. The cryptosystem proposed works, in the sense that it allows decryption. The best cryptanalytic method there is to predict further output is enumerating the 64-bit key by brute force. That's in ...

5

The fundamental property of the Rabin-Miller primality test is that, if the value $N$ being tested is composite, then it will return "composite" at least 75% of the time. That is, if we define the function $RabinMiller( N, A )$ that runs the Rabin-Miller test against the number $N$, using $A$ as a witness, then for any composite $N$, $RabinMiller( N, A )$ ...

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

Before answering the actual question, I will offer some general advice. It is important to pay attention, both in class and to the textbook you are reading. If learning how to solve such exercises is a key goal of the course, such solutions have very probably been discussed at length in class. Moreover, your textbook also has proof examples, and in this ...

4

Contrary to what's stated in the question and its comments, extracting any $m\le n$ bits from the sequence of the states of an $n$-bit LFSR still result in a sequence with period $2^n-1$, assuming the state of the $n$-bit LFSR is not zero and its generating polynomial is primitive. Proof sketch: by a fundamental property of LFSR with primitive feedback ...

4

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

4

The classical way to generate a random permutation is the Fisher-Yates shuffle; it takes an underlying random number generator, and produces a random permutation. With just a bit of care, it can generate each permutation with equal probability (assuming the underlying random number generator outputs are independent and uniformly distributed). The only ...

4

Since this looks like homework, I'm not going to answer the question directly (and I hope others won't either), but I'll just give some hints: You're on a good direction. If you want to prove that $G'$ is a secure PRG, then your general approach (trying to show that a distinguisher for $G'$ implies a distinguisher for $G$) is a good strategy. Keep at it. ...

4

You are quite correct. A PRP in counter mode is, in fact, distinguishable from a random sequence if you approach the "birthday bound". We get around this by never generating that much output at once. With a 128 bit block cipher, an output of $2^{40}$ bytes (which is a lot of output) gives us a distinguishing advantage of about $2^{-56}$ (the probability ...

4

All quantities are non-negative integers. $X_n$ is the 31-bit state with $X_{n+1}=(a·X_n+b)\bmod 2^{31}$, $a=214013$, $b=2531011$. $R_n=\lfloor X_n/2^{16}\rfloor$ is the 15-bit output. $S_n=X_n-2^{16}·R_n$ is the hidden 16-bit portion of the state. Assume we have the first few outputs $R_0$, $R_1$.. and want to find $X_0$. We derive: ...

4

You already answered your own question: given the output from 2 calls to the rand() function and $2^{16}$ steps of computation, you can recover the internal state completely, simply by brute-forcing the parts of the state that you are not aware of. That is a break. You say it's "hardly a break", but that is too-narrow thinking. A break is a break; ...

4

I recommend against using RAND_pseudo_bytes(). OpenSSL's CPRNG does not provide better pseudo-random numbers than /dev/urandom but it is much harder to use right. It has a couple of known flaws, for example it doesn't handle fork() very well. The standard PRNG is not very well designed, too. The FIPS mode PRNG is a bit better, though. /dev/urandom (Linux, ...

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