Fast MAC for 64-bit inputs I am looking for a fast MAC (~few machine instructions) to be used for hash tables with 64-bit public inputs.  I can't use SipHash as the hash function will be inlined in too many places and so the code size of SipHash is too large.  The sole use of the MAC value will be in hash tables.  I want to avoid hash collision DoS.
I'll precisely define the problem, and propose a solution based on AES-128, requiring about 13 instructions on many modern CPUs for something academically secure in a model where the hashes leak, down to about 8 instructions if we trust my intuition that we can in practice reduce the number of rounds in a model where only the number of collisions leaks.



It is asked a function changing a 64-bit input $m$ into an hash suitable as primary index in a hash table, avoiding malicious choice of $m$ intentionally causing collision at that stage (we ignore later collision resolution). The number $n$ of hash table entries is a public parameter, with $\log_2(n)\ll64$, perhaps $\log_2(n)\approx24$ (good for 16 million entries in the table). The function will also have a secret key parameter $k$. We'll note $h=f_{(n,k)}(m)$ where $f_{(n,k)}$ is the desired function, $m$ is the 64-bit input, and $h$ is the hash output, with $0\le h&lt;n$. Evaluation of $f_{(n,k)}$ for additional values of $m$ must be fast, and compact (it is duplicated many times to avoid function call overhead).

The minimum desired security property, handling counting of collisions by timing measurement, is that an adversary not knowing $k$ (because it was chosen randomly at hash table creation, and not revealed) and able to choose up to $n$ distinct $m_u$, can can not cause significantly more collisions than for a random choice of function $f$, with knowledge when choosing $m_u$ of the number of collisions for each $v&lt;u$, that is of the number of $w&lt;v$ with $f_{(n,k)}(m_v)=f_{(n,k)}(m_w)$.

A simpler and stronger security property, handling the case where the results of an in-order hashtable traversal are leaked, would be that the adversary can not distinguish $f_{(n,k)}(m_u)$ from random, including in an interactive setup where the adversary chooses $m_u$ with knowledge of $f_{(n,k)}(m_v)$ for each $v&lt;u$.



The stronger security property is met by any MAC reduced modulo $n$; that however is neither fast nor compact if we chose, say, HMAC-SHA-256. But if there is hardware support, a good option, also secure with cryptographic certainty under the stronger security property, is to built the MAC around AES-128: 


pad $m$ to 128-bit (e.g. with zeroes)
apply AES-128 encryption with key $k$
reduce result modulo $n$.


Note: that works fine for $m$ of any fixed size up to 128 bits, or $m$ of variable size up to 127 bits with some injective padding to 128 bits.

For even more speed at the expense of academically recognized security, we can arguably reduce the number of AES rounds, from 10 down to some debatable minimum, perhaps 5 if we are content with the minimum desired security property handling timing attacks only (I would not consider 4 without extra precautions, see note below). That's not conservative; but getting to know only the collisions rather than the AES ciphertext, for a limited number of queries, make things hard for the adversary.

If the CPU has the AES NI instruction set, $r\le10$ AES-128 rounds cost $r+1$ instructions (one initial pxor, $\max(r,9)$ aesenc, and when $r=10$ one aesenclast) which can each reference a pre-computed AES 128-bit subkey stored in memory at initialization of the hash table.

For simplicity and speed, and when $n\ll64$, the reduction modulo $n$ can be made over only half of the AES result, with only minor security impact (entries at the end of the tables will be slightly less hit). Modern 64-bit CPUs compute the remainder of the division of a 64-bit quantity by a 32-bit quantity with a single instruction.

Note: when we push things towards speed and heavily venture in the round reduction route, it seems worthwhile to slightly bend the problem definition by choosing $n$ odd (or better $(n\bmod8)\in\{3,5\}$), which allows the reduction step modulo $n$ to add some final diffusion; and, assuming we can keep the exact choice of $n$ secret (including: the adversary can not reliably measure our allocated memory), choose $n$ random in a small public interval (like from the targeted $n$ to 105% of that), in order to make that extra step keyed.



If we want something that can be coded in portable C, or without aesenc, we'll want to replace AES with some other primitive, likely of the ARX variety; considerations impacting its choice include compiler support for wide wordsize and fast rotation.