• George Spelvin's avatar
    random32: make prandom_u32() output unpredictable · c51f8f88
    George Spelvin authored
    Non-cryptographic PRNGs may have great statistical properties, but
    are usually trivially predictable to someone who knows the algorithm,
    given a small sample of their output.  An LFSR like prandom_u32() is
    particularly simple, even if the sample is widely scattered bits.
    
    It turns out the network stack uses prandom_u32() for some things like
    random port numbers which it would prefer are *not* trivially predictable.
    Predictability led to a practical DNS spoofing attack.  Oops.
    
    This patch replaces the LFSR with a homebrew cryptographic PRNG based
    on the SipHash round function, which is in turn seeded with 128 bits
    of strong random key.  (The authors of SipHash have *not* been consulted
    about this abuse of their algorithm.)  Speed is prioritized over security;
    attacks are rare, while performance is always wanted.
    
    Replacing all callers of prandom_u32() is the quick fix.
    Whether to reinstate a weaker PRNG for uses which can tolerate it
    is an open question.
    
    Commit f227e3ec ("random32: update the net random state on interrupt
    and activity") was an earlier attempt at a solution.  This patch replaces
    it.
    Reported-by: default avatarAmit Klein <aksecurity@gmail.com>
    Cc: Willy Tarreau <w@1wt.eu>
    Cc: Eric Dumazet <edumazet@google.com>
    Cc: "Jason A. Donenfeld" <Jason@zx2c4.com>
    Cc: Andy Lutomirski <luto@kernel.org>
    Cc: Kees Cook <keescook@chromium.org>
    Cc: Thomas Gleixner <tglx@linutronix.de>
    Cc: Peter Zijlstra <peterz@infradead.org>
    Cc: Linus Torvalds <torvalds@linux-foundation.org>
    Cc: tytso@mit.edu
    Cc: Florian Westphal <fw@strlen.de>
    Cc: Marc Plumb <lkml.mplumb@gmail.com>
    Fixes: f227e3ec ("random32: update the net random state on interrupt and activity")
    Signed-off-by: default avatarGeorge Spelvin <lkml@sdf.org>
    Link: https://lore.kernel.org/netdev/20200808152628.GA27941@SDF.ORG/
    [ willy: partial reversal of f227e3ec; moved SIPROUND definitions
      to prandom.h for later use; merged George's prandom_seed() proposal;
      inlined siprand_u32(); replaced the net_rand_state[] array with 4
      members to fix a build issue; cosmetic cleanups to make checkpatch
      happy; fixed RANDOM32_SELFTEST build ]
    Signed-off-by: default avatarWilly Tarreau <w@1wt.eu>
    c51f8f88
random.c 67.7 KB