You are not logged in.

#1 07 Dec 2006 10:15 am

dp_wiz
Member
From: Dmitrov, Russia
Registered: Dec 2006
Posts: 14
Website

EA's great CRC16 implementation

Hi there!

Please help me with that crc16 part of auth token generation.
I trying to make that in Python. Tried already lots of varies, but all of them isn't matching the working one. hmm

Can someone post correct crc-table and explain crc16 algo', not in that hacky assemblish PHP, but in plain english?

PS: Tried to extract table from C# module, but its computation func isn't matching too.

PPS: My burning brain will say many thanks to its savior roll

Last edited by dp_wiz (07 Dec 2006 10:22 am)

Offline

 

#2 07 Dec 2006 11:28 am

MadHatter
Administrator
From: Dallas TX
Registered: Jun 2006
Posts: 529
Website

Re: EA's great CRC16 implementation

its CRC 16 CCITT with an initial value of 0 instead of 65535 (0xffff) and a polynomial of 0x1021 (4129).  I havent had time to get around to writing a simple version in php but I have written a C# version if thats of any help to you (edit: guess not... sorry).  I don't know python well enough to write the implementation in it.

when I get a minute, I'll see if I can work something out in python.  you'll need to make sure your data types are correct.  if they're not their values will overflow and you'll end up w/ a wrong computation.

Offline

 

#3 07 Dec 2006 11:47 am

MadHatter
Administrator
From: Dallas TX
Registered: Jun 2006
Posts: 529
Website

Re: EA's great CRC16 implementation

oh, if you're just looking for the table, here are the values:

decimal version:

Code:

0 4129 8258 12387 16516 20645 24774 28903 
33032 37161 41290 45419 49548 53677 57806 61935 
4657 528 12915 8786 21173 17044 29431 25302 
37689 33560 45947 41818 54205 50076 62463 58334 
9314 13379 1056 5121 25830 29895 17572 21637 
42346 46411 34088 38153 58862 62927 50604 54669 
13907 9842 5649 1584 30423 26358 22165 18100 
46939 42874 38681 34616 63455 59390 55197 51132 
18628 22757 26758 30887 2112 6241 10242 14371 
51660 55789 59790 63919 35144 39273 43274 47403 
23285 19156 31415 27286 6769 2640 14899 10770 
56317 52188 64447 60318 39801 35672 47931 43802 
27814 31879 19684 23749 11298 15363 3168 7233 
60846 64911 52716 56781 44330 48395 36200 40265 
32407 28342 24277 20212 15891 11826 7761 3696 
65439 61374 57309 53244 48923 44858 40793 36728 
37256 33193 45514 41451 53516 49453 61774 57711 
4224 161 12482 8419 20484 16421 28742 24679 
33721 37784 41979 46042 49981 54044 58239 62302 
689 4752 8947 13010 16949 21012 25207 29270 
46570 42443 38312 34185 62830 58703 54572 50445 
13538 9411 5280 1153 29798 25671 21540 17413 
42971 47098 34713 38840 59231 63358 50973 55100 
9939 14066 1681 5808 26199 30326 17941 22068 
55628 51565 63758 59695 39368 35305 47498 43435 
22596 18533 30726 26663 6336 2273 14466 10403 
52093 56156 60223 64286 35833 39896 43963 48026 
19061 23124 27191 31254 2801 6864 10931 14994 
64814 60687 56684 52557 48554 44427 40424 36297 
31782 27655 23652 19525 15522 11395 7392 3265 
61215 65342 53085 57212 44955 49082 36825 40952 
28183 32310 20053 24180 11923 16050 3793 7920

hex version:

Code:

