51
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];
...
44
"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 ...
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
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 ...
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'
13.5k3 gold badges37 silver badges71 bronze badges
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
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, ...
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
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 ...
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 ...
answered Aug 29 '19 at 21:12
Squeamish Ossifrage
42.4k3 gold badges83 silver badges175 bronze badges
25
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 ...
24
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'
13.5k3 gold badges37 silver badges71 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 ...
22
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 ...
22
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 ...
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 ...
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
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 ...
Only top voted, non community-wiki answers of a minimum length are eligible
