Which algorithm is the simplest reversible fixed-size length-preserving symmetric "cryptography" with low probability of collision?

Question

I am not a mathematician/cryptographer, so I could not take much advantage of this other question, and it seems (?) to have more requirements than me (SAC).

I say simple, because I need it to be have a fast implementation and also because security is irrelevant in my use case. However, a low collision probability is an important requirement. By low I mean something comparable to the odds of MD5(textA + keyB) = MD5(textC + keyD), for different texts and keys. Both text and key have a fixed size, e.g., 16 bytes. Plus sign here means concatenation.

For instance, AES would be suitable for this task, but it is 100x slower than MD5. Of course, MD5 is irreversible, so I can't use it.

Another requirement is that it should also be non-commutative, i.e. encrypt(textA, keyB) != encrypt(keyB, textA) otherwise I guess I could just use the XOR bit-wise operation.

EDIT

What I have done so far was to implement the following 128-bit "cryptography" in Python. However, with many collisions:

def pepper(msg):
    bit = (msg & 0b1111111) % 120 + 8
    return msg ^ (2 ** bit)


def rev_hash(msg_int, key_int):
    """A "reversible hash", the nightmare of cryptologists."""
    lshift = (((msg_int & mask_127ones) << 1) | (msg_int >> 127))
    result = lshift ^ key_int
    return pepper(result)


def rev_unhash(encrypted_msg_int, key_int):
    xor = pepper(encrypted_msg_int) ^ key_int
    rshift = (xor >> 1) | ((xor & 1) << 127)
    return rshift

Answer 1

What's asked is fulfilled by a block cipher with 128-bit key and block size (but notice that it's trivial to make collisions when one of the keys is known). We can't use a stream cipher (collisions would be trivial even with both keys secret), nor OAEP padding as used in RSA encryption (as practiced it is not length-preserving, and not exactly simple).

AES-128 is one suitable block cipher, and is not slow . It commonly runs at over 1 million 16-byte encryptions per second per core in pure software, sometime 20M (for repeated use with the same key), or even 200M with AES-NI hardware. Sure, that's not for AES implemented in pure python.

But using AES from python is easy, even if we use the question's message-as-int interface.

from Crypto.Cipher import AES

def rev_hash(msg_int, key_int):
    return int.from_bytes(AES.new(key_int.to_bytes(16,'big'),AES.MODE_ECB).encrypt(msg_int.to_bytes(16,'big')),'big')

def rev_unhash(encrypted_msg_int, key_int):
    return int.from_bytes(AES.new(key_int.to_bytes(16,'big'),AES.MODE_ECB).decrypt(encrypted_msg_int.to_bytes(16,'big')),'big')

Try it online!

That might be acceptably fast. It would be hard to beat if we used the native bytestring interface (avoiding to_bytesand from_bytes), and modified the interface to reuse the AES instances across calls with the same key.

---

It is possible to make a block cipher that's simple, fast, secure: pick at most two of these features. Here, one of the requirement can be read as: making collisions must be comparable in difficulty to making collisions between MD5 hashes with different (secret) keys appended, even with many plaintext/ciphertext pairs at hand for both keys. Combined with reversibility, that means 64-bit security, since MD5 remains that strong against collisions under these conditions. With this requirement, it's hard to make something simple and fast, especially in pure python.

Without any claim of security, here is a very simple self-contained 128-bit block cipher

def rev_hash(msg_int, key_int):
    for x in [305065944875308933,445871615361279994733287202953785,859072698151683073,893999628687995393356516725455569]:
        msg_int = (((msg_int>>64)^msg_int^key_int)*x+1)&((1<<128)-1)
    return msg_int^key_int

def rev_unhash(encrypted_msg_int, key_int):
    encrypted_msg_int ^= key_int
    for x in [409772003941621297,679237006192346672534347824675841,229702291678999561,786310896237332493342854003018061]:
        encrypted_msg_int = ((encrypted_msg_int*x-x)&((1<<128)-1))^key_int
        encrypted_msg_int ^= encrypted_msg_int>>64
    return encrypted_msg_int

Try it online!

Rationale: there are 5 rounds, each reversibly acting on the whole state. Each round uses XOR with the key, and (except for the last round) modular multiplication by a constant (which gives left diffusion) with addition of 1 modulo 2¹²⁸, and XOR of the left half into the right one (which gives right diffusion, and alternates addition and XOR to break linearity). The constants are pre-computed as four 18-digits random primes selected among about a million for having 33-digit modular inverses, alternating with the inverses. Such use of round-dependent constants hopefully partially compensates for the total lack of key schedule. Things are arranged so that the encryption is compact. Decryption is even so slightly more complex, because it needs to proceed in reverse order. The addition avoids a stationary point at zero with key 0.

Speed is only marginally better than in first example using AES (like by a mere factor of two), at the expense of security. And again the first example would be much faster with a rethought interface.