0x0 0x1021 0x2042 0x3063 0x4084 0x50a5 0x60c6 0x70e7 
0x8108 0x9129 0xa14a 0xb16b 0xc18c 0xd1ad 0xe1ce 0xf1ef 
0x1231 0x210 0x3273 0x2252 0x52b5 0x4294 0x72f7 0x62d6 
0x9339 0x8318 0xb37b 0xa35a 0xd3bd 0xc39c 0xf3ff 0xe3de 
0x2462 0x3443 0x420 0x1401 0x64e6 0x74c7 0x44a4 0x5485 
0xa56a 0xb54b 0x8528 0x9509 0xe5ee 0xf5cf 0xc5ac 0xd58d 
0x3653 0x2672 0x1611 0x630 0x76d7 0x66f6 0x5695 0x46b4 
0xb75b 0xa77a 0x9719 0x8738 0xf7df 0xe7fe 0xd79d 0xc7bc 
0x48c4 0x58e5 0x6886 0x78a7 0x840 0x1861 0x2802 0x3823 
0xc9cc 0xd9ed 0xe98e 0xf9af 0x8948 0x9969 0xa90a 0xb92b 
0x5af5 0x4ad4 0x7ab7 0x6a96 0x1a71 0xa50 0x3a33 0x2a12 
0xdbfd 0xcbdc 0xfbbf 0xeb9e 0x9b79 0x8b58 0xbb3b 0xab1a 
0x6ca6 0x7c87 0x4ce4 0x5cc5 0x2c22 0x3c03 0xc60 0x1c41 
0xedae 0xfd8f 0xcdec 0xddcd 0xad2a 0xbd0b 0x8d68 0x9d49 
0x7e97 0x6eb6 0x5ed5 0x4ef4 0x3e13 0x2e32 0x1e51 0xe70 
0xff9f 0xefbe 0xdfdd 0xcffc 0xbf1b 0xaf3a 0x9f59 0x8f78 
0x9188 0x81a9 0xb1ca 0xa1eb 0xd10c 0xc12d 0xf14e 0xe16f 
0x1080 0xa1 0x30c2 0x20e3 0x5004 0x4025 0x7046 0x6067 
0x83b9 0x9398 0xa3fb 0xb3da 0xc33d 0xd31c 0xe37f 0xf35e 
0x2b1 0x1290 0x22f3 0x32d2 0x4235 0x5214 0x6277 0x7256 
0xb5ea 0xa5cb 0x95a8 0x8589 0xf56e 0xe54f 0xd52c 0xc50d 
0x34e2 0x24c3 0x14a0 0x481 0x7466 0x6447 0x5424 0x4405 
0xa7db 0xb7fa 0x8799 0x97b8 0xe75f 0xf77e 0xc71d 0xd73c 
0x26d3 0x36f2 0x691 0x16b0 0x6657 0x7676 0x4615 0x5634 
0xd94c 0xc96d 0xf90e 0xe92f 0x99c8 0x89e9 0xb98a 0xa9ab 
0x5844 0x4865 0x7806 0x6827 0x18c0 0x8e1 0x3882 0x28a3 
0xcb7d 0xdb5c 0xeb3f 0xfb1e 0x8bf9 0x9bd8 0xabbb 0xbb9a 
0x4a75 0x5a54 0x6a37 0x7a16 0xaf1 0x1ad0 0x2ab3 0x3a92 
0xfd2e 0xed0f 0xdd6c 0xcd4d 0xbdaa 0xad8b 0x9de8 0x8dc9 
0x7c26 0x6c07 0x5c64 0x4c45 0x3ca2 0x2c83 0x1ce0 0xcc1 
0xef1f 0xff3e 0xcf5d 0xdf7c 0xaf9b 0xbfba 0x8fd9 0x9ff8 
0x6e17 0x7e36 0x4e55 0x5e74 0x2e93 0x3eb2 0xed1 0x1ef0

if these are the values you were using, then post your code that does the crc calculation and lets have a look.

Offline

 

#4 07 Dec 2006 12:22 pm

dp_wiz
Member
From: Dmitrov, Russia
Registered: Dec 2006
Posts: 14
Website

Re: EA's great CRC16 implementation

input data: 74 fd 40 45 64 00 00 00 6f 17 e6 04 00 00 00

This one is taken from someone's script:

Code:

def calc( data ):
    crc = 0
    for char in data:
        crc = (crc >> 8) ^ table[ (crc ^ ord(char)) & 0xFF ]
    return crc

The result against your table and data is "0x402".

Here is my silly attempt to mimic the C# function of yours:

Code:

def compute(data):
    crc = 0
    for byte in (ord(part) for part in data):
        ushort = (crc << 8)
        if crc > 65536:
            crc %= 65536
        crc = (ushort ^ table[((crc >> 8) ^ (0xff & byte))])
    return crc

Result: "0xc9e4"

The correct one is "0x8562"

Offline

 

#5 07 Dec 2006 12:31 pm

dp_wiz
Member
From: Dmitrov, Russia
Registered: Dec 2006
Posts: 14
Website

Re: EA's great CRC16 implementation

Found some weirdnesses... hmm

Isn't "0xff & byte" always == byte itself?

That "crc >> 8" need to be: SHR or SAR?

PS: Does your C# implementation is giving auth-correct CRC? wink

Offline

 

#6 07 Dec 2006 1:28 pm

MadHatter
Administrator
From: Dallas TX
Registered: Jun 2006
Posts: 529
Website

Re: EA's great CRC16 implementation

dp_wiz :

Isn't "0xff & byte" always == byte itself?

