[RFC PATCH v1 00/52] Audit kernel random number use

[George Spelvin <lkml@SDF.ORG>]

Sorry for the long Cc list, but this is a treewide cleanup and
I wanted to send this cover letter to everyone.  Individual patches
are Cc: the relevant maintainers, and the whole series can be found
on linux-kernel@vger.

The original itch I wanted to scratch was fixing the numerous
instances of "get_random_u32() % range" and "prandom_u32() % range"
in the kernel.  % is fast to type but slow to execute: even in the
optimized special case that the range is a compile-time constant,
the modulo requires two multiplies to evaluate.

prandom_u32_max() works better; it used reciprocal_scale(), which
ends up doing (u64)prandom_u32() * range >> 32".

This is not only faster and less code, the random numbers are
more uniform.  When the range is not a power of 2, some outputs are
generated more often than others.  With the modulo technique, those
are all the outputs less than 0x100000000 % range.  When multiplying,
the overrepresented outputs are at least spread uniformly across the
possible outputs.

The multiplicative technique can also be easily extended to
generate perfectly uniform random numbers (by detecting an
overrepresented case and looping if it happens) if desired.


But as I started in on the project, I kept finding more things
that needed fixing.  This patch series is what I have ready at the moment.

I could use feedback on individual patches, but also the series as
a whole.  How should it be broken up?  How should it be submitted?

Perhaps, with this series as motivation, merge the random.[ch]
changes, and then do the rest piecemeal?

The series (currently based on v5.5.10) consists of:

01..07: These are various bugs I came across while looking for code to
    replace.  They are independent of the rest of the series, but related.
08: (EXT4) This is a bit of code I'm not sure about.  Sometimes a
    random number is used, and sometimes a hash is used as input to the
    range reduction.  Does the modulo have to be preserved for backward
    compatibility?
09: If the range is a compile-time constant power of 2, then gcc optimizes
    the modulo better than the multiply in prandom_u32_max().  This patch
    fixes that, so that you don't have to worry about the numerical
    value of the range; prandom_u32_max() is always as good or better.
10: This is a very optional patch, for disucssion.  When the range is
    a compile-time constant, making the output of prandom_u32_max()
    perfectly uniform is quite cheap.  This adds the extra test
    and retry loop to that common special case.  Worth bothering?
11: This is the big one (which probably needs to be broken up by
    subsystem), doing a treewide replacement of prandom_u32() % range,
    when the range is not obviously a power of 2.
12: The same, for prandom_u32_state()
13..19: These are patches that were pulled out of the previous two
    because they're involve some more complex code changes.
20..23: Changes to the prandom_u32() generator itself.  Including
    switching to a stronger & faster PRNG.
24..35: Places where crypto-strength get_random_* was used, but only
    pseudorandom numbers are justified.  Examples are:
    - self-test code
    - Seeding other PRNGs
    - random backoffs and timeouts
36..38: Improvements to the batched entropy pool in random.c.
39: (ARM64) Avoid the need for a temporary buffer (and subsequent wiping)
    when transferring random seed material across kexec.
40..44: Replace get_random_bytes() with get_random_{u32,u64,long},
    where the slightly weaker security guarantees of the latter
    suffice.
45: Add a get_random_max() function, using batched crypto-quality
    entropy.  This is more complex than prandom_u32_max()
    because it has to support 64-bit results and is perfectly
    uniform in all cases.
46..49: Use get_random_max in various applications
50: Is the first part of the next phase.  This adds a function to
    fill a byte buffer from the batched entropy buffer, a drop-in
    replacement for get_random_bytes().  I'm particularly seeking
    comment on what this function, with its different security
    guarantees, should be called.  One option I'm considering is
    to name it get_random_bytes, and move the (relatively few)
    call sites that really need unbacktrackable random numbers
    to another name like get_secret_bytes().

