How can I figure out a hash algorithm?

Question

This may be trivial, and may be impossible... this is outside my field but willing to learn.

I have a hardware device that accepts a network MAC address (6 bytes of data) like this: 38-60-77-EC-1D-33

and produces a 2-byte hash, like this: F0-9B

The same address always produces the same hash, and I can test any address I want, but only by hand. I have tried a handful of addresses to see if it's just a linear value, but it's not. This may simply be a checksum - there's no obvious security application, it's just a hardware handshake.

... is it going to be possible to reverse-engineer this? If so, how should I go about it?

This is going to be hard, isn't it.

Edit: Here are some samples:

00:00:00:00:00:00   684C
00:00:00:00:00:01   1717
00:00:00:00:00:02   96FA
00:00:00:00:00:03   E9A1
00:00:00:00:00:04   9520
00:00:00:00:00:05   EA7B
00:00:00:00:00:06   6B96
00:00:00:00:00:07   14CD
00:00:00:00:00:08   9294
00:00:00:00:00:09   EDCF

01:00:00:00:00:00   DF52
02:00:00:00:00:00   1BC7
00:01:00:00:00:00   BB1B
00:00:01:00:00:00   6434

Edit #2: There is clearly a pattern. I've run 50 strategic numbers and so far I've figured out that:

• The last digit repeats a pattern every 16 (F) numbers where every number appears exactly once. The digits change after 256 (FF) numbers but still repeat in groups of 16.
• Also in each group of 16 numbers, the first digit is one of only 4 numbers. Each group of 16 (so far) uses a different 4 numbers, but the order they appear is perfectly consistent.

I think at this point it's just going to be "educated" brute force, but I'm much more optimistic than I was 4 hours ago. I've tried a few online checksum calculators, but if this sounds like a known algorithm I'd appreciate the help, and I'll keep hacking away...

Answer 1

This function has all appearance of being affine (or loosely speaking: linear), in the sense that has in cryptanalysis: $$\forall (x,y,z),\;f(x\oplus y\oplus z)=f(x)\oplus f(y)\oplus f(z)$$ In other words: if the exclusive-OR of the inputs in any 4 lines is zero (e.g. the first 4 lines), then the XOR of their output is zero.

It follows that we can compute the output for any input $x$, as $$f(x)=f(0)\oplus\left(\bigoplus_{j\text{ with bit }j\text{ set in }x}\big(f(2^j)\oplus f(0)\big)\right)$$ where $f(2^j)$ is the output for input the 48-bit bitstring with only bit $j$ set. A similar equation can be derived without guesswork from any set of input/output pairs with one more elements than there are input bits, and all the inputs but one linearly independent.

This also gives the equation for any output bit as a function of the input bits, as a chain of exclusive-OR of input bits and a constant bit.

Code implementing this is a three-liner with a loop on the 48 input bits, plus a table of 48 words of 16 bits; that makes the whole thing less than 200 bytes of compiled code, running under a microsecond on a PC.

Further analysis could perhaps reveal more regularity; like, this could be a truncated CRC of the input bits in some order. That guesswork could be necessary if you do not obtain enough input (in particular, if some input bit does not change in any of the available input/output pairs, the only way to guess its influence on output is to find some regularity in the influence of those inputs bits that vary). That would also allow making the code shorter, faster, and with a simpler specification.

---

Note: I decided to answer the question even though it contains a dump of plaintext-ciphertext pairs (usually a no-no on CSE), because it illustrates well a common (reverse)-engineering problem: making something compatible with a deployed unknown function, on the sole basis of examples, when that function turns out to be affine, as does any function written using only bitwise eXclusive-OR, shifts and rotations. The technique I describe works for many functions found in the field; in particular anything worth the name CRC, including countless failed attempts to implement some standard or academically proper CRC, which ended up in some ugly proprietary mess.