linux-kernel - Re: [PATCH] prandom: make use of smaller types in prandom_u32

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [day] [month] [year] [list]

Message-ID: <CANpmjNMjUpx37KKc-zb--Z-=fpETwDGkyb9-mAOGLqZ+CBU-BA@mail.gmail.com>
Date:   Thu, 29 Sep 2022 15:02:09 +0200
From:   Marco Elver <elver@...gle.com>
To:     "Jason A. Donenfeld" <Jason@...c4.com>
Cc:     linux-kernel@...r.kernel.org, linux-crypto@...r.kernel.org,
        Dominik Brodowski <linux@...inikbrodowski.net>
Subject: Re: [PATCH] prandom: make use of smaller types in prandom_u32_max

On Thu, 29 Sept 2022 at 12:31, Jason A. Donenfeld <Jason@...c4.com> wrote:
>
> When possible at compile-time, make use of smaller types in
> prandom_u32_max(), so that we can use smaller batches from random.c,
> which in turn leads to a 2x or 4x performance boost. This makes a
> difference, for example, in kfence, which needs a fast stream of small
> numbers (booleans).
>
> At the same time, we use the occasion to update the old documentation on
> these functions. prandom_u32() and prandom_bytes() have direct
> replacements now in random.h, while prandom_u32_max() remains useful as
> a prandom.h function, since it's not cryptographically secure by virtue
> of not being evenly distributed.
>
> Cc: Marco Elver <elver@...gle.com>
> Cc: Dominik Brodowski <linux@...inikbrodowski.net>
> Signed-off-by: Jason A. Donenfeld <Jason@...c4.com>

Acked-by: Marco Elver <elver@...gle.com>

> ---
>  include/linux/prandom.h | 17 +++++++++++------
>  1 file changed, 11 insertions(+), 6 deletions(-)
>
> diff --git a/include/linux/prandom.h b/include/linux/prandom.h
> index deace5fb4e62..78db003bc290 100644
> --- a/include/linux/prandom.h
> +++ b/include/linux/prandom.h
> @@ -12,11 +12,13 @@
>  #include <linux/percpu.h>
>  #include <linux/random.h>
>
> +/* Deprecated: use get_random_u32 instead. */
>  static inline u32 prandom_u32(void)
>  {
>         return get_random_u32();
>  }
>
> +/* Deprecated: use get_random_bytes instead. */
>  static inline void prandom_bytes(void *buf, size_t nbytes)
>  {
>         return get_random_bytes(buf, nbytes);
> @@ -37,17 +39,20 @@ void prandom_seed_full_state(struct rnd_state __percpu *pcpu_state);
>   * prandom_u32_max - returns a pseudo-random number in interval [0, ep_ro)
>   * @ep_ro: right open interval endpoint
>   *
> - * Returns a pseudo-random number that is in interval [0, ep_ro). Note
> - * that the result depends on PRNG being well distributed in [0, ~0U]
> - * u32 space. Here we use maximally equidistributed combined Tausworthe
> - * generator, that is, prandom_u32(). This is useful when requesting a
> - * random index of an array containing ep_ro elements, for example.
> + * Returns a pseudo-random number that is in interval [0, ep_ro). This is
> + * useful when requesting a random index of an array containing ep_ro elements,
> + * for example. The result is somewhat biased when ep_ro is not a power of 2,
> + * so do not use this for cryptographic purposes.
>   *
>   * Returns: pseudo-random number in interval [0, ep_ro)
>   */
>  static inline u32 prandom_u32_max(u32 ep_ro)
>  {
> -       return (u32)(((u64) prandom_u32() * ep_ro) >> 32);
> +       if (__builtin_constant_p(ep_ro <= 1U << 8) && ep_ro <= 1U << 8)
> +               return (get_random_u8() * ep_ro) >> 8;
> +       if (__builtin_constant_p(ep_ro <= 1U << 16) && ep_ro <= 1U << 16)
> +               return (get_random_u16() * ep_ro) >> 16;
> +       return ((u64)get_random_u32() * ep_ro) >> 32;
>  }
>
>  /*
> --
> 2.37.3
>