George Spelvin (50):
  IB/qib: Delete struct qib_ivdev.qp_rnd
  lib/fault-inject.c: Fix off-by-one error in probability
  fault-inject: Shrink struct fault_attr
  batman-adv: fix batadv_nc_random_weight_tq
  net/rds/bind.c: Use prandom_u32_max()
  ubi/debug: Optimize computation of odds
  mm/slab: Use simpler Fisher-Yates shuffle
  fs/ext4/ialloc.c: Replace % with reciprocal_scale() TO BE VERIFIED
  <linux/random.h> prandom_u32_max() for power-of-2 ranges
  <linux/random.h> Make prandom_u32_max() exact for constant ranges
  Treewide: Extirpate "prandom_u32() % range"
  Treewide: Extirpate prandom_u32_state(rnd) % range
  Avoid some useless msecs/jiffies conversions
  crypto/testmgr.c: use prandom_u32_max() & prandom_bytes()
  drivers/block/drbd/drbd_main: fix _drbd_fault_random()
  include/net/red.h: Simplify red_random() TO BE VERIFIED
  net/802/{garp,mrp}.c: Use prandom_u32_max instead of manual equivalent
  net/ipv6/addrconf.c: Use prandom_u32_max for rfc3315 backoff time computation
  net/sched/sch_netem: Simplify get_crandom
  lib/random32: Move prandom_warmup() inside prandom_seed_early()
  lib/random32.c: Change to SFC32 PRNG
  lib/random32: Use random_ready_callback for seeding.
  prandom_seed_state(): Change to 32-bit seed type.
  crypto4xx_core: Use more appropriate seed for PRNG
  HID: hid-lg: We only need pseudorandom bytes for the address
  drivers/nfc/nfcsim: use prandom_32() for time delay
  drivers/s390/scsi/zcsp_fc.c: Use prandom_u32_max() for backoff
  drivers/target/iscsi: Replace O(n^2) randomization
  fs/ocfs2/journal: Use prandom_u32() and not /dev/random for timeout
  kernel/locking/test-ww_mutex.c: Use cheaper prandom_u32_max()
  lib/nodemask.c: Use cheaper prandom_u32_max() in node_random()
  lib/test*.c: Use prandom_u32_max()
  lib/test_vmalloc.c: Use pseudorandom numbers
  mm/slub.c: Use cheaper prandom source in shuffle_freelist
  USB: serial: iuu_phoenix: Use pseudorandom for xmas mode
  random: Merge batched entropy buffers
  random: Simplify locking of batched entropy
  random: use chacha_permute() directly
  arm: kexec_file: Avoid temp buffer for RNG seed
  arch/*/include/asm/stackprotector.h: Use get_random_canary() consistently
  drivers/block/drbd/drbd_nl.c: Use get_random_u64()
  drivers/ininiband: Use get_random_u32()
  drivers/isdn: Use get_random_u32()
  arm64: ptr auth: Use get_random_u64 instead of _bytes
  random: add get_random_max() function
  mm/shuffle.c: use get_random_max()
  kernel/bpf/core.c: Use get_random_max32()
  arch/arm/kernel/process.c: Use get_random_max32() for sigpage_addr()
  arch/x86/entry/vdso/vma.c: Use get_random_max32() for vdso_addr
  random: add get_random_nonce()

 arch/arm/include/asm/stackprotector.h         |   9 +-
 arch/arm/kernel/process.c                     |   2 +-
 arch/arm64/include/asm/pointer_auth.h         |  20 +-
 arch/arm64/include/asm/stackprotector.h       |   8 +-
 arch/arm64/kernel/machine_kexec_file.c        |   8 +-
 arch/arm64/kernel/pointer_auth.c              |  62 +-
 arch/mips/include/asm/stackprotector.h        |   7 +-
 arch/powerpc/include/asm/stackprotector.h     |   6 +-
 arch/sh/include/asm/stackprotector.h          |   8 +-
 arch/x86/entry/vdso/vma.c                     |   2 +-
 arch/x86/include/asm/stackprotector.h         |   4 +-
 arch/x86/mm/pageattr-test.c                   |   4 +-
 arch/xtensa/include/asm/stackprotector.h      |   7 +-
 crypto/testmgr.c                              |  21 +-
 drivers/block/drbd/drbd_main.c                |  37 +-
 drivers/block/drbd/drbd_nl.c                  |   4 +-
 drivers/char/random.c                         | 581 +++++++++++++-----
 drivers/crypto/amcc/crypto4xx_core.c          |   7 +-
 drivers/crypto/chelsio/chtls/chtls_io.c       |   4 +-
 drivers/gpu/drm/i915/selftests/i915_gem_gtt.c |   2 +-
 drivers/gpu/drm/i915/selftests/scatterlist.c  |   4 +-
 drivers/hid/hid-lg.c                          |   2 +-
 drivers/infiniband/core/cm.c                  |   2 +-
 drivers/infiniband/core/cma.c                 |   5 +-
 drivers/infiniband/core/sa_query.c            |   2 +-
 drivers/infiniband/hw/cxgb4/id_table.c        |   4 +-
 drivers/infiniband/hw/i40iw/i40iw_verbs.c     |   2 +-
 drivers/infiniband/hw/qib/qib_verbs.c         |   2 -
 drivers/infiniband/hw/qib/qib_verbs.h         |   1 -
 drivers/infiniband/sw/siw/siw_mem.c           |   9 +-
 drivers/infiniband/sw/siw/siw_verbs.c         |   2 +-
 drivers/infiniband/ulp/srp/ib_srp.c           |   3 +-
 drivers/isdn/mISDN/tei.c                      |   5 +-
 drivers/mmc/core/core.c                       |   4 +-
 drivers/mtd/nand/raw/nandsim.c                |   4 +-
 drivers/mtd/tests/mtd_nandecctest.c           |  10 +-
 drivers/mtd/tests/stresstest.c                |  15 +-
 drivers/mtd/ubi/debug.c                       |   2 +-
 drivers/mtd/ubi/debug.h                       |   6 +-
 drivers/net/ethernet/broadcom/cnic.c          |   3 +-
 .../broadcom/brcm80211/brcmfmac/p2p.c         |   2 +-
 .../net/wireless/intel/iwlwifi/mvm/mac-ctxt.c |   2 +-
 drivers/nfc/nfcsim.c                          |   3 +-
 drivers/s390/scsi/zfcp_fc.c                   |   2 +-
 drivers/scsi/fcoe/fcoe_ctlr.c                 |  10 +-
 drivers/scsi/qedi/qedi_main.c                 |   2 +-
 .../target/iscsi/iscsi_target_seq_pdu_list.c  |  72 +--
 drivers/usb/serial/iuu_phoenix.c              |   7 +-
 fs/ceph/inode.c                               |   2 +-
 fs/ceph/mdsmap.c                              |   2 +-
 fs/ext2/ialloc.c                              |   3 +-
 fs/ext4/ialloc.c                              |   5 +-
 fs/ext4/super.c                               |   8 +-
 fs/ocfs2/journal.c                            |   7 +-
 fs/ubifs/debug.c                              |  11 +-
 fs/ubifs/lpt_commit.c                         |  12 +-
 fs/xfs/xfs_error.c                            |   2 +-
 include/crypto/chacha.h                       |   1 +
 include/linux/fault-inject.h                  |   4 +-
 include/linux/random.h                        | 279 ++++++++-
 include/net/red.h                             |  22 +-
 kernel/bpf/core.c                             |   4 +-
 kernel/locking/test-ww_mutex.c                |  23 +-
 lib/crypto/chacha.c                           |   2 +-
 lib/fault-inject.c                            |  12 +-
 lib/find_bit_benchmark.c                      |   4 +-
 lib/interval_tree_test.c                      |   9 +-
 lib/nodemask.c                                |   2 +-
 lib/random32.c                                | 558 +++++++++--------
 lib/rbtree_test.c                             |   2 +-
 lib/reed_solomon/test_rslib.c                 |   4 +-
 lib/sbitmap.c                                 |   7 +-
 lib/test-string_helpers.c                     |   2 +-
 lib/test_bpf.c                                |   2 +-
 lib/test_hexdump.c                            |  10 +-
 lib/test_list_sort.c                          |   2 +-
 lib/test_parman.c                             |   2 +-
 lib/test_vmalloc.c                            |  58 +-
 mm/shuffle.c                                  |   2 +-
 mm/slab.c                                     |  25 +-
 mm/slab_common.c                              |  15 +-
 mm/slub.c                                     |   2 +-
 mm/swapfile.c                                 |   2 +-
 net/802/garp.c                                |   2 +-
 net/802/mrp.c                                 |   2 +-
 net/batman-adv/bat_iv_ogm.c                   |   4 +-
 net/batman-adv/bat_v_elp.c                    |   2 +-
 net/batman-adv/bat_v_ogm.c                    |  10 +-
 net/batman-adv/network-coding.c               |   9 +-
 net/bluetooth/hci_request.c                   |   2 +-
 net/ceph/mon_client.c                         |   2 +-
 net/core/neighbour.c                          |   6 +-
 net/core/pktgen.c                             |  20 +-
 net/core/stream.c                             |   2 +-
 net/ipv4/igmp.c                               |   6 +-
 net/ipv4/inet_connection_sock.c               |   2 +-
 net/ipv6/addrconf.c                           |  17 +-
 net/ipv6/mcast.c                              |  10 +-
 net/packet/af_packet.c                        |   2 +-
 net/rds/bind.c                                |   2 +-
 net/sched/act_gact.c                          |   2 +-
 net/sched/act_sample.c                        |   2 +-
 net/sched/sch_netem.c                         |  23 +-
 net/sctp/socket.c                             |   2 +-
 net/sunrpc/xprtsock.c                         |   2 +-
 net/tipc/socket.c                             |   5 +-
 net/wireless/scan.c                           |   2 +-
 net/xfrm/xfrm_state.c                         |   2 +-
 sound/core/pcm_lib.c                          |   2 +-
 sound/core/pcm_native.c                       |   2 +-
 110 files changed, 1324 insertions(+), 917 deletions(-)

-- 
2.26.0