107

In short, it is more than a belief: there is strong evidence that humans are not good entropy sources. There is a test for this Man vs. Machine. Or, why Man is not a Particularly Good Source of Entropy. Try to win! So we don't rely on whether generating a random number from the mind or random keyboard typings and mouse movements that seem like a monkey ...


36

First problem is you're not specifying at all how many swaps you need to do for a given message length, other than saying it's "several." For an $n$-bit messsage there are $n!$ ways of rearranging its bits, gives a lower bound of $\mathrm{log}_2(n!) = \sum_{i=1}^{n}\mathrm{log}_2(i)$ bits for on how much pseudorandomness you'll need. Rather than analyze a ...


34

I think you're misinterpreting the source. The source says the TRNGs "rely" on compression (a cryptographic hash would be the compression function, or possibly some simpler function to increase throughput). The random data isn't insecure after compression, it's insecure before compression. Why? When you roll dice there's an equal probability of it ...


32

A colleague of mine told me about a website that, given a sufficient quantity of output from an PRNG, had been able to deduce which application the PRNG was from. As you correctly identified this would present an immediate and probably devastating attack to any cryptographic PRNG as it indeed would allow you to easily distinguish a random string from a PRNG ...


30

For me, the fraud-related applications of Benford's Law come to mind. When people make up data they tend to create overly uniform data, even when it's not appropriate. There's a definite psychology going on that may cause people to be less random than they are intending to be (Wikipedia links to a paper claiming humans are in fact bad at this). Or perhaps ...


28

One tool that tries to do this is untwister. It's almost certainly not the tool you were thinking of, though, as it cannot determine if the output came from OpenSSL specifically. It can determine Glibc's rand(), Mersenne Twister (MT19937), PHP's MT-variant (php_mt_rand), Ruby's MT-variant DEFAULT::rand(), and Java's Random() class, though, and can recover ...


19

The RFC specifies things in terms of bits. Each call to HMAC outputs hlen bits. tlen is the count of bits obtained so far; when at least qlen bits have been obtained, this step is finished. The sample code is written in Java in which the elementary unit of information is the octet ("byte" in usual terminology). The supported hash functions always output a ...


18

Why would a dice rolled be "more random" than simply coming up with a sequence in your head, and then changing some of them? Humans have too many biases regarding what a random sequence is. If you ask humans to generate a random sequence, they will probably pay attention not to use the same character in a row, i.e., aa or bb, as they think that ab ...


15

Randomness is a measurable, statistical property of a set of values. It doesn't mean the same as "hard for a human to guess." Your sample string is hard for a human to guess, but it isn't very random. There is a tool called "ent" for most Unix systems that can quantify the randomness, by some measures, of a file. Available here: https://...


14

People are not that bad, but we're slow. See How were one-time pads and keys historically generated? In summary, MB's of 100% secure key material were generated for one time pads by people simply key smashing on type writers. Sufficient to win three world wars. It's just that a human's entropy rate is a little lower than a laser phase based TRNG. ...


11

Using /dev/urandom to generate cryptographic keys or secrets can be an issue when the state of the OS is not unique. This is the typically case when a VM was just booted from a template: the state of the CSPRNG could be shared among multiple VMs. In cases similar to this one, it is important to use /dev/random or getrandom() instead of /dev/urandom, so that ...


10

First of all the first Entropy calculation is not correct. Recall the definition of (Shannon) entropy: $$H(X) = -\sum_{i=1}^n {\mathrm{P}(x_i) \log_{\,b} \mathrm{P}(x_i)}$$ If uniformly chosen a digits entropy is $$H(X) = -\frac{1}{10} \log_2\left(\frac{1}{10}\right) = 3.3219280...$$ Case $<250$ with 16 digits; \begin{align} H_1(X) &= 16 \cdot - ...


10

The obvious way to do this is to generate N words, and use logical operations to combine them in a single word such that each bit of the output word is a 1 with probability approximately 0.1 (and the individual bits are uncorrelated). In the simplest case, you could generate 3 words, and just AND them together into a single one. In C, this would be: ...


10

The short answer is that LLL (or more generally, lattice reduction methods) is useful when you can convert your problem into finding a small linear combination of known vectors. Let's take your example and make it concrete. Let $m = 2^{64}$, $a = 7244019458077122845$, $b=1$, and the we have a generator that outputs the upper 16 bits of the state at each ...


9

Just use SecureRandom and let the OS take care of it.


9

Evidence suggests that people asked to generate random data will produce repetition in the data substantially less often than random chance would. For example, let's assume you were asked to generate random digits (i.e., just 0 through 9). In purely random data, a sequence like NN (i.e., the same digit twice in a row) happens about 10% of the time. That is, ...


