1 2 Previous Next 55 Replies Latest reply on Mar 2, 2012 7:29 AM by 12Robots Go to original post
• ###### 40. Re:  CreateUUID

I have decided to discuss your demonstrations first. The discussion on your definition of 'randomness' and 'uniqueness' follows later.

To demonstrate how these concepts are very different let's look at some test results from within a small system

Say the system has a range of 1000 possible values, and we take ten samples.  And the algorithms are "perfect".

The random sample could be:

500, 123, 666, 42, 1, 789, 501, 42, 317, 256.

Note that 42 has - completely randomly - occurred twice.  In fact just as random as the result above, would be this result:

1, 1, 1, 1, 1, 1, 1, 1, 1, 1

That is no less likely to be the result than the seemingly more random one.

If we extend this out to be 1000 samples, there is an equal chance of any given element having the same value as one other element as there is for it to be any other specific number.

Duplicates are part and parcel, and completely "expected" in random number series.

I accept that this is a demonstration of randomness. However, I fail to see the connection with the context of CFToken. To substantiate this, I will now show that your statement,  'Duplicates are part and parcel, and completely "expected" in random number series', falls short of the mark.

Your statement applies only to samples drawn from a small population! The CFtoken context gives us an indication of the kind of poputation size we ought to be thinking about: upwards of 16^16, that is, upwards of 10 to the power 19. If the samples are drawn from a population consisting of a very large number of distinct entities, the rules of the game change.

While I agree with you that any 2 such samples have the same probability of occurring, I think your statement, 'Duplicates are part and parcel, and completely "expected"', is wrong in this case. In fact, it is a trivial exercise to actually prove that duplicates become less and less expected as the population size grows.

On the other hand, a unique algorithm "guarantees" (for all intents and purposes) that the results are... well... unique.

In the 1000-item example, a completely legit uniqueness algorithm might be to simply increment a counter:

1,2,3,4,5,6,7,8,9,10.

(and this algorithm still works perfectly right out to the full 1000 item sample size).

There is no randomness there (randomness is not part of the remit of a uniqueness algorithm), and it is entirely predictable (lack of predictability is not part of the remit of a uniqueness algorthim).  Also a preceding result directly inflences the next result (the next being an increment of the previous).

So this in itself demonstrates that randomness and uniqueness are very different qualities, and differ significantly when it comes to the qualities that each are measured by (predictability, and how much one value influences another).

When it comes to real-world examples, UUIDs can be generated in a completely predictable fashion.  The composition of a UUID could be:

* MAC address of a NIC in the box generating the UUID

* the time down to some arbitrary accuracy (the one I looked at was down to 100ns)

* a correction value (should the time be adjusted backwards between one UUID and the next)

* a counter (to allow for UUIDs to be generated faster than the accuracy of the clock)

If one presupposes that a MAC address is adequate to be a unique spatial identifier, and the correction values and counter are large enough to not overflow, then this will generate unique values, and not be at all random.

If one was not satisfied with the MAC solution, and technology was slightly better than we currently have, a "perfect" uniqueness algorithm could be implemented using the geolocation of the machine running the algorithm (accurate to a degree smaller than the size of the machine, so it guarantees no machines can have a same value), and a time clock more accurate than the time it takes to generate a result (so every result from a given machine occurs at a different time). The unique value then is simply machine location + current time.

Really the only similarity between the two concepts is that both use an algorithm, and both provide results. Beyond that, they are mostly disconnected concepts.

All well argued and all plausible, I must admit. However, you talk about a unique algorithm, whereas uniqueness applies to the entities or samples generated, and not to the method of generation. That was the foundation of your argument on uniqueness. A feeble foundation never leads to a solid building.

The way I read it, this is one of those tales that is full of sound and fury, but that signifies little. As I have already reminded you, the Adobe livedocs gives us a starter, namely, uniqueness on the basis of at least 16^16 entities.

Is that enough?

No. I'll return to show you an argument that establishes equivalence between randomness and uniquenss in the CFToken context. I have to run -- duty calls.

• ###### 41. Re:  CreateUUID

Owain North wrote:

I like turtles.

In my opinion, certainly the deepest wisdom in this thread so far.

