0
$\begingroup$

A common family of requirements for (cryptographic) keyed hash functions is that the function $h(k,-)$ should have good collision resistance for all keys $k$, even if the key $k$ is known to the attacker. I'm looking for something with slightly weaker security properties to this, but which is unusually fast. Specifically, I only need collision resistance subject to the assumption that $k$ is unknown to the attacker and kept secret. However, the task of computing $h(k, x)$ should be a lot faster than computing $\mathrm{Blake3}(k+x),$ where $k$ denotes concatenation, despite that $\mathrm{Blake3}$ is usually considered a "fast" hashing algorithm.

Motivation: The point is to get hashing speeds that are so high, that there's simply no reason not to hash an object before sending it to disk (e.g. if we're trying to free up RAM). This can easily be achieved using a non-cryptographic hash, of course, but hashes are more useful if they can be used to decide object equality without ever having to reload those objects from disk.

Remark: In case anyone's wondering, my personal interest in this topic stems from the problem of designing a virtual machine for a programming language I'm working on. Most uses probably won't be very IO intensive, but I'm designing things defensively to help ensure that things "just work" when the programmer starts doing funky things. For example, currently I've got timestamps attached to all objects, and depending on current RAM usage and the object's time-since-last-access, a memory management thread will sometimes decide to send the object to disk.

Anyway, a potential improvement on this design involves holding onto a small "avatar" for the object even after it's been dumped to disk. The avatar is supposed to track basic info about the object like its class, its reference count, as well as class-specific attributes of interest. For example, if it's a hashtable, the avatar might record the number of key-value pairs in the table. If it's a string, the avatar might record the length of the string, and possibly a bit more data to facilitate lazy deletion of characters from each end of the string. Wherever possible, you obviously try to do things via the avatar, without having to reload the entire object.

Of course, once this idea of avatars got into my head, the question of whether these avatars should store hashes of the objects they represent arose naturally. Computing them has a couple of benefits. For starters, it means that equality of objects can be checked via avatars, which is obviously quite appealing. It also allows you to avoid storing duplicate objects into the database.

On the other hand, I'm a bit worried about the runtime costs of computing these things. If someone's program literally never makes use of the hashes, that's a lot of CPU time consumed on something that isn't helping the end-user. I'd just feel a lot more comfortable with a computationally cheaper solution, and I think using a full-blown cryptographic hash like Blake3 might be overkill.

$\endgroup$
15
  • $\begingroup$ Welcome to Cryptography.SE. We want cryptographic has functions (keyed or not) as fast as possible and as much as secure. We want slow hash functions ( well adjustable ) for the password hashing algorithm. maybe you just need xxhash.com also see at github.com/Cyan4973/xxHash $\endgroup$
    – kelalaka
    Nov 24, 2023 at 20:31
  • $\begingroup$ @kelalaka, well xxhash seems not to have the cryptographic properties I'm looking for, unfortunately. $\endgroup$ Nov 24, 2023 at 20:41
  • 1
    $\begingroup$ What comes closest to your requirements are universal hashes; built with polynomial evaluation (GCM, Poly1305), or Cryptographic CRCs. The major drawback is that: most of the time, the adversary shouldn't learn the output of the hash. So you'd need to either pass this output through as a slower PRF or "encrypt" This output with a stream cipher. Which may yield acceptable performance depending on your use. Caveat: these are usually quite brittle and misuses can be more devastating compared to regular hashing. $\endgroup$ Nov 24, 2023 at 21:12
  • $\begingroup$ @MarcIlunga, okay, thanks. Cryptographic CRC's seem intriguing (in fact it would never have occurred to me that this was even possible). $\endgroup$ Nov 24, 2023 at 21:26
  • 2
    $\begingroup$ @kodlu See "LFSR-based Hashing and Authentication" (1994) $\endgroup$ Nov 25, 2023 at 6:03

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.