Non-repeating, non-sequential numbers and web sessions

I have an application that needs to create a non-repeating,
non-sequential number identical in purpose to the session ID web
applications us to discriminate between user sessions.

I was looking around the VWave code and found what looked to be the way
VWave does it:

    HttpSession>>#initKey

        key := WebSession sessionKeyStream next printString, Timestamp
    now asSeconds printString, Time millisecondClockValue printString.

It looks workable, but was unable to find documentation that the
resulting bytestring would be unique.

Any comments or alternative approaches?

--
Visit <http://tggagne.blogspot.com/>,<http://gagne.homedns.org/> or
      <http://gagne.homedns.org/~tgagne/> for more great reading.

You could try using a GUID. Simply load "Com- All" and evaluate
"External.GUID new". This will create a GUID based on the CoCreateGuid
function in Windows. If you are on other platforms, I do not know if
VisualWorks supports GUID creation.

More information on GUID/UUID is found here
http://www.famkruithof.net/guid-uuid-info.html

Runar Jordahl

UUIDs are presumably the sort of thing you're looking for. There is a preview version of a UUID parcel in the 7.5 builds. These aren't going to be guaranteed globally unique, they settle for the "extremely unlikely" case. I believe the only mechanism within UUID's for trying to really guarantee uniqueness relies on the MAC address of the network card, and with virtualization that's becoming increasingly unreliable anyway, and it seems to have been pretty much abandoned. Anyway, that parcel supports several of the UUID variations. It's certainly more likely to be unique than Wave's mechanism.

At 03:06 PM 11/22/2006, Thomas Gagné wrote:

I have an application that needs to create a non-repeating, non-sequential number identical in purpose to the session ID web applications us to discriminate between user sessions.

I was looking around the VWave code and found what looked to be the way VWave does it:

   HttpSession>>#initKey

       key := WebSession sessionKeyStream next printString, Timestamp
   now asSeconds printString, Time millisecondClockValue printString.

It looks workable, but was unable to find documentation that the resulting bytestring would be unique.

Any comments or alternative approaches?

--
Visit < http://tggagne.blogspot.com/ >,< http://gagne.homedns.org/> or
     < http://gagne.homedns.org/~tgagne/> for more great reading.

Unless I'm much mistaken, someone should be blushing now: "Timestamp now asSeconds" is already included in "Time millisecondClockValue". All in all initKey looks like a pretty bad way to handle things, but should be OK for most use. KeyStream has <300,000 values (VW7.4), but the millisecond clock means that you'd need 300,000 requests in a millisecond to get a duplicate. Since each initKey takes 25us, that's pretty unlikely :-).

If you have a requirement that the string is or looks random, initKey is very bad: most of its bits can be predicted.

I'd imagine it would be better to move KeyStream to MinimumStandardRandom, to get >3,000,000,000 values. That in itself would be enough for most applications, providing you could save the seed on exit and read it on re-start. Calculating each value takes about 8us, including printing (without dividing by m). Or then you could go the whole hog and use DSSRandom: even that only takes 200us per value including printing (100 digit values!).

Steve

Steve,

        further, millisecondClockValue and secondClock are derived from microsecondClock, which, although it does depend on OS clock resolution, is the primitive source for all times in the system.  If one is to use times for seeds then microsecondClock is the one to use.

"Steven Kelly" <[hidden email]> wrote:

| Unless I'm much mistaken, someone should be blushing now: "Timestamp now asSeconds" is already included in "Time millisecondClockValue". All in all initKey looks like a pretty bad way to handle things, but should be OK for most use. KeyStream has <300,000 values (VW7.4), but the millisecond clock means that you'd need 300,000 requests in a millisecond to get a duplicate. Since each initKey takes 25us, that's pretty unlikely :-).

| If you have a requirement that the string is or looks random, initKey is very bad: most of its bits can be predicted.

| I'd imagine it would be better to move KeyStream to MinimumStandardRandom, to get >3,000,000,000 values. That in itself would be enough for most applications, providing you could save the seed on exit and read it on re-start. Calculating each value takes about 8us, including printing (without dividing by m). Or then you could go the whole hog and use DSSRandom: even that only takes 200us per value including printing (100 digit values!).

| Steve

