50
I wouldn't try to explain the mathematics of the backdoor. Just explain that the NSA hid a secret backdoor in there.
Instead, I would suggest focusing on the history and the context. For instance, you could explain about Crypto.AG, how they spiked their RNG to help the NSA spy on their customers. You could explain how random number generators are a ...
49
No.
The rate of memory error in a correctly working computer at ground level is very low; anything larger than one error detected per week (as reported by machine with ECC logging) is reason for maintenance [#]. Hence the proposed method requires a terminally impractical delay to get any entropy, or an unreliable computer; and for one well built, that ...
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];
...
39
"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 ...
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'
12.1k3 gold badges33 silver badges64 bronze badges
34
Blum-Blum-Shub is a stream cipher: given a short key, it produces an effectively unlimited-length stream of pseudorandom bits. Other well-known examples of stream ciphers include AES-CTR and RC4.
Blum-Blum-Shub gets mentioned a lot by non-expert cryptographers. I suspect this is because it comes with a "proof" of security, which sounds like a wonderful ...
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, ...
30
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 ...
29
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 ...
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 ...
answered Aug 29 '19 at 21:12
Squeamish Ossifrage
40.3k3 gold badges76 silver badges166 bronze badges
23
Here is a list of products and companies who have had their EC DRBG algorithm validated by NIST.
http://csrc.nist.gov/groups/STM/cavp/documents/drbg/drbgval.html
The validation lists all modes that have been validated, so you can see which ones have gone to the effort of having their implementation of Dual_EC_DRBG validated. Tim Dierks points out that, for ...
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 ...
23
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 ...
22
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'
12.1k3 gold badges33 silver badges64 bronze badges
22
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 ...
21
RSA BSAFE Libraries (Both for Java and C/C++) use it as their default PRNG.
Java:
http://developer-content.emc.com/docs/rsashare/share_for_java/1.1/dev_guide/group__LEARNJSSE__RANDOM__ALGORITHM.html
C/C++:
https://community.emc.com/servlet/JiveServlet/previewBody/4950-102-2-17171/Share-C_1.1_rel_notes.pdf
This obviously impacts users of the library such ...
21
First of all, there is a difference between writing to /dev/random and/or /dev/urandom and increasing the entropy count maintained in the Kernel.
This is the reasony why, by default, /dev/random is world-writable - any input will only augment, but never replace the internal state of the RNG; if you write completely predictable data, you're doing no good, ...
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 method given in this other answer is correct: to choose a uniformly random integer in range $[0,k-1]$ given a string of uniformly random integers in range $[0,n-1]$ with $1<k≤n$, get one integer $x$ from the string until $x<⌊n/k⌋⋅k$, then output $y=x\bmod k$. If we have $k≤n<2k$ (as in the question where $k=201$, $n=256$), that simplifies to: ...
19
I will answer considering Linux OS, as being one of most popular Unix-like OS (between OSes which have urandom). If you need other OS, please, inform me.
Also I will answer using source code of random.c driver from Linux 3.3.3 Kernel, because it is one of best documentation of /dev/random mechanics. And the other is paper: Analysis of the Linux Random Number ...
19
Entropy is a function of the distribution. That is, the process used to generate a byte stream is what has entropy, not the byte stream itself. If I give you the bits 1011, that could have anywhere from 0 to 4 bits of entropy; you have no way of knowing that value.
Here is the definition of Shannon entropy. Let $X$ be a random variable that takes on the ...
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
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
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 ...
18
Frankly, I'd be surprised if anyone did use it. Even before the potential backdoor was discovered back in 2007, the Dual_EC_DRBG was known to be much slower and slightly more biased than all the other random number generators in NIST SP 800-90. To quote Bruce Schneier:
"If this story leaves you confused, join the club. I don't understand why the NSA was ...
18
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 ...
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 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 ...
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; ...
Only top voted, non community-wiki answers of a minimum length are eligible
