ID hashing and Obfuscation using Knuth's Algorithm

Related tags

Security optimus-go
Overview

ID Obfuscation/Hashing Transformer for Go GoDoc Go Report Card

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.

See: http://en.wikipedia.org/wiki/Modular_multiplicative_inverse

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
  • electron-alert - SweetAlert2 for Electron Applications
  • 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.

© 2014-20 PJ Engineering and Business Solutions Pty. Ltd.

Issues
  • fail for number greater than max_int

    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 meani!=Decode(Encode(i))

    question 
    opened by newyangyang 10
  • Local prime generation

    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?

    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

    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

    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

    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

    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
null 8 Dec 20, 2021
Volana - Shell command obfuscation to avoid detection systems

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

Ariary 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

Andrey Skurlatov 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

Reinaldy Rafli 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

Raja Bhatia 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,

Sergey Kamardin 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"

Dwi Agung Prastya 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

Aly Ragab 4 Feb 12, 2022
An easy-to-use XChaCha20-encryption wrapper for io.ReadWriteCloser (even lossy UDP) using ECDH key exchange algorithm, ED25519 signatures and Blake3+Poly1305 checksums/message-authentication for Go (golang). Also a multiplexer.

Quick start Prepare keys (on both sides): [ -f ~/.ssh/id_ed25519 ] && [ -f ~/.ssh/id_ed25519.pub ] || ssh-keygen -t ed25519 scp ~/.ssh/id_ed25519.pub

null 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

yanheng 2 Apr 14, 2022
Jeff Buchbinder 5 Apr 25, 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

Alex Flores 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

Matt Silverlock 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.

Aqua Security 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

null 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

null 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

ssh-vault 350 Jun 27, 2022