Hacker News Reader

Comment by blahedo | Hacker News Reader

Perhaps, but the mindset here is fundamentally academic: here is an interesting problem, I wonder what I can learn about its properties? And having looked into those properties, the author decides to write them up and disseminate them. (Very well, I might add. I filed the link in a bookmark folder I keep for "articles I'd like to assign my students to read, next time I teach a relevant class. This one is well-written and well-referenced.)

View on HN

Sure, but I still see two problems:

1. Math.random, despite his insistence, isn't broken. There are different degrees of randomness that a programmer might need for their program and Math.random simply didn't suit his.

2. Their initial implementation of a critical portion of their infrastructure was so naïve, I almost couldn't couldn't believe it. I just seemed like such an anti-pattern to try to build your own UUIDs, discover (in production!) that they're not so good and then spend days figuring out why a built-in random number generator that ships in every browser isn't so great.

1. In this case we're arguing semantics. Fine, it's not broken, but it's still bad and there are better alternatives with no drawbacks. Arguing to keep it is sort of like arguing to keep an O(n) algorithm that has an O(log n) alternative that's also more intuitive and easier to code. If you still don't believe me, here's what Brendan Eich thinks[1].

2. I've addressed the standard solution / UUID question elsewhere[2]. The way we were generating identifiers is not an anti-pattern. It's a pattern. It's the standard way to produce a random string from an alphabet. If you look at the source code of any website, from HN to Google, I guarantee you will find an almost identical piece of code somewhere. The code is simple, but that doesn't make it bad.

[1] https://twitter.com/BrendanEich/status/667735502691373056

[2] https://news.ycombinator.com/item?id=10605977

Your code used the naive algorithm and the system PRNG to generate a set of "random" and thus probably "unique" strings. The PRNGs supplied with many languages are widely known to be of poor quality. The results were bad, for reasons you later discovered. "Anti-pattern" sounds correct to me.

A safe approach is to run multiple uncorrelated sources of probable uniqueness/[pseudo]randomness through a modern cryptographic hash function, and generate your "unique" string from the hash output.

In other words the code itself is, in principal, fine. The PRNG it used was not fine. Had it used a CSPRNG there would not be a problem, and generating identifiers in this manner is perfectly safe and not an anti-pattern. Hashing the output of an already good (CS)PRNG is the real anti-pattern. It can only reduce entropy and make things worse.

I've acknowledged the incorrect assumptions / taken blame for not doing proper diligence on the PRNG. What I'm saying here is that the identifier generation technique is not, in principal, flawed. It is a common technique and it has many legitimate use cases. It's simple enough that pulling in a dependency to solve it for you is not an obviously better alternative.

True randomness and a crypto-strength PRNG are good options here, but they're not necessary. There are peer reviewed proofs that show something like MT19937 is suitable (perhaps even better suited) for this sort of task. See the deeply nested comment thread ITT for more of that debate.

Suppose, somehow, you seed your super-duper PRNG with the same value on multiple servers. If you are not incorporating other forms of entropy into your unique IDs, you are hosed.

The cryptographic hash acts sort of like a blender for all your random/unique-ish information sources. Counters/MACs/urandom/times/IPaddrs/etc go in, a nicely mixed value comes out.

Meh. You should just use all of that random unique-ish stuff to properly seed your PRNG. You're trying to improve the generator "randomly," which is generally dangerous and can be counterproductive. Better to rely on sound theory and good practice / keep it simple. Leave all that craziness to the kernel entropy pool and just use it as a seed.

You might want to read this:

http://security.stackexchange.com/questions/89813/managing-k...

Anyways, if you decide you want to learn more about secure hash functions and cryptography in general, you can't go wrong with Bruce Schneier's "Applied Cryptography".

Good luck!

Applied Cryptography is a good book. I first read it more than 15 years ago :). Schneier actually designed the CSPRNG that is used by OS X. It's called Yarrow and is SHA based. It does more or less what you suggest, but with many subtle improvements to mitigate attacks. It has features that you're unlikely to properly reproduce in user-space. Trying to improve its output by re-hashing in user-space is, even if done properly, unnecessary. If you screw something up and do it improperly you could easily reduce the quality of the generator.

I'm not sure how your link is relevant. If there's not enough entropy on the system for the kernel, there's not enough for you either.

Reply on news.ycombinator.com