# Tag Info

15

You don't want to use something like the Mersenne Twister for gambling. It is not cryptographically secure. Given a small amount of output, it is relatively straightforward to compute all future outputs. These algorithms are designed for things like Monte-Carlo simulations and things of that ilk. A better option is to select a 128-bit key at random and ...

13

A simple way to imagine the effect of the hash function is a truncation. A "good" hash function ought to behave like a random oracle. If your source has entropy $s$ bits, then this means that the source somehow assumes $2^s$ possible values. When processed with a random oracle with an $n$-bit output, you force the $2^s$ input values into $2^n$ possible ...

9

We currently have no way to prove that a specific PRNG is cryptographically secure. In fact, we currently cannot prove that there exists a cryptographically secure PRNG (!). If you scale back the requirement from "mathematical proof" to "something we generally accept", there's still no way for an automated test to verify that a specific output is ...

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

"PRNG" means "Pseudorandom Number Generator" which means that a sequence of numbers (bits, bytes...) is produced from an algorithm which looks random, but is in fact deterministic (the sequence is generated from some unknown internal state), hence pseudorandom. Such pseudorandomness can be cryptographically secure, or not. It is cryptographically secure if ...

7

With a 64-bit known polynomial, future output of an LFSR can be trivially predicted from the last 64 bits output. Even if the 64-bit polynomial is unknown, the last 128 bits are enough, using the Berlekamp–Massey algorithm. Thus indeed, the LFSR-based PRNG in the hardware described in a section 27 of the document linked to in question, with some additional ...

6

Quoting Poncho's answer: Well, the chief vulnerability is that if an attacker is given a large enough sample of Mersenne Twister output, he can then predict future (and past) outputs. This is a gross violation of the properties that a cryptographically secure random number generator is supposed to have (where you're supposed to not even be able to tell ...

6

It fails to be a cryptographically-strong PRNG because it is predictable: given some outputs, you can predict the next outputs. For instance, if you observe the outputs at offsets 0, 1, and 4096, you can predict what the output will be at offset 4097. What it's missing: it's not that it's missing some little tweak (just change line 7 to use addition ...

5

As Paŭlo Ebermann already mentioned in his comments, SHA3 can indeed be used as a pseudo-random number generator. The paper "Sponge-based pseudo-random number generators" talks about just that and it also describes a clean and efficient way to construct a re-seedable PRNG with a (Keccak) sponge function. What you'll get is a PRNG based on a cryptographic ...

4

The NIST special publication 800-90 series (NIST SP 800-90A, NIST SP 800-90B and NIST SP 800-90C) contain a set of PRNGs and tests for cryptographically secure PRNGs. Unfortunatelly, right now (13/10/2013) the NIST website is down, however you can find copies of the NIST statistical test suite via Google at sites like this one.

4

First, on the difference between perfect security and semantic security. Both definitions concern confidentiality, so let us first define what confidentiality means. Note first that an adversary as some a priori knowledge of the message. We can capture that by e.g. having the adversary choose two messages and then flipping a fair coin to decide which one to ...

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

I'd rather add this as a comment. Alas, I lack the reputation for that. I'm a programmer, not a cryptography expert, but for some strange reason I like to lurk here regardless. The cryptography aspect aside (others are much better at that) I'd like to focus on the programming perspective, and why your reasoning is wrong. First of all: lurking here taught ...

3

You need a CSPRNG. And yes, a good CSPRNG should mix some new random data in the pool (reseed) periodically. Here are a few options: SecureRandom in Java RNGCryptoServiceProvider in .Net openssl_random_pseudo_bytes() or mcrypt_create_iv() in PHP RAND_bytes() from OpenSSL /dev/urandom on some Unix-like systems

3

It is a little unclear, how you transformed all your numbers... e.g. how did you interpret your decimal numbers "as binary" and "create a bitmap"? Then you look at the binary representation and guess what.... and they are just the numbers 0-9 in binary and added on an static number (no idea where that came from). Things to consider: Of course the numbers ...

3

Does anyone have a reliable source for this? Well, you are asking about the definition of a CSPRNG, and whether this second criteria is a necessary part. Well, it comes down the to exact definition of the term 'CSPRNG'. If we define a CSPRNG as something that generates output which is indistinguishable from random (your first criteria), then a ...

3

The best that can be done for a PRNG is to reduce the problem of distinguishing its outputs from random (or predicting them) to some believed-to-be-hard problem. A PRNG based on AES in counter mode can be proven to be as secure as AES in some sense. Similarly a PRNG based on a HMAC-SHA256 can be shown to be as secure as HMAC-SHA256. There are PRNGs based ...

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

If nothing else, it makes the output of the pool irrecoverable. One of Fortuna's goals is to make prior Fortuna outputs safe from a compromise (the discovery of all of Fortuna's current data by an adversary). If the pool continued on without a reset, with little or no entropy added before the compromise took place, the adversary could more easily calculate ...

3

Using a stream cipher for mass generation of "random" bytes is a fairly good solution, however the risk is loosing Forward Secrecy at some point. The trick then is re-keying the cipher often enough, and having a good source of random data with which to rekey your cipher. See Fortuna.

2

Yes, this can be done with strong extractors and strong blenders.

2

The hexadecimal output of an IV matching the block size of Serpent should be 32 characters. Since you are getting 42, that is an extra 5 bytes of data. The last 5 bytes of every IV you posted is 3056E60801, which leads me to strongly believe this is an implementation issue, possibly related to reinterpret_cast. In terms of the RNG itself, it appears to be ...

2

As mentioned, most proofs of PRNG security are really proofs of a protocol that uses some underlying construct. The proofs say, "If the construct can't be broken, then the protocol that uses it can't be broken any easier than that." That makes all these proofs subject to the assumption that the underlying construct (like factoring, quadratic residuosity, ...

2

I would try to avoid doing any cryptography using javascript… but that's just my personal opinion. Anyway, if you really want to walk the Javascript path, you could skip the libraries and take a look at the window.crypto.getRandomValues() function, as long as you can live with the fact that it's an experimental API and not yet supported in all browsers… it ...

2

This question is about artifacts produced by buggy debug code written in C++, and squarely off-topic; but I can't vote to close it (I tried), because there is a bounty. IMHO the problem is: char const * is not the appropriate type for a pointer to an arbitrary collection of bytes of some length, like an IV is. The thing pointed-to by a char const * is a C ...

2

As noted by izaera, that reset of the pool is explicitly specified in Fortuna, and not an implementation artifact. The pools in Fortuna are SHA-256 hashes. By definition, in order to obtain a pool's result, the SHA-256 hash must be obtained (in the present code, that's the job of sha256_done). With a standard SHA-256 implementation, there is no way to ...

2

If you are concerned about database size, only the master key needs to be stored when you use HKDF. Ditto when sending it to another computer. Otherwise, two independent random keys are clearly secure and simpler to implement, so you should do that.

1

Since Blum-Micali is cryptographically secure, you know that there won't be a short cycle (not one short enough to detect in polynomial time), because a short cycle would violate cryptographic security. Therefore, you don't need to worry about this. It's not worth your time worrying about it: it's very unlikely you'll run into a short cycle. That said, ...

1

Ferguson and Schneier define SHAd-256 in their book Practical Cryptography in Chapter 6.3.1 Length Extensions. For any hash function SHA-X, where X is 1, 256, 384 or 512 we define SHAd-X as the function that maps m to SHA-X(SHA-X(m)). In particular, SHAd-256 is just the function m ↦ SHA-256(SHA-256(m)). They clearly defined SHAd-256 to prevent length ...

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