# ID hashing and Obfuscation using Knuth's Algorithm

### Related tags

Security optimus-go

# ID Obfuscation/Hashing Transformer for Go

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.

the project to show your appreciation.

## 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 `generator.GenerateSeed()` function to generate all 3 required parameters if you want.

### 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`

New returns an Optimus struct that can be used to encode and decode integers. A common use case is for obfuscating internal ids of database primary keys. It is imperative that you keep a record of `prime`, `modInverse` and `random` so that you can decode an encoded integer correctly. `random` must be an integer less than `MAX_INT`.

WARNING: The function panics if prime is not a valid prime. It does a probability-based prime test using the MILLER-RABIN algorithm.

CAUTION: DO NOT DIVULGE prime, modInverse and random!

`func NewCalculated(prime uint64, random uint64) Optimus`

NewCalculated returns an Optimus struct that can be used to encode and decode integers. `random` must be an integer less than `MAX_INT`. It automatically calculates prime's mod inverse and then calls New.

`func (o Optimus) Encode(n uint64) uint64 `

Encode is used to encode n using Knuth's hashing algorithm.

`func (o Optimus) Decode(n uint64) uint64`

Decode is used to decode n back to the original. It will only decode correctly if the Optimus struct is consistent with what was used to encode n.

`func (o Optimus) Prime() uint64`

Prime returns the associated prime.

CAUTION: DO NOT DIVULGE THIS NUMBER!

`func (o Optimus) ModInverse() uint64`

ModInverse returns the associated mod inverse.

CAUTION: DO NOT DIVULGE THIS NUMBER!

`func (o Optimus) Random() uint64`

Random returns the associated random integer.

CAUTION: DO NOT DIVULGE THIS NUMBER!

`func ModInverse(n int64) uint64`

ModInverse returns the modular inverse of a given prime number. The modular inverse is defined such that `(PRIME * MODULAR_INVERSE) & (MAX_INT_VALUE) = 1`.

NOTE: prime is assumed to be a valid prime. If prime is outside the bounds of an int64, then the function panics as it can not calculate the mod inverse.

`func generator.GenerateSeed() (Optimus, error)`

GenerateSeed will generate a valid optimus object which can be used for encoding and decoding values.

See http://godoc.org/github.com/pjebs/optimus-go/generator#GenerateSeed for details on how to use it.

## 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.

## Other useful packages

• dataframe-go - Statistics and data manipulation
• dbq - Zero boilerplate database operations for Go
• igo - A Go transpiler with cool new syntax such as fordefer (defer for for-loops)
• mysql-go - Properly cancel slow MySQL queries
• react - Build front end applications using Go
• remember-go - Cache slow database queries

## Final Notes

Feel free to fork and/or provide pull requests. Any bug reports will be warmly received.

• #### fail for number greater than max_int

Hey, bro. I tested your code, but fail with number greater than 2147483647(i.e. max_int in your code) with `Encode(n uint64) uint64` . By failure , I mean`i!=Decode(Encode(i))`

question
opened by newyangyang 10
• #### Local prime generation

You mention trust in the UTM (or any other) prime list as a possible security problem, which I understand.

