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

[Ariadne Conill <ariadne@dereferenced.org>]

Hi,

On Sun, 1 Jan 2023, Alejandro Colomar via Libc-alpha wrote:

> Hello Damien,
>
> On 1/1/23 00:07, Damien Miller wrote:
>> On Sat, 31 Dec 2022, Theo de Raadt wrote:
>> 
>>> 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.
>> 
>> I agree - specifying a zero upper-bound is numerically nonsensical,
>> and could often be the result of a bug in the caller.
>> 
>> Changing it is likely to break code like this in a plausibly exploitable
>> way:
>> 
>> elem_t *random_elem(elem_t **elems, size_t nelems) {
>> 	return elems[arc4random_uniform(nelems)];
>> }
>
> The above code is already broken.  In case nelems is 0, the array has exactly 
> 0 elements, so the pointer &elems[0] is a pointer to one-past-the-last 
> element. It is legal to hold such a pointer, but not to dereference it (I 
> guess I don't need to quote the standard here).
>
> Such a pointer dereference *is dangerous*, and *is very-likely exploitable*.
>
> Having a random 32-bit number instead is likely to be a pointer addressing an 
> invalid memory address, and result in a crash.  And crashes are good, right?

In scenarios where available address space is constrained, the likelihood 
of a crash verses state corruption elsewhere in a program is reduced 
considerably.  I think we should avoid defining interfaces based on the 
assumption that some minimal amount of address space is available.

> Changing the behavior of arc4random_uniform() wouldn't make this code more 
> broken, but rather uncover the bug in it.

The better approach would be for random_elem to check that there is at 
least one element available.  Making arc4random_uniform(0) do something 
unexpected will probably break legitimate code.  I can think of many 
situations where arc4random_uniform(0) would be legitimately called.

>> Therefore IMO the only safe return from arc4random_uniform(0) is 0.
>
> I'd argue it's the opposite.  0 is the most unsafe value it can return in 
> such a case, since it's the least likely to result in a crash.  The Undefined 
> Behavior is invoked, and in a way that is likely to modify memory that is 
> available to the process.

If you are using arc4random_uniform to blindly pick elements out of an 
array without doing the bounds checking yourself, you're already setting 
yourself up for failure.  In an ideal world, we would add an additional 
API which is designed for picking elements and which did this type of 
bounds check and then failed safely.  Something like:

inline void *
arc4random_pickelem(void **elems, size_t elemsize, size_t nelems)
{
 	if (__builtin_object_size(elems, 0) < (nelems * elemsize)) {
 		errno = EINVAL;
 		return NULL;
 	}

 	ptrdiff_t diff = arc4random_uniform(nelems) * elemsize;
 	return (char *)(elems + diff);
}

Changing arc4random_uniform(0) to return non-zero will probably break 
monte carlo simulations and such which reasonably depend on the behavior 
that arc4random_uniform(0) == 0.

>
> 42 would be a better value.
> An even better value would be UINT32_MAX, which would almost-certainly 
> guarantee a crash everywhere.
> However, it makes more sense to just let it be an unbounded random value, 
> which will likely result in the same crashes as with UINT32_MAX, but would be 
> more useful for other purposes.

What purpose do you envision where arc4random_uniform(0) being non-zero 
would be considered useful?  If you want to safely pick elements from 
arrays at random, then we should build an interface for doing this safely, 
rather then changing the behavior of pre-existing ones.

Ariadne