111
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 ...
49
"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 ...
49
(..) would it be viable to allocate a very large amount of memory (perhaps in a long loop) and use the errors that eventually occur as a source of randomness?
No. Practical use of memory errors as a source of randomness would require manipulation of DRAM timing parameters, as envisioned in this answer and it's reference.
The rate of memory error in a ...
45
You asked for the practical impact, so the answer is that for \$120 I could probably have your entire password database done by tomorrow.
Here is your program, or something similar to it:
using System;
using System.Text;
using System.Security.Cryptography;
class Program {
static void Main(string[] args) {
byte[] pwd = new byte[128];
...
38
What are the criteria that make an RNG cryptographically secure?
In short, a DRBG [deterministic random bit generator] is formally considered computationally secure if a computationally-limited attacker has no advantage in distinguishing it from a truly random source.
What does this mean? Given a DRBG F and a truly random oracle G, let A be a probabilistic ...
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 ...
35
The title of this article is complete hype. Tip: when a journalist says “X could solve Y”, read “X probably won't solve Y”. Much of the content of the article is hype too.
Cryptography has a random number problem, but the problem is not producing random numbers, and the proposal in this article wouldn't be useful to produce random numbers anyway.
...
answered Dec 12 '18 at 19:17
Gilles 'SO- stop being evil'
15.9k3 gold badges41 silver badges81 bronze badges
34
Define $H(x) = \operatorname{SHA-256}(x) \mathbin\| 1$; that is, append a single 1 bit to SHA-256. Can you find a collision under $H$? Does $H$ have anything resembling uniform distribution?
This counterexample is not merely pathological; designs like Rumba20 and VSH provide collision resistance but neither preimage resistance nor uniformity.
That said, ...
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 ...
33
First, insecure PRNGs are typically faster than CSPRNGs. CSPRNGs based on /dev/urandom (if you're familiar with Linux), for example, have to call the crypto kernel module driver every time. For reference:
the BearSSL implementation of ChaCha20, which can be used as a CSPRNG, on an Intel Xeon CPU at 3.10 GHz, reaches 270.72 MB/s;
an implementation of a ...
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 ...
31
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 ...
26
A True Random Number Generator uses a physical phenomenon not known to be fully deterministic as origin of the discrete values (bits or integer numbers) that it outputs. That phenomenon can for example be a dice throw, thermal noise, disintegration of a radioactive substance… What detects this phenomenon can be followed by a conditioning stage to turn the ...
26
From what you have described, it sounds like your system works as follows:
Consult the system clock to find a 32-bit seed $s$.
Use System.Random to generate a passphrase $p = G(s)$. (Here $G$ is shorthand for whatever computation happens inside System.Random.)
Hash the passphrase with PBKDF(2?) into output $x = H(p, \sigma)$, where $\sigma$ is a salt known ...
26
The solution is simply to make sure that you have good randomness. At the size of the numbers we are considering, the probability of a repeat when using good randomness is extremely small. To make this clear, there are well over $2^{1000}$ prime numbers of length 1024. The probability of a repeat at any reasonable number of primes chosen, when using true ...
25
This construction gives you cryptographic-quality pseudorandom output, but it isn't as secure as it can be for a random generator.
With commonly used hash functions $H$ (such as any of the SHA2 and SHA3 family), as far as we know, the bits of $H(\textrm{seed}, n)$ are unpredictable if you only know $n$ and $H(\textrm{seed}, m_i)$ for any number of values $...
answered Dec 12 '19 at 12:29
Gilles 'SO- stop being evil'
15.9k3 gold badges41 silver badges81 bronze badges
23
Yes, it is unsafe to seed a PRNG with only with the system time. No, that's not all Bouncy Castle's SecureRandom does.
The SecureRandom default constructor calls SetSeed(GetSeed(8)); which calls Master.GenerateSeed(length); which calls SetSeed(DateTime.Now.Ticks); which is misleading because SetSeed only adds seed material to an already existing prng (the ...
21
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 ...
20
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 ...
19
Even in context, much of what is written in the blog post makes no sense. E.g., it says:
While it can be argued that the DRNG is in reality just splitting a 128-bit value into two pieces and handing them to you one piece at a time, from a theoretical viewpoint this does not matter. While the original value had 128 bits of entropy, the end result is that ...
19
Update: Since I wrote this post, CryptGenRandom has been deprecated. Apparently it is now recommended to use BCryptGenRandom from the "Cryptography Next Generation" API.
(Confusingly, it has nothing to do with bcrypt.)
Yes, Windows has something similar. It can be accessed through CryptGenRandom.
With Microsoft CSPs, CryptGenRandom uses the same random ...
19
The Government's elliptic curve backdoor is real, isn't it?
We don't know for sure, but there are indicators into that direction. More importantly though,
yes, you can backdoor the RNG, as was pointed out shortly after its publication (PDF)
yes, the parameters have been replaced in-the-wild by attackers to break VPN appliances using this RNG.
Does this ...
19
Yes, it is cryptographically secure, pseudo random output, seeded by retrieving secure random data from the operating system.
If it is random or not depends on the fact if the OS RNG is random. This is usually the case on normal desktops, but you'd better be sure for e.g. limited embedded systems. If no truly random data can be retrieved - according to ...
18
The key element in the definition of a PRG is the observer (aka distinguisher, algorithm, test, etc) that the PRG is supposed to fool.
A statistical PRG fools a specific set of observers, whereas a cryptographic PRG fools all efficient observers.
This strong definition is essential for cryptography::
The only assumption the designer should make about the ...
18
If one source remains uncompromised plus statistically random on all bits, and both sources remain independent, then a xor of both sources together can also be considered uncompromised plus statistically random for all bits.
Basic proof:
Label the the results two RNGs $X$ and $Y$, consider bits $X_n$, $Y_n$ and $Z_n = X_n \oplus Y_n$
Assume each value of ...
18
The official documentation for System.Random explicitly says it should not be used for generating passwords. It’s predictable, and seeded only from the system clock. This means System.Random has at most 20 bits of entropy to anyone who has a clock accurate to within a second.
Indeed, try creating two new instances in quick succession on different threads; ...
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 ...
17
What tests can I do to ensure my PRNG is working correctly?
That depends on what exactly you mean by “working correctly”.
You can do statistical tests to check for various statistical flaws your random number generator might be subject to, but you have be aware of the fact that statistical testing cannot serve as a substitute for cryptanalysis… meaning: ...
17
Let me begin by saying that if you have a hardware source of randomness, you don't need to be stingy with it.
1) Does modulo affect the quality of randomness, faking in some way the distribution of values?
Yes, it does. Or at any rate, it can --- see my answer to (3) below for more details. (I'm assuming by "quality of randomness", you specifically mean ...
Only top voted, non community-wiki answers of a minimum length are eligible