Everything

php

xoshiro** edge case (all zeros)

php.internals

Anton Smirnov

4 years ago

Hi!

Randomness again. Sorry if I just missed some relevant discussion

xoshiro** has a known edge case: all-zero seed

<?php

$engine = new \Random\Engine\Xoshiro256StarStar(str_repeat("\0", 32));

while (true) {
echo hex2bin($engine->generate()), PHP_EOL; // 0000000000000000
}

It should be documented and/or handled

It's only for a string seed, int seed is not affected

--
Anton

zeriyoshi

4 years ago

2022年8月4日(木) 17:10 Anton Smirnov <sandfox@sandfox.me>:

> Hi!
>
> Randomness again. Sorry if I just missed some relevant discussion
>
> xoshiro** has a known edge case: all-zero seed
>
> <?php
>
> $engine = new \Random\Engine\Xoshiro256StarStar(str_repeat("\0", 32));
>
> while (true) {
>     echo hex2bin($engine->generate()), PHP_EOL; // 0000000000000000
> }
>
> It should be documented and/or handled
>
> It's only for a string seed, int seed is not affected
>
> --
> Anton
>
> --
> PHP Internals - PHP Runtime Development Mailing List
> To unsubscribe, visit: https://www.php.net/unsub.php
>
>

Hi.

Thanks for the report! This is dangerous behavior and we will attempt to
fix it for 8.2beta3.

Best regards
Go Kudo

Tim Düsterhus

4 years ago

Hi

On 8/4/22 10:09, Anton Smirnov wrote:

> xoshiro** has a known edge case: all-zero seed

Indeed, good catch. I had that in mind, but forgot about it.

> <?php
>
> $engine = new \Random\Engine\Xoshiro256StarStar(str_repeat("\0", 32));
>
> while (true) {
>      echo hex2bin($engine->generate()), PHP_EOL; // 0000000000000000
> }
>
> It should be documented and/or handled
>
> It's only for a string seed, int seed is not affected
>

I've created a PR here:

https://github.com/php/php-src/pull/9250

I've opted to throw a ValueError in that case, as that's the only safe
option that does not introduce a bias.

The 32xNUL seed basically should only happen for manually written
testing input and not happen otherwise. An actual random seed will
result in 32 NUL bytes with just a 2**-256 chance and when relying on
the implicit CSPRNG seeding (`null` as seed parameter) my PR will just
retry to catch even that edge case.

Best regards
Tim Düsterhus

Hans Henrik Bergan

4 years ago

dangerous to be sure, but it's also a technically valid seed,
are you sure we should disallow a valid seed?

On Thu, 4 Aug 2022 at 20:33, Tim Düsterhus <tim@bastelstu.be> wrote:

Jordan LeDoux

4 years ago

On Thu, Aug 4, 2022 at 1:33 PM Hans Henrik Bergan <divinity76@gmail.com>
wrote:

> dangerous to be sure, but it's also a technically valid seed,
> are you sure we should disallow a valid seed?
>
>

How is it a valid seed if it creates invalid outputs?

Anton Smirnov

4 years ago

On Thu, 2022-08-04 at 22:32 +0200, Hans Henrik Bergan wrote:

> dangerous to be sure, but it's also a technically valid seed,
> are you sure we should disallow a valid seed?

Reference implementation defines it as invalid:
https://prng.di.unimi.it/xoshiro256starstar.c

Some implementations choose to seed the RNG with 0x0000...0001 but that
kinda inroduces bias

Tim Düsterhus

4 years ago

Hi

On 8/4/22 22:32, Hans Henrik Bergan wrote:

> dangerous to be sure, but it's also a technically valid seed,
> are you sure we should disallow a valid seed?

The all-zero state is not a valid state as per the reference
implementation at: https://xoshiro.di.unimi.it/xoshiro256starstar.c

> The state must be seeded so that it is not everywhere zero.

The period of Xoshiro256** is officially defined to be 2**256 - 1
instead of 2**256 for that reason.

Best regards
Tim Düsterhus