6
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ What about something like $\text{SHA}(m||k)$ truncated to 64/32 bits? Or the full HMAC business if necessary? $\endgroup$
    – Paul Uszak
    Jan 9 at 3:54
  • $\begingroup$ @PaulUszak unfortunately, according to some benchmarks, SHA1 is several times slower than Blake3, Siphash, and most non-cryptographic hash functions. I would prefer something that's as fast or faster than Siphash $\endgroup$
    – Nee
    Jan 9 at 4:07
  • $\begingroup$ Discohash seems quick, but not sure if it's safe or tested much. Must the hash function itself be keyed? $\endgroup$
    – Modal Nest
    Jan 9 at 7:30
  • $\begingroup$ I'm open to a different reading of requirement 2 than in my answer, if it's stated an order of magnitude of the number of pairs $(m,r)$ an adversary can gather. $\endgroup$
    – fgrieu
    Jan 9 at 14:24
3
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Thank you so much for an elaborate answer! The method involving irreducible polynomial is very interesting and I may actually be able to use it, but yes, the second requirement should have been "if some number of pairs $ (m, r) $ are known..." -- I apologise for the ambiguity and my delayed response. Still, thank you for considering both interpretations and providing me with more options to read up on and use. Much appreciated! $\endgroup$
    – Nee
    Jan 10 at 18:04

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.