lkml.org 
[lkml]   [2005]   [Apr]   [14]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    Date
    From
    SubjectRe: Fortuna
    Just to refersh everyone's memory as to the strengths and weaknesses
    of Fortuna...

    First, a reminder that the design goal of /dev/random proper is
    information-theoretic security. That is, it should be secure against
    an attacker with infinite computational power. If you want a weaker
    guarantee, use /dev/urandom.

    I've heard a suggestion that something like /dev/urandom, but which blocks
    until it has received a minimum amount of seed material at least once,
    would be a nice thing. So boot-time crypto initialization can stall
    until it has achieved a minimum level of security.

    The minimum could be measured two ways:
    - Some reasonable default, like 256 bits, or
    - (clever) the size of the read() request, which is presumably the
    key size that the user needs. This might be too subtle to explain
    to programmers, though.


    Anyway, there are two main parts to Fortuna. The central "random pool",
    and the round-robin sub-pool system for reseeding the main pool.

    Fortuna uses a "small pool, trust the crypto" central pool.
    /dev/random uses a large pool that is deliberately designed to be
    robust against failure of the crypto primitives. Indeed, the basic
    design just uses it as a uniform hash. Cryptographic strength is
    irrelevant to the information-theoretic guarantees.

    This portion of Fortuna is at odds with /dev/random's design goals,
    but it could be replaced easily enough. It's not the clever part.


    The "neat idea" in Fortuna is the round-robin sub-pool seeding technique,
    which attempts to avoid the entire issue of entropy estimation.

    Now, for information-theoretic guarantees, entropy measurement is
    *required*. You cannot be information-theoretic secure unless you
    have received more seed entropy than you have produced output.

    However, Fortuna has a different philosophy. This difference is why
    Fortuna will NEVER be an "exact drop-in replacement" for /dev/random,
    although it can do the job for /dev/urandom. There are important
    user-visible differences in the guarantees it makes. Someone may
    argue that the difference is immaterial in practice, but existence of
    a difference is indisputable.


    It tries to divide up the seed entropy into sub-pools and hold off
    re-seeding the main pool until the sub-pool has accumulated enough entropy
    to cause "catastrophic reseeding" of the main pool, adding enough entropy
    at once that someone who had captured the prior state of the main pool
    would not be able (due to computational limits and the one-way nature
    of the pool output function) to reverse-engineer the post-state.

    The way it schedules the additions, it doesn't know *which* re-seed of
    the main pool will be catastrophic, but it knows that it will be within
    a factor of 64 of the shortest time that's possible.


    However, it possible to come up with some pathological entropy sources
    for which the standard Fortuna design completely fails to achieve that
    goal.

    So Fortuna would be helped by some better understanding of what exactly
    makes it fail, so the discussion could move to whether real-world
    seed sources have those properties.

    But until that understanding is gained, Fortuna is questionable.


    Appendix: how to "break" Fortuna.

    First, the standard assumptions: the "attacker" can collect arbitrary
    amounts of RNG output at any time, and can see all operations on the
    pool except for the value of the seed material.

    In particular, if the attacker's uncertainty about the pool's state
    is small, she can collect enough output to distinguish all the
    possibilities and attempt a brute-force computation to recover the
    unknown state information.

    Finally, assume the attacker knows the full initial state of the
    generator.

    For a classic 32-subpool Fortuna, let the seed be a 32-bit integer.
    Every time a new seed is produced, shift the previous value and insert
    a fresh random bit. Thus, the seed does deliver 1 bit of entropy
    per sample, which should make for a secure source.

    If you want to be cruel, encrypt that seed with a strong cipher known
    only to the attacker before producing output. That keeps the nature
    of the seed from the Fortuna implementation.

    Anyway, every 32 cycles, a seed word is added to subpool 0, which is then
    immediately added to the main pool. An attacker who knows the prior
    state of the main pool can attempt a brute-force search for the 32 bits
    of the seed word in a reasonable period of time.

    Because of the shifting property, an attacker who knows the seeds added
    to pool 0 at times t and t+32 can also deduce, with perfect accuracy,
    the seeds added to the other 31 pools at times t+1 through t+31.

    The result being that the other subpools, which are supposed to be hoarding
    secret information unknown to the attacker, are actually being seeded with
    bits known to the attacker.

    The ultimate result is that catastrohpic reseeding never takes place.
    If we could somehow separate the "fresh" entropy in the input samples
    from the "holdover" material, the problem would go away, but that's
    an entropy measurement problem!

    Until this cloud is dissipated by further analysis, it's not possible to
    say "this is shiny and new and better; they's use it!" in good conscience.
    -
    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-14 16:19    [W:6.611 / U:0.000 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site