0
$\begingroup$

I have a wireless capture of data and it's 12 bit hash. I am trying to identify the actual function that would have generated the hash data.

I tried all the generic 12 bit CRC polynomials but none of them seem to generate the appropriate output.

Any ideas on how I could reverse engineer the hash function?

Here's the input and the generated hash (inputString,hashString)

For some of these sequences there is only a 1 bit change from one packet to the next, but the hash changes significantly. I guess that indicates a really good hash function? But still really stumped on how I would go about this.

So have some additional data that I believe could help narrow down the problem but still not sure how to attack it however here goes... The packet seems to be transmitted twice. the second transmission is basically the original transmission xor'd with 0xff (NOT operation on original bytes)

4c024a41b060a1,148
b3fdb5be4f9f5e,eba

Line 1 - data 4c 02 4a 41 b0 60 a1

Not each bytes of line 1 gives us b3 fd 5b be 4f 9f 5e

Also noticed that the high byte of the checksum/hash seems to be following the not rule as well but not the low nibble - Line 1 Checksum/Hash 148 Line 2 Checksum(eba) = NOT 14 = eb but then the a breaks the rule - not sure what to make of it...

additional samples below

4c022d41b060a1,a88
b3fdd2be4f9f5e,57a      
4c022e41b060a2,b08
b3fdd1be4f9f5d,4f4
4c022f41b060a1,930
b3fdd0be4f9f5e,6ce
4c023041b060a2,b68
b3fdcfbe4f9f5d,49b
4c023141b060a1,950
b3fdcebe4f9f5e,6a5
4c023241b060a2,8d0
b3fdcdbe4f9f5d,72d
4c023341b060a1,ae8
b3fdccbe4f9f5e,513
4c023441b060a2,c08
b3fdcbbe4f9f5d,3ff
4c023541b060a1,e30
b3fdcabe4f9f5e,1c3
4c023641b060a2,fb0
b3fdc9be4f9f5d,047
4c023741b060a1,d88
b3fdc8be4f9f5e,27c
4c023841b060a2,5a8
b3fdc7be4f9f5d,a53
4c023941b060a1,790
b3fdc6be4f9f5e,864
4c023a41b060a1,e08
b3fdc5be4f9f5e,1f7
4c023b41b060a1,428
b3fdc4be4f9f5e,bdc
4c023c41b060a1,ad0
b3fdc3be4f9f5e,524
4c023d41b060a1,0f0
b3fdc2be4f9f5e,f0f
4c023e41b060a1,968
b3fdc1be4f9f5e,699
4c023f41b060a1,348
b3fdc0be4f9f5e,cb3
4c024041b060a1,c30
b3fdbfbe4f9f5e,3ce
4c024141b060a1,610
b3fdbebe4f9f5e,9ef
4c024241b060a1,f88
b3fdbdbe4f9f5e,075
4c024341b060a1,5a8
b3fdbcbe4f9f5e,a5d
4c024441b060a1,b50
b3fdbbbe4f9f5e,4af
4c024541b060a1,170
b3fdbabe4f9f5e,e8e
4c024641b060a1,8e8
b3fdb9be4f9f5e,713
4c024741b060a1,2c8
b3fdb8be4f9f5e,d3d
4c024841b060a1,2f0
b3fdb7be4f9f5e,d0b
4c024941b060a1,8d0
b3fdb6be4f9f5e,72d
4c024a41b060a1,148
b3fdb5be4f9f5e,eba
4c024b41b060a1,b68
b3fdb4be4f9f5e,49e
4c024c41b060a1,590
b3fdb3be4f9f5e,a69
4c024d41b060a2,7a8
b3fdb2be4f9f5d,853
4c024e41b060a2,e30
b3fdb1be4f9f5d,1ce
4c024f41b060a2,41d
9998a71c7cb217,ffb
4c025041b060a2,e50
b3fdafbe4f9f5d,1a8
4c025141b060a2,470
b3fdaebe4f9f5d,b8d
4c025241b060a2,de8
b3fdadbe4f9f5d,21b
4c025341b060a2,7c8
b3fdacbe4f9f5d,835
4c025441b060a2,930
b3fdabbe4f9f5d,6cf
4c025541b060a2,310
b3fdaabe4f9f5d,ced
4c025641b060a2,a88
b3fda9be4f9f5d,573
4c025741b060a2,0a8
b3fda8be4f9f5d,f5e
4c025841b060a2,090
b3fda7be4f9f5d,f66
4c025941b060a2,ab0
b3fda6be4f9f5d,54d
4c025a41b060a2,328
b3fda5be4f9f5d,cd3
4c025b41b060a2,908
b3fda4be4f9f5d,6f1
4c025c41b060a2,7f0
b3fda3be4f9f5d,805
4c025d41b060a2,dd0
b3fda2be4f9f5d,22f
4c025e41b060a2,448
b3fda1be4f9f5d,bb0
4c025f41b060a2,e68
b3fda0be4f9f5d,196
4c026041b060a2,730
b3fd9fbe4f9f5d,8cf

