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 11 months ago

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


jenssegers 1 year ago

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


Joel 1 year 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 2 years ago

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


jenssegers 2 years 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 2 years 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.