| > -----Original Message-----
| > From: Thomas Gagné [mailto:[hidden email]]
| > Sent: 22 November 2006 22:06
| > To: vwnc
| > Subject: Non-repeating, non-sequential numbers and web sessions
| >
| > I have an application that needs to create a non-repeating,
| > non-sequential number identical in purpose to the session ID web
| > applications us to discriminate between user sessions.
| >
| > I was looking around the VWave code and found what looked to be the way
| > VWave does it:
| >
| >     HttpSession>>#initKey
| >
| >         key := WebSession sessionKeyStream next printString, Timestamp
| >     now asSeconds printString, Time millisecondClockValue printString.
| >
| > It looks workable, but was unable to find documentation that the
| > resulting bytestring would be unique.
| >
| > Any comments or alternative approaches?
| >
| > --
| > Visit <http://tggagne.blogspot.com/>,<http://gagne.homedns.org/> or
| >       <http://gagne.homedns.org/~tgagne/> for more great reading.
---
Eliot Miranda                 ,,,^..^,,,                mailto:[hidden email]
VisualWorks Engineering, Cincom  Smalltalk: scene not herd  Tel +1 408 216 4581
3350 Scott Blvd, Bldg 36 Suite B, Santa Clara, CA 95054 USA Fax +1 408 216 4500

A GUID is sufficient but maybe not necessary:

> I have an application that needs to create a non-repeating,
> non-sequential number identical in purpose to the session ID web
> applications us to discriminate between user sessions.

It sounds like it's enough that the number be unique from Thomas' server, not necessarily unique if there are a million such servers all generating numbers simultaneously. GUIDs also try to work under the requirement that the servers cannot communicate. If they could communicate, it would be simpler that each server request numbers from a central server. For scalability, this would normally be implemented so that they request a batch of numbers at a time.

Sorry, I know this level of detail is probably overkill, and any of the solutions suggested would be just fine in most situations. I've just always found these issues of "global uniqueness" fascinating!

Steve

A co-worker of mine has suggested looking into how Apache manufactures
those numbers.  Apparently they have some formula that guarantees (I'll
have to read more about it) global uniqueness.  I'm unsure how they do
it, but if I can borrow the code and perhaps make it a shared-library
it's worth a shot.

Does that sound reasonable or is it an example of inappropriate reuse?

--
Visit <http://tggagne.blogspot.com/>,<http://gagne.homedns.org/> or
      <http://gagne.homedns.org/~tgagne/> for more great reading.

What does everyone think of using/copying
<http://httpd.apache.org/docs/2.2/mod/mod_unique_id.html>?

--
Visit <http://tggagne.blogspot.com/>,<http://gagne.homedns.org/> or
      <http://gagne.homedns.org/~tgagne/> for more great reading.

You said you wanted non-sequential values, but this is pretty much sequential. It's also highly predictable (don't know if spoofing through prediction is an issue for you).

I'm only an amateur at this stuff, but to my eye it looks like this mod has been made by people who know Unix and web servers, but not necessarily so much about random numbers, security or cryptography. If you want non-sequential values, random seems the best way to go [I won't bother saying "pseudo-random" since I'm with Einstein: nothing is truly random :)]. If you need values that are hard to predict, you need "cryptographic" random. If you're just on Unix, don't most Unices these days have a good source of random numbers (not just algorithmically generated) in /dev/rand?

If all you need is a non-sequential value that doesn't repeat on a single server in N values, how about this: Just use the KeyStream approach with a counter, possibly with a better Random subclass to increase N. Save the counter and seed to a file every 100 values and on exit. On a restart after a clean exit you just read the counter and seed from the file and continue. After a crash, read them then calculate and throw away the next 100 values (to avoid duplicating keys you gave out between writing the file and crashing).

Steve

Steven Kelly wrote:
> Or then you
> could go the whole hog and use DSSRandom: even that only takes 200us
> per value including printing (100 digit values!).

DSSRandom is kinda awkward and somewhat expensive. An interesting alternative can be found in CiphersDevelopment in the public repository. It's called Fortuna and it's one of the newer ones from Schneier (more details can be found in his Practical Cryptography). There are comments and tests in that package as well to get you started quickly. And who knows, we might even ship it officially one day :). Any feedback is of course welcome.

Martin