CODEWITHSUNDEEP
algorithmhash
Jay MacDonald
Jay MacDonald

Reputation: 13

Can anyone help me identify the algorithm?

This proprietary network protocol uses a weird (CRC?) hashing algorithm I've not seen before. It calculates this from the port.

From investigation, I've got the following hashes:

0-85
1-84
85-d0

7770-df
7771-de
7772-c9
7773-d0
7774-db
7775-da 
7776-e5 
7777-e4
7778-e7

This is submitted at 0x03 of the connection packet, and changes depending on port number.

Thanks,

Upvotes: 1

Views: 218

Answers (1)

Thomas M. DuBuisson
Thomas M. DuBuisson

Reputation: 64740

For the one-byte inputs the algorithm:

f x = 0x80 .|. (0xF0 .&. x `shiftL` 4) .|. x `xor` 0x05

or in C style:

#define F(x) (0x80 | (0xF0 & (x << 4)) | (x ^ 0x05))

EDIT: I changed the 0xF into 0xF0, which is what I ment.

Matches for the given examples (more examples needed).

You're two-byte examples are insufficient (see my comment) so I won't bother with those.

EDIT: How I worked this out:

Step one: write everything down in bits, space separate the nibbles (4 bits) because designs often do something different on the nibble boundary - that is they might do x & 0x80 | x ^ 0x05 but less often do x & 0x84 | x ^ 0x01.

0000 0000 --> 1000 0101
0000 0001 --> 1000 0100

See that, it looks like we get an 0x80 for free (or) and the second nibble got an xor 0x05. Testing 0 and 1 was smart. Hamming distance one values and zero values are always good tests. So right now I'm thinking the alg is:

#define f(x) (x ^ 0x85)

Then we get the test pair 0x85 to 0xd0:

1000 0101 --> 1101 0000

So the lower nibble still looks right (xor with 0x05) but the upper nibble needs to change to an OR, not an XOR:

#define f(x) ( (0xF0 & x | 0x80) \ // Upper nibble
             | 0x0F & (x ^ 0x05))   // Lower nibble

This is the same as

#define f(x) ( x^0x05 | 0x80)

But that still doesn't do it! Notice we get the same bit pattern in our resulting upper nibble as in our input lower nibble, see that 0101? Lets OR the lower nibble with the upper and call that the upper:

#define f(x) ( (x^0x05) | 0x80 | (0xF0 & (x << 4))

And now we match all three of the test cases (which isn't much, really)

This isn't what I put above that you accepted, perhaps you fixed my typo of 0xF into the intended 0xF0? If not then be sure you notice that bug and change your code. You could even include a few known-answer unit tests if this is for any serious use.

Oh, and since I have it handy, here it is in runnable form.

#include <stdio.h>
#define F(x) (0x80 | (0xF0 & (x << 4)) | (x ^ 0x05))

void main()
{
        printf("%02x %02x %02x\n", F(0), F(1), F(0x85));
}

Upvotes: 1

Related Questions