Lightweight 8 byte hash function algorithm

Question

I need to extract an 8 byte digest from a variable length string so I'm looking for such an algorithm that I will implement in c/c++. That will be part of a digital signature procedure on a microcontroller, so it has to be:

• writable in few lines of code, since the firmware has to be kept as little as possible;
• low in resource consumption, expecially ram (preferably less than 100 bytes);
• strong enough that changing a single character at any point of the string would change the overall digest.

I took a look at existing algorithms such as crc64 but they seems to be too heavy for my platform.

Answer 1

There is no chance to do a secure hash in 64 bits. Even SHA-1 at 160 bit 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-adversarial collisions just use the following, it is fine:

constexpr uint64 P1 = 7;
constexpr uint64 P2 = 31;

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

Answer 2

As AndrewTomazos-Fathomling said, it's impossible to do a secure hash in 64 bits, so if that's your intention then my advice is STOP, pick up a book and read about cryptographically secure hashing.

If you don't plan on using this as a secure hash and you do not care about collisions or attacks, then the answer he gave you works just fine and you can tweak the primes P1 and P2 as necessary. I will give you another alternative which allows you to do tagged hashing and mixes things up more.

// Disclaimer: I make no claims about the quality of this particular hash - it's 
// 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);
}