Hot answers tagged

74

"lucky" is not a property of the attacker. There's no "lucky" attacker nor "normal" attacker. They both have the same probability (low, very low) to guess the key. You can decrease the probability at will by increasing the length of the key (i.e. the no. of bits). You cannot really argue "what if the attacker is lucky" because "being lucky" is a posteriori ...


42

Note: This answer assumes that by "lucky" OP meant "able to remove X% of valid answers", because I believe that was intent. Of course you can't measure luck ;) And if he is very lucky, say 90% chance, that means that 1 bit is actually only 0.1 bit.So in face of a very lucky opponent, a 128 bit password has only 12.8 bit strength. Well, let's validate ...


38

If you repeatedly apply a generic function on its result, in a finite domain, you tend to obtain a "rho" structure: at some point, you enter a cycle whose length is (roughly) $\sqrt{N}$, where $N$ is the size of the output space for your function. In the case of MD5, $N = 2^{128}$ (MD5 outputs 128-bit values), so the cycle will have length about $2^{64}$ ...


33

You are likely going to have both false positives and false negatives if you try to use Shannon entropy for this. Many compressed files would have close to 8 bits of entropy per byte, resulting in false positives. Any encrypted file that has some non-binary encoding (like a file containing an ASCII-armored PGP message, or just a low entropy header) could ...


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 ...


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 ...


25

So if at each bit he has a 50% chance, that means that 1 bit is actually only half bit. And if he is very lucky, say 90% chance, that means that 1 bit is actually only 0.1 bit.So in face of a very lucky opponent, a 128 bit password has only 12.8 bit strength. You're miscomputing how "luck" affects the number of bits. For a 50% chance, that does ...


24

If a computer is doing the selection of PIN numbers, then you would be very lucky indeed to guess a PIN in three times. The entropy - assuming that all numbers are valid - is of course $\log_2{10^8} \approx 26.57$ bits. The chances of guessing the PIN correctly in 3 tries is $$1 - \frac{x-1}{x} \cdot \frac{x - 2}{x-1} \cdot \frac{x-3}{x-2} = 1 - \frac{x-3}{...


23

I don't get nearly the amount of entropy stated in the comic. Interestingly enough the reasoning for the entropy rating are actually justified in the comic by the little boxes which each represent 1 bit of uncertainty. This means for Tr0ub4dor&3 It's estimatated that the word itself "Troubador" comes up in dictionaries which contain about $2^{16}$ ...


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, ...


22

You've actually been trapped by the mindset that OTP will hide all information about the underlying plaintext. This is not true as you have observed. The definition of perfect secrecy, given in Introduction to Modern Cryptography by Katz-Lindell, reads like this: Definition 2.3 An encryption scheme $(\text{Gen, Enc, Dec})$ with message space $\mathcal M$...


21

You're absolutely correct: numbers (or a given binary string) don't have entropy. However, a number can be sampled from a distribution that has entropy. In other words, the entropy is a property of the process used to generate a number, not of the number itself. So if I just give you the number 4, and assure you that I picked this number uniformly at random ...


20

The answer rather depends on what you mean by 'entropy'; if you mean 'Shannon Entropy', then no, a deterministic function cannot increase entropy. For example, if the unhashed password has only 7 different possible values, then the hashed version of the password will also have (at most) 7 different possible values; you've made things look more obscure, but ...


20

First let's say that entropy is a property of a generation process. A number, by itself, does not have any entropy. What has entropy is the algorithm or process which has produced that number, and the entropy measures what the number could have been. In that sense, the formulation in the Wikipedia page lacks rigour. For a "nothing up my sleeve" number, we ...


20

On the other hand, the Shannon entropy of a 6-sided die tossed 100 times is $-6 × 1/6 × \log_2(1/6) = 2.5849625007$ bits. That is wrong: $-6\cdot\frac16\cdot\log_2\frac16$ is the entropy of a single die roll. Assuming the $100$ die rolls are independent, you can simply sum the entropies of the individual rolls to obtain $$ 100 \cdot\left(-6 \cdot\frac16\...


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

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 ...


17

A simple way to imagine the effect of the hash function is a truncation. A "good" hash function ought to behave like a random oracle. If your source has entropy $s$ bits, then this means that the source somehow assumes $2^s$ possible values. When processed with a random oracle with an $n$-bit output, you force the $2^s$ input values into $2^n$ possible ...


17

Very short answer: No Quite Short answer: No, because a scheme can only be a One-Time-Pad if the entire pad is perfectly random and secret. Concise answer: It sounds like you're trying to build a stream cipher. The security of it really comes down to how much of the scheme you think can be kept secret. If I listen in to your wifi and hear you requesting a ...


17

Expected entropy in the output of a random oracle The expected entropy in the output of a $h$-bit random oracle fed with random $h$-bit input is close to $h-0.8272$ bit, for even moderate $h$ (e.g. at least $32$). As $h$ grows, that expected entropy becomes arbitrary close to $h-\eta$ bit with $$\begin{align}\eta&=\frac 1{e\ln(2)}\sum_{i=1}^\infty\frac{\...


17

Is it possible to securely transfer random values in such a way that they are still viable for use in cryptography? Yes and this is done all the time. If you use a TLS_RSA cipher suite, the client uses RSA to encrypt key material, i.e. random values, and transfer that securely to the server for key derivation. The owner of the random.org service ...


17

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 ...


15

I'm not sure what you're trying to understand and if the other answers cover it, so I'm trying a different approach and interpret your question like this: What if an attacker guesses the right sequence of 128 bits on her first try by pure chance? That's certainly possible but so unlikely that we don't normally consider that possibility. If you want to ...


15

Assuming that $b = 2^k-1$ for some positive integer $k$, XORing two (or more) numbers in the range $[0,b]$ will indeed yield a number in the same range. If the numbers are random, uniformly distributed over the range and independent, then the result will also be random and uniformly distributed. In fact, we can even prove a stronger result saying that if ...


14

They are both equal. Passphrase security is based on the amount of entropy that the passphrase contains. In your case, both of your pieces of data are only different in the encoding. The actual entropy that they contain is the same. You are generating a secret that is (assuming that the random source is really random) 16 bytes long. So it has 128 bits of ...


13

No. This is not safe. The one-time pad requires that the pad be generated by a true-random process, where each bit of the pad is chosen uniformly at random (0 or 1 with equal probability), independent of all other bits. Any deviation from that, and what you haven't is no longer the one-time pad cryptosystem -- it is some kludgy thing. In particular, once ...


13

I know that humans would find it impossible to maintain a 128 bit password -- however, I wonder if there is some technical reason why a 52 bit password would not be as weak as a 52-bit encryption key for that matter. First, I would argue that 128 bits is not impossible to remember. My current password manager master password is almost 100 bits (6 words from ...


13

If the source as 3 entropy bits per 1024 source bits, constructing a 128-bit seed requires $\lceil128\cdot 1024/3\rceil=43691$ source bits at least. The "XOR 350 bits with jump 128 bits" translates to (correcting the question's formula) $$o_i=n_i\oplus n_{i+128}\oplus n_{i+2\cdot128}\oplus n_{i+3\cdot128}\oplus\dots\oplus n_{i+348\cdot128}\oplus n_{i+349\...


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