yea, ff & byte will be byte as long as byte is unsigned (which it is).  I ported this from a C implementation and the input was a char but the operation was done on an unsigned short, and was used to convert the value.

the index of the table is (crc >> 8) ^ byte.  not knowing how the data types work out in python, I cant say what would be best for conversion.  obviously the value should be between 0 and 255 (or 1 and 256 depending on how arrays work in python).

dp_wiz :

That "crc >> 8" need to be: SHR or SAR?

crc >> 8 is a shr since its unsigned there's no need to maintain the sign bit.

dp_wiz :

PS: Does your C# implementation is giving auth-correct CRC? wink

yep.

Offline

 

#7 07 Dec 2006 1:32 pm

MadHatter
Administrator
From: Dallas TX
Registered: Jun 2006
Posts: 529
Website

Re: EA's great CRC16 implementation

dp_wiz :

input data: 74 fd 40 45 64 00 00 00 6f 17 e6 04 00 00 00

This one is taken from someone's script:

Code:

def calc( data ):
    crc = 0
    for char in data:
        crc = (crc >> 8) ^ table[ (crc ^ ord(char)) & 0xFF ]
    return crc

The result against your table and data is "0x402".

Here is my silly attempt to mimic the C# function of yours:

Code:

def compute(data):
    crc = 0
    for byte in (ord(part) for part in data):
        ushort = (crc << 8)
        if crc > 65536:
            crc %= 65536
        crc = (ushort ^ table[((crc >> 8) ^ (0xff & byte))])
    return crc

Result: "0xc9e4"

The correct one is "0x8562"

e4 c9 is the correct value to append to the byte array for the input you posted which gets encrypted and base64 encoded. 

how did you come up w/ 62 85?

that first function you posted is actually correct for crc 16, but this is crc 16 ccitt and they are different (ccitt stands for Comité consultatif international téléphonique et télégraphique or International Telegraph and Telephone Consultative Committee and was the algorithm they standardized on for calculating checksums for their telecom networks).

Offline

 

#8 07 Dec 2006 2:08 pm

dp_wiz
Member
From: Dmitrov, Russia
Registered: Dec 2006
Posts: 14
Website

Re: EA's great CRC16 implementation

MadHatter :

dp_wiz :

input data: 74 fd 40 45 64 00 00 00 6f 17 e6 04 00 00 00

MadHatter :

e4 c9 is the correct value to append to the byte array for the input you posted which gets encrypted and base64 encoded.

You tried it against stats server? Thanks for taking that risk ((:
But how it can be, different correct crc-s for same input?

MadHatter :

how did you come up w/ 62 85?

That's (with input data) is from Wiki:

http://bf2tech.org/index.php/BF2142_Statistics :

had I used the 00 client flag bytes 15 & 16 would be:
byte 15: 85
byte 16: 62

Offline

 

#9 07 Dec 2006 2:21 pm

MadHatter
Administrator
From: Dallas TX
Registered: Jun 2006
Posts: 529
Website

Re: EA's great CRC16 implementation

input data: 74 fd 40 45 64 00 00 00 6f 17 e6 04 00 00 00 has one too many bytes to be the pre-crc bytes of the auth token ( 14 bytes + 2 checksum bytes.  this one has 15 bytes).

the crc16 ccitt checksum of 74 fd 40 45 64 00 00 00 6f 17 e6 04 00 00 00 is 0xc9e4

the crc16 ccitt checksum of 74 fd 40 45 64 00 00 00 6f 17 e6 04 00 00 is 0x6285


I probably need to simplify how I said that on the wiki.  with the different permutations of the payload this may have not been too clear.

Offline

 

#10 07 Dec 2006 11:23 pm

dp_wiz
Member
From: Dmitrov, Russia
Registered: Dec 2006
Posts: 14
Website

Re: EA's great CRC16 implementation

Ooops... Will put this on the top of the rule list: "Verify the test data before verify code with it" cool

PS: And another one: "do not code byte-crunchers after 11 PM"...

Last edited by dp_wiz (07 Dec 2006 11:24 pm)

Offline

 

#11 08 Dec 2006 12:50 am

MadHatter
Administrator
From: Dallas TX
Registered: Jun 2006
Posts: 529
Website

Re: EA's great CRC16 implementation

been there w/ the "verify test data" as I'm sure everybody has, but to be honest, I do my best work between the hours of 11pm and 2am (when not gaming), I just try to stay away from the byte crunchers all together big_smile (not much luck w/ that though).  I have the brain dead problem during normal work hours tongue

Offline

 



© 2003 - 2019 NullFX
Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License