# Tag Info

0

One can not substantiate (much less assert) the correctness of a Cryptographically Secure Pseudo Random Number Generator using tests of its output (because any useful test fits the definition of a break of the CSPRNG); that seems to be what's attempted in the question (since it is about "check the correctness of the PRNG" and asked in a crypto group). Such ...

5

Who can tell when my machine was booted? Anyone who observed it go on, at least. That could include someone sniffing your wlan traffic. However, if the computer in question is a shared server, anyone with access can probably call uptime. After all, /dev/random uses timings for it's cryptographically secure output. In setups where timing ...

3

I'll formalize things a bit, because I think it is then easier to understand what is going on. Definitions. A random variable $X$ is defined by a set of possible events $(x_1,...,x_n)$ and the probabilities of these events $P(x_1),...,P(x_n)$, and its entropy is defined as$$H(X):=-\sum_{i=0}^n P(x_i)\cdot \log_2(P(x_i)) \mbox{ bits}.$$ When all events have ...

0

There's a lot of nay sayers that refute the benefit of one time pads. It's a little like positing that matches are useless and must not even be contemplated because turbo lighters exist now. I believe that matches are probably still sold somewhere. More seriously, consider:- A blue sky figure of 4GB for a OTP is a little OTT. When you need the security ...

-1

Yes absolutely. I believe that web cams make excellent true random number generators, but. The camera has to be operated within a visually managed environment. This is necessary to determine and control entropy of the resultant images for quality control purposes. The trick is not to rely on the scene the camera sees, but the image noise. Only God ...

4

No, Curve25519 signature is not vulnerable to bad RNG during signature generation; that's because Curve25519 signature needs no random number during signature generation. By contrast, in ECDSA, a fresh random number is needed for each signature, and if it gets known, that allows to recover the private key from the signature and public key; same if the same ...

5

Any key generation algorithm for any cryptosystem is going to be weak if the attacker can predict what seed was used to generate the key. They can just generate the same key. However, assuming the the random number generator is not that bad, different algorithms start to look different. If you are just using the output of the random number generator as a ...

2

Any PRNG with a finite state size is eventually periodic. The maximum period possible is $2^n$ for an $n$-bit state, but the average with a well mixed state is $2^{n/2}$. Here the hash function used is SHA-512, but the state is 1024 bits. A first guess would be a period of $2^{512}$, rather than the $2^{256}$ mephisto gives. Let's look at the cycles. Both ...

1

Yes, this PRG is theoretically periodic. Approximately after generating $2^{512}$ outputs a state will be generated that collides with a previous state. (A previous version of this answer said $2^{256}$ as I missed that two outputs are used for the state. Otus answer pointed out this mistake.) This follows from the birthday problem. However, $2^{512}$ is ...

8

For RSA, the answer whether it is feasible for a single computer depends on the reason your generating them (and specifically, whether they need to remain secure if you publish a number of them). For example, if you're generating the RSA keys to search for some criteria (e.g. the hash of the public key has a specific pattern), and you'll discard the ones ...

10

It is feasible to generate 300 million public key pairs of reasonable strength in 8 hours on a single computer, easily with ECDSA using a single core/thread, and even with DSA using quite a common multi-core computer. RSA would require many standard computers (baring hardware accelerators for modular exponentiation), assuming all the public keys are made ...

2

So if I plan to accommodate in the ballpark of 10,000 entries, and want it to take a million random guesses to get lucky and find one, I should only need 10,000 * 1,000,000 keys. Yes, this is correct. If you have $n$ (randomly chosen) valid keys out of $N$ total, then the probability of a single key being valid is $p = n/N$, and so the average number ...

0

I don't think the birthday paradox applies here. The way the probability is computed in the birthday paradox depends only on the number of possible states (i.e number of days) and the number of attempts (i.e. number of people you look at). But in your case the probability of a successful collision obviously not only depends on the number of attempts and ...

1

2 important points: There is a difference between guessing a particular key, and guessing any one of a number of keys. The birthday example is the latter. This is one reason why a user/password pair is commonly used. You may be able to guess a password that matches someone's password, but you also have to know which user it matches in order to take ...

2

A proof by contradiction seems most appropriate here. Assume that $H$ is not cryptographically secure. This means it fails to provide at least one of the properties of a CSPRNG as defined in your class, textbook, whatever. Then you must show how you can use an attack on $H$ to attack the cryptographic security of $G$. To do this, note that ...

4

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

2

Let's assume that randInt gives you cryptographically random (independent) numbers in the range $[0, N)$. Then you can generate a larger number by taking two of those, $x_1$ and $x_2$ and adding $x_1 + x_2 \cdot N$ (which is just bit concatenation if $N = 2^n$). That's a random number in the range $[0, N^2)$, assuming the original numbers were random and ...

1

There are many "cryptographically strong pseudorandom generators" and we know how to construct them well. If you have a strong 128-bit (or more) key $k$, then you can just use AES-CTR to get as much randomness as you need: $AES_k(0)||AES_k(1)||AES_k(2)||\cdots$. You can also do a similar thing with SHA256. The real problem that arises is where to get the key ...

Top 50 recent answers are included