Geek Answers Handbook

Lightweight 8-byte hash function algorithm

I need to extract an 8-byte digest from a variable-length string, so I'm looking for an algorithm that I will implement in c / C ++. This will be part of the digital signature process on the microcontroller, so it should be:

  • written in several lines of code, since the firmware should be stored as little as possible;
  • low resource consumption, expansive (preferably less than 100 bytes);
  • strong enough that changing one character at any point in the line will change the overall digest.

I took a look at existing algorithms like crc64, but they seem to be too heavy for my platform.

+6
source share
3 answers

As AndrewTomazos-Fathomling said, it is not possible to make a secure hash in 64 bits, so if this is your intention, then my STOP advice is to take a book and read about cryptographically secure hashing.

If you do not plan to use this as a safe hash, and you do not need collisions or attacks, then the answer that he gave you works fine, and you can change the prime numbers P1 and P2 if necessary. I will give you another alternative that allows you to flag hashing and mix things more.

// Disclaimer: I make no claims about the quality of this particular hash - it // certainly not a cryptographically secure hash, nor should it *ever* be // construed as such. unsigned long long quickhash64(const char *str, unsigned long long mix = 0) { // set 'mix' to some value other than zero if you want a tagged hash const unsigned long long mulp = 2654435789; mix ^= 104395301; while(*str) mix += (*str++ * mulp) ^ (mix >> 23); return mix ^ (mix << 37); }
+1
source

There is no way to make a safe hash of 64 bits. Even 160 bit SHA-1 is considered theoretically broken. You should use SHA2-256 if you really care about secure digital signing. If you don't care about security and just want a hash function that avoids non-confessional collisions, just use the following: this is normal:

 constexpr uint64 P1 = 7; constexpr uint64 P2 = 31; uint64 hash = P1; for (const char* p = s; *p != 0; p++) { hash = hash * P2 + *p; }
+7
source

Below is a modified version of the 32-bit version found in my old source files

 static unsigned long long llhash(const char *str) { unsigned long long hash = 5381; int c; while (c = *str++) hash = ((hash << 5) + hash) + c; return hash; }

But hashing will always lead to collisions. Of course, some algorithms are better than others.

Edit: I found the source of the 32-bit version: http://www.cse.yorku.ca/~oz/hash.html

+3
source

More articles:


All Articles