Tag Info

Hot answers tagged

33

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


13

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


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


8

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


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


5

The modulus 77 leads to a short period.


5

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


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

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


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

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

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


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

Perhaps you are thinking of the Micali-Schnorr PRNG, as described in Algorithm 5.37 of the Handbook of Applied Cryptography? Algorithm 5.37 in HAC never states that $e$ is known to the adversary, or even that $n$ is known. Also, Algorithm 5.37 outputs only the least significant bits of the number, on each iteration. So I think you are confusing RSA as ...


3

I will add a few points worth considering to @fgrieu's answer. The output sequence of period $2^n-1$ from a $n$-bit maximal length LFSR has the property that it contains runs of zeroes and ones in (close to) the correct proportions. In particular, there is one run of $n$ consecutive ones (no run of $n$ consecutive zeroes, but there is one run of $n-1$ ...


3

I'm not a hundred percent certain on your definition of "AE-Secure", but I would have to say yes. Existence of a PRG implies existence of one-way functions, which in turn implies existence of both, symmetric encryption and message authentication codes. From those two primitives you should be able to construct authenticated encryption.


3

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


3

If for some reason the solution given by @poncho does not please you (e.g. you want $N$ to be on the magnitude of a few billions but you do not have a few gigabytes of RAM), then there are other solutions, in which you get the permutation as an evaluable procedure (in other words, a block cipher). A practical solution is the Thorp shuffle. It is ...


3

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


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

Well, this is essentially homework (it wasn't assigned, however you are attempting to learn from it), and so I won't give you an explicit answer; instead, I'll try to point you in a direction where you can figure out the answer yourself. First of all, how would you solve this if you were given the values $a$ and $m$? Once you have answered that, let us ...


3

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



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