121
The main difficulty with the one-time pad is that it requires pre-arrangement. In order for me to use a one-time pad to communicate with you, we must either have arranged ahead of time for a one-time pad that we will use (which must be as large as our communication will be), or else we must have some secure way of communicating that will allow us to agree on ...
58
For symmetric encryption algorithms, your question is basically "Why do we use AES or DES rather than another function that provides the same properties as AES or DES but forces us to use the second weakest chaining mode and never lets us use the same key twice?" Well, the answer is obvious, we sometimes want strong chaining modes and we often like to use ...
50
There is a theorem in cryptography that states that secure encryption and secure PRNG are equivalent, and in fact you just proved half of it.
Given a secure PRNG, you can create a secure encryption algorithm using the method you just provided (using the key as the PRNG-seed). The other half is that given a secure encryption algorithm, you can create a ...
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 ...
48
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 ...
44
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];
...
37
"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'
10.5k3 gold badges31 silver badges62 bronze badges
33
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 ...
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, ...
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 ...
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 ...
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 ...
21
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 ...
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
To complement fgrieu's short answer, here is an overview of the two RNG algorithm sets.
Hash-DRBG
The state of Hash-DRBG is composed of a value $V$ (which is updated with each request of new bits), and a same-size constant $C$ (which is only updated on reseeding the generator), and a counter $c$ to track when the next reseeding is needed.
Only $V$ is ...
19
The answer you posted is actually correct (more or less, see below): have each participant commit to their random number $r_i$ by publishing, e.g., $\mathcal{H}(r_i)$ in the first round. And then in the second round, each participant opens the commitment by publishing $r_i$ and everyone checks that it matches the committed value by hashing it. The final ...
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 ...
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
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; ...
17
There is a very easy reason why one-time pads are not always used. It requires information sent before the encryption is set up, i.e. both the sender and the recipient need to have access to the pads themselves. That's a big pain, especially if all information was to be sent with one time pads. How would one distribute the pads themselves?
There is also a ...
Only top voted, non community-wiki answers of a minimum length are eligible