• ###### 42. Re:  CreateUUID

Let's clarify this outwith the context of CF.

Randomness.  A series of values is random if the next value cannot be inferred from the previous values (in part or as a whole), and no previous values have any influence over subsequent values.  A measure of the randomness of an algorithm is how well it fulfils that criteria.

Uniqueness.  A value within a series is unique if it occurs only once.  A measure how well an algorithm provides unique results is in what the probability of getting duplicate results is.

To demonstrate how these concepts are very different let's look at some test results from within a small system

There are quite a number of loose ends here. The context and definitions just don't tie up.

You start by saying the context is CF, by which I presume you mean CFToken. Again, remember that the population size is >= 16^16. Yet the last sentence in this excerpt is looking at some test results from a "small" system.

There is an obvious difference between your definitions and mine. You talk about the randomness and uniqueness of algorithms. Whereas I talk about the randomness and uniqueness of samples or entities like CFToken. No right or wrong there. Whichever definition one uses, what matters is whether one consistently goes from definition to conclusion.

Well, you don't. You say, for example, that "A value within a series is unique if it occurs only once". This is blatantly false. Correct is: a value within a series is unique if the probability of it occurring more than once is close to zero.

• ###### 43. Re:  CreateUUID

I am trying to simplify my proof to a readable format accessible to everyone in the forum. Please bear with me.

• ###### 44. Re:  CreateUUID

Instead you hide behind a smokescreen of insults and trivial, half-baked ideas. Let's get back to basics. Here again is my attempt at establishing the context in which I said uniqueness is equivalent to randomness:

Uniqueness: If you pick one CFToken from an extremely large list of CFTokens generated by ColdFusion, the probability of there being another one identical to it is negligible.

Randomness: If you pick any arbitrary number of consecutive CFTokens in the list, you will be unable to find an algorithm to use them to predict the next one.

I may or may not be right, but that is another matter. I have at least put up. Whereas, you and Dave criticize and criticize, without ever once telling the forum what you understand by randomness or uniqueness.

So let's skip the chase. Tell us what you mean by "randomness" and "uniqueness". In any context you choose to name. If what I've seen so far is anything to go by, we'll be waiting here till we begin to grow feathers.

This will be my last post in this thread, but I think you deserve as good an explanation as I can provide.

Earlier in the thread, you stated that the words "uniqueness" and "randomness" meant the same thing, in a specific context. Here, you are providing separate definitions for each, and these definitions do not mean the same thing. That was the gist of my earlier point. That's all. I don't even need to define the words to dispute what I see as the contradiction between your own statements. Perhaps you can provide alternative definitions for the two words where they do, in fact, mean the same thing, but what you've written so far contradicts itself on its face. Perhaps it may be the case that any algorithm that guarantees randomness also guarantees uniqueness, but again that doesn't affect the contradiction in what you've written. Perhaps it is the case that the algorithm that CF uses for CFTOKEN guarantees randomness as a side-effect of guaranteeing uniqueness or vice-versa, but again that doesn't affect the contradiction in what you've written. One doesn't need to be a mathematician to see this.

Now, perhaps you will choose to mark this as "seen, but not read" - that's fine with me, I suppose. I'm not sure how you see something without reading at least some of it, or why you'd bother pointing out that you'd done this, but I guess that doesn't really matter. I am offering my response in good faith, as I always do.

Dave Watts, CTO, Fig Leaf Software

• ###### 45. Re:  CreateUUID

Dave Watts wrote:

Instead you hide behind a smokescreen of insults and trivial, half-baked ideas. Let's get back to basics. Here again is my attempt at establishing the context in which I said uniqueness is equivalent to randomness:

Uniqueness: If you pick one CFToken from an extremely large list of CFTokens generated by ColdFusion, the probability of there being another one identical to it is negligible.

Randomness: If you pick any arbitrary number of consecutive CFTokens in the list, you will be unable to find an algorithm to use them to predict the next one.

I may or may not be right, but that is another matter. I have at least put up. Whereas, you and Dave criticize and criticize, without ever once telling the forum what you understand by randomness or uniqueness.

