[uuid] basic_random_generator doesn't produce a fully randomized uuid when sizeof(unsigned long) == 4
Hi Andy, I wonder if the following is a flaw in basic_random_generator<> (boost/uuid/uuid_generators.hpp, line 366-374)? On many platforms sizeof(unsigned long) == 4. This means that the first 8 bytes of the uuid are populated with random data, but in my tests the remaining 8 bytes are populated with repeated data, and then only by relying on the undefined behaviour of >> when its "right operand is greater than or equal to the length in bits of the promoted left operand." For example, try the following test program with a Win32 build by Visual C++ 9.0 - #include <iostreams> #include <boost/uuid/uuid_generators.hpp> #include <boost/uuid/uuid_io.hpp> int main( int, char*[] ) { std::cout << boost::uuids::random_generator()() << std::endl; return 0; } This produced for me: f1633d75-ee94-47b9-ae94-37b9ee9437b9 Or wrapped to show the problem: f1633d75- ee94-47b9- ae94-37b9 ee94 37b9 Is 8 bytes of randomness enough, or is this a mistake? Best regards, Gareth ************************************************************************ The information contained in this message or any of its attachments may be confidential and is intended for the exclusive use of the addressee(s). Any disclosure, reproduction, distribution or other dissemination or use of this communication is strictly prohibited without the express permission of the sender. The views expressed in this email are those of the individual and not necessarily those of Sony or Sony affiliated companies. Sony email is for business use only. This email and any response may be monitored by Sony to be in compliance with Sony's global policies and standards
On 2 March 2010 06:21, Sylvester-Bradley, Gareth <Gareth.Sylvester-Bradley@eu.sony.com> wrote:
Is 8 bytes of randomness enough, or is this a mistake?
This is definitely a mistake, since it means only about 4 billion 'til a collision, completely destroying the utility of random UUIDs. Not to mention that shifting by >= the width isn't well-defined, which means there's no guarantee it even gives different UUIDs. Good catch.
This is definitely a mistake, since it means only about 4 billion 'til a collision, completely destroying the utility of random UUIDs. Not to mention that shifting by >= the width isn't well-defined, which means there's no guarantee it even gives different UUIDs.
Right.
Good catch.
Simplest patch could be just: 370a370
i=0;
Best regards, Gareth ************************************************************************ The information contained in this message or any of its attachments may be confidential and is intended for the exclusive use of the addressee(s). Any disclosure, reproduction, distribution or other dissemination or use of this communication is strictly prohibited without the express permission of the sender. The views expressed in this email are those of the individual and not necessarily those of Sony or Sony affiliated companies. Sony email is for business use only. This email and any response may be monitored by Sony to be in compliance with Sony's global policies and standards
On Tue, 02 Mar 2010 16:05 +0000, "Sylvester-Bradley, Gareth" <Gareth.Sylvester-Bradley@eu.sony.com> wrote:
This is definitely a mistake, since it means only about 4 billion 'til a collision, completely destroying the utility of random UUIDs. Not to mention that shifting by >= the width isn't well-defined, which means there's no guarantee it even gives different UUIDs.
Right.
Good catch.
Absolutely great catch! It is definitely a mistake.
Simplest patch could be just:
370a370
i=0;
This is exactly what I meant it to be. Reset i every time it equals sizeof(unsigned long). Just to double check, I fix this in trunk and wait to put it into release until it is open for these changes. Correct?
Best regards, Gareth
Thanks very much! Andy.
Andy Tompkins wrote:
On Tue, 02 Mar 2010 16:05 +0000, "Sylvester-Bradley, Gareth" <Gareth.Sylvester-Bradley@eu.sony.com> wrote:
This is definitely a mistake, since it means only about 4 billion 'til a collision, completely destroying the utility of random UUIDs. Not to mention that shifting by >= the width isn't well-defined, which means there's no guarantee it even gives different UUIDs. Right.
Good catch.
Absolutely great catch! It is definitely a mistake.
Simplest patch could be just:
370a370
i=0;
This is exactly what I meant it to be. Reset i every time it equals sizeof(unsigned long).
Just to double check, I fix this in trunk and wait to put it into release until it is open for these changes. Correct?
Release branch is open for all changes at this point, so feel free to merge this to release branch as soon as you see new test run on trunk, and everything looks OK. You might want to update release notes, per website update instructions, too. - Volodya
participants (4)
-
Andy Tompkins -
Scott McMurray -
Sylvester-Bradley, Gareth -
Vladimir Prus