Simple hash function to implement on a microcontroller

Question

I'm looking for a very simple hash function to implement on a microcontroller. The microcontroller displays a 4 digit alphanumeric session id on a display. I want to give the hash function a count and get back a number, which would later be turned into a 4-digit alphanumeric number. Any suggestions for a lightweight hash function?

Answer 1

How secure do you want this thing to be, and what are your code size versus space trade-offs? Are you going to be needing sequential numbers only, or values in arbitrary sequence?

Two simple hash-generation approaches are: // Get a random bit via linear congruential generator: int random_bit1(void) { static unsigned long seed; seed = seed*magicConstant + 12345; return (seed >> 31); // Use upper bit--not lower bit! }

int random_bit2(void)
{
  // Get a 'random' bit via linear feedback shift register
  unsigned long shifter;
  if (!shifter)
    shifter = 1;
  else if (shifter & 1)
    shifter = (shifter>>1);
  else
    shifter = (shifter>>1);
  return (shifter & 1);
}

To generate a four digit number, use something like the following:

int result = 0;
int i;
for (i=0; i<30; i++) // The higher the count, the less biased the results
{
  result *= 2;
  if (result >= 10000)
    result -= 10000;
  result += randomBit();
}

Note that both of the above bit-generation algorithms can be adapted to return the nth value for any arbitrary n in a reasonable amount of time, though the code to do that will be a fair bit more complicated. On the other hand, neither algorithm will be hard to reverse-engineer.

If you're only going to need values in sequence (meaning that after you've outputted the nth thing, you'll never need to output any lower-numbered thing, and you won't mind if computing a higher-numbered thing requires computing all intervening values) it is possible to build up some security by using six or so independent pseudo-random-bit generators (perhaps shift registers with different periods), and then use something like:

int reallyrandombit(void)
{
  if (randombit1())
  {
    if (randombit2())
      return randombit3();
    else
      return randombit4();
  }
  else
  {
    if (randombit3())
      return randombit5();
    else
      return randombit6();
  }
}

Note that for good results there should be some mixing of how random generators get used (note that random3 is used in two different places) but one should avoid feedback paths (none of the random generators affects the shifting of anything which would affect it) unless one has the tools to fully analyze them.

Answer 2

CRC32 would do the job if you don't need cryptographic security. It gives you a 32-bit output value, and only requires simple operations. Plenty of implementations out there for most major micro families, too. Split down to 4 bytes and do modulus on a 32-character alphabet (1-9 A-Z, skipping a few chars like I and J) for each, and there's your code.

Answer 3

You might be interested in this Crypto library. Its released under the GPL v3.

Crypto-avr-lib is a set of implementations of different cryptographic primitives. Due to the special limitations of microcontrollers (very little space, RAM and flash are ranging from a few bytes to a few KiB) reference or "normal" optimised implementations are not usable. Therefore we try to provide special implementations which respect the extreme limited resources of microcontroller applications.

There are several hash algorithms available:

• Blake
• BlueMidnightWish
• Grøstl
• MD5
• SHA-256
• SHA-1
• SHA-3 (Keccak)
• SHABAL
• Skein
• Twister
• Whirlpool

You can access the full code through their Subversion repository at http://das-labor.org/svn/microcontroller-2/crypto-lib.

Answer 4

• If you're really not bothered about security
• If all you want to do is 'mess up' a number

Then there are a bunch of really simple ways to do this, here are two I can think of:

void really_simple_hash(uint16_t x)
{
    SWAP_NIBBLES(FIRST_BYTE(x));
    SWAP_NIBBLES(SECOND_BYTE(x));
    x ^= 0xAAAA;
    return x;
}

On a PIC18, this translates into very simple code:

SWAPF  x,   f
SWAPF  x+1, f
movlw  0xAA
xorwf  x,   f
xorwf  x+1, f

It's pretty lightweight at only 5uS execution time on a PIC18 running at 10MIPS. If that's not enough of a mess, you can shuffle the bits around in the number. Again, on a PIC18:

rrcf   x,   f        ; Then we take each bit of the source word
rlcf   y+1, f        ; and shift it into one of the destination bytes
rrcf   x+1, f
rlcf   y,   f        ; There are:
rrcf   x,   f        ; - eight right shifts of x,
rlcf   y+1, f        ; - eight right shifts of x+1,
rrcf   x+1, f        ; - eight left shifts of y,
rlcf   y+1, f        ; - eight left shifts of y+1,
rrcf   x,   f
rlcf   y,   f        ; You can do them in whatever sequence you want
rrcf   x+1, f
rlcf   y,   f
rrcf   x,   f
rlcf   y+1, f
rrcf   x,   f
rlcf   y,   f
rrcf   x,   f
rlcf   y,   f
rrcf   x,   f       
rlcf   y+1, f       
rrcf   x+1, f
rlcf   y,   f
rrcf   x,   f
rlcf   y+1, f
rrcf   x+1, f
rlcf   y+1, f
rrcf   x,   f
rlcf   y,   f
rrcf   x+1, f
rlcf   y,   f
rrcf   x,   f
rlcf   y+1, f
rrcf   x,   f
rlcf   y,   f
rrcf   x,   f
rlcf   y,   f        ; Finally, the result is stored in y

It's still pretty lightweight, with an execution time of only 37uS for that same PIC18.

Answer 5

If it doesn't need to be strong cryptographic:

• pick a random key of same length in bits;
• share the key between sender and receiver;
• sender-side: crypto-text = clear-text EOR key (you can do this byte by byte).

Optional:

• receiver-side clear-text = crypto-text EOR key.