So let's skip the chase. Tell us what you mean by "randomness" and "uniqueness". In any context you choose to name. If what I've seen so far is anything to go by, we'll be waiting here till we begin to grow feathers.

This will be my last post in this thread, but I think you deserve as good an explanation as I can provide.

Earlier in the thread, you stated that the words "uniqueness" and "randomness" meant the same thing, in a specific context. Here, you are providing separate definitions for each, and these definitions do not mean the same thing. That was the gist of my earlier point. That's all. I don't even need to define the words to dispute what I see as the contradiction between your own statements. Perhaps you can provide alternative definitions for the two words where they do, in fact, mean the same thing, but what you've written so far contradicts itself on its face. Perhaps it may be the case that any algorithm that guarantees randomness also guarantees uniqueness, but again that doesn't affect the contradiction in what you've written. Perhaps it is the case that the algorithm that CF uses for CFTOKEN guarantees randomness as a side-effect of guaranteeing uniqueness or vice-versa, but again that doesn't affect the contradiction in what you've written. One doesn't need to be a mathematician to see this.

Now, perhaps you will choose to mark this as "seen, but not read" - that's fine with me, I suppose. I'm not sure how you see something without reading at least some of it, or why you'd bother pointing out that you'd done this, but I guess that doesn't really matter. I am offering my response in good faith, as I always do.

Dave, I have just opened my e-mail, and read your response with interest. In fact, though it's too early for me to come to the forum, I decided to make an exception.

Forget the "seen, but not read" quip. We were after all in the heat of the action.

Your present argument is strong. You pong my ping back to me. Quite some food for thought there. It's indeed now up to me to show how the two things weave into one.

I already did so, but entirely in logical symbols. As I said earlier, I'm in the process of translating it from abracadabra into plain English. Not easy when one is in the middle of a hectic stretch of a project.

I hope you will be satisfied by my attempt. Thanks for the challenging read.

• ###### 46. Re:  CreateUUID

I hope you will be satisfied by my attempt. Thanks for the challenging read.

I am certainly satisfied that you are also responding in good faith, and that's all I can really ask for from anyone.

Dave Watts, CTO, Fig Leaf Software

• ###### 47. Re:  CreateUUID

BKBK wrote:

I am trying to simplify my proof to a readable format accessible to everyone in the forum. Please bear with me.

Here then is an attempt. You can download the PDF from https://acrobat.com/#d=h5Y6AC5XiWCwHHa-BkTe8g.

• ###### 48. Re:  CreateUUID

I couldn't get to it with my Adobe account.

Permissions issues are the story of my life, though.

Dave Watts, CTO, Fig Leaf Software

• ###### 49. Re:  CreateUUID

Not that it helps you Dave, but I could see it fine (albeit it took an absolute age to load).  So - BKBK - perhaps the perms are set for some users but not others?

Or Dave, are you clicking just from the email from the forums?  I went into the web UI and clicked the link from there (so I was alrady authenticated before clicking the link)?

--

• ###### 50. Re:  CreateUUID

• ###### 51. Re:  CreateUUID

Not that it helps you Dave, but I could see it fine (albeit it took an absolute age to load).  So - BKBK - perhaps the perms are set for some users but not others?

Or Dave, are you clicking just from the email from the forums?  I went into the web UI and clicked the link from there (so I was alrady authenticated before clicking the link)?

I was clicking the link in the email, rather than going into the forums and clicking from there. Once I did that I could see it just fine, so there's no permissions issue.

BKBK, on first glance, I must say that you have certainly put a lot of effort into this. Probably more than it really deserves, since I can't really pay you for that effort. But in the end, I still disagree. I will try to address the core of this disagreement after my noon deadline, but for now, suffice it to say that I don't think we agree on what "equivalence" means, and the reduceability of words to logical operands.

All that said, I congratulate you on the most thorough response I've ever seen to a forum post.

Dave Watts, CTO, Fig Leaf Software

• ###### 52. Re:  CreateUUID

Not that it helps you Dave, but I could see it fine (albeit it took an absolute age to load).  So - BKBK - perhaps the perms are set for some users but not others?

Or Dave, are you clicking just from the email from the forums?  I went into the web UI and clicked the link from there (so I was alrady authenticated before clicking the link)?

