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

NewV4: non-random uuid #73

Closed
josselin-c opened this Issue Mar 23, 2018 · 24 comments

Comments

Projects
None yet
@josselin-c

josselin-c commented Mar 23, 2018

I'm running this on my macbook pro.

I'm using uuid.Must(uuid.NewV4()).String() to generate random identifiers. I'm generating theses identifiers at a very low rate of a few dozen per days

Here are some non-random UUID that I got in the last weeks:

02524e6f-65a7-4cf5-8000-0000000000002
6e3ef1c8-0000-4000-8000-0000000000001
fa07f1e9-a8a0-427f-8103-e34e000000000
2cfa392b-71d5-4000-8000-000000000000
5f16db16-56ce-4000-8000-000000000000
bac73b37-aab3-498b-8000-000000000000
da5bd82d-4f98-4b51-8000-000000000000
eb245e52-535f-4274-8350-3a7200000000
f7510000-0000-4000-8000-000000000000
5936f955-286e-47ac-8000-000000000000
0a14da92-0000-4000-8000-000000000000
80730000-0000-4000-8000-000000000000
cd2b88a5-0000-4000-8000-000000000000

I think I shouldn't have theses.

@domino14

This comment has been minimized.

domino14 commented Apr 3, 2018

humans are bad at telling randomness. While it is extraordinarily, astronomically unlikely that you would have so many uuids with that many zeros, it is still theoretically possible.

@josselin-c

This comment has been minimized.

josselin-c commented Apr 3, 2018

In an IDs such as 80730000-0000-4000-8000-000000000000 there are ~14 consecutive bytes of zeros.. While a probability of something like 1/2**(14*8) isn't nil, it's still too low for my taste. Drawing theses IDs 5 times out of ~1000 isn't just bad luck. In real life, if it was possible, I would start mining bitcoins with my super powers!

6e3ef1c8-0000-4000-8000-0000000000001
f7510000-0000-4000-8000-000000000000
0a14da92-0000-4000-8000-000000000000
80730000-0000-4000-8000-000000000000
cd2b88a5-0000-4000-8000-000000000000

I don't know the root cause of this.

@peterstace

This comment has been minimized.

peterstace commented Apr 3, 2018

These UUIDs seem suspiciously non-random to me as well.

NewV4 gets its randomness from crypto/rand.Reader (and is basically a passthrough to populate a UUID). The code in NewV4 is really simple, I don't see how it could go wrong.

The only possibilities I can think of:

  • There is a bug in crypto/rand (seems unlikely).
  • Since crypto/rand.Reader is just a variable, some malicious/accidental code could be swapping it out for a less random io.Reader implementation.
@josselin-c

This comment has been minimized.

josselin-c commented Apr 4, 2018

Okay, I can reproduce it!
On my machine I have two separate processes: one webserver (ServerA) that calls uuid.Must(uuid.NewV4()).String() while simultaneously doing http requests to another webserver (ServerB) used for image resizing (imgproxy).

I instrumented ServerA with this code:

	go func() {
		for {
			time.Sleep(1 * time.Second)
			for i := 0; i < 1000; i++ {
				u := uuid.Must(uuid.NewV4()).String()
				if strings.Contains(u, "000000000") {
					log.Fatal(u)
				}
			}
		}
	}()

Which runs without crashing if ServerA idle or handling standard requests. If ServerA is calling ServerB (to resize images), the ServerA immediately crash with a bad uuid.
I'll try to make a self-contained reproducer

@josselin-c

This comment has been minimized.

josselin-c commented Apr 4, 2018

Okay, I found the problem.
Here is the current NewV4 code:

// NewV4 returns random generated UUID.
func (g *rfc4122Generator) NewV4() (UUID, error) {
	var err error
	var c int
	u := UUID{}
	if _, err = g.rand.Read(u[:]); err != nil {
		return Nil, err
	}
	u.SetVersion(V4)
	u.SetVariant(VariantRFC4122)

	return u, nil
}

Read() gives no guaranties about the number of bytes actually read. From https://golang.org/pkg/io/#Reader:

Read reads up to len(p) bytes into p. It returns the number of bytes read (0 <= n <= len(p)) and any error encountered

Turns out, on some occasions Read would read less than len(u) bytes. I thinks uuid should use ReadFull instead of plain Read().

@domino14

This comment has been minimized.

domino14 commented Apr 4, 2018

@josselin-c Could you make a patch and see if you can reproduce the error with your script and ReadFull? I wonder if using ReadFull would outright return an error in this case, because there aren't enough bytes to read.

@domino14

This comment has been minimized.

domino14 commented Apr 4, 2018

One more thing that is interesting to me is the fact that the UUIDs you posted are not of equal length.

josselin-c pushed a commit to josselin-c/go.uuid that referenced this issue Apr 4, 2018

Josselin Costanzi
Fix potential non-random UUIDs
Use ReadFull to fetch random bytes from crypto/rand instead of calling
Read directly as Read may read less bytes than asked.

Fix satori#73
@mikesun

This comment has been minimized.

mikesun commented Jun 1, 2018

So it looks like this commit introduced the bug: 0ef6afb

Prior to that commit, rand.Read() was used, which is a wrapper that uses io.ReadFull(): https://golang.org/pkg/crypto/rand/#Read

@CameronAckermanSEL

This comment has been minimized.

CameronAckermanSEL commented Jul 10, 2018

How is a critical bug like this still unresolved? Especially given that someone already did the work to fix it.

@theckman

This comment has been minimized.

theckman commented Jul 18, 2018

A few people in the Go community have banded together to adopt this package. We've just cut a v2.0.0 release of our fork: https://github.com/gofrs/uuid/releases/tag/v2.0.0

This is a GitHub organization with a few community members in it, so this package isn't being maintained by one individual. We're also available on the Gophers slack in #gofrs.

@rkuris

This comment has been minimized.

rkuris commented Jul 18, 2018

@zerkms

This comment has been minimized.

zerkms commented Jul 18, 2018

@rkuris gofrs being an activists collaboration is open for any suggestions, as soon as we all can agree it adds value to the project

A required note: this is not an official position, just my personal understanding of the aim of the organisation.

@sethgrid

This comment has been minimized.

sethgrid commented Aug 16, 2018

@josselin-c could you update the issue description and link to the new https://github.com/gofrs/uuid project?

arkhaix added a commit to arkhaix/go-epub that referenced this issue Aug 24, 2018

Switched to google/uuid
satori/uuid can sometimes fail to retrieve enough random bytes from the random stream, and the maintainers aren't fixing it.  See satori/go.uuid#73

talal added a commit to sapcc/limes that referenced this issue Sep 18, 2018

majewsky added a commit to sapcc/limes that referenced this issue Sep 26, 2018

talal added a commit to sapcc/limes that referenced this issue Sep 26, 2018

@satori satori closed this in #75 Oct 16, 2018

@ceriath ceriath referenced this issue Nov 13, 2018

Merged

Remove go.uuid #2224

avelino added a commit to avelino/awesome-go that referenced this issue Nov 14, 2018

Remove go.uuid (#2224)
go.uuid is currently the most starred uuid repo for go. However, it is unmaintained and contains at least one critical security, which has been fixed by PR but took nearly half a year to be merged, since the owner is not really active (satori/go.uuid#75). There is an actively maintained fork at https://github.com/gofrs/uuid which is already listed here too. go.uuid should be removed.

See 
satori/go.uuid#75
satori/go.uuid#73
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment