Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Uuid:uuid4() collisions #80

Closed
giorgiosironi opened this issue Aug 27, 2015 · 98 comments
Closed

Uuid:uuid4() collisions #80

giorgiosironi opened this issue Aug 27, 2015 · 98 comments
Labels
bug

Comments

@giorgiosironi
Copy link

@giorgiosironi giorgiosironi commented Aug 27, 2015

We are generating about 1M UUID4 a day, and we are getting several hundred collisions a day, such as:

[2015-08-26 21:29:19 +0200] [production-onebipws-1.apache - 17819] [DEBUG] [Request] 
time_total=0.145
"request_id":"fdfb98c1-4367-4f22-b68a-d7cdaedcc069" 

[2015-08-27 00:36:16 +0200] [production-onebipws-1.apache - 17819] [DEBUG] [Request] 
time_total=0.016
"request_id":"fdfb98c1-4367-4f22-b68a-d7cdaedcc069"

The issue seem to be correlated with the same Apache process regenerating the same UUID after several hours. It also seem to be correlated with particular EC2 machines which presents the problem.

We checked to have openssl_random_pseudo_bytes and if it was using a strong algorithm:

root@dev-all-onebip:~/projects/.../onebip-ultimate$  (master) # php -r "var_dump(function_exists('openssl_random_pseudo_bytes'));"                                      
bool(true)
root@dev-all-onebip:~/projects/.../onebip-ultimate$  (master) # php -r 'openssl_random_pseudo_bytes(16, $strong); var_dump($strong);'
bool(true)

How can we debug this problem?

@ircmaxell
Copy link

@ircmaxell ircmaxell commented Aug 27, 2015

Which version of UUID are you using? Can you try switching to master?

@giorgiosironi
Copy link
Author

@giorgiosironi giorgiosironi commented Aug 27, 2015

We are on 2.8.1, but from what I see the code for uuid4() is identical to master:

public static function uuid4()
{
    $bytes = self::generateBytes(16);
    // When converting the bytes to hex, it turns into a 32-character
    // hexadecimal string that looks a lot like an MD5 hash, so at this
    // point, we can just pass it to uuidFromHashedName. 
    $hex = bin2hex($bytes);
    return self::uuidFromHashedName($hex, 4);
}

private static function generateBytes($length)
{
    if (self::hasOpensslRandomPseudoBytes()) {
        return openssl_random_pseudo_bytes($length);
    }
    ...
}

Here is a sample of the duplicated UUIDs:
https://gist.github.com/giorgiosironi/f1ce4682868ca6a6279d

@ramsey
Copy link
Owner

@ramsey ramsey commented Aug 27, 2015

I wonder if you'll experience the same if you switch to using @ircmaxell's RandomLib.

Using master or 3.0.0-alpha3, you can do so like this:

$uuidFactory = new \Ramsey\Uuid\UuidFactory();
$uuidFactory->setRandomGenerator(new \Ramsey\Uuid\Generator\RandomLibAdapter());
\Ramsey\Uuid\Uuid::setFactory($uuidFactory);

$uuid = \Ramsey\Uuid\Uuid::uuid4();
@giorgiosironi
Copy link
Author

@giorgiosironi giorgiosironi commented Aug 27, 2015

Currently I am trying to reproduce the problem with a cli script to avoid impacting the production system, if I have a test that produces collisions I will try rerun it with RandomLib.

@ramsey
Copy link
Owner

@ramsey ramsey commented Aug 27, 2015

Can you share your test that produces collisions? Does it consistently reproduce them, and is it always reproducing them for the same UUIDs?

@fabre-thibaud
Copy link
Contributor

@fabre-thibaud fabre-thibaud commented Aug 27, 2015

Yup, would be interesting to have more information on your setup (OS version, openssl version, machine architecture (x86 vs x86_64) ... the more the better)

I'm unable to get a single collision on a 12M set:

<?php

require_once 'vendor/autoload.php';

while (1) {
    file_put_contents('uuids.txt', \Rhumsaa\Uuid\Uuid::uuid4() . PHP_EOL, FILE_APPEND);
}
thibaud@thibaud-zbox:~/Workspaces/uuid$ wc -l uuids.txt 
12143446 uuids.txt
thibaud@thibaud-zbox:~/Workspaces/uuid$ sort uuids.txt | uniq -d
thibaud@thibaud-zbox:~/Workspaces/uuid$

EDIT This is with OpenSSL enabled

@ircmaxell
Copy link

@ircmaxell ircmaxell commented Aug 27, 2015

Try generating them on multiple servers. Part of mt_rand()'s output is based on server timestamp, so collisions are probable there (assuming openssl disabled).

@giorgiosironi
Copy link
Author

@giorgiosironi giorgiosironi commented Aug 27, 2015

I do not have yet a script reproducing the problem (it's production traffic presenting the issue), but it happens on a single server, also as stated in the first comment we have the openssl extension enabled.
Versions:

root@production-onebipws-1:~$  # openssl version
OpenSSL 1.0.1 14 Mar 2012
root@production-onebipws-1:~$  # php -v
PHP 5.4.43-1+deb.sury.org~precise+1 (cli) (built: Jul 15 2015 12:05:17) 
Copyright (c) 1997-2014 The PHP Group
Zend Engine v2.4.0, Copyright (c) 1998-2014 Zend Technologies
    with Zend OPcache v7.0.2, Copyright (c) 1999-2013, by Zend Technologies
@ircmaxell
Copy link

@ircmaxell ircmaxell commented Aug 27, 2015

That's a very serious problem then. Could you check to see if the $strong parameter of openssl_random_pseudo_bytes() is showing true or false on this server?

@fabre-thibaud
Copy link
Contributor

@fabre-thibaud fabre-thibaud commented Aug 27, 2015

@ircmaxell He mentionned in the first post that it returns true :)

@giorgiosironi Does it happen on any other server or only that one ? Is there a software (OS, PHP, OpenSSL) version difference between that specific server and the others that do not collide ?

@ircmaxell
Copy link

@ircmaxell ircmaxell commented Aug 27, 2015

He may be getting true from the command line. That doesn't mean it can't
return different values during load, or when these collisions are
generated...
On Aug 27, 2015 12:10 PM, "Thibaud Fabre" notifications@github.com wrote:

@ircmaxell https://github.com/ircmaxell He mentionned in the first post
that it returns true :)

@giorgiosironi https://github.com/giorgiosironi Does it happen on any
other server or only that one ? Is there a software (OS, PHP, OpenSSL)
version difference between that specific server and the others that do not
collide ?


Reply to this email directly or view it on GitHub
#80 (comment).

@ramsey
Copy link
Owner

@ramsey ramsey commented Sep 2, 2015

Any more word on this? @renan reported similar findings on Twitter:

https://twitter.com/renan_saddam/status/637024558038544388

@giorgiosironi
Copy link
Author

@giorgiosironi giorgiosironi commented Sep 6, 2015

What we have done until now:

  • implemented retry on collisions with a new generation to avoid data loss
  • extracting data lost in the last two months
  • reimporting it in the system
  • switched back the code to the uniqid()+mt_rand() previous implementation, which has still caused collisions in the past but at a 1% rate with respect to openssl
@fabre-thibaud
Copy link
Contributor

@fabre-thibaud fabre-thibaud commented Sep 6, 2015

@giorgiosironi Did you manage to find out if openssl_random_pseudo_bytes was storing a false flag in the $strong argument when you get collisions ?

@giorgiosironi
Copy link
Author

@giorgiosironi giorgiosironi commented Sep 6, 2015

No, because that would require forking the library and/or patching it in production which has an high development cost

@ramsey
Copy link
Owner

@ramsey ramsey commented Sep 6, 2015

Can you put a single PHP script on one of the production machines and run it to see?

@ramsey
Copy link
Owner

@ramsey ramsey commented Sep 6, 2015

Or maybe I misunderstood the ask. I see @aztech-dev was asking if you could see if $strong is false only when you see a collision. Sorry for the confusion.

@giorgiosironi
Copy link
Author

@giorgiosironi giorgiosironi commented Sep 6, 2015

About the single PHP script, I did run the same code shown in #80 (comment) in the affected servers and it gave the same result of the function being present and $strong being true.

@ramsey
Copy link
Owner

@ramsey ramsey commented Sep 6, 2015

@giorgiosironi I see your PHP and OpenSSL versions above. What EC2 instance type are you using, since you mentioned that you see this happening on a specific EC2 instance type?

@renan
Copy link

@renan renan commented Sep 7, 2015

I am logging the collisions to see how frequent they are, if any.

In the meantime I have executed the test script @aztech-dev provided in few machines:

  • No collisions on a 2.5M set when running on MacBook Pro with latest OS X, PHP 5.5.26, and OpenSSL 0.9.8zg
  • No collisions on a 23.7M set on Ubuntu 14.04.3 running PHP 5.5.9, and OpenSSL 1.0.1f