I was clicking the link in the email, rather than going into the forums and clicking from there. Once I did that I could see it just fine, so there's no permissions issue.

BKBK, on first glance, I must say that you have certainly put a lot of effort into this. Probably more than it really deserves, since I can't really pay you for that effort. But in the end, I still disagree. I will try to address the core of this disagreement after my noon deadline, but for now, suffice it to say that I don't think we agree on what "equivalence" means, and the reduceability of words to logical operands.

All that said, I congratulate you on the most thorough response I've ever seen to a forum post.

Agree with everything you say there, the most important bit being how good the doc is (TBH, I didn't read it all - I'm at work - but I will later).

My point of contention is this... what BKBK initially said was this:

BKBK wrote:

12Robots wrote:

The random string is not meant to make the token more unique, it is meant to make it random.

Actually, more unique means random!

So was making a connection between uniqueness and randomness being related.

And this is what Jason, Dave and I have been disagreeing with. "Unique" does not mean "random", and "random" does not mean "unique".

BKBK also said this:

In the above context (of CFToken) uniqueness and randomness are synonymous.

This is not correct either.  I would accept that "in the context of a CFToken value, either approach would be OK for all intents and purposes", but that's not the same as them being synonymous.  They are still distinct concepts (I think we can all agree on that), it's just that either concept will suitably meet the requirement CFToken has.

And that's what the doc seems to discuss: that for the purpose of a CFTOKEN value, a random value will be - for all intents and purposes - as good as a specifically unique value.

I don't think anyone would quibble with that.

Indeed this all started with me questioning the merit of adding an additional random element to a UUID to construct the CFToken value, because it seems like pointless egregiousness (if that's a word).  The UUID by itself already fulfils the requirement, and has the benefit of being an-industry-accepted approach to such things.  What Adobe seems to have done is to invent their own little solution, where the industry-accepted solution is already just fine.  And that - IMO - is a bit thick of them.

--

• ###### 53. Re:  CreateUUID

I don't think Adobe is being thick at all. Nor are they going against any industry standard.

Session tokens need to be unique and sufficiently random. CF's UUIDs provide the uniqueness and the Random long integer at the end provides the sufficient randomness. I believe you said earlier in your thread that based on what you saw in the source code that the CF UUID by itself provided abotu 96-bits of randomness (Do any of us have any idea what the entropy limitations are on that method, cause that could reduce the bits of randomness).

The industry standard ( turn to OWASP for that) is *at least* 128-bits of randomly generated numbers created by a cryptographically strong PRNG. https://www.owasp.org/index.php/Insufficient_Session-ID_Length

So what I see is Adobe living up to (and possibly exceeding and future-proofing) the industry standard. The UUIDs by themselves are not sufficient to meet OWASP recommendations.

Jason

• ###### 54. Re:  CreateUUID

I don't think Adobe is being thick at all. Nor are they going against any industry standard.

Session tokens need to be unique and sufficiently random. CF's UUIDs provide the uniqueness and the Random long integer at the end provides the sufficient randomness. I believe you said earlier in your thread that based on what you saw in the source code that the CF UUID by itself provided abotu 96-bits of randomness (Do any of us have any idea what the entropy limitations are on that method, cause that could reduce the bits of randomness).

The industry standard ( turn to OWASP for that) is *at least* 128-bits of randomly generated numbers created by a cryptographically strong PRNG. https://www.owasp.org/index.php/Insufficient_Session-ID_Length

So what I see is Adobe living up to (and possibly exceeding and future-proofing) the industry standard. The UUIDs by themselves are not sufficient to meet OWASP recommendations.

That doc says "128 bits" not "128 bits of randomness".  A UUID is 128-bit.  Just that only 96-bits of the CF ones are random.

That OWASP is saying 128-bits and a UUID is 128-bits is not coincidence.

By my reading of the doc, CF's 128-bit UUID provides 96-bits of entropy.  1.5x the amount they suggest in their calculations.

So what I see is Adobe living up to (and possibly exceeding and future-proofing) the industry standard.

But, yeah, fair enough.  It makes sense on this basis.

--