CRC reverse engineering
in [Cryptography]
|
Prev: Kerberos V4
Next: encryption on HAM radio
From: mvrpfswe on 2 May 2007 12:16 Hi, I have a CRC reverse engineering problem that I have not been able to solve. I am currently running out of ideas of how to approach the problem, please help. Here is a description of what I have done so far. The application of this is to read out serial numbers from electronic markers these are all hard coded and can not be altered. The data below has been read out of unique electronic markers (The guts of the markers consists of one Zarlink 15076CKG and some support components, I don't have the datasheet for the part it seams to be a custom IC). Each line represents one marker and the byte mapping is: 4 bytes of a binary serial number MSB first (this I have verified since the markers are tagged with the matching number) 2 bytes of ??? probably a type field (all markers are of the same type) 2 bytes of something that looks like a CRC. The data is read from the marker at register address 0x60 through 0x67. To make any use of the makers I need to figure out the algorithm to compute the last 2 bytes so I can verify that the correct serial has been read out. I have considered reading the data multiple times and have a voting scheme to determine if the correct data has been read, but I think it's a very ugly and crude solution around a (simple??) problem. Here is what I have done so far (many of the ideas taken from postings in this group, many thanks to you all). According to other postings here it states that the xor between two CRC with only a single bit change is the same. - This is true for all. I also found that if A^B = D A^C = E Then the crc polynomial is (2*D)^E if A, B and C is a factor of 2 (bit shift by 1) from each other (somewhere in the data stream). There are 2 sections in the data that has the property S/N low byte 0x80 and 0xA0 the computation of this gives polynomial 0xE507. I have tried all possible (brute force) CRC(16bit) start bytes with all possible final xor combinations and come up short. Also tried to append all combinations of 1 or 2 bytes to the dataset in the end without success. I tried to use a 32-bit CRC only using the lower 2 bytes as the result value. -There is one polynomial 0xCA18E507 that with 0 or all F:s as start with an xor value at the end generates a combination that matches S/N 0x80 through 0x83 but none of the others. Also tried to vary the start CRC state with all combinations (using the 0xCA... polynomial) without any success. I used a modified version of the crc16wierd.c algorithm posted by xmath. It does return values with the same properties as the data in the markers just not the same. Marker data: 0x00, 0x03, 0xB4, 0x7E, 0x40, 0x44, 0xA8, 0x5A, 0x00, 0x03, 0xB4, 0x80, 0x40, 0x44, 0xB0, 0xDA, 0x00, 0x03, 0xB4, 0x81, 0x40, 0x44, 0xEF, 0x0C, 0x00, 0x03, 0xB4, 0x82, 0x40, 0x44, 0xEA, 0x71, 0x00, 0x03, 0xB4, 0x83, 0x40, 0x44, 0xB5, 0xA7, 0x00, 0x03, 0xB4, 0x85, 0x40, 0x44, 0xB6, 0x5D, 0x00, 0x03, 0xB4, 0x86, 0x40, 0x44, 0xB3, 0x20, 0x00, 0x03, 0xB4, 0x88, 0x40, 0x44, 0xEF, 0x78, 0x00, 0x03, 0xB4, 0x89, 0x40, 0x44, 0xB0, 0xAE, 0x00, 0x03, 0xB4, 0x8C, 0x40, 0x44, 0xB6, 0x29, 0x00, 0x03, 0xB4, 0x8F, 0x40, 0x44, 0xB3, 0x54, 0x00, 0x03, 0xB4, 0x90, 0x40, 0x44, 0xEA, 0x99, 0x00, 0x03, 0xB4, 0x93, 0x40, 0x44, 0xEF, 0xE4, 0x00, 0x03, 0xB4, 0x9C, 0x40, 0x44, 0xEC, 0x6A, 0x00, 0x03, 0xB4, 0x9E, 0x40, 0x44, 0xB6, 0xC1, 0x00, 0x03, 0xB4, 0xA0, 0x40, 0x44, 0xEA, 0x5C, 0x00, 0x03, 0xB4, 0xA1, 0x40, 0x44, 0xB5, 0x8A, 0x00, 0x03, 0xB4, 0xA2, 0x40, 0x44, 0xB0, 0xF7, 0x00, 0x03, 0xB4, 0xA5, 0x40, 0x44, 0xEC, 0xDB, 0x00, 0x03, 0xB4, 0xA6, 0x40, 0x44, 0xE9, 0xA6, 0x00, 0x03, 0xB4, 0xA8, 0x40, 0x44, 0xB5, 0xFE, 0x00, 0x03, 0xB4, 0xAB, 0x40, 0x44, 0xB0, 0x83, 0x00, 0x03, 0xB4, 0xAC, 0x40, 0x44, 0xEC, 0xAF, 0x00, 0x03, 0xB4, 0xAD, 0x40, 0x44, 0xB3, 0x79, 0x00, 0x03, 0xB4, 0xB3, 0x40, 0x44, 0xB5, 0x62, 0x00, 0x03, 0xB4, 0xB4, 0x40, 0x44, 0xE9, 0x4E, 0x00, 0x03, 0xB4, 0xB5, 0x40, 0x44, 0xB6, 0x98, 0x00, 0x03, 0xB4, 0xB6, 0x40, 0x44, 0xB3, 0xE5, There must be a more elegant way of figuring this out rather then a brute force, if anyone has any Idea on how to approach this problem please let me know. Thanks Johan
From: David Wagner on 2 May 2007 13:16 mvrpfswe wrote: >There must be a more elegant way of figuring this out rather then a >brute force, One conceptually simple thing you can try is linear algebra. Assume that each bit of the presumed-CRC-output can be written an (unknown) linear function data bits; write down a system of linear equations; and then use linear algrebra (Gaussian elimination) to solve the system of linear equations and find the linear function (if there is one) that describes how to compute that output bit as a function of the input bits.
From: GiuseppeEvilcry on 2 May 2007 13:28 Hello, Take a look to this link, it should help you.. http://nfotemple.free.fr/site_cryptokg/site_christal/texts/crc/index.html Regards, Evilcry mvrpfswe ha scritto: > Hi, > > I have a CRC reverse engineering problem that I have not been able to > solve. I am currently running out of ideas of how to approach the > problem, please help. > > Here is a description of what I have done so far. > > The application of this is to read out serial numbers from electronic > markers these are all hard coded and can not be altered. The data > below has been read out of unique electronic markers (The guts of the > markers consists of one Zarlink 15076CKG and some support components, > I don't have the datasheet for the part it seams to be a custom IC). > > Each line represents one marker and the byte mapping is: > 4 bytes of a binary serial number MSB first (this I have verified > since the markers are tagged with the matching number) > 2 bytes of ??? probably a type field (all markers are of the same > type) > 2 bytes of something that looks like a CRC. > The data is read from the marker at register address 0x60 through > 0x67. > > To make any use of the makers I need to figure out the algorithm to > compute the last 2 bytes so I can verify that the correct serial has > been read out. I have considered reading the data multiple times and > have a voting scheme to determine if the correct data has been read, > but I think it's a very ugly and crude solution around a (simple??) > problem. > > Here is what I have done so far (many of the ideas taken from postings > in this group, many thanks to you all). > > According to other postings here it states that the xor between two > CRC with only a single bit change is the same. > - This is true for all. > > I also found that if > A^B = D > A^C = E > Then the crc polynomial is (2*D)^E if A, B and C is a factor of 2 (bit > shift by 1) from each other (somewhere in the data stream). > There are 2 sections in the data that has the property S/N low byte > 0x80 and 0xA0 the computation of this gives polynomial 0xE507. > > I have tried all possible (brute force) CRC(16bit) start bytes with > all possible final xor combinations and come up short. > Also tried to append all combinations of 1 or 2 bytes to the dataset > in the end without success. > > I tried to use a 32-bit CRC only using the lower 2 bytes as the result > value. > -There is one polynomial 0xCA18E507 that with 0 or all F:s as start > with an xor value at the end generates a combination that matches S/N > 0x80 through 0x83 but none of the others. > Also tried to vary the start CRC state with all combinations (using > the 0xCA... polynomial) without any success. > > I used a modified version of the crc16wierd.c algorithm posted by > xmath. It does return values with the same properties as the data in > the markers just not the same. > > Marker data: > 0x00, 0x03, 0xB4, 0x7E, 0x40, 0x44, 0xA8, 0x5A, > 0x00, 0x03, 0xB4, 0x80, 0x40, 0x44, 0xB0, 0xDA, > 0x00, 0x03, 0xB4, 0x81, 0x40, 0x44, 0xEF, 0x0C, > 0x00, 0x03, 0xB4, 0x82, 0x40, 0x44, 0xEA, 0x71, > 0x00, 0x03, 0xB4, 0x83, 0x40, 0x44, 0xB5, 0xA7, > 0x00, 0x03, 0xB4, 0x85, 0x40, 0x44, 0xB6, 0x5D, > 0x00, 0x03, 0xB4, 0x86, 0x40, 0x44, 0xB3, 0x20, > 0x00, 0x03, 0xB4, 0x88, 0x40, 0x44, 0xEF, 0x78, > 0x00, 0x03, 0xB4, 0x89, 0x40, 0x44, 0xB0, 0xAE, > 0x00, 0x03, 0xB4, 0x8C, 0x40, 0x44, 0xB6, 0x29, > 0x00, 0x03, 0xB4, 0x8F, 0x40, 0x44, 0xB3, 0x54, > 0x00, 0x03, 0xB4, 0x90, 0x40, 0x44, 0xEA, 0x99, > 0x00, 0x03, 0xB4, 0x93, 0x40, 0x44, 0xEF, 0xE4, > 0x00, 0x03, 0xB4, 0x9C, 0x40, 0x44, 0xEC, 0x6A, > 0x00, 0x03, 0xB4, 0x9E, 0x40, 0x44, 0xB6, 0xC1, > 0x00, 0x03, 0xB4, 0xA0, 0x40, 0x44, 0xEA, 0x5C, > 0x00, 0x03, 0xB4, 0xA1, 0x40, 0x44, 0xB5, 0x8A, > 0x00, 0x03, 0xB4, 0xA2, 0x40, 0x44, 0xB0, 0xF7, > 0x00, 0x03, 0xB4, 0xA5, 0x40, 0x44, 0xEC, 0xDB, > 0x00, 0x03, 0xB4, 0xA6, 0x40, 0x44, 0xE9, 0xA6, > 0x00, 0x03, 0xB4, 0xA8, 0x40, 0x44, 0xB5, 0xFE, > 0x00, 0x03, 0xB4, 0xAB, 0x40, 0x44, 0xB0, 0x83, > 0x00, 0x03, 0xB4, 0xAC, 0x40, 0x44, 0xEC, 0xAF, > 0x00, 0x03, 0xB4, 0xAD, 0x40, 0x44, 0xB3, 0x79, > 0x00, 0x03, 0xB4, 0xB3, 0x40, 0x44, 0xB5, 0x62, > 0x00, 0x03, 0xB4, 0xB4, 0x40, 0x44, 0xE9, 0x4E, > 0x00, 0x03, 0xB4, 0xB5, 0x40, 0x44, 0xB6, 0x98, > 0x00, 0x03, 0xB4, 0xB6, 0x40, 0x44, 0xB3, 0xE5, > > There must be a more elegant way of figuring this out rather then a > brute force, if anyone has any Idea on how to approach this problem > please let me know. > > Thanks > Johan
From: BillMays on 2 May 2007 16:52 There are many CRC-16 bit primes, 1 is used the most (called CRC-16), then 1 other, but there are a lot more. CRC is usally used on longer message lengths, 4 bytes seems a little short. Could be a home brew, LRC with some more stuff like the credit cards. "mvrpfswe" <mvrpfswe(a)gmail.com> wrote in message news:1178122600.529857.86340(a)e65g2000hsc.googlegroups.com... > Hi, > > I have a CRC reverse engineering problem that I have not been able to > solve. I am currently running out of ideas of how to approach the > problem, please help. > > Here is a description of what I have done so far. > > The application of this is to read out serial numbers from electronic > markers these are all hard coded and can not be altered. The data > below has been read out of unique electronic markers (The guts of the > markers consists of one Zarlink 15076CKG and some support components, > I don't have the datasheet for the part it seams to be a custom IC). > > Each line represents one marker and the byte mapping is: > 4 bytes of a binary serial number MSB first (this I have verified > since the markers are tagged with the matching number) > 2 bytes of ??? probably a type field (all markers are of the same > type) > 2 bytes of something that looks like a CRC. > The data is read from the marker at register address 0x60 through > 0x67. > > To make any use of the makers I need to figure out the algorithm to > compute the last 2 bytes so I can verify that the correct serial has > been read out. I have considered reading the data multiple times and > have a voting scheme to determine if the correct data has been read, > but I think it's a very ugly and crude solution around a (simple??) > problem. > > Here is what I have done so far (many of the ideas taken from postings > in this group, many thanks to you all). > > According to other postings here it states that the xor between two > CRC with only a single bit change is the same. > - This is true for all. > > I also found that if > A^B = D > A^C = E > Then the crc polynomial is (2*D)^E if A, B and C is a factor of 2 (bit > shift by 1) from each other (somewhere in the data stream). > There are 2 sections in the data that has the property S/N low byte > 0x80 and 0xA0 the computation of this gives polynomial 0xE507. > > I have tried all possible (brute force) CRC(16bit) start bytes with > all possible final xor combinations and come up short. > Also tried to append all combinations of 1 or 2 bytes to the dataset > in the end without success. > > I tried to use a 32-bit CRC only using the lower 2 bytes as the result > value. > -There is one polynomial 0xCA18E507 that with 0 or all F:s as start > with an xor value at the end generates a combination that matches S/N > 0x80 through 0x83 but none of the others. > Also tried to vary the start CRC state with all combinations (using > the 0xCA... polynomial) without any success. > > I used a modified version of the crc16wierd.c algorithm posted by > xmath. It does return values with the same properties as the data in > the markers just not the same. > > Marker data: > 0x00, 0x03, 0xB4, 0x7E, 0x40, 0x44, 0xA8, 0x5A, > 0x00, 0x03, 0xB4, 0x80, 0x40, 0x44, 0xB0, 0xDA, > 0x00, 0x03, 0xB4, 0x81, 0x40, 0x44, 0xEF, 0x0C, > 0x00, 0x03, 0xB4, 0x82, 0x40, 0x44, 0xEA, 0x71, > 0x00, 0x03, 0xB4, 0x83, 0x40, 0x44, 0xB5, 0xA7, > 0x00, 0x03, 0xB4, 0x85, 0x40, 0x44, 0xB6, 0x5D, > 0x00, 0x03, 0xB4, 0x86, 0x40, 0x44, 0xB3, 0x20, > 0x00, 0x03, 0xB4, 0x88, 0x40, 0x44, 0xEF, 0x78, > 0x00, 0x03, 0xB4, 0x89, 0x40, 0x44, 0xB0, 0xAE, > 0x00, 0x03, 0xB4, 0x8C, 0x40, 0x44, 0xB6, 0x29, > 0x00, 0x03, 0xB4, 0x8F, 0x40, 0x44, 0xB3, 0x54, > 0x00, 0x03, 0xB4, 0x90, 0x40, 0x44, 0xEA, 0x99, > 0x00, 0x03, 0xB4, 0x93, 0x40, 0x44, 0xEF, 0xE4, > 0x00, 0x03, 0xB4, 0x9C, 0x40, 0x44, 0xEC, 0x6A, > 0x00, 0x03, 0xB4, 0x9E, 0x40, 0x44, 0xB6, 0xC1, > 0x00, 0x03, 0xB4, 0xA0, 0x40, 0x44, 0xEA, 0x5C, > 0x00, 0x03, 0xB4, 0xA1, 0x40, 0x44, 0xB5, 0x8A, > 0x00, 0x03, 0xB4, 0xA2, 0x40, 0x44, 0xB0, 0xF7, > 0x00, 0x03, 0xB4, 0xA5, 0x40, 0x44, 0xEC, 0xDB, > 0x00, 0x03, 0xB4, 0xA6, 0x40, 0x44, 0xE9, 0xA6, > 0x00, 0x03, 0xB4, 0xA8, 0x40, 0x44, 0xB5, 0xFE, > 0x00, 0x03, 0xB4, 0xAB, 0x40, 0x44, 0xB0, 0x83, > 0x00, 0x03, 0xB4, 0xAC, 0x40, 0x44, 0xEC, 0xAF, > 0x00, 0x03, 0xB4, 0xAD, 0x40, 0x44, 0xB3, 0x79, > 0x00, 0x03, 0xB4, 0xB3, 0x40, 0x44, 0xB5, 0x62, > 0x00, 0x03, 0xB4, 0xB4, 0x40, 0x44, 0xE9, 0x4E, > 0x00, 0x03, 0xB4, 0xB5, 0x40, 0x44, 0xB6, 0x98, > 0x00, 0x03, 0xB4, 0xB6, 0x40, 0x44, 0xB3, 0xE5, > > There must be a more elegant way of figuring this out rather then a > brute force, if anyone has any Idea on how to approach this problem > please let me know. > > Thanks > Johan >
From: Volker Hetzer on 3 May 2007 08:11
mvrpfswe schrieb: > Hi, > > I have a CRC reverse engineering problem that I have not been able to > solve. I am currently running out of ideas of how to approach the > problem, please help. > > Here is a description of what I have done so far. > > The application of this is to read out serial numbers from electronic > markers these are all hard coded and can not be altered. The data > below has been read out of unique electronic markers (The guts of the > markers consists of one Zarlink 15076CKG and some support components, > I don't have the datasheet for the part it seams to be a custom IC). > > Each line represents one marker and the byte mapping is: > 4 bytes of a binary serial number MSB first (this I have verified > since the markers are tagged with the matching number) > 2 bytes of ??? probably a type field (all markers are of the same > type) > 2 bytes of something that looks like a CRC. > The data is read from the marker at register address 0x60 through > 0x67. > > To make any use of the makers I need to figure out the algorithm to > compute the last 2 bytes so I can verify that the correct serial has > been read out. I have considered reading the data multiple times and > have a voting scheme to determine if the correct data has been read, > but I think it's a very ugly and crude solution around a (simple??) > problem. My personal choice woul;d be to contact the guys who coded it. CRCs are /meant/ to be verified and with a 16bit CRC no security issues can be possibly involved. They should be willing and able to tell you the details of the CRC calculation. Lots of Greetings! Volker -- For email replies, please substitute the obvious. |