The server of which gave me collisions is not around anymore, but was running Ubuntu 12.04.4, PHP 5.3.x and don't know the OpenSSL version. But was all from Ubuntu LTS versions.

@ramsey
Copy link
Owner

@ramsey ramsey commented Sep 7, 2015

I don't have any data to base this on, but off the cuff, it sounds like the underlying system has a lack of randomness on it. Maybe?

@ramsey
Copy link
Owner

@ramsey ramsey commented Sep 30, 2015

Just a thought: can you set up monitoring such that, when a collision occurs, you get a report on the read-out of the current value in /proc/sys/kernel/random/entropy_avail?

If the number is > 200, then your entropy level is good. If it's < 200, then that's an indication that there's a problem.

@langemeijer
Copy link

@langemeijer langemeijer commented Sep 30, 2015

I've been watching this thread, because it scared the shit out of me, but I want to share some of my initial thoughts here.

@giorgiosironi shared this piece of code:

private static function generateBytes($length)
{
    if (self::hasOpensslRandomPseudoBytes()) {
        return openssl_random_pseudo_bytes($length);
    }
    ...
}

For me the scary part is the dots. What's there? mt_rand to generate uuids?

In the first post in this issue he shared a piece of shell output

root@dev-all-onebip:~/projects/.../onebip-ultimate$  (master) # php -r "var_dump(function_exists('openssl_random_pseudo_bytes'));"                                      
bool(true)
root@dev-all-onebip:~/projects/.../onebip-ultimate$  (master) # php -r 'openssl_random_pseudo_bytes(16, $strong); var_dump($strong);'
bool(true)

But this doesn't prove that openssl is actually used in the generateBytes() method. I would have liked to see a phpinfo() output from a web request where we can confim that the openssl extension was actually loaded in the webserver.

Modern distro's have split the php.ini and conf.d for the cli and different sapi's. My guess is that openssl was loaded in cli, but not in webserver sapi.

@ramsey
Copy link
Owner

@ramsey ramsey commented Sep 30, 2015

@langemeijer Here's that equivalent block of code in 3.0.0: https://github.com/ramsey/uuid/blob/3.0.0/src/Generator/RandomGeneratorFactory.php#L58-L74

Your comment makes me think it might be a good idea to "tag" a Uuid object at its point of creation with details about what generator, provider, etc. was used to create it. I'm not sure what this would look like in practice, and you may certainly create a Uuid from a string, bytes, or fields you pass in to it, so that information won't be available in that context, but it might be good to provide this information (when creating a Uuid) for debugging purposes.

@matteosister
Copy link

@matteosister matteosister commented Oct 6, 2015

I confirm that we also have collissions on our uuids.
We have a table with 2,5M rows. I grouped by unique identifier, and counted the occurrence, and I have many collisions. In one case I have 5 equal uuids.... 😨

We are on ec2 too.

@ramsey
Copy link
Owner

@ramsey ramsey commented Oct 8, 2015

@matteosister Are you able to set up your environment so that you can capture information at the point a collision occurs? Specifically, what is the value of /proc/sys/kernel/random/entropy_avail when the collision occurs? Also, can you give specifics about the EC2 instance you're using (AWS instance type, uname -a, php --version, cat /etc/issue, etc.)?

@ramsey
Copy link
Owner

@ramsey ramsey commented Oct 8, 2015

@matteosister Also, an example of the code you're using to generate the UUIDs, too, please.

@matteosister
Copy link

@matteosister matteosister commented Oct 9, 2015

@ramsey we are trying to isolate the problem....and we have a suspect that something could be related to an edge case in our own code. I will report back when I'm sure. Thanks!

@Lansoweb
Copy link

@Lansoweb Lansoweb commented Nov 15, 2015

@ramsey I'm running a test on 3 AWS instances (micro, small and medium), one CentOS and 2 AmazonLinux). Each one already has more than 2M (the micro has 12.134.008) without duplicates. Will keep running for a while and report back later. I'm also saving the entropy_avail with each uuid, to if i got a hit, will report the entropy as well.

danlamanna added a commit to Kitware/CDash that referenced this issue Nov 21, 2016
danlamanna added a commit to Kitware/CDash that referenced this issue Nov 21, 2016
@ramsey ramsey added the bug label Feb 23, 2017
derekmarcotte added a commit to derekmarcotte/PHP-PasswordLib that referenced this issue Oct 19, 2017
This uses openssl_random_pseudo_bytes.  This is suggested for use only with
with php5-openssl compiled against LibreSSL:

  OpenSSL copying RNG state on fork:
    ramsey/uuid#80 (comment)
  Fixed in LibreSSL:
    http://opensslrampage.org/post/91910269738/fix-for-the-libressl-prng-issue-under-linux

