UEID (Unique Enough IDs, part 2)

As part of an open-source project I’m working on (right now, we are still at the technical feasibility stage where we explore and eliminate technical risks, full disclosure will come later) we have to issue session numbers. They’re not session numbers in the usual sense, but they still need to be unique, and not amenable to simple attacks.

There are a couple of ways of generating unique session numbers. RFC 4122-compliant unique IDs is one possible way.

Python does provide a UUID module (import uuid), and while its implementation is compliant to RFC 4122, it still need a little help. For example, if you’re thinking of using uuid.uuid1() to generate UUIDs, you notice that

import uuid, os

for _ in xrange(20):
    print uuid.uuid1()
    time.sleep(1)

produces the not very uniquely looking:

6850c980-655a-11e1-ad4c-f46d049a0bd8
68e9d63e-655a-11e1-ad4c-f46d049a0bd8
6982d6c2-655a-11e1-ad4c-f46d049a0bd8
6a1bd87c-655a-11e1-ad4c-f46d049a0bd8
6ab4d8ce-655a-11e1-ad4c-f46d049a0bd8
6b4da554-655a-11e1-ad4c-f46d049a0bd8
6be66c58-655a-11e1-ad4c-f46d049a0bd8
6c7f33ca-655a-11e1-ad4c-f46d049a0bd8
6d17fb00-655a-11e1-ad4c-f46d049a0bd8
6db0c268-655a-11e1-ad4c-f46d049a0bd8
6e4989a8-655a-11e1-ad4c-f46d049a0bd8
6ee25174-655a-11e1-ad4c-f46d049a0bd8
6f7b18c8-655a-11e1-ad4c-f46d049a0bd8
7013e04e-655a-11e1-ad4c-f46d049a0bd8
70aca798-655a-11e1-ad4c-f46d049a0bd8
71456dc0-655a-11e1-ad4c-f46d049a0bd8
71de34b0-655a-11e1-ad4c-f46d049a0bd8
7276fb28-655a-11e1-ad4c-f46d049a0bd8
730fc1f0-655a-11e1-ad4c-f46d049a0bd8
73a8884a-655a-11e1-ad4c-f46d049a0bd8

Only a relatively small part of the key changes between calls. As I’ve said before, using slow- or little-varying keys is just begging to get hacked. Not sure how realistic it is to have a time-based attack on sessions numbers, but the fact is that they’re not random enough. They may be locally UUIDs, but they’re not random enough to rule out the possibility of finding a session number.

Fortunately, we can feed the UUID class a random stream of garbage strong random bits and it will kindly convert it into a RFC-4122-looking UUID. The following code:

session_id = uuid.UUID(bytes=os.urandom(16))

gets the random bits from the /dev/urandom device, which is not quite cryptographic grade, but much stronger than the infamous C library rand. The random stream is RFC-4122 formatted and yields:

2ba28331-6623-9da0-5dca-c9d45e446381
fb35c53b-dbcb-7b60-f825-33f85ee037b1
1ef51981-7279-29de-b6b4-b12baf664997
6dca9a08-f300-abdb-ee5d-52add464dce6
2f7a9978-000b-6c37-2179-049deea3f087
1e350dcd-89d6-2378-06da-e4db3c509fe8
b2408a16-2923-dd2a-9eaa-9fb01efde1ce
24f3afec-dc51-4fd7-89e5-5db11f650d52
897b2644-12e9-3da4-52cc-992fff4f8eef
52c00394-01e2-88bc-0c29-33f77ea2791a
90a016f7-8c1a-67f2-835e-dd399148ad2a
3c684d11-d558-e5d5-ecb2-9aaf145bf8b4
0135b666-dc88-16bf-278d-605d70cd0203
4d0f6f7e-e67b-3e1c-8ea9-495ff60d1621
a49de6e8-aa25-9dde-8c32-e8d8e5b8bc3e
e5d681a9-da44-d7ae-72c9-7deaa3b96f27
079cc2f1-b6b1-1a1d-2bdf-2096f677c983
e56f648b-7038-b287-5285-2c689e3a07b3
cf9be65a-41b1-d99b-e0ef-5a79eda8c3e7
e4fdf6eb-5d39-b58b-fa1b-b35adbcd0efd

for immediately consecutive calls.

*
* *

So basically, we’re probably better off using simply strong random numbers converted into (long) identifiers. The (current) Python documentation state that for uuid1, If clock_seq is given, it is used as the sequence number; otherwise a random 14-bit sequence number is chosen. 14 strongly random bits may be somewhat of a protection (it can yield 2^{14}=16384 different combination) and the simple experiment above indicate that some extra time-based random elements are used (there are more than 14 bits varying between calls, maybe 20, maybe up to 28), but it still doesn’t look nearly random enough to rule out exploits.

*
* *

Strong sessions numbers are one thing, but one may as well use extra protection such as correlating IP addresses and browser id with the session numbers. In our ultimate application, there is no need for cryptographic signature and the usual secure web-based transaction framework, only that we are (very) confident that the data associated with a session number comes from the session owner, and that we can discard (or at least segregate) suspicious/malevolent data we receive.

2 Responses to UEID (Unique Enough IDs, part 2)

  1. jfdube says:

    Nice piece. You might want to take a look at this blog post: http://jfdube.wordpress.com/2011/09/21/guid-generation/ on the same subject!

  2. Noach says:

    Steven, I’m certainly no expert on UUIDs, but it seems to me you’ve totally missed the point of them. From the RFC:
    “6. Security Considerations
    Do not assume that UUIDs are hard to guess; they should not be used
    as security capabilities (identifiers whose mere possession grants
    access), for example.”

    And from the Wikipedia page:
    “The intent of UUIDs is to enable distributed systems to uniquely identify information without **significant central coordination**.”
    “Anyone can create a UUID and use it to identify something with reasonable confidence that the same identifier will never be **unintentionally** created by anyone to identify something else.”

    In other words, UUIDs have nothing to do with cryptographic unpredictability. They are simply a means of generating a unique (for all *practical* purposes) number without having to actually *coordinate* that uniqueness.

    The reason why your version 1 UUIDs are all so similar is that version 1 UUIDs are simply a timestamp combined with your network interface’s MAC address. (MAC addresses are guaranteed to be globally unique, by central coordination among the hardware manufacturers.) Quoting the Wikipedia article again:
    “This scheme [version 1] has been criticized in that it is not sufficiently “opaque”; it reveals both the identity of the computer that generated the UUID and the time at which it did so. However, its uniqueness is deterministic.”

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: