random32: make prandom_u32() output unpredictable
A message that is not in the archive (sent off-list or not yet received): [email protected]
PATCH 1/1 random32: make prandom_u32() output unpredictable
From: George Spelvin <[email protected]>
commit c51f8f88d705e06bd696d7510aff22b33eb8e638 upstream.
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 f227e3ec3b5c ("random32: update the net random state on interrupt and activity") was an earlier attempt at a solution. This patch replaces it.
[ willy: partial reversal of f227e3ec3b5c; 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 ]
--- drivers/char/random.c | 1 - include/linux/prandom.h | 36 +++- kernel/time/timer.c | 7 - lib/random32.c | 462 +++++++++++++++++++++++++++++------------------- 4 files changed, 317 insertions(+), 189 deletions(-)
drivers/char/random.c +0 -1
@@ -1277,7 +1277,6 @@ void add_interrupt_randomness(int irq, int irq_flags)fast_mix (fast_pool);add_interrupt_bench (cycles); -this_cpu_add (net_rand_state.s1, fast_pool->pool[cycles &3 ]);if (unlikely (crng_init ==0 )) { if ((fast_pool->count >= 64) &&
include/linux/prandom.h +34 -2
@@ -16,12 +16,44 @@ void prandom_bytes(void *buf, size_t nbytes);void prandom_seed (u32 seed);void prandom_reseed_late (void ); +#if BITS_PER_LONG ==64 +/* +* The core SipHash round function. Each line can be executed in +* parallel given enough CPU resources. +*/ +#define PRND_SIPROUND (v0, v1, v2, v3) ( \ + v0 += v1, v1 = rol64(v1, 13), v2 += v3, v3 = rol64(v3, 16), \ + v1 ^= v0, v0 = rol64(v0, 32), v3 ^= v2, \ + v0 += v3, v3 = rol64(v3, 21), v2 += v1, v1 = rol64(v1, 17), \ + v3 ^= v0, v1 ^= v2, v2 = rol64(v2, 32) \ +) + +#define PRND_K0 (0x736f6d6570736575 ^ 0x6c7967656e657261) +#define PRND_K1 (0x646f72616e646f6d ^ 0x7465646279746573) + +#elif BITS_PER_LONG ==32 +/* +* On 32-bit machines, we use HSipHash, a reduced-width version of SipHash. +* This is weaker, but 32-bit machines are not used for high-traffic +* applications, so there is less output for an attacker to analyze. +*/ +#define PRND_SIPROUND (v0, v1, v2, v3) ( \ + v0 += v1, v1 = rol32(v1, 5), v2 += v3, v3 = rol32(v3, 8), \ + v1 ^= v0, v0 = rol32(v0, 16), v3 ^= v2, \ + v0 += v3, v3 = rol32(v3, 7), v2 += v1, v1 = rol32(v1, 13), \ + v3 ^= v0, v1 ^= v2, v2 = rol32(v2, 16) \ +) +#define PRND_K0 0x6c796765 +#define PRND_K1 0x74656462 + +#else +#error Unsupported BITS_PER_LONG +#endif +struct rnd_state {__u32 s1, s2, s3, s4; }; -DECLARE_PER_CPU(struct rnd_state, net_rand_state); -u32 prandom_u32_state (struct rnd_state *state);void prandom_bytes_state (struct rnd_state *state,void *buf,size_t nbytes);void prandom_seed_full_state (struct rnd_state __percpu *pcpu_state);
kernel/time/timer.c +0 -7
@@ -1743,13 +1743,6 @@ void update_process_times(int user_tick)scheduler_tick ();if (IS_ENABLED (CONFIG_POSIX_TIMERS ))run_posix_cpu_timers (); - -/* The current CPU might make use of net randoms without receiving IRQs -* to renew them often enough. Let's update the net_rand_state from a -* non-constant value that's not affine to the number of calls to make -* sure it's updated when there's some activity (we don't care in idle). -*/ -this_cpu_add (net_rand_state.s1,rol32 (jiffies,24 ) + user_tick); }/**
lib/random32.c +283 -179
503 lines not on this page · raw message
Signature · 1 line
2.9.0
PATCH 1/1 random32: make prandom_u32() output unpredictable
In reply to a message not in the archiveFrom: George Spelvin <[email protected]>
commit c51f8f88d705e06bd696d7510aff22b33eb8e638 upstream.
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 f227e3ec3b5c ("random32: update the net random state on interrupt and activity") was an earlier attempt at a solution. This patch replaces it.
[ willy: partial reversal of f227e3ec3b5c; 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 ]
--- drivers/char/random.c | 1 - include/linux/prandom.h | 36 +++- kernel/time/timer.c | 7 - lib/random32.c | 462 +++++++++++++++++++++++++++++------------------- 4 files changed, 317 insertions(+), 189 deletions(-)
drivers/char/random.c +0 -1
@@ -1330,7 +1330,6 @@ void add_interrupt_randomness(int irq, int irq_flags)fast_mix (fast_pool);add_interrupt_bench (cycles); -this_cpu_add (net_rand_state.s1, fast_pool->pool[cycles &3 ]);if (unlikely (crng_init ==0 )) { if ((fast_pool->count >= 64) &&
include/linux/prandom.h +34 -2
@@ -16,12 +16,44 @@ void prandom_bytes(void *buf, size_t nbytes);void prandom_seed (u32 seed);void prandom_reseed_late (void ); +#if BITS_PER_LONG ==64 +/* +* The core SipHash round function. Each line can be executed in +* parallel given enough CPU resources. +*/ +#define PRND_SIPROUND (v0, v1, v2, v3) ( \ + v0 += v1, v1 = rol64(v1, 13), v2 += v3, v3 = rol64(v3, 16), \ + v1 ^= v0, v0 = rol64(v0, 32), v3 ^= v2, \ + v0 += v3, v3 = rol64(v3, 21), v2 += v1, v1 = rol64(v1, 17), \ + v3 ^= v0, v1 ^= v2, v2 = rol64(v2, 32) \ +) + +#define PRND_K0 (0x736f6d6570736575 ^ 0x6c7967656e657261) +#define PRND_K1 (0x646f72616e646f6d ^ 0x7465646279746573) + +#elif BITS_PER_LONG ==32 +/* +* On 32-bit machines, we use HSipHash, a reduced-width version of SipHash. +* This is weaker, but 32-bit machines are not used for high-traffic +* applications, so there is less output for an attacker to analyze. +*/ +#define PRND_SIPROUND (v0, v1, v2, v3) ( \ + v0 += v1, v1 = rol32(v1, 5), v2 += v3, v3 = rol32(v3, 8), \ + v1 ^= v0, v0 = rol32(v0, 16), v3 ^= v2, \ + v0 += v3, v3 = rol32(v3, 7), v2 += v1, v1 = rol32(v1, 13), \ + v3 ^= v0, v1 ^= v2, v2 = rol32(v2, 16) \ +) +#define PRND_K0 0x6c796765 +#define PRND_K1 0x74656462 + +#else +#error Unsupported BITS_PER_LONG +#endif +struct rnd_state {__u32 s1, s2, s3, s4; }; -DECLARE_PER_CPU(struct rnd_state, net_rand_state); -u32 prandom_u32_state (struct rnd_state *state);void prandom_bytes_state (struct rnd_state *state,void *buf,size_t nbytes);void prandom_seed_full_state (struct rnd_state __percpu *pcpu_state);
kernel/time/timer.c +0 -7
@@ -1743,13 +1743,6 @@ void update_process_times(int user_tick)scheduler_tick ();if (IS_ENABLED (CONFIG_POSIX_TIMERS ))run_posix_cpu_timers (); - -/* The current CPU might make use of net randoms without receiving IRQs -* to renew them often enough. Let's update the net_rand_state from a -* non-constant value that's not affine to the number of calls to make -* sure it's updated when there's some activity (we don't care in idle). -*/ -this_cpu_add (net_rand_state.s1,rol32 (jiffies,24 ) + user_tick); }/**
lib/random32.c +283 -179
503 lines not on this page · raw message
Signature · 1 line
2.9.0
PATCH 1/1 random32: make prandom_u32() output unpredictable
In reply to a message not in the archiveFrom: George Spelvin <[email protected]>
commit c51f8f88d705e06bd696d7510aff22b33eb8e638 upstream.
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 f227e3ec3b5c ("random32: update the net random state on interrupt and activity") was an earlier attempt at a solution. This patch replaces it.
[ willy: partial reversal of f227e3ec3b5c; 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 ]
--- drivers/char/random.c | 1 - include/linux/prandom.h | 36 +++- kernel/time/timer.c | 7 - lib/random32.c | 462 +++++++++++++++++++++++++++++------------------- 4 files changed, 317 insertions(+), 189 deletions(-)
drivers/char/random.c +0 -1
@@ -1257,7 +1257,6 @@ void add_interrupt_randomness(int irq, int irq_flags)fast_mix (fast_pool);add_interrupt_bench (cycles); -this_cpu_add (net_rand_state.s1, fast_pool->pool[cycles &3 ]);if (unlikely (crng_init ==0 )) { if ((fast_pool->count >= 64) &&
include/linux/prandom.h +34 -2
@@ -16,12 +16,44 @@ void prandom_bytes(void *buf, size_t nbytes);void prandom_seed (u32 seed);void prandom_reseed_late (void ); +#if BITS_PER_LONG ==64 +/* +* The core SipHash round function. Each line can be executed in +* parallel given enough CPU resources. +*/ +#define PRND_SIPROUND (v0, v1, v2, v3) ( \ + v0 += v1, v1 = rol64(v1, 13), v2 += v3, v3 = rol64(v3, 16), \ + v1 ^= v0, v0 = rol64(v0, 32), v3 ^= v2, \ + v0 += v3, v3 = rol64(v3, 21), v2 += v1, v1 = rol64(v1, 17), \ + v3 ^= v0, v1 ^= v2, v2 = rol64(v2, 32) \ +) + +#define PRND_K0 (0x736f6d6570736575 ^ 0x6c7967656e657261) +#define PRND_K1 (0x646f72616e646f6d ^ 0x7465646279746573) + +#elif BITS_PER_LONG ==32 +/* +* On 32-bit machines, we use HSipHash, a reduced-width version of SipHash. +* This is weaker, but 32-bit machines are not used for high-traffic +* applications, so there is less output for an attacker to analyze. +*/ +#define PRND_SIPROUND (v0, v1, v2, v3) ( \ + v0 += v1, v1 = rol32(v1, 5), v2 += v3, v3 = rol32(v3, 8), \ + v1 ^= v0, v0 = rol32(v0, 16), v3 ^= v2, \ + v0 += v3, v3 = rol32(v3, 7), v2 += v1, v1 = rol32(v1, 13), \ + v3 ^= v0, v1 ^= v2, v2 = rol32(v2, 16) \ +) +#define PRND_K0 0x6c796765 +#define PRND_K1 0x74656462 + +#else +#error Unsupported BITS_PER_LONG +#endif +struct rnd_state {__u32 s1, s2, s3, s4; }; -DECLARE_PER_CPU(struct rnd_state, net_rand_state); -u32 prandom_u32_state (struct rnd_state *state);void prandom_bytes_state (struct rnd_state *state,void *buf,size_t nbytes);void prandom_seed_full_state (struct rnd_state __percpu *pcpu_state);
kernel/time/timer.c +0 -7
@@ -1655,13 +1655,6 @@ void update_process_times(int user_tick)scheduler_tick ();if (IS_ENABLED (CONFIG_POSIX_TIMERS ))run_posix_cpu_timers (p); - -/* The current CPU might make use of net randoms without receiving IRQs -* to renew them often enough. Let's update the net_rand_state from a -* non-constant value that's not affine to the number of calls to make -* sure it's updated when there's some activity (we don't care in idle). -*/ -this_cpu_add (net_rand_state.s1,rol32 (jiffies,24 ) + user_tick); }/**
lib/random32.c +283 -179
503 lines not on this page · raw message
Signature · 1 line
2.9.0
PATCH 1/1 random32: make prandom_u32() output unpredictable
In reply to a message not in the archiveFrom: George Spelvin <[email protected]>
commit c51f8f88d705e06bd696d7510aff22b33eb8e638 upstream.
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 f227e3ec3b5c ("random32: update the net random state on interrupt and activity") was an earlier attempt at a solution. This patch replaces it.
[ willy: partial reversal of f227e3ec3b5c; 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 ]
--- drivers/char/random.c | 1 - include/linux/prandom.h | 36 +++- kernel/time/timer.c | 7 - lib/random32.c | 462 +++++++++++++++++++++++++++++------------------- 4 files changed, 317 insertions(+), 189 deletions(-)
drivers/char/random.c +0 -1
@@ -1211,7 +1211,6 @@ void add_interrupt_randomness(int irq, int irq_flags)fast_mix (fast_pool);add_interrupt_bench (cycles); -this_cpu_add (net_rand_state.s1, fast_pool->pool[cycles &3 ]);if (unlikely (crng_init ==0 )) { if ((fast_pool->count >= 64) &&
include/linux/prandom.h +34 -2
@@ -16,12 +16,44 @@ void prandom_bytes(void *buf, size_t nbytes);void prandom_seed (u32 seed);void prandom_reseed_late (void ); +#if BITS_PER_LONG ==64 +/* +* The core SipHash round function. Each line can be executed in +* parallel given enough CPU resources. +*/ +#define PRND_SIPROUND (v0, v1, v2, v3) ( \ + v0 += v1, v1 = rol64(v1, 13), v2 += v3, v3 = rol64(v3, 16), \ + v1 ^= v0, v0 = rol64(v0, 32), v3 ^= v2, \ + v0 += v3, v3 = rol64(v3, 21), v2 += v1, v1 = rol64(v1, 17), \ + v3 ^= v0, v1 ^= v2, v2 = rol64(v2, 32) \ +) + +#define PRND_K0 (0x736f6d6570736575 ^ 0x6c7967656e657261) +#define PRND_K1 (0x646f72616e646f6d ^ 0x7465646279746573) + +#elif BITS_PER_LONG ==32 +/* +* On 32-bit machines, we use HSipHash, a reduced-width version of SipHash. +* This is weaker, but 32-bit machines are not used for high-traffic +* applications, so there is less output for an attacker to analyze. +*/ +#define PRND_SIPROUND (v0, v1, v2, v3) ( \ + v0 += v1, v1 = rol32(v1, 5), v2 += v3, v3 = rol32(v3, 8), \ + v1 ^= v0, v0 = rol32(v0, 16), v3 ^= v2, \ + v0 += v3, v3 = rol32(v3, 7), v2 += v1, v1 = rol32(v1, 13), \ + v3 ^= v0, v1 ^= v2, v2 = rol32(v2, 16) \ +) +#define PRND_K0 0x6c796765 +#define PRND_K1 0x74656462 + +#else +#error Unsupported BITS_PER_LONG +#endif +struct rnd_state {__u32 s1, s2, s3, s4; }; -DECLARE_PER_CPU(struct rnd_state, net_rand_state); -u32 prandom_u32_state (struct rnd_state *state);void prandom_bytes_state (struct rnd_state *state,void *buf,size_t nbytes);void prandom_seed_full_state (struct rnd_state __percpu *pcpu_state);
kernel/time/timer.c +0 -7
@@ -1636,13 +1636,6 @@ void update_process_times(int user_tick)#endif scheduler_tick ();run_posix_cpu_timers (p); - -/* The current CPU might make use of net randoms without receiving IRQs -* to renew them often enough. Let's update the net_rand_state from a -* non-constant value that's not affine to the number of calls to make -* sure it's updated when there's some activity (we don't care in idle). -*/ -this_cpu_add (net_rand_state.s1,rol32 (jiffies,24 ) + user_tick); }/**
lib/random32.c +283 -179
503 lines not on this page · raw message
Signature · 1 line
2.9.0
PATCH 1/1 random32: make prandom_u32() output unpredictable
In reply to a message not in the archiveFrom: George Spelvin <[email protected]>
commit c51f8f88d705e06bd696d7510aff22b33eb8e638 upstream.
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 f227e3ec3b5c ("random32: update the net random state on interrupt and activity") was an earlier attempt at a solution. This patch replaces it.
[ willy: partial reversal of f227e3ec3b5c; 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 ]
--- drivers/char/random.c | 1 - include/linux/prandom.h | 36 +++- kernel/time/timer.c | 7 - lib/random32.c | 462 +++++++++++++++++++++++++++++------------------- 4 files changed, 317 insertions(+), 189 deletions(-)
drivers/char/random.c +0 -1
@@ -1246,7 +1246,6 @@ void add_interrupt_randomness(int irq, int irq_flags)fast_mix (fast_pool);add_interrupt_bench (cycles); -this_cpu_add (net_rand_state.s1, fast_pool->pool[cycles &3 ]);if (unlikely (crng_init ==0 )) { if ((fast_pool->count >= 64) &&
include/linux/prandom.h +34 -2
@@ -16,12 +16,44 @@ void prandom_bytes(void *buf, size_t nbytes);void prandom_seed (u32 seed);void prandom_reseed_late (void ); +#if BITS_PER_LONG ==64 +/* +* The core SipHash round function. Each line can be executed in +* parallel given enough CPU resources. +*/ +#define PRND_SIPROUND (v0, v1, v2, v3) ( \ + v0 += v1, v1 = rol64(v1, 13), v2 += v3, v3 = rol64(v3, 16), \ + v1 ^= v0, v0 = rol64(v0, 32), v3 ^= v2, \ + v0 += v3, v3 = rol64(v3, 21), v2 += v1, v1 = rol64(v1, 17), \ + v3 ^= v0, v1 ^= v2, v2 = rol64(v2, 32) \ +) + +#define PRND_K0 (0x736f6d6570736575 ^ 0x6c7967656e657261) +#define PRND_K1 (0x646f72616e646f6d ^ 0x7465646279746573) + +#elif BITS_PER_LONG ==32 +/* +* On 32-bit machines, we use HSipHash, a reduced-width version of SipHash. +* This is weaker, but 32-bit machines are not used for high-traffic +* applications, so there is less output for an attacker to analyze. +*/ +#define PRND_SIPROUND (v0, v1, v2, v3) ( \ + v0 += v1, v1 = rol32(v1, 5), v2 += v3, v3 = rol32(v3, 8), \ + v1 ^= v0, v0 = rol32(v0, 16), v3 ^= v2, \ + v0 += v3, v3 = rol32(v3, 7), v2 += v1, v1 = rol32(v1, 13), \ + v3 ^= v0, v1 ^= v2, v2 = rol32(v2, 16) \ +) +#define PRND_K0 0x6c796765 +#define PRND_K1 0x74656462 + +#else +#error Unsupported BITS_PER_LONG +#endif +struct rnd_state {__u32 s1, s2, s3, s4; }; -DECLARE_PER_CPU(struct rnd_state, net_rand_state); -u32 prandom_u32_state (struct rnd_state *state);void prandom_bytes_state (struct rnd_state *state,void *buf,size_t nbytes);void prandom_seed_full_state (struct rnd_state __percpu *pcpu_state);
kernel/time/timer.c +0 -7
@@ -1596,13 +1596,6 @@ void update_process_times(int user_tick)scheduler_tick ();if (IS_ENABLED (CONFIG_POSIX_TIMERS ))run_posix_cpu_timers (p); - -/* The current CPU might make use of net randoms without receiving IRQs -* to renew them often enough. Let's update the net_rand_state from a -* non-constant value that's not affine to the number of calls to make -* sure it's updated when there's some activity (we don't care in idle). -*/ -this_cpu_add (net_rand_state.s1,rol32 (jiffies,24 ) + user_tick); }/**
lib/random32.c +283 -179
503 lines not on this page · raw message
Signature · 1 line
2.9.0
PATCH 1/1 random32: make prandom_u32() output unpredictable
In reply to a message not in the archiveFrom: George Spelvin <[email protected]>
commit c51f8f88d705e06bd696d7510aff22b33eb8e638 upstream.
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 f227e3ec3b5c ("random32: update the net random state on interrupt and activity") was an earlier attempt at a solution. This patch replaces it.
[ willy: partial reversal of f227e3ec3b5c; 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 ]
--- drivers/char/random.c | 2 - include/linux/prandom.h | 36 +++- kernel/time/timer.c | 7 - lib/random32.c | 463 +++++++++++++++++++++++++++++------------------- 4 files changed, 317 insertions(+), 191 deletions(-)
drivers/char/random.c +0 -2
@@ -678,7 +678,6 @@ static void credit_entropy_bits(struct entropy_store *r, int nbits) r->initialized =1 ; r->entropy_total =0 ;if (r == &nonblocking_pool) { -prandom_reseed_late ();process_random_ready_list ();wake_up_all (&urandom_init_wait);pr_notice ("random: %s pool is initialized\n" , r->name);
@@ -923,7 +922,6 @@ void add_interrupt_randomness(int irq, int irq_flags)fast_mix (fast_pool);add_interrupt_bench (cycles); -this_cpu_add (net_rand_state.s1, fast_pool->pool[cycles &3 ]);if ((fast_pool->count <64 ) && !time_after (now, fast_pool->last +HZ ))
include/linux/prandom.h +34 -2
@@ -16,12 +16,44 @@ void prandom_bytes(void *buf, size_t nbytes);void prandom_seed (u32 seed);void prandom_reseed_late (void ); +#if BITS_PER_LONG ==64 +/* +* The core SipHash round function. Each line can be executed in +* parallel given enough CPU resources. +*/ +#define PRND_SIPROUND (v0, v1, v2, v3) ( \ + v0 += v1, v1 = rol64(v1, 13), v2 += v3, v3 = rol64(v3, 16), \ + v1 ^= v0, v0 = rol64(v0, 32), v3 ^= v2, \ + v0 += v3, v3 = rol64(v3, 21), v2 += v1, v1 = rol64(v1, 17), \ + v3 ^= v0, v1 ^= v2, v2 = rol64(v2, 32) \ +) + +#define PRND_K0 (0x736f6d6570736575 ^ 0x6c7967656e657261) +#define PRND_K1 (0x646f72616e646f6d ^ 0x7465646279746573) + +#elif BITS_PER_LONG ==32 +/* +* On 32-bit machines, we use HSipHash, a reduced-width version of SipHash. +* This is weaker, but 32-bit machines are not used for high-traffic +* applications, so there is less output for an attacker to analyze. +*/ +#define PRND_SIPROUND (v0, v1, v2, v3) ( \ + v0 += v1, v1 = rol32(v1, 5), v2 += v3, v3 = rol32(v3, 8), \ + v1 ^= v0, v0 = rol32(v0, 16), v3 ^= v2, \ + v0 += v3, v3 = rol32(v3, 7), v2 += v1, v1 = rol32(v1, 13), \ + v3 ^= v0, v1 ^= v2, v2 = rol32(v2, 16) \ +) +#define PRND_K0 0x6c796765 +#define PRND_K1 0x74656462 + +#else +#error Unsupported BITS_PER_LONG +#endif +struct rnd_state {__u32 s1, s2, s3, s4; }; -DECLARE_PER_CPU(struct rnd_state, net_rand_state); -u32 prandom_u32_state (struct rnd_state *state);void prandom_bytes_state (struct rnd_state *state,void *buf,size_t nbytes);void prandom_seed_full_state (struct rnd_state __percpu *pcpu_state);
kernel/time/timer.c +0 -7
@@ -1432,13 +1432,6 @@ void update_process_times(int user_tick)#endif scheduler_tick ();run_posix_cpu_timers (p); - -/* The current CPU might make use of net randoms without receiving IRQs -* to renew them often enough. Let's update the net_rand_state from a -* non-constant value that's not affine to the number of calls to make -* sure it's updated when there's some activity (we don't care in idle). -*/ -this_cpu_add (net_rand_state.s1,rol32 (jiffies,24 ) + user_tick); }/*
lib/random32.c +283 -180
504 lines not on this page · raw message
Signature · 1 line
2.9.0