Re: [PATCH] Give a useful meaning to arc4random_uniform(0);

["Theo de Raadt" <deraadt@openbsd.org>]

Your proposal failed to update the manual page.  That was my first
hint that somethign is amiss.

Right now the manual it is super clear that it returns a value "less
than upper_bound".  Which by prototype is uint32_t.

How would you rewrite the manual page to explain this behaviour?

Since your change choose a strange condition where it will return
a value greater than upper_bound.

Also, right now an (incorrect?) call of arc4random_uniform(0)
will return 0, but with your proposal it will return a non-zero
number.  Have you audited the entire universe of software to
ensure that your change doesn't introduce a bug in some other
piece of software?  I doubt you did that.  Very unprofessional
of you to not study the impact and just wave the issue away.

I think Special-casing the value of 0 to mean something new
and undocumented behaviour makes no sense.  It is even potentially
undocumentable.

The decision to return 0 was made very carefully.  It results programs
passing mathematically calculated erroneous values not going further off
the rails in a compliant fashion.  If they are using the value to index
into an array, they will tend to access in-range, rather than out of
range.  Do you like introducing memory safety bugs into software you
did not review but which will be affected by your proposal to change
a standard well-known API which has been in use since 2008.

I do not like your proposal at all.  A function like arc4random_range()
is even more likely to be used wrong by passing backwards points
and you seem to have a lot of hubris to add a range check to it.
Is this really all just "everyone else's big code will be perfect like
my 12 lines of code"?

Also, you have not cc'd all authors of this layer.  I am adding them.  


Alejandro Colomar <alx.manpages@gmail.com> wrote:

> Special-casing it in the implementation to return 0 was useless.
> Instead, considering 0 as the value after UINT32_MAX has the property
> that it allows implementing the following function without any
> special cases:
> 
> uint32_t
> arc4random_range(uint32_t min, uint32_t max)
> {
> 	return arc4random_uniform(max - min + 1) + min;
> }
> 
> This works for any values of min and max (as long as min <= max, of
> course), even for (0, UINT32_MAX).
> 
> Oh, and the implementation of arc4random_uniform(3) is now 2 lines
> simpler. :)
> 
> This will work with the current implementation because powerof2(3) will
> also consider 0 as a power of 2.  See powerof2(3):
> 
>  SYNOPSIS
>        #include <sys/param.h>
> 
>        int powerof2(x);
> 
>  DESCRIPTION
>        This  macro  returns true if x is a power of 2, and false
>        otherwise.
> 
>        0 is considered a power of 2.  This can make  sense  con‐
>        sidering wrapping of unsigned integers, and has interest‐
>        ing properties.
> 
> Cc: Theo de Raadt <deraadt@theos.com>
> Cc: Todd C. Miller <Todd.Miller@sudo.ws>
> Cc: "Jason A. Donenfeld" <Jason@zx2c4.com>
> Cc: Cristian Rodríguez <crrodriguez@opensuse.org>
> Cc: Adhemerval Zanella <adhemerval.zanella@linaro.org>
> Cc: Yann Droneaud <ydroneaud@opteya.com>
> Cc: Joseph Myers <joseph@codesourcery.com>
> Signed-off-by: Alejandro Colomar <alx@kernel.org>
> ---
> 
> Hi,
> 
> I CCd Theo and Todd, because theirs is the original implementation, and
> while this is a useful feature (IMO), it wouldn't make sense to do it
> without consensus with other implementations, and especially with the
> original implementation.
> 
> I found this useful for shadow, where the existing code had a function
> that produced a "random" value within a range, but due to the bogus
> implementation, it had bias for higher values.  Implementing a *_range()
> variant in terms of *_uniform() made it really simple, but the
> *_uniform() function needed to do something useful for 0 for that to
> work.
> 
> Cheers,
> 
> Alex
> 
>  stdlib/arc4random_uniform.c | 10 ++++------
>  1 file changed, 4 insertions(+), 6 deletions(-)
> 
> diff --git a/stdlib/arc4random_uniform.c b/stdlib/arc4random_uniform.c
> index 5aa98d1c13..1cd52c0d1c 100644
> --- a/stdlib/arc4random_uniform.c
> +++ b/stdlib/arc4random_uniform.c
> @@ -29,15 +29,13 @@
>     the asked range after range adjustment.
>  
>     The algorithm avoids modulo and divide operations, which might be costly
> -   depending on the architecture.  */
> +   depending on the architecture.
> +
> +   0 is treated as if it were UINT32_MAX + 1, and so arc4random_uniform(0)
> +   is equivalent to arc4random().  */
>  uint32_t
>  __arc4random_uniform (uint32_t n)
>  {
> -  if (n <= 1)
> -    /* There is no valid return value for a zero limit, and 0 is the
> -       only possible result for limit 1.  */
> -    return 0;
> -
>    /* Powers of two are easy.  */
>    if (powerof2 (n))
>      return __arc4random () & (n - 1);
> -- 
> 2.39.0
>