According to my experiments, it only takes a few seconds to locally compute the first 50+ million primes. (3.5 s using @hacatu's C implementation of an prime sieve with wheel size 210, 7.5 s using a straightforward Dart port of the same).

I would expect a Go implementation to be in the same ballpark. You might consider changing to that. The few seconds for the one-off computation will not be a setback.

opened by MarcelWaldvogel 7
• #### Rust implementation?

I'm interested in leveraging something like this in both Go (static site generator) and Rust (proxy server) to obfuscate Web-bound data. Are you aware of a Rust implementation of this algo? Thanks in advance.

opened by ghost 4
• #### Move GenerateSeed() to a separate sub-package

Use of `GenerateSeed()` is optional (and even discouraged). The code of this function brings a dependency on a full HTTP client in an otherwise small package.

Users of this library should not be forced to have this dependency. So it would be better to move the `GenerateSeed()` function to a separate package (suggestion: `github.com/pjebs/optimus-go/seed`).

opened by dolmen 4
• #### Proposed refactoring

I started to fork this project and just go my own way since my changes are significant, but I thought I'd see if you would incorporate my changes into optimus. Thanks for considering.

There are a few commits included that change way too many things at once (sorry), but here are the main takeaways:

1. Move the helper functions into a separate `ogen` subpackage.
2. Remove the prime assertion check from `New`.

To replicate the assertion functionality, you would simply call the assertion yourself:

``````optimus.AssertPrime(p)
o := optimus.New(p, m, r)
``````

This PR changes the API, but I think it's worth it. After making these changes, optimus should be much leaner and a little faster for production use.

I haven't yet updated the README or added a proper godoc section for package `ogen`.

PS: I also changed `MAX_INT` to a true max 32-bit int. If you intend to maintain compatibility with the upstream PHP package, we should undo that change.

opened by moorereason 2
• #### Generate Prime Number in GenerateSeed() Locally

I've implemented a prime number generator in Go at https://github.com/caleblloyd/primesieve. It is able to generate a prime up to MAXID=2147483647 in around 7 seconds worst case scenario on a modern MacBook Pro.

This pull request replaces the logic in GenerateSeed() that pulls a prime number off the internet with logic that generates a prime number locally on the machine.

This breaks backwards compatibility of the GenerateSeed() function. The old function was potentially insecure and suggested manual checking of the prime number scraped from the web, therefore it was not suited for programmatic use. The new GenerateSeed function is well suited for programmatic use. For this reason, I think the BC Breaking change is OK (since programmatic use of the old function is a security risk)

opened by caleblloyd 1
• #### Control Optimus output size

Is it possible to limit the digit number of the optimus obfuscation output? Like, generate obfuscated ids with up to 7digits.

I understand this would limit the number of possible ids, but it would still be helpful for my use-case.

opened by PedroEFLourenco 9
###### Volana - Shell command obfuscation to avoid detection systems

volana (moon in malagasy) { Use it ; ??(hide from); ??(detected by) } Shell comm

38 Jun 20, 2022
###### A light package for generating and comparing password hashing with argon2 in Go

argon2-hashing argon2-hashing provides a light wrapper around Go's argon2 package. Argon2 was the winner of the Password Hashing Competition that make

17 Mar 29, 2022
###### Hashing algorithms simplified (supports Argon2, Bcrypt, Scrypt, PBKDF2, Chacha20poly1305 and more in the future)

PHC Crypto Inspired by Upash, also implementing PHC string format Usage Currently there are two options of using this package: Import all Import speci

23 Apr 23, 2022
###### Argon2 password hashing package for go with constant time hash comparison

argon2pw Argon2 password hashing package with constant time hash comparison Preface: Argon2 was selected as the winner of the Password Hashing Competi

88 Jun 26, 2022
###### Consistent hashing hashring implementation.

hashring Consistent hashing hashring implementation. Overview This is an implementation of the consistent hashing hashring data structure. In general,

29 Apr 24, 2022
###### Argon2 password hashing for Golang

Argon2 This is simple pure Golang implementation for password hash using Argon2. Usage package main import ( "fmt" "github.com/prastuvwxyz/argon2"

2 Dec 6, 2021
###### An API for hashing password in PostgreSQL with Golang

hashing-password An API for hashing password in PostgreSQL with Golang Using PostgreSQL to store Encrypted string (can be passwords ideally) using Sal

4 Feb 12, 2022
25 May 27, 2022
###### XXTEA is a fast and secure encryption algorithm.

XXTEA Golang Introduction xxtea is a fast and secure encryption algorithm. This project is the Golang implementation of the xxtea encryption algorithm

2 Apr 14, 2022
###### Small utility package for stealing tokens from other processes and using them in current threads, or duplicating them and starting other processes

getsystem small utility for impersonating a user in the current thread or starting a new process with a duplicated token. must already be in a high in

10 May 29, 2022
###### A convenience library for generating, comparing and inspecting password hashes using the scrypt KDF in Go 🔑

simple-scrypt simple-scrypt provides a convenience wrapper around Go's existing scrypt package that makes it easier to securely derive strong keys ("h

180 Jun 8, 2022
###### Tracee: Linux Runtime Security and Forensics using eBPF

Tracee is a Runtime Security and forensics tool for Linux. It is using Linux eBPF technology to trace your system and applications at runtime, and analyze collected events to detect suspicious behavioral patterns.

1.9k Jun 27, 2022
###### Generate mega-workflows using Wappalyzer outputs and existing tech-detect

Usage Usage of ./build/generate-nuclei-templates: -clone-path string Path to clone Wappalyzer repository (default "./wappalyzer") -debug

5 Dec 15, 2021
###### Kerberoasting attack implementation in Golang using go-ldap and gokrb5

Goberoast Kerberoasting attack implementation in Golang using go-ldap and gokrb5. Build You can build the project by simply typing go build within the

0 Jan 19, 2022
###### 🌰 encrypt/decrypt using ssh keys

ssh-vault ?? encrypt/decrypt using ssh private keys Documentation https://ssh-vault.com Usage \$ ssh-vault -h Example: \$ echo "secret" | ssh-vault -u

350 Jun 27, 2022