Fortuna
Quoted 8 lines
Quoted 3 lines
First, a reminder that the design goal of
/dev/randomproper is information-theoretic security. That is, it should be secure against an attacker with infinite computational power.I am skeptical.
I have never seen any convincing evidence for this claim, and I suspect that there are cases in which/dev/randomfails to achieve this standard.
I'm not sure which claim you're skeptical of. The claim that it's a design goal, or the claim that it achieves it?
I'm pretty sure that's been the *goal* since the beginning, and it says so in the comments:
* Even if it is possible to
* analyze SHA in some clever way, as long as the amount of data
* returned from the generator is less than the inherent entropy in
* the pool, the output data is totally unpredictable.
That's basically the information-theoretic definition, or at least alluding to it. "We're never going to give an attacker the unicity distance needed to *start* breaking the crypto."
The whole division into two pools was because the original single-pool design allowed (information-theoretically) deriving previous /dev/random output from subsequent /dev/urandom output. That's discussed in section 5.3 of the paper you cited, and has been fixed.
There's probably more discussion of the subject in linux-kernel around the time that change went in.
Whether the goal is *achieved* is a different issue. random.c tries pretty hard, but makes some concessions to practicality, relying on computational security as a backup. (But suggestions as to how to get closer to the goal are still very much appreciated!)
In particular, it is theoretically possible for an attacker to exploit knowledge of the state of the pool and the input mixing transform to feed in data that permutes the pool state to cluster in SHA1 collisions (thereby reducing output entropy), or to use the SHA1 feedback to induce state collisions (therby reducing pool entropy). But that seems to bring whole new meaning to the word "computationally infeasible", requiring first preimage solutions over probability distributions.
Also, the entropy estimation may be flawed, and is pretty crude, just heavily derated for safety. And given recent developments in keyboard skiffing, and wireless keyboard deployment, I'm starting to think that the idea (taken from PGP) of using the keyboard and mouse as an entropy source is one whose time is past.
Given current processor clock rates and the widespread availability of high-resolution timers, interrupt synchronization jitter seems like a much more fruitful source. I think there are many bits of entropy in the lsbits of the RDTSC time of interrupts, even from the periodic timer interrupt! Even derating that to 0.1 bit per sample, that's still a veritable flood of seed material.
/dev/random has an even more important design goal of being universally available; it should never cost enough to make disabling it attractive. If this conflicts with information-theoretic security, the latter will be compromised. But if a practical information-theoretic /dev/random is (say) just too bulky for embedded systems, perhaps making a scaled-back version available for such hosts (as a config option) could satisfy both goals.
Ted, you wrote the thing in the first place; is my summary of the goals correct? Would you like comment patches to clarify any of this?
Thank you for pointing out the paper; Appendix A is particularly interesting. And the [BST03] reference looks *really* nice! I haven't finished it yet, but based on what I've read so far, I'd like to *strongly* recommnd that any would-be /dev/random hackers read it carefully. It can be found at
http://www.wisdom.weizmann.ac.il/~tromer/papers/rng.pdf
Happily, it *appears* to confirm the value of the LFSR-based input mixing function. Although the suggested construction in section 4.1 is different, and I haven't seen if the proof can be extended.
Quoted 10 lines · On Sat, Apr 16, 2005 at 11:10:33AM -0000, [email protected] wrote:
Thank you for pointing out the paper; Appendix A is particularly interesting. And the [BST03] reference looks *really* nice! I haven't finished it yet, but based on what I've read so far, I'd like to *strongly* recommnd that any would-be
/dev/randomhackers read it carefully. It can be found at
http://www.wisdom.weizmann.ac.il/~tromer/papers/rng.pdfHappily, it *appears* to confirm the value of the LFSR-based input mixing function. Although the suggested construction in section 4.1 is different, and I haven't seen if the proof can be extended.
Correct me if I'm wrong here, but uniformity of the linear function isn't sufficant even if we implemented like this (right now it's more a+X than a <dot> X).
The part which suggests choosing an irreducible poly and a value "a" in the preprocessing stage ... last I checked the value for a and the poly need to be secret. How do you generate poly and a, Catch-22? Perhaps I'm missing something and someone can point it out.
JLC
Quoted 8 lines
Correct me if I'm wrong here, but uniformity of the linear function isn't sufficent even if we implemented like this (right now it's more a+X than a <dot> X).
The part which suggests choosing an irreducible poly and a value "a" in the preprocessing stage ... last I checked the value for a and the poly need to be secret. How do you generate poly and a, Catch-22? Perhaps I'm missing something and someone can point it out.
No, the value (the parameter pi) are specifically described as "the public parameter". See the "Preprocessing" paragraph at the end of section 1.2 on page 3. "This string is then hardwired into the implementation and need not be kept secret."
All that's required is that the adversary can't tailor his limited control over the input based on knowing pi.
There's a simple proof in all the papers that if an adversary knows *everything* about the randomness extraction function, and has total control over the input distribution, you're screwed.
Basically, suppose you have a 1024-bit input block, the attacker is required to choose a distribution with at least 1023 bits of entropy, and you only want 1 bit out. Should be easy, right?
Well, with any *fixed* function, the possible inputs are divided into those that hash to 0, and those that hash to 1. One of those sets must have at least 2^1023 members. Suppose it's 0. The attacker can choose the input distribution to be "uniformly at random from the
Quoted 1 line
= 2^1023 inputs that hash to 0" and keep the promise while totally
breaking your extraction function.
But this paper says that if the attacker has to choose 2^t possible input distributions (based on t bits of control over the input) *before* the random parameter pi is chosen, then they're locked out. *After* learning pi, they can choose *which* of the 2^t input distributions to use.
The thing is, you need a parameterized family of hash functions. They choose a random multiplier mod GF(2^n). Their construction is based on the well-known 2-universal family of hash functions hash(x) = (a*x+b) mod p.
The /dev/random input mix is based on choosing a "random" polynomial (since there was a lot of efficiency pressure, it isn't actually very random; the question is, is it non-random enough to help an attacker). Remiander modulo a uniformly chosen random irreducible polynomial is a well-known ("division hash") family of universal hash functions, but it's a little bit weaker than the above, and I have to figure out of the proof extends.
Quoted 4 lines · Jean-Luc Cooke
The part which suggests choosing an irreducible poly and a value "a" in the preprocessing stage ... last I checked the value for a and the poly need to be secret. How do you generate poly and a, Catch-22? Perhaps I'm missing something and someone can point it out.
I don't think you're missing anything. What you say matches my understanding as well.
Quoted 11 lines · linux
Quoted 7 lines · David Wagner
Quoted 3 lines · linux
First, a reminder that the design goal of
/dev/randomproper is information-theoretic security. That is, it should be secure against an attacker with infinite computational power.I am skeptical.
I have never seen any convincing evidence for this claim, [..]I'm not sure which claim you're skeptical of. The claim that it's a design goal, or the claim that it achieves it?
Oops! Gosh, I was unclear, wasn't it? Sorry about that. I meant the latter claim.
I certainly agree that information-theoretic security is a stated goal of /dev/random. I'm just not certain that it achieves this goal. (Caveat: I don't think that failing to achieve this goal is problematic.)
Quoted 4 lines
Whether the goal is *achieved* is a different issue.
random.ctries pretty hard, but makes some concessions to practicality, relying on computational security as a backup. (But suggestions as to how to get closer to the goal are still very much appreciated!)
Ok.
Quoted 7 lines
In particular, it is theoretically possible for an attacker to exploit knowledge of the state of the pool and the input mixing transform to feed in data that permutes the pool state to cluster in SHA1 collisions (thereby reducing output entropy), or to use the SHA1 feedback to induce state collisions (therby reducing pool entropy). But that seems to bring whole new meaning to the word "computationally infeasible", requiring first preimage solutions over probability distributions.
Well, wait a second. You have to make up your mind about whether you are claiming information-theoretic security, or claiming computational security. If the former, then this is absolutely an admissible attack. There is nothing whatsoever wrong with this attack, from an information-theoretic point of view. On the other hand, if we are talking about computational security, then I totally agree that this is a (computationally) infeasible attack.
Quoted 6 lines
Also, the entropy estimation may be flawed, and is pretty crude, just heavily derated for safety. And given recent developments in keyboard skiffing, and wireless keyboard deployment, I'm starting to think that the idea (taken from PGP) of using the keyboard and mouse as an entropy source is one whose time is past.
Quoted 6 lines
Given current processor clock rates and the widespread availability of high-resolution timers, interrupt synchronization jitter seems like a much more fruitful source. I think there are many bits of entropy in the lsbits of the RDTSC time of interrupts, even from the periodic timer interrupt! Even derating that to 0.1 bit per sample, that's still a veritable flood of seed material.
Makes sense.
As for your question about what one could do to achieve information-theoretic security, there is a bunch of theoretical work in the CS theory world on this subject (look up, e.g., "extractors"). Here is my summary about what is possible:
1) If you don't know anything about your source, and you don't start with any entropy, then information-theoretically secure randomness extraction is impossible -- at least in principle. You pick any deterministic algorithm for randomness extraction, and I will show you a source for which that algorithm fails.
2) If you start with a short seed of uniformly distributed perfect randomness, and you have a lower bound on the amount of entropy provided by your source, then you can extract random bits in a way that is provably information-theoretically secure. Note that you don't have to know anything about the distribution of the source, other than that its (min-)entropy is not too small. The simplest construction uses a 2-universal hash function keyed by the seed (its security is established by the Leftover Hashing Lemma), but there are other constructions, including a class of schemes known as "extractors". This approach does require a short seed of perfect true randomness for every chunk of output you want to generate, though.
3) If you make certain assumptions about the source, you can extract entropy in a way that is provably information-theoretically secure, without needing the short seed. However, the assumptions required are typically fairly strong: e.g., that your source is completely memoryless; that you have multiple sources that are totally independent (i.e., uncorrelated in any way); or that your source has a certain structure (e.g., k of the n bits are uniformly random and independent, and the other n-k bits are fixed in advance). People are actively working to push the boundaries in this category.
I'm not sure whether any of the above will be practically relevant. They may be too theoretical for real-world use. But if you're interested, I could try to give you more information about any of these categories.
Quoted 6 lines · linux
Thank you for pointing out the paper; Appendix A is particularly interesting. And the [BST03] reference looks *really* nice! I haven't finished it yet, but based on what I've read so far, I'd like to *strongly* recommnd that any would-be
/dev/randomhackers read it carefully. It can be found at
http://www.wisdom.weizmann.ac.il/~tromer/papers/rng.pdf
Yeah, [BST03] seems worth reading. It has a reasonable survey of some previous work, and is well-written.
However, I'm pretty skeptical about [BST03] as a basis for a real-world randomness generator. It assumes that there are only 2^t possible distributions for the source, and the set of possible distributions has been fixed in advance (before the design of your randomness generator is revealed). Consequently, it fails to defend against adaptive attacks.
If the attacker can feed in maliciously chosen inputs (chosen after the attacker learns which randomness extraction algorithm you are using), then the BST03 scheme promises nothing. For instance, if you feed in timings of network packets, then even if you don't count them as providing any entropy, the mere act of feeding them into your randomness generator causes their theorems to be clearly inapplicable (since no matter what value of t you pick, the adversary can arrange to get more than t bits of freedom in the network packets he sends you).
So I'm not sure [BST03]'s theorems actually promise what you'd want.
On the other hand, if you want to take their constructions as providing some intuition or ideas about how one might build a randomness generator, while realizing that their theorems don't apply and there may be no useful guarantees that can be proven about such an approach, I don't have any objections to that view.
By the way, another example of work along these lines is
http://theory.lcs.mit.edu/~yevgen/ps/2-ext.ps
That paper is more technical and theoretically-oriented, so it might be harder to read and less immediately useful. It makes a strong assumption (that you have two sources that are independent -- i.e., totally uncorrelated), but the construction at the heart of their paper is pretty simple, which might be of interest.
Quoted 3 lines
Happily, it *appears* to confirm the value of the LFSR-based input mixing function. Although the suggested construction in section 4.1 is different, and I haven't seen if the proof can be extended.
Well, I don't know. I don't think I agree with that interpretation.
Let me give a little background about 2-universal hashing. There is a basic result about use of 2-universal hash functions, which says that if you choose the seed K truly at random, then you can use h_K(X) to extract uniform random bits from a non-uniform source X. (Indeed, you can even reveal K without harming the randomness of h_K(X).) The proof of this fact is usually known as the Leftover Hashing Lemma.
One of the standard constructions of a 2-universal hash function is as a LFSR-like scheme, where the seed K is used to select the feedback polynomial. But notice that it is critical that the feedback polynomial be chosen uniformly at random, in a way that is unpredictable to the attacker, and kept secret until you receive data from the source.
What /dev/random does is quite different from the idea of 2-universal hashing developed in the theory literature and recounted in [BST03]. /dev/random fixes a single feedback polynomial in advance, and publishes it for the world to see. The theorems about 2-universal hashing promise nothing about use of a LFSR with a fixed feedback polynomial.