[lkml]   [2011]   [Aug]   [20]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
    SubjectRe: [PATCH 0/2] Improve sequence number generation.
    (Apologies if I'm obverbroad on the Cc: list.)

    I've beeen concerned by the recent change to initial sequence number
    generation, from a time-varying 24-bit hash of the endpoint addresses
    to a fixed 32-bit hash.

    First of all, my apologies that I didn't see this when it was posted
    for comment August 7; I only noticed when I tried to merge some local
    experiments with -stable and found a conflict in drivers/random.c.

    My concern primarily is that the local secret used to compute the hashes
    is generated very early in the boot sequence, before any significant
    amount of entropy is accumulated. And since it's constant for the uptime
    of the machine, an attacker has a considerable length of time to find
    and explot the secret value.

    While the increase to 32 bits is definitely desirable, and defends
    against a much less sophisticated attack, I'm concerned that this is a
    case of robbing Peter to pay Paul.

    Trying to improve this, I'm working in a few directions:
    1) Postpone the seeding as late in the boot process as possible.
    It's quite low-overhead to generate it only when the first TCP
    connection is made, which hopefully is preceded by running
    init and at least a little bit of device driver activity.

    2) Do *both*: Use a fixed 32-bit offset *plus* a time-varing one.
    They can be added together and provide the security advantages of
    both. The only cost is having to compute two hashes per SYN.

    The main problem here is coming up with a hash function fast enough
    that computing both hashes is no slower than one MD5 invocation.

    3) Extend the 24-bit time-varying hash to a 28-bit one.
    This can cause the sequence numbers to wrap in 7/8 of the time
    they would with a fixed offset, but that doesn't seem too bad.
    (That's worst case; it's a triangular distribution centered
    on 15/16.)

    It's relatively easy to hash quickly with 15 64-bit registers, but doing
    it with 7 32-bit registers is decidedly trickier.

    I'm currently playing with a 36-round 6x32-bit variant of the SHA-3
    candidate Skein. I haven't run the genetic algorithm to select optimal
    rotation constants, but they shouldn't affect the timing.
    (I'm also going to ask the Skein team to look over my work.)

    So far, it is notably faster than MD5 (89 ns/hash vs. 148 on a 2.5 GHz
    Phenom), as well as being much smaller (383 bytes as opposed to 1951 for
    the core transform). One limitation is that it only hashes 6 32-bit
    words per transform. Thus, IPv6 would need to use two iterations,
    or go back to MD5.

    As mentioned, we can use a different algorithm for 64-bit processors.
    Or even 32-bit ones with more registers. So the speed problem only
    exists for IPv6 on 32-bit x86.

    (For example, on a 64-bit processor, two parallel MD5 tranforms
    can be computed in barely more time than one.)

    A few questions, all related to performance requirements:
    * Should I worry about 32-bit x86 performance at all, since it's
    pretty unlikely that a 32-bit machine will be running traffic levels
    (1000+ connections/sec) where it matters?
    * Should I worry about 32-bit IPv6 performance, since that's even more
    unlikely to be running heavy loads on 32-bit hardware?
    * If yes, is this fast enough to be acceptable, or do I need to work
    harder to find more speed?

    Willy, apparently you did some benchmarking of various hash functions.
    Is that data available somewhere? Even if not, just a brief description
    of the methodology and assumptions would help to make sure I'm measuring
    in a reasonable way.

     \ /
      Last update: 2011-08-21 01:43    [W:0.022 / U:10.268 seconds]
    ©2003-2017 Jasper Spaans. hosted at Digital OceanAdvertise on this site