3
\$\begingroup\$

I wanted to implement a simple algorithm for encoding id of entries in a database to avoid:

  • Storing the UID (unique id) in the table along with the id
  • Complex and costly algorithm.
  • Users to give meaning to the id in the sense:
    • Yeah if this id is bigger than that id it was inserted later in the DB
    • I can probably get the previous and the next element by adding one to my id

So I need two inputs:

  1. One id
  2. The domain of my id, or the maximum number of entries in that table.

A nice kind of algorithms for this purpose is a FFX algorithm (Format Preserving Encryption). But they usually rely on complex hash function such as SHA or MD5. In my case I just want a very simple simple algorithm that I could implement in MySQL as a generated column for instance.

So I wrote this code:

import math


class Tumbler:
    def __init__(self, maximum, rounds=12):
        bits = math.ceil(math.log(maximum, 2))
        u, v = bits // 2, bits - bits // 2
        self.u = u
        self.v = v
        self.bits = bits
        self.rounds = rounds
        self.maximum = maximum

    def hash(self, x, m):
        """ Jenkins Hash 32bits."""
        x = (x + int('7ed55d16', 16)) + (x << 12)
        x = (x ^ int('c761c23c', 16)) ^ (x >> 19)
        x = (x + int('165667b1', 16)) + (x << 5)
        x = (x + int('d3a2646c', 16)) ^ (x << 9)
        x = (x + int('fd7046c5', 16)) + (x << 3)
        x = (x ^ int('b55a4f09', 16)) ^ (x >> 16)
        return x % m

    def split(self, x, u):
        return (x >> u, x & (2 ** u - 1))

    def _encrypt(self, x, nonce=1):
        for i in range(self.rounds):
            a, b = self.split(x, self.v)
            c = a ^ self.hash(b * i + nonce, (2 ** self.u - 1))
            x = b << self.u | c
        return x

    def _decrypt(self, x, nonce=1):
        for i in reversed(range(self.rounds)):
            b, c = self.split(x, self.u)
            a = c ^ self.hash(b * i + nonce, (2 ** self.u - 1))
            x = (a << self.v) | b
        return x

    def encrypt(self, x, nonce=1):
        while True:
            x = self._encrypt(x, nonce)
            if x <= self.maximum:
                return x

    def decrypt(self, x, nonce=1):
        while True:
            x = self._decrypt(x, nonce)
            if x <= self.maximum:
                return x

Here an output:

>>> t = Tumbler(162)
>>> [(i, t.encrypt(i), t.decrypt(t.encrypt(i))) for i in range(min(16, t.maximum))]

[(0, 48, 0),
 (1, 97, 1),
 (2, 80, 2),
 (3, 159, 3),
 (4, 95, 4),
 (5, 3, 5),
 (6, 38, 6),
 (7, 108, 7),
 (8, 50, 8),
 (9, 162, 9),
 (10, 24, 10),
 (11, 94, 11),
 (12, 69, 12),
 (13, 126, 13),
 (14, 43, 14),
 (15, 120, 15)]

Another example would be to shuffle a deck of 52 cards:

shuffling_method = 1
t = Tumbler(52, shuffling_method)
[(i, t.encrypt(i), t.decrypt(t.encrypt(i))) for i in range(t.maximum)]

If I want another shuffle set, I could use a different shuffling_method.

And of course I could use a better hashing function:

import hashlib

class Tumbler2(Tumbler):
    def hash(self, x, m):
        return int(hashlib.md5(bytes(str(x))).hexdigest, 16) % m
\$\endgroup\$
5
\$\begingroup\$

Part of code review is challenging assumptions, so to begin with I'd like to challenge the motivation for this code.

You say you want to avoid "Storing the UID (unique id) in the table along with the id". Why would you have two? Any one of those is enough to uniquely identify a row - they are both unique, after all. If you mean the surrogate key (serial number, UUID or similar) and the business key (for example username), then it absolutely makes sense to store both of them in the same table. Surrogate keys have been discussed for decades, but the industry consensus nowadays seems to be:

  1. The business key should be exposed to end users. That is, a user should know their own username and employee number, even if these are created by the system.
  2. Tables should have a surrogate key, and this key should not be exposed to end users. This does not just include direct user interfaces, but also for example URLs. The reason for this is to be sure that the surrogate key remains an implementation detail which could later be changed, such as when moving from a guessable serial number to a UUID.

You also want to avoid a "[c]omplex and costly algorithm". Version-4 UUIDs are probably the cheapest unguessable surrogate keys you can get your hands on these days without massive implementation effort, as long as you use pretty much any database other than MySQL - PostgreSQL has them, as does the major closed-source databases.

The last reason is related to unguessable IDs, already discussed above.

All in all it looks like implementing v4 UUIDs in MySQL is probably the cheapest option if you must use that database, otherwise you can just use an existing, safe, fast and F/LOSS solution.


That said, some suggestions for the Python code:

  • __init__ takes an optional rounds parameter, but the only place that's used it's called shuffling_method, which seems inconsistent. Changing the number of rounds doesn't constitute changing the "method".
  • Rather than assigning u and v at the same time you can save one operation by assigning u first and reusing its value to define v.
  • Naming is incredibly important for maintainability. I basically have to read the entire code block to guess what a, b, c, m, u, v and x mean. A good variable name is better than a good comment, and will allow the reader to understand a piece of code with as little context as possible.
  • Having twinned methods encrypt and _encrypt, decrypt and _decrypt is a code smell. If they are doing the same thing, why are they not one method? If they are doing different things, why are they named effectively the same?
  • There are four different Jenkins hash functions, but it's not obvious which one this is. That would be very helpful for someone trying to verify the implementation.
  • This comes under the category of implementing your own crypto, since you're trying to make the sequence non-guessable. This hash function looks fairly niche based on the Wikipedia article, and it even looks like the Jenkins hash without an additional secret is guessable.
\$\endgroup\$
  • \$\begingroup\$ I like your answer and I learned the term surrogate key. I am not using UUID because I want a business key to be easily readable. for this I convert the output of my tumbler into a representation like: ABC-123 (three chars and three numbers). The first char is linked to a DB table (or better, a Model, in my MCV design). As you suggested, I was really wondering whether I have to create a business_id column in my database, but as my business_id can be generated from an algorithm, I decided to NOT put it in the database, but this is indeed debatable. \$\endgroup\$ – nowox Jun 30 at 19:28
  • \$\begingroup\$ About the a, b, c, ... you are perfectly right I should have added some documentation with an ASCII art of the Feistel cipher with the position of A, B, C and D. \$\endgroup\$ – nowox Jun 30 at 19:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.