View Single Post September 24th, 2006 #4 dcn123 Junior Member   Join Date: Sep 2006 Posts: 1 Thanks for the corrections. Repeating the analysis (below) assuming the contending bits are random still gives a 25% probability of good checksum on collided message. Is this to be expected? David Nemes 1. Discovery Collision Analysis 1.1 Uncollided msg MID1 | 0xAA MID1 | 0x55 MID0 | 0xAA MID0 | 0x55 DID3 | 0xAA DID3 | 0x55 DID2 | 0xAA DID2 | 0x55 DID1 | 0xAA DID1 | 0x55 DID0 | 0xAA DID0 | 0x55 ------------- CSUM1 | 0xAA CSUM1 | 0x55 CSUM0 | 0xAA CSUM0 | 0x55 CSUM = (MID1|0xAA + MID0|0xAA + DID3|0xAA + DID2|0xAA + DID1|0xAA + DID0|0xAA) + (MID1|0x55 + MID0|0x55 + DID3|0x55 + DID2|0x55 + DID1|0x55 + DID0|0x55) = (MID1 + MID0 + DID3 + DID2 + DID1 + DID0) + 6*0xFF = (MID1 + MID0 + DID3 + DID2 + DID1 + DID0) + 0x5FA 1.2 Collided Msg Suppose there are 2 responders A and B with UIDs which differ only in DIDx. CSUMB - CSUMA = (DIDBx|0xAA + DIDBx|0x55) - (DIDAx|0xAA + DIDAx|0x55) = DIDBx - DIDAx In general it is assumed that the collision between 2 bytes would preserve the noncontending bit positions which have the same value in both bytes, and create random bit values in the contending bit positions which have different values in both bytes. COLLISION(X, Y) = (X & Y) | [(X ^ Y) & R], where 0 <= R <= 255 is a uniformly distributed random number. For the special case where DIDBx is obtained from DIDAx by changing a single bit from 0 to 1, and also where bit k of CSUMA is 0 (which would happen 50% of the time): bit k of DIDAx = 0, bit k of CSUMA = 0, DIDBx = DIDAx + (1 << k), where 0 <= k <= 7. DIDAx & DIDBx = DIDAx CSUMB - CSUMA = (1 << k) CSUMA & CSUMB = CSUMA Collided msg would differ from original msgs A and B in the DIDx bytes and the checksum bytes, as follows. COLLISION(DIDAx|0xAA, DIDBx|0xAA) = [(DIDAx | 0xAA) & (DIDBx | 0xAA)] | [((DIDAx | 0xAA) ^ (DIDBx | 0xAA)) & R1] = [(DIDAx & DIDBx) | 0xAA] | [(DIDAx ^ DIDBx) & 0x55 & R1] = [DIDAx | 0xAA] | [(1 << k) & 0x55 & R1] COLLISION(DIDAx|0x55, DIDBx|0x55) = [(DIDAx | 0x55) & (DIDBx | 0x55)] | [((DIDAx | 0x55) ^ (DIDBx | 0x55)) & R2] = [(DIDAx & DIDBx) | 0x55] | [(DIDAx ^ DIDBx) & 0xAA & R2] = [DIDAx | 0x55] | [(1 << k) & 0xAA & R2] COLLISION(CSUMA1|0xAA, CSUMB1|0xAA) = [(CSUMA1 & CSUMB1) | 0xAA] | [(CSUMA1 ^ CSUMB1) & 0x55 & R3] = [CSUMA1 | 0xAA] COLLISION(CSUMA1|0x55, CSUMB1|0x55) = [(CSUMA1 & CSUMB1) | 0x55] | [(CSUMA1 ^ CSUMB1) & 0xAA & R4] = [CSUMA1 | 0x55] COLLISION(CSUMA0|0xAA, CSUMB0|0xAA) = [(CSUMA0 & CSUMB0) | 0xAA] | [(CSUMA0 ^ CSUMB0) & 0x55 & R5] = [CSUMA0 | 0xAA] | [(1 << k) & 0x55 & R5] COLLISION(CSUMA0|0x55, CSUMB0|0x55) = [(CSUMA0 & CSUMB0) | 0x55] | [(CSUMA0 ^ CSUMB0) & 0xAA & R6] = [CSUMA0 | 0x55] | [(1 << k) & 0xAA & R6] Taking checksum over collided msg gives CSUM(over EUID part of collided msg) - CSUMA = ([DIDAx | 0xAA] | [(1 << k) & 0x55 & R1]) + ([DIDAx | 0x55] | [(1 << k) & 0xAA & R2]) - [DIDAx | 0xAA] - [DIDAx | 0x55] when k is even: CSUM(over EUID part of collided msg) - CSUMA = ([DIDAx | 0xAA] | [(1 << k) & 0x55 & R1]) + ([DIDAx | 0x55]) - [DIDAx | 0xAA] - [DIDAx | 0x55] = [(1 << k) & R1] when k is odd: CSUM(over EUID part of collided msg) - CSUMA = ([DIDAx | 0xAA]) + ([DIDAx | 0x55] | [(1 << k) & 0xAA & R2]) - [DIDAx | 0xAA] - [DIDAx | 0x55] = [(1 << k) & R2] CSUM1(recovered from CSUM part of collided msg) = [CSUMA1 | 0xAA] & [CSUMA1 | 0x55] = CSUMA1 CSUM0(recovered from CSUM part of collided msg) = ([CSUMA0 | 0xAA] | [(1 << k) & 0x55 & R5]) & ([CSUMA0 | 0x55] | [(1 << k) & 0xAA & R6]) = CSUMA0 | [(1 << k) & 0xAA & R6] | [(1 << k) & 0x55 & R5] => CSUM(recovered from CSUM part of collided msg) = CSUMA | [(1 << k) & 0xAA & R6] | [(1 << k) & 0x55 & R5] when k is even: CSUM(recovered from CSUM part of collided msg) = CSUMA | [(1 << k) & R5] when k is odd: CSUM(recovered from CSUM part of collided msg) = CSUMA | [(1 << k) & R6] For collided msg to have good checksum, when k is even: CSUMA + [(1 << k) & R1] = CSUMA | [(1 << k) & R5], which is true whenever bit k of R1 = bit k of R5 (50% chance given that bit k of CSUMA = 0, or 25% chance when bit k of CSUMA has any value). For collided msg to have good checksum, when k is odd: CSUMA + [(1 << k) & R2] = CSUMA | [(1 << k) & R6], which is true whenever bit k of R2 = bit k of R6 (50% chance given that bit k of CSUMA = 0, or 25% chance when bit k of CSUMA has any value). CONCLUSION: For a single bit difference in the device IDs, there is at least a 25% chance of the discovery collision having a good checksum when ideally the discovery collision checksum should be bad.  