ID hashing and Obfuscation using Knuth's Algorithm
Go
Latest commit 5a9075e Jun 28, 2015 pjebs Updates for GAE
Permalink
Failed to load latest commit information.
LICENSE Read Me added May 7, 2015
README.md Updates for GAE Jun 29, 2015
gae.go Updates for GAE Jun 29, 2015
optimus.go Updates for GAE Jun 29, 2015
optimus_test.go Updates for GAE Jun 29, 2015
standalone.go Updates for GAE Jun 29, 2015

README.md

ID Obfuscation/Hashing Transformer for Go GoDoc

There are many times when you want to generate obfuscated ids. This package utilizes Knuth's Hashing Algorithm to transform your internal ids into another number to hide it from the general public.

An example may be your database table. You may have a primary key that points to a particular customer. For security reasons you don't want to expose that id to the outside world. That is exactly where this package becomes handy.

Optimus encodes your internal id to a number that is safe to expose. Finally it can decode that number back so you know which internal id it refers to.

Full Unit Tests are provided. The package is Google App Engine compatible.

Installation

go get -u github.com/pjebs/optimus-go

Usage

Step 1

  • Find or Calculate a PRIME number from somewhere. It must be smaller than 2147483647 (MAXID)
  • Calculate the Mod Inverse of the Prime number such that (PRIME * INVERSE) & MAXID == 1
  • Generate a Pure Random Integer less than 2147483647 (MAXID).

You can use the built-in GenerateSeed() function to generate all 3 required parameters if you want. This is not recommended though because it is reliant on the prime numbers listed on the website: http://primes.utm.edu/lists/small/millions/. This adds a point of insecurity.

If you do use the GenerateSeed() function, make sure that you verify:

  • That website has not been hijacked
  • The 50 million prime numbers listed on the site have not been modified to all point to the same number (i.e. they are all different)
  • You independently verify that the Prime Number generated is in fact a PRIME number!

Step 2

package hello

import (
    "fmt"
    "github.com/pjebs/optimus-go"
)

o := optimus.New(1580030173, 59260789, 1163945558) //Prime Number: 1580030173, Mod Inverse: 59260789, Pure Random Number: 1163945558

new_id := o.Encode(15) //internal id of 15 being transformed to 1103647397

orig_id := o.Decode(1103647397) //Returns 15 back

Please note that in order for Optimus to transform the id back to the original, all 3 numbers of the constructor must be consistent. You will need to store it somewhere after generation and usage.

Methods

type Optimus struct {
    prime      uint64
    modInverse uint64
    random     uint64
}
func New(prime uint64, modInverse uint64, random uint64) Optimus

Returns an Optimus struct which can be used to encode and decode integers. Usually used for obfuscating internal ids such as database table rows. Panics if prime is not valid.

func NewCalculated(prime uint64, random uint64) Optimus

Returns an Optimus struct which can be used to encode and decode integers. Usually used for obfuscating internal ids such as database table rows. This method calculates the modInverse computationally. Panics if prime is not valid.

func (this Optimus) Encode(n uint64) uint64 

Encodes n using Knuth's Hashing Algorithm. Ensure that you store the prime, modInverse and random number associated with the Optimus struct so that it can be decoded correctly.

func (this Optimus) Decode(n uint64) uint64

Decodes a number that had been hashed already using Knuth's Hashing Algorithm. It will only decode the number correctly if the prime, modInverse and random number associated with the Optimus struct is consistent with when the number was originally hashed.

func (this Optimus) Prime() uint64

Returns the Associated Prime Number. DO NOT DEVULGE THIS NUMBER!

func (this Optimus) ModInverse() uint64

Returns the Associated ModInverse Number. DO NOT DEVULGE THIS NUMBER!

func (this Optimus) Random() uint64

Returns the Associated Random Number. DO NOT DEVULGE THIS NUMBER!

func ModInverse(n uint64) uint64

Calculates the Modular Inverse of a given Prime number such that (PRIME * MODULAR_INVERSE) & (MAX_INT_VALUE) = 1 Panics if n is not a valid prime number. See: http://en.wikipedia.org/wiki/Modular_multiplicative_inverse

func GenerateSeed(req *http.Request) (*Optimus, error, uint8)

Generates a valid Optimus struct using a randomly selected prime number from this site: http://primes.utm.edu/lists/small/millions/ The first 50 million prime numbers are distributed evenly in 50 files. This Function is Time, Memory and CPU intensive. Run it once to generate the required seeds. WARNING: Potentially Insecure. Double check that the prime number returned is actually prime number using an independent source. The largest Prime has 9 digits. The smallest has 1 digit. The final return value is the website zip file identifier that was used to obtain the prime number NB: Parameter req should be nil if not using Google App Engine.

Alternatives

There is the hashids package which is very popular. Out of the box, it produces obfuscated ids that can contain any number of characters.

However:

  • Knuth's algorithm is 127 times faster in benchmarks
  • Hashids produce strings that contain characters other than just numbers.
    • If you were to modify the code (since the default minimum alphabet size is 16 characters) to allow only characters (0-9), it removes the first and last numbers to use as separators.
    • If the character '0' by coincidence comes out at the front of the obfuscated id, then you can't convert it to an integer when you store it. An integer will remove the leading zero but you need it to decode the number back to the original id (since hashid deals with strings and not numbers).

Inspiration

This package is based on the PHP library by jenssegers.

Final Notes

If you found this package useful, please Star it on github. Feel free to fork or provide pull requests. Any bug reports will be warmly received.

PJ Engineering and Business Solutions Pty. Ltd.