4

Is there an AES based non-cryptographic hash algorithm?

I think this could be useful, as we have AES-NI instructions, such a hash could be very fast.

I'd like to use this for fingerprinting (so its output should be at least 128-bits) and error detection purposes.

(I've googled for this, but all I found is cryptographic hashes)

geza
  • 28,403
  • 6
  • 61
  • 135
  • 1
    Is your reasoning that a non-cryptographic hash algorithm could achieve greater performance? Try just using a cryptographic one with the zero key. Or try using the final block of a CBC with the zero key. These have the advantage of already being implemented so you can discover the performance almost for free. – Thomas M. DuBuisson Dec 11 '17 at 17:57
  • @ThomasM.DuBuisson: It's simple. AES has much more rounds that's needed. I've created a simple test, and it **seems** that only 2 rounds are enough. Compared to the 10 rounds which AES-128 needs, it's 5x faster. But I'm no expert, hence the question. – geza Dec 11 '17 at 18:01
  • Yes, it is known that two rounds of AES achieves full diffusion. So you can make a new cipher, AES-2, and get a CMAC with that cipher which would be a reasonable non-cryptographic hash. I don't think you need to implement this to get a good guess of the performance - just dividing an existing CMAC benchmark time by 6 will be an decent proxy. – Thomas M. DuBuisson Dec 11 '17 at 18:13
  • @ThomasM.DuBuisson: I think that better solutions exist. For example, I've created a hash, which is more than 30x faster (~30GB/sec) than AES-128-CBC (~1GB/sec on my machine). The problem is that it fails some of the SMHasher tests. Maybe someone else played with this problem too, and already have a working solution, which passes SMHasher, while has a very good speed. – geza Dec 11 '17 at 18:41
  • @zaph: I did. Fingerprinting and error detection. Not for hash tables. – geza Dec 11 '17 at 18:49
  • See https://stackoverflow.com/questions/20692386/are-there-in-x86-any-instructions-to-accelerate-sha-sha1-2-256-512-encoding - x86 instructions to accelerate SHA (SHA1/2/256/512) encoding. – ziesemer Dec 11 '17 at 18:50
  • @ziesemer: thanks. The problem with this that SHA instructions are still new, a lot of CPUs don't support it. On the other hand, AES is widely available now, not only on x86, but on ARM as well. – geza Dec 11 '17 at 18:52
  • @geza - understood. See also, https://crypto.stackexchange.com/questions/15914/accelerated-hashing-on-consumer-grade-cpu . Ideally, this would be a better discussion for crypto.stackexchange.com... – ziesemer Dec 11 '17 at 18:54
  • If you go to crypto.stackexchange.com then it would need to be a cryptographic discussion to be on topic. Perhaps ask about the fastest block-cipher based hash/mac (VMAC and UMAC will probably be among the recommendations). You could then take the obvious round-reduced variant. I really don't know the right stackexchange site for this discussion. – Thomas M. DuBuisson Dec 11 '17 at 19:10
  • @ziesemer: I think this question is off-topic on crypto.stackexchange, because it is not about cryptography at all. We just have AES-NI instructions, which can be used in a way which wasn't intended. So AES can be treated as a building block of a non-crypto hash, not something which has anything to do with cryptography. – geza Dec 11 '17 at 19:44

1 Answers1

2

MeowHash is a new (still not officially released) AES-NI-based hash function that is extremely fast and appears to be very robust for the functions you mentioned (but not cryptography):

Write-up: https://mollyrocket.com/meowhash

Repo: https://github.com/cmuratori/meow_hash

Roy Tinker
  • 10,044
  • 4
  • 41
  • 58