[lkml]   [2004]   [Sep]   [25]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
    SubjectRe: [PROPOSAL/PATCH] Fortuna PRNG in /dev/random
    > I was trying to point out a flaw in Ted's logic.  He said "we've recently
    > discoverd these hashes are weak because we found collsions. Current
    > /dev/random doesn't care about this."

    And he's exactly right. The only attack that would be vaguely relevant
    to /dev/random's use would be a (first) preimage attack, and even that's
    probably not helpful.

    There *is* no flaw in his logic. The attack we need to guard against
    is, given hash(x) and a (currently mostly linear) state mixing function
    mix(), one that would let you compute (partial information about)
    y[i+1] = hash(x[i+1]) from y[1] = hash(x[1]) ... y[i] = hash(x[i])
    where x[i] = mix(x[i-1]).

    Given that y[i] is much smaller than x[i], you'd need to put together
    a lot of them to derive something, and that's distinctly harder than
    a single-output preimage attack.

    > I certainly wasn't saying padding was a requirment. But I was trying to
    > point out that the SHA-1 implementaion crrently in /dev/random by design is
    > collision vulnerable. Collision resistance isn't a requirment for its
    > purposes obviously.

    No, it is, by design, 100% collision-resistant. An attacker neither
    sees nor controls the input x, so cannot use a collision attack.
    Thus, it's resistant to collisions in the same way that it's resistant
    to AIDS.

    [There's actually a flaw in my logic. I know Ted knows about it, because
    he implemented a specific defense in the /dev/random code against it; it's
    just not 100% information-theoretic ironclad. If anyone else can spot
    it, award yourself a clue point. But it's still not a plausible attack.]

    FURTHERMORE, even if an attacker *could* control the input, it's still
    exactly as collision resistant as unmodified SHA-1. Because it only
    accepts fixed-size input blocks, padding is unnecessary and irrelevant
    to security. Careful padding is ONLY required if you are working with

    The fact that collision resistance is not a security requirement is a
    third point.

    > Guess my pointing this out is a lost cause.

    In much the same way that pointing out that the earth is flat is a
    lost cause. If you want people to believe nonsense, you need to dress
    it up a lot and call it a religion.

    As for Ted's words:
    > Whether or not we should trust the design of something as
    > critical to the security of security applications as /dev/random to
    > someone who fails to grasp the difference between these two rather
    > basic issues is something I will leave to the others on LKML.

    Fortuna may be a good idea after all (I disagree, but I can imagine
    being persuaded otherwise), but it has a very bad advocate right now.
    Would anyone else like to pick up the torch?

    By the way, I'd like to repeat my earlier question: you say Fortuna ia
    well-regarded in crypto circles. Can you cite a single paper to back
    that conclusion? Name a single well-known cryptographer, other than
    the authors, who has looked at it in some detail?

    There might be one, but I don't know of any. I respect the authors
    enough to know that even they recognize that an algorithm's designers
    sometimes have blind spots.
    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to
    More majordomo info at
    Please read the FAQ at

     \ /
      Last update: 2005-03-22 14:06    [W:0.047 / U:5.728 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site