> I could run it out to md5 and trim the first n chars but that’s not going to be very unique.
What? MD5 going to be orders of magnitude better than what he's given.
> Storing a truncated checksum in a unique field means that the frequency of collisions will increase geometrically as the number of unique keys for a base 62 encoded integer approaches 62^n.
Well, duh. That's a given. And his solution won't do any better.
> I’d rather do it right than code myself a timebomb.
Doing it right would be using a real hash. Not something you came up with over a cup of coffee.
> Pretty random-looking, huh?
If that's his idea of testing for randomness... Use any randomness test and I guarantee you MD5 will preform better and faster.
> This is a minimum security technique.
This is the best piece of advice in the whole piece. Please never ever use this for something you want to be secure. I haven't tried to break it (maybe I'll do that over the weekend), but giving it a first glance I would be willing to bet anyone with some skill would be able to do so.
"Anyone, no matter how unskilled, can design an algorithm that he himself cannot break." -- Bruce Schneier
Okay, sure, but that's trivial. You've just created a bijection from Z[62^5] to Z[62^5]. I could just use "X+1 mod 62^5" and get the same effect, minus some fake attempt at security.
You won't get any better with that. Even if MD5 was a true source of randomness, the problem is still that you've only got 32 bits, so you'd expect a collision after 2^16 with a random function.
Besides, xoring the other bits does nothing to increase the security on non-broken hashing functions. Take the extreme case of xoring every bit to generate either a 0 or a 1. You've put a lot of effort into generating that single bit, but it's no more random than if you just took the lsb of the hash.
If you use a prime near 62^n/2, udihash(range(1,10)) would still be unique but it would return a list that clearly has some linearity (V0001, 00002, V0003, 00004, V0005, 00006, V0007, 00008, V0009, 0000A, etc).
Using a prime near the golden ratio makes the list appear less linear (cJio3, EdRc6, qxAQ9, TGtEC, 5ac2F, huKqI, KE3eL, wXmSO, YrVGR, BBE4U).
Why wouldn't you run MD5 with binary output, then convert the output to base 62? That's ~21 digits in base 62 and doesn't require figuring out your own hashing function.
This looks like a clumsy way to implement modulus multiplication. My php is (thankfully) rusty, but it looks like an affine cipher with a fixed key?
If it is, a user can obtain two consecutive "hashes" and calculate past and future hashes. If they know the corresponding plaintext for a single hash, they can calculate arbitrary hashes.
> openssl_encrypt('asdf', 'aes-256-cfb', 'a password', false, 'initialization v');
returns: 4kavvg==
You get the same direct mapping of inputs to outputs but you don't have to re-invent affine ciphers and make guesses about its security properties. And since you're just using it to turn a small integer into something bigger to make clients/users happy and not to protect data, Mr. Ptacek won't flame you out.
On a related note, I've been trying to figure out a way to encode MongoDB ObjectIDs ( a 24-char hex string, like `"4d82a373aeb4b69aec000001"` ) into a shorter Base64 string usable in URLs (eg, `/posts/{id}` ). The problem is, it still takes a 16-char Base64 to represent the same number as a 24-char hex string, and the Base64 one is even uglier.
I've been contemplating a way to generate my own ids, similar to this, but was running into trouble on how to make sure its always generated unique, on distinct machines.
just use a b64uri-encoded uuid, it will be 22 characters long, but you will never run into a problem and the aesthetic quality of your random ids should never matter.
Yes, at some point you need some sort of atomic ID generation. I'm using Riak for the key-value store and Redis's atomic incr for the ID generation. Anyone who wants to save an object into the bucket first has to get a unique ID from Redis to be rotated and base62 encoded.
21 comments
[ 5.4 ms ] story [ 75.7 ms ] thread> I could run it out to md5 and trim the first n chars but that’s not going to be very unique.
What? MD5 going to be orders of magnitude better than what he's given.
> Storing a truncated checksum in a unique field means that the frequency of collisions will increase geometrically as the number of unique keys for a base 62 encoded integer approaches 62^n.
Well, duh. That's a given. And his solution won't do any better.
> I’d rather do it right than code myself a timebomb.
Doing it right would be using a real hash. Not something you came up with over a cup of coffee.
> Pretty random-looking, huh?
If that's his idea of testing for randomness... Use any randomness test and I guarantee you MD5 will preform better and faster.
> This is a minimum security technique.
This is the best piece of advice in the whole piece. Please never ever use this for something you want to be secure. I haven't tried to break it (maybe I'll do that over the weekend), but giving it a first glance I would be willing to bet anyone with some skill would be able to do so.
"Anyone, no matter how unskilled, can design an algorithm that he himself cannot break." -- Bruce Schneier
These keys are GUARANTEED to be unique. You can run all the way up to 62^n without any key conflicts.
If you truncated an MD5 to 3 characters, by 62^3/2 you'd have a 50% chance of collision.
Besides, xoring the other bits does nothing to increase the security on non-broken hashing functions. Take the extreme case of xoring every bit to generate either a 0 or a 1. You've put a lot of effort into generating that single bit, but it's no more random than if you just took the lsb of the hash.
Anybody know what this appearance of randomness is?
Using a prime near the golden ratio makes the list appear less linear (cJio3, EdRc6, qxAQ9, TGtEC, 5ac2F, huKqI, KE3eL, wXmSO, YrVGR, BBE4U).
This looks like a clumsy way to implement modulus multiplication. My php is (thankfully) rusty, but it looks like an affine cipher with a fixed key?
If it is, a user can obtain two consecutive "hashes" and calculate past and future hashes. If they know the corresponding plaintext for a single hash, they can calculate arbitrary hashes.
True about consecutive hash calculation. Notedly it's for obfuscation, not encryption.
> openssl_encrypt('asdf', 'aes-256-cfb', 'a password', false, 'initialization v');
returns: 4kavvg==
You get the same direct mapping of inputs to outputs but you don't have to re-invent affine ciphers and make guesses about its security properties. And since you're just using it to turn a small integer into something bigger to make clients/users happy and not to protect data, Mr. Ptacek won't flame you out.
I've been contemplating a way to generate my own ids, similar to this, but was running into trouble on how to make sure its always generated unique, on distinct machines.