5 ms·

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 so

by mmalone 11y ago

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 https://twitter.com/BrendanEich/status/667735502691373056 [2] https://news.ycombinator.com/item?id=10605977 https://news.ycombinator.com/item?id=10605977

ss95060 11y ago
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.
- mmalone 11y ago
  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.
  - ss95060 11y ago
    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.
    - mmalone 11y ago
      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.
      - ss95060 11y ago
        You might want to read this: http://security.stackexchange.com/questions/89813/managing-keys-generated-with-insufficient-entropy/89817 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!
        mmalone 11y ago
        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.

by mmalone 11y ago

ss95060 11y ago

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.

mmalone 11y ago
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.
- ss95060 11y ago
  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.
  - mmalone 11y ago
    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.
    - ss95060 11y ago
      You might want to read this: http://security.stackexchange.com/questions/89813/managing-keys-generated-with-insufficient-entropy/89817 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!
      - mmalone 11y ago
        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.