8

You can just follow the instructions on HotBits, which is exactly what you're trying to build. It's been running for years and is the only radioactive TRNG on the internet. It goes into great depth regarding underlying nuclear physics, sample distributions and extractor mechanism. Although not really within the realms of strict cryptography, there is also a ...


7

Radioactive decay is normally measured by an exponential process assuming environment parameters are constant. This means that the average time between decays assuming stationarity is an exponential random variable, with $$ Pr[T_i>t]=\exp(-\lambda t) $$ for a constant $\lambda.$ If you know $\lambda$ you can divide time into intervals of length $T_0$ such ...


6

Define the Mutual Information of a pair of random variables. $$I(X; Y) = H(X) - H(X\mid Y)$$ For discrete random variables we hae that $H(X\mid X) = 0$, so: $$I(X; X) = H(X)$$ The Data-Procesing Inequality states that for any function $f$, we have that: $$I(f(X); f(Y)) \leq I(X; Y)$$ While we won't need it here, this includes randomized functions, provided ...


6

PRGs get an input (seed) and generates a larger output value than the input. Indeed. The standard definition of a PRG makes it a deterministic polynomial-time algorithm with input a seed in $\{0,1\}^n$ and output in $\{0,1\}^{\ell(n)}$ with $\forall n, \ell(n)>n$; and an other characteristic (pseudorandomness). is it possible that some outputs will ...


5

If an attacker has a way of getting you to encrypt a message of their choosing this way, it would be trivial break. Imagine you swap each bit randomly with another bit. If you have a message of 800 bits an attacker could discover the entire pattern with 11 attempts. The attacker could set bits 0-399 to 1 and map those to 1s in the encrypted message and ...


5

In cryptography you usually want to use min-entropy (which is a lower bound on security) instead of shannon-entropy (which can be higher than the security if the attacker is content with breaking only a fraction of the targets). Min-entropy is simply $-\log p$ where p is the probability of the most likely value. In this case this works out to: $$-16 \cdot \...


5

what is the purpose of this line of code? while (bits - val + (n - 1) < 0); From a syntactic perspective, it ends the do opened above. From a functional perspective, it makes the pseudo-random number generated uniform on the specified interval. I'll focus on the later aspect. Assume n was $3\cdot2^{29}\,$ (that is 3<<29) rather than $6$. After the ...


5

This section talks about Fortuna, where it uses a block cipher with a 128-bit block and a 256-bit key size. The cipher is used in CTR mode. In the CTR mode, if an attacker can access the internal state than then the security is lost ( the key and current counter value), therefore after a request, 2 new blocks are generated and used as a new key, and the old ...


4

Take (hypothetical) seeded deterministic PRNG algorithm Gen1. If you use Gen1 to produce a stream, and I use Gen1 with the same seed, I will get an identical stream. As per Wikipedia's definition, a PRNG is deterministic. Now consider another hypothetical seeded deterministic PRNG Gen2, which uses a different algorithm than Gen1. If I use Gen2 with the same ...


4

But this notation is defined (informally) in the first paper. The notation $O(\nu(n))$ is used for any function, $f(n)$, that vanishes faster than the inverse of any polynomial, that is for every polynomial, $\mathrm{poly} (n)$, and $n$ large enough, $f(n) \leq 1/\mathrm{poly}(n)$ Therefore, what it means is no probabilistic polynomial time (PPT) algorithm ...


4

Why such naive and simple thing is not appealing If you're talking about a method that internally generates 500,000 0 bits and 500,000 1 bits, shuffles them (by some method), and then outputs them, that would not be considered a CSRNG. What is the "real" compass? The compass is "can we devise an efficient test that distinguishes the output ...


4

I can't tell whether this is what motivated NIST, but I found a paper that has an argument for LFSR counters in some applications: Mukhopadhyay, Sourav and Palash Sarkar. 2006. "Application of LFSRs for Parallel Sequence Generation in Cryptologic Algorithms." Cryptology ePrint Archive: Report 2006/042. Abstract. We consider the problem of ...


4

The main issue would be the MT seed size. MT has a large enough state, but the seed is generally just a 32 bit word $w$. See here for more information. SHA on the output won't guard you from a brute force attack on the seed; an attacker can just try and generate the stream and perform the SHA calculations and compare. So you need to somehow extend the seed ...


3

...would it help in any way with the issues discussed here? No, not really. There's always been a gap between myriad theoretical mathematical extractor constructs and those used in commercial validated TRNGs. I honestly don't know why as that seems like an unlikely dichotomy, yet it demonstrably exists. The two should ideally converge to a common output ...


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