# Tag Info

34

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

16

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

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

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

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

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

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

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

5

The modulus 77 leads to a short period.

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

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

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

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

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

The system you describe is not a one-time pad, it is a stream cipher, and a bad one for that. A one time pad has real (truly) random bits in the XOR pad, which are never reused for two messages. "Their" cipher has a pseudorandom pad (with non-crypto PRNG), and if I understand right, even the same one for each message. Even a real random one-time-pad is ...

4

Amongst others there are these things possibly going wrong: If people enter initial seeds, they usually do not use proper independent and identically distributes random variables, but code words, phrases, passwords etc. PBKDF2 is lot better way to construct the shared secret(s) from the input. RNG (random number generator) is not intended to do well as key ...

4

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

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

If you define pseudorandom as (computationally) indistinguishable from random, then your proposal breaks the pseudorandom property. Here is why, given all the previous bits, can you predict (with significantly better than 0.5 probability) what the next bit will be? The answer is yes, you can predict it 100% of the time.

4

If you can generate uniform random numbers, you can use a variant of Fisher-Yates. //given an array s with the elements to be permuted for i from n-1 to 1: t = rand(0, i) # inclusive swap(s[i], s[t])

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