Below data has the initial 4C byte stripped as it was a constant. I tried calculating checksum with and without it but no joy...

16bbd143e0a1,5c8
16bcd143e0a1,b30
16bdd143e0a1,110
16bed143e0a1,888
16bfd143e0a1,2a8
16c0d143e0a1,dd0
16c1d143e0a1,7f0
16c2d143e0a1,e68
16c3d143e0a1,448
16c4d143e0a1,ab0
16c5d143e0a1,090
16c6d143e0a1,908
16c7d143e0a1,328
16c8d143e0a1,310
16c9d143e0a1,930
16cad143e0a1,0a8
16cbd143e0a1,a88
16ccd143e0a1,470
16cdd143e0a1,e50
16ced143e0a1,7c8
16cfd143e0a1,de8
16d0d143e0a1,7a8
16d1d143e0a1,d88
16d2d143e0a1,410
16d3d143e0a1,e30
16d4d143e0a1,0c8
16d5d143e0a1,ae8
16d6d143e0a1,370
16d7d143e0a1,950
16d8d143e0a1,968
16d9d143e0a1,348
16dad143e0a1,ad0
16dbd143e0a1,0f0
16dcd143e0a1,e08
16ddd143e0a1,428
16ded143e0a1,db0
16dfd143e0a1,790
16e0d143e0a1,ec8
16e1d143e0a1,4e8
16e2d143e0a1,d70
16e3d143e0a1,750
16e4d143e0a1,9a8
16e5d143e0a1,388
16e6d143e0a1,a10
16e7d143e0a1,030
16e8d143e0a1,008
16e9d143e0a1,a28
16ead143e0a1,3b0
16ebd143e0a1,990
16ecd143e0a1,768
16edd143e0a1,d48
16eed143e0a1,4d0
16efd143e0a1,ef0
16f0d143e0a1,4b0
16f1d143e0a1,e90
16f2d143e0a1,708
16f3d143e0a1,d28
16f4d143e0a1,3d0
16f5d143e0a1,9f0
16f6d143e0a1,068
16f7d143e0a1,a48
16f8d143e0a1,a70
16f9d143e0a1,050
16fad143e0a1,9c8
16fbd143e0a1,3e8
16fcd143e0a1,d10
16fdd143e0a1,730
16fed143e0a1,ea8
16ffd143e0a1,488
1700d143e0a1,8c8
1701d143e0a1,2e8
1702d143e0a1,b70
1703d143e0a1,150
1704d143e0a1,fa8
1705d143e0a1,588
1706d143e0a1,c10
1707d143e0a1,630
1708d143e0a1,608
1709d143e0a1,c28
170ad143e0a1,5b0
170bd143e0a2,788
170cd143e0a2,970
170dd143e0a2,350
170ed143e0a2,ac8
170fd143e0a2,0e8
1710d143e0a2,aa8
1711d143e0a2,088
1712d143e0a2,910
1713d143e0a2,330
1714d143e0a2,dc8
1715d143e0a2,7e8
1716d143e0a2,e70
1717d143e0a2,450
1718d143e0a2,468
1719d143e0a2,e48
171ad143e0a2,7d0
171bd143e0a2,df0
171cd143e0a2,308
171dd143e0a2,928
171ed143e0a2,0b0
171fd143e0a2,a90
1720d143e0a2,3c8
1721d143e0a2,9e8
1722d143e0a2,070
1723d143e0a2,a50
1724d143e0a2,4a8
1725d143e0a2,e88
1726d143e0a2,710
1727d143e0a2,d30
1728d143e0a2,d08
1729d143e0a2,728
172ad143e0a2,eb0
172bd143e0a2,490
172cd143e0a2,a68
172dd143e0a2,048
172ed143e0a2,9d0
172fd143e0a2,3f0
1730d143e0a2,9b0
1731d143e0a2,390
$\endgroup$
7
  • 2
    $\begingroup$ Don't cross-post!. Keep one copy! $\endgroup$
    – kelalaka
    Mar 1 at 16:08
  • $\begingroup$ Oddly enough got a comment in that StackExchange pointing me here, but I will add some more details that might make it more relevant here $\endgroup$
    – jay
    Mar 1 at 19:16
  • 1
    $\begingroup$ It's definitely linear (or affine, which is linear with a constant xor'ed in). It's likely some sort of CRC, however it may be from a nonzero initial state. $\endgroup$
    – poncho
    Mar 1 at 19:36
  • $\begingroup$ @poncho how did you deduce that it's linear? I am very new to this domain but reading stackoverflow.com/questions/23562583/… seems to indicate that I would have to check for CRC(a xor b) = CRC(a) XOR CRC(b), but since I do not have a CRC for the 0xFF sequence how can I know for a fact that it is linear? $\endgroup$
    – jay
    Mar 1 at 20:50
  • $\begingroup$ Another relationship that is true for linearity/affinity transforms (this does doesn't make the distinction) is if $A \oplus B \oplus C \oplus D = 0$, then $CRC(A) \oplus CRC(B) \oplus CRC(C) \oplus CRC(D) = 0$. There are entries in your second table {16bcd143e0a1,b30; 16bdd143e0a1,110; 16bed143e0a1,888; 16bfd143e0a1,2a8) whose inputs meet the first criteria ; it is straightforward to see that the outputs meet the second criteria $\endgroup$
    – poncho
    Mar 1 at 21:10

1 Answer 1

1
$\begingroup$

There's smarter things than brute forcing. As noted this appear to be an affine function for 48 bits to 12 bits, As such it can be written $\mathbf y=\mathbf xA+\mathbf c$ where $\mathbf y$ is a 12-long bit vector representing the output and $\mathbf x$ is a 48-long bit vector representing the input. Determining $A$ and $\mathbf c$ determines the function. We can determine five rows of $A$ from your second data set as it consists of $\mathbf x$ values where the low 32-bits are identical as are the top 7-bits.

XORing 0x1700d143e0a1 onto all inputs and 0x8c8 onto all outputs gives pairs $(\mathbf z,\mathbf z A)$. We note the pair (0x100000000,0xa20) which tells us that the 15th row of $A$ (counting 0-up) is (in binary) 101000100000. Likewise the pair (0x200000000,0x3b8) gives 14th row 001110111000. Similarly we have 13th row 011101100000, 12th row 111011000000, 11th row 001001100000 and 10th row 101000111010.

If you can get matched hashes for inputs that are less sequential, you should be able to recover the full function with a little over 50 values. Just XOR one input, output pair with the others can make a binary matrix of the others: $$\begin{bmatrix}\mathbf z_0 &|&\mathbf z_0 A\\ \mathbf z_1 &|&\mathbf z_1 A\\ \vdots &&\vdots\\ \mathbf z_n &|&\mathbf z_n A\\\end{bmatrix}$$ and put the matrix in systematic form using row operations, you will get $$\begin{bmatrix}I|A\\ 0|0\\\end{bmatrix}$$ and so recover $A$, if necessary you can then also recover $\mathbf c$ by taking any input/output pair and letting $\mathbf c=y\oplus\mathbf xA$.

$\endgroup$
2
  • $\begingroup$ Hi Daniel, This is amazing - I am trying to understand your point about the (z, ZA) pair and the rows - however I am not really following - as I am a total newbie at this and guessing I need to find a good reference to understand the notation you have used. Any pointers to a good book/resource so I can understand your notation. I might have to write it out on paper starting with xor'ng 0x1700d143e0a1 across all the inputs and then maybe your observation will jump out and I will get it :-(. Really appreciate any pointers in understanding how you solved this! $\endgroup$
    – jay
    Mar 2 at 1:49
  • $\begingroup$ I think this is starting to make sense. Basically because it is linear by isolating each bit in the input section and the corresponding output - I would end up creating a lookup table where I can lookup each bit output and then XOR all the relevant ones given an arbitrary 48 bit wide input to comeup with the actual output? Wow that is pretty sweet - you sir are a genius :-) $\endgroup$
    – jay
    Mar 2 at 2:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.