Tag Info

Hot answers tagged

32

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


12

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


12

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


10

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

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

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


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


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


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

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

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


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

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

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


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

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

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

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

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

In most PRNGs this leads to a total disaster, in particular when generator's state is bigger than the result returned as pseudo random (call to rand()). If you take Mersenne Twister with it's big period guaranteed and apply the construction you expose, as it returns 32 bit integers, eventually you will get a repeated value that was used to seed previously, ...


3

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


3

rand() is bad because it's not a random function - not even a mediocre one. Every library, operating system, yahoo with a keyboard, can write his own rand and get away with it. The purpose of rand is to give output that looks random enough to be used in non-critical applications, usually with an LCG. Once in a blue moon you might come across some library ...


2

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.


2

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


2

Well, successive calls rand() just produce numbers that "look random". Now, rand() doesn't take a seed; that means that everytime the program runs, calls to rand() will generate the exact same sequence of numbers. This is a deliberate design decision; that means that the program behavior is reproducible (which can be important if you're debugging). If you ...


2

All psuedo random generators keep some limited state to calculate the next number in the sequence. you can think of it like a function $\delta(S)= \{output, S'\}$ with $S$ the internal state of the generator and represented by a finite number of bits. This means that the number of states is limited (though it can be very big: a standard mersenne twister ...



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