Jens Segers on May 10 2015

Id transformation with Optimus

Recently I wrote a blog post and gave a talk at php.gent about id obfuscation and how it can help hide your application internals from malicious users. While doing some research about other obfuscation techniques, I stumbled upon an implementation based on Donald Knuth's integer hash. This unbelievable small and fast algorithm will generate random-like integers with the ability to convert them back to the original value. This technique was so cool that I decided to create a PHP package for it called Optimus.

Optimus

Go ahead and install it using composer:

composer require jenssegers/optimus

Using the package is fairly simple, but there is some math involved before you can start using it. Luckily, I managed to make this as easy as possible with an included command line script.

First you need to pick a prime number. You can calculate this yourself or pick one from this list. For the decoding process, the algorithm needs the "inverse prime", so that (PRIME * INVERSE) & MAXID == 1. To calculate this number you can use the included optimus tool:

> php vendor/bin/optimus spark 1580030173
Prime: 1580030173
Inverse: 59260789
Random: 1163945558

With these numbers you can fire up your own Optimus instance:

use Jenssegers\Optimus\Optimus;

new Optimus(1580030173, 59260789, 1163945558);

Make sure that you use the same numbers throughout your entire application. I would suggest registering a shared instance on your IoC container of choice like this:

$app['Jenssegers\Optimus\Optimus'] = function () {
    return new Optimus(1580030173, 59260789, 1163945558);
};

To start encoding and decoding id's, you can use the encode and decode methods:

$encoded = $optimus->encode(20);

Which will result in 1535832388. To decode it back to its original value simple do:

$original = $optimus->decode(1535832388);

I hope you find this technique as interesting as I do. It's amazing how fast it can encode and decode values. I did a quick benchmark and compared it to Hashids, and Optimus turned out to be over 125 times faster! What are you waiting for, test drive your Optimus today!


Comments

Propaganistas 8 months ago

I created a simple package that automatically implements route id obfuscation using Optimus: https://github.com/Propaganistas/Laravel-FakeId


jenssegers 9 months ago

@Joel I had no collisions with everything under 32 bit :)


Joel 10 months ago

@jenssegers. love the concept. did you complete that collision test / uniqueness? if so, can you let us know the results.

Thanks


jenssegers 1 year ago

@K. Yesterday I added support for 32 bit systems by using the GMP extension ;)


K. 1 year ago

Looks like sanitizer issue...

(1580030173 x 59260789) & 2147483647 === 0, not 1 (on 32 bit system)


K. 1 year ago

Hello. Are you sure the formula is correct? (PRIME INVERSE) & MAXID == 1 Is seems from numbers from your example that (1580030173 59260789) & 2147483647 equals to 0, not 1.


Connie 1 year ago

Articles like this really grease the shafts of kngloedwe.


jamlee 1 year ago

ah,yes it is great because of all of my article is stored in database and identified by increment id .


jenssegers 1 year ago

@Ozzy Thanks for the link! I did not invent the hash algorithm, but from what I found in my research it should not produce collisions as long as your original id's don't exceed the max 32 bit integer number. I'm currently running a collision test and will post the result here when it finishes :)


Ozzy 1 year ago

This looks awesome. I assume there is no possibility of hashed ID collision? Looks like this could be used to hash user ids on a website to hide user numbers or guessing of profiles. I will definitely be using it for a project of mine.

My application for this would be to have a hash_id column indexed next to an id column and use the hash_id as a reference to the data.

Just a suggestion, the website you link to has only the first 50 million prime numbers available, I stumbled upon this site a while back: http://numbersofprime.com/

Has the first 2 billion prime numbers and you can view them without downloading the large zip files.