linux-kernel - Re: [crng-random:jd/get_random_u32_below 24/26] include/linux/random.h:64:77: sparse: sparse: cast truncates bits from constant value (e24d4d50 becomes 50)

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 for Android: free password hash cracker in your pocket

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

Message-ID: <Y0W3C5n4Tjy/Cri6@zx2c4.com>
Date:   Tue, 11 Oct 2022 12:33:47 -0600
From:   "Jason A. Donenfeld" <Jason@...c4.com>
To:     Rasmus Villemoes <linux@...musvillemoes.dk>
Cc:     kernel test robot <lkp@...el.com>,
        "Jason A. Donenfeld" <zx2c4@...nel.org>, kbuild-all@...ts.01.org,
        linux-kernel@...r.kernel.org
Subject: Re: [crng-random:jd/get_random_u32_below 24/26]
 include/linux/random.h:64:77: sparse: sparse: cast truncates bits from
 constant value (e24d4d50 becomes 50)

On Tue, Oct 11, 2022 at 03:21:44PM +0200, Rasmus Villemoes wrote:
> On 11/10/2022 11.59, kernel test robot wrote:
> 
> > c440408cf6901e Jason A. Donenfeld 2017-01-22  53  
> > dbc0933c6b1d8c Jason A. Donenfeld 2022-10-08  54  u32 __get_random_u32_below(u32 ceil);
> > dbc0933c6b1d8c Jason A. Donenfeld 2022-10-08  55  /* Returns a random integer in the interval [0, ceil), with uniform distribution. */
> > dbc0933c6b1d8c Jason A. Donenfeld 2022-10-08  56  static inline u32 get_random_u32_below(u32 ceil)
> > dbc0933c6b1d8c Jason A. Donenfeld 2022-10-08  57  {
> > dbc0933c6b1d8c Jason A. Donenfeld 2022-10-08  58  	if (!__builtin_constant_p(ceil))
> > dbc0933c6b1d8c Jason A. Donenfeld 2022-10-08  59  		return __get_random_u32_below(ceil);
> > dbc0933c6b1d8c Jason A. Donenfeld 2022-10-08  60  
> > dbc0933c6b1d8c Jason A. Donenfeld 2022-10-08  61  	for (;;) {
> > dbc0933c6b1d8c Jason A. Donenfeld 2022-10-08  62  		if (ceil <= 1U << 8) {
> > dbc0933c6b1d8c Jason A. Donenfeld 2022-10-08  63  			u32 mult = ceil * get_random_u8();
> > dbc0933c6b1d8c Jason A. Donenfeld 2022-10-08 @64  			if (is_power_of_2(ceil) || (u8)mult >= -(__force u8)ceil % ceil)
> > dbc0933c6b1d8c Jason A. Donenfeld 2022-10-08  65  				return mult >> 8;
> 
> I don't have a good suggestion for how to silence sparse, but I think
> the cast and unary minus here needs to be interchanged. I.e., the
> condition should be
> 
>   if (is_power_of_2(ceil) || (u8)mult >= ((__force u8)-ceil) % ceil)
> 
> Otherwise it fails to provide uniform distribution for ceil=11, 19, 22,
> 23, ... [these are the numbers that are not divisors of 2^32-2^8].

Thanks! Note that this is an incomplete dev branch I haven't posted to
the ML yet. As for the sparse error, I think I'll fix both issues at
once by just doing (256 - ceil) % ceil.

Jason