Fast irreversible transformation/compression of short messages using a secret

Question

I'm looking for a very fast function $f(m, k) $ that takes a 64-bit integer $m$ and a fixed secret key $k$ of virtually any size (generated by a CSPRNG) and turns them into a 64- or 32-bit integer $ r $, with a few additional requirements:

1. $ r $ must depend on both $m$ and $ k $ and be reasonably well-distributed
2. if a pair of $ m $ and $ r $ is known, it should not be possible to efficiently calculate $ k $ or produce $ f(m_1, k) = r_1 $
3. $ r $ will be used as a kind of a key or tag associated with $ m $, but it doesn't have to uniquely identify $ m $ (i.e. the existence of $ m_1 $, $ m_2 $ such that $f(m_1, k) = f(m_2, k) = r $ is completely normal), so I'm not too concerned about collisions

IOW, I need a way to quickly and irreversibly transform/compress/scramble a fixed-size integer (possibly shortening it) using a secret.

I think ideally this would be solved by a keyed cryptographic hash function like Blake* or Siphash. For example, Siphash was specifically designed to work well on small inputs and maintain key secrecy, and it's currently used in CPython for hash table lookups. Performance-wise Siphash-2-4 is maybe tolerable for my use case and seems to check all the boxes, but since I only need to process a 64-bit integer, it feels like an overkill and I'm still interested in anything more lightweight.

I've also looked at several non-cryptographic hash functions and their performance is very appealing, but I'm afraid many of them will fail the second requirement I listed (especially if I feed them $ k || m $, which simplifies brute-force attack in case of FNV-1A and Murmurhash3). XXH3 explicitly lets me provide a secret to customize hash values, and it seems to outperform any other decent hash function in existence, but it's also explicitly non-cryptographic, so unfortunately I'm not sure if it can provide the same level of security as Siphash, even for a use case as simple as mine.

I've also tried creating my own mixing/compression function (which most likely is not secure) and considered using a mixing/compression function from an existing algorithm (most likely not designed to be used separately from the original algorithm).

Am I missing a simpler way to do this?

Answer 1

In the first part of this answer, I restrict to reading requirement 2 as "if one pair $(m,r)$ is known…", and assume that $k$ is chosen at random. I entirely disregard security when an adversary knows two distinct pairs $(m,r)$, or when related keys $k$ are used.

The following construction uses the Galois Field $(\mathbb F_{2^{64}},\oplus,\otimes)$, with some irreducible polynomial¹:

$$f:\{0,1\}^{64}\times\{0,1\}^{128}\to\{0,1\}^{64}\\ (m,k)\mapsto (k_1\otimes m)\oplus k_0=r\\ \text{ where }\ k_1\mathbin\|k_0=k\ \text{ and }\ |k_0|=64=|k_1|$$

Given $(m,r)$ and $(m_1,r_1)$ with $m\ne m_1$, there exists a unique² key $k$ with $f(m,k)=r$ and $f(m_1,k)=r_1$. It follows that the construction perfectly meets it's security objective, regardless of the computational power of adversaries.

Note: For any fixed $k$ with $k_1\ne0$, there are no collisions.

Note: We wan restrict to a smaller output by removing any number of bits from the the result. We can correspondingly shorten the key $k$ by removing the bits of $k$ (in $k_0$) that do not influence the result.

Note: Computation of $f$ is simple and efficient on a CPU with built-in support for binary field arithmetic, including most modern x86 CPUs, which have carry-less multiplication. There's little point to this method otherwise.

#include <stdint.h>
#if OPTIMIZED // for Intel Westmere (2010), AMD Jaguar (2013) and later.
#include <immintrin.h>
inline uint64_t f(uint64_t m, const uint64_t k[2]) {
  __m128i u,v;
  u.m128i_u64[0] = k[1];
  u.m128i_u64[1] = 27;                  // X**64 + x**4 + x**3 + x + 1
  v.m128i_u64[0] = m;
  v = _mm_clmulepi64_si128(u, v, 0);    // u.m128i_u64[0] * v.m128i_u64[0]
  u = _mm_clmulepi64_si128(u, v, 17);   // u.m128i_u64[1] * v.m128i_u64[1]
  return k[0] ^ v.m128i_u64[0] ^ u.m128i_u64[0];
}
#else // no _mm_clmulepi64_si128
#pragma warning(disable : 4146)         // silence silly compiler's warning
uint64_t f2(uint64_t m, const uint64_t k[2]) {
  uint64_t a = k[1], x = (m & -(a & 1)) ^ k[0];
  a = (a >> 1) | (1ull << 63);          // insert sentinel
  do                                    // 63 times
    x ^= (m = (27 & -(m >> 63)) ^ (m + m)) & -(a & 1);
  while ((a >>= 1) != 1);
  return x;
}
#endif

---

Now I read requirement 2 as "if some number of pairs $(m,r)$ are known…". If said number is large (larger than we are willing to process 64-bit key blocks), we can no longer build a perfectly secure system.

What the question asks can be nicely solved with a 64-bit block cipher, but then there is the question of choosing it. TEA? RC5? Blowfish? Prince? Simon? Speck? One of the lightweight crypto candidates? Any will do. And then we could venture into something custom.

---

¹ e.g. $x^{64}+x^4+x^3+x+1$, see Joerg Arndt's Binary irreducible polynomials with lowest-most possible set bits. This polynomial happens to also be primitive, but we do not need that property.

² Proof: that $k$ can be found as $k_1\gets(r\oplus r_1)\oslash (m\oplus m_1)$, $k_0\gets(k_1\otimes m)\oplus r$, $k\gets k_1\mathbin\|k_0$.