Messages in this thread | | | From | (David Wagner) | Subject | Re: Fortuna | Date | Sun, 17 Apr 2005 00:36:29 +0000 (UTC) |
| |
linux 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/random hackers 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.
>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. - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
| |