Additionally, CVE-2015-8867 was fixed only in versions 5.6.12, 5.5.28,
5.4.44 and above:

  https://bugs.php.net/bug.php?id=70014
  http://www.php.net/ChangeLog-5.php

CVE-2015-8867 does not affect versions compiled against LibreSSL.

For these reasons, it only is considered a LOW source of randomness,
unless it is compiled against LibreSSL.

The reason for this to exist at all is because of problems with the
nature of /dev/urandom.  For example, if we cannot open or read the
file.  openssl_random_pseudo_bytes should never fail.
@callistino
Copy link

@callistino callistino commented Apr 2, 2019

Hi everyone. I'm having UUID collisions on my system. This thread makes it really clear is most likely a setup or system issue. I just need some guidance if anyone knows where to start troubleshooting. I'm using php:7.1.27-apache-stretch docker container and here are some of the outputs based on the some of the scripts on this issue:

entropy: > 3500
random_generator: \Ramsey\Uuid\Generator\RandomBytesGenerator
ramsey/uuid: 3.8.0
apache-uptime: 1 day 4 hours

I didn't want to open a new issue and attract unwanted attention but if that's going to be better I will do so.

@paragonie-scott
Copy link

@paragonie-scott paragonie-scott commented Apr 2, 2019

@callistino What is the output of this code snippet?

<?php
var_dump(bin2hex(random_bytes(16)));

If you get an exception, you need to fix your OS. Ask your ISP to make sure you can read /dev/urandom from PHP.

@spinitron
Copy link

@spinitron spinitron commented Apr 2, 2019

It doesn't need to be complicated

function randomUuid()
{
    $bytes = random_bytes(16);
    $bytes[6] = chr((ord($bytes[6]) & 0x0f) | 0x40);
    $bytes[8] = chr((ord($bytes[8]) & 0x3f) | 0x80);
    $id = str_split(bin2hex($bytes), 4);

    return "{$id[0]}{$id[1]}-{$id[2]}-{$id[3]}-{$id[4]}-{$id[5]}{$id[6]}{$id[7]}";
}
@callistino
Copy link

@callistino callistino commented Apr 2, 2019

var_dump(bin2hex(random_bytes(16)));
-- string(32) "bf2e38bbcecd7f358439c8bbceabcf3a"

@spinitron you mean using that instead of ramsey/uuid?

@ramsey
Copy link
Owner

@ramsey ramsey commented Apr 3, 2019

@callistino, that's what they mean 😀

Though, in this case, that comment likely wouldn't help you, since you're already using the random_bytes() generator, and that's where you'd be getting collisions from, since ramsey/uuid isn't using anything special.

How are you generating the UUIDs? Can you show some sample code? Are they random UUIDs (version 4), or are you using a different version (version 1, version 5, etc.)?

@bicatu
Copy link

@bicatu bicatu commented Apr 4, 2019

I haven't noticed any collision myself, and I am using version 4. Should I be worried? Is there any check I should do?

@ramsey
Copy link
Owner

@ramsey ramsey commented Apr 4, 2019

There shouldn't be any collisions, so I want to fully understand the problem here before jumping to any conclusions. 😄

@callistino
Copy link

@callistino callistino commented Apr 6, 2019

it was indeed a system issue of some sort. I rebooted and it's not happening anymore. I have a script running for a couple of days and no collisions there either. Not sure what it was at this point but I'm blaming OS, hardware and config not this library. I just wanted to get some directions as to what to test and check.

@ramsey
Copy link
Owner

@ramsey ramsey commented Apr 6, 2019

@callistino Good to hear you were able to get around it by rebooting. Let us know if the problem occurs again.

@abcapili
Copy link

@abcapili abcapili commented Sep 2, 2020

Just encountered this issue, not re-opening this ticket probably bumping this up. Here's our setup: multiple docker containers hosting the same app - presumably created from same image for load balancing and autoscaling:

  • Service 1 generates UUIDv4
  • Service 2 records UUIDv4 from service 1
  • Service 1 data gets deleted / complete wipe
  • Service 2 after deletion of data from Service 1 somehow received previously used UUIDv4.

Collision happened in less than 24 hours. Perhaps this may be the same issue as @callistino's - i.e., hardware, OS, or config.

@ramsey
Copy link
Owner

@ramsey ramsey commented Sep 2, 2020

@abcapili What version of PHP are you using? mod_php or php-fpm? What version of ramsey/uuid?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
You can’t perform that action at this time.