lkml.org 
[lkml]   [2005]   [Apr]   [16]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    From
    SubjectRe: Fortuna
    Date
    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/

    \
     
     \ /
      Last update: 2005-04-17 02:42    [W:0.023 / U:151.248 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site