When I managed to decode the main payload in the frames, I learned that the frames are send with the least significant bit (lsb) first, so I was actually showing the captured frames in "reverse". This ended up being a bit confusing since binary number are normally shows with the msb at the left, and lsb at the right, so in this post I will show the frames reverse compared to the previous posts, so what looked like:
preamble/header payload checksum 11111010100011001001 110010111110011111010000000000000000 110100111110010 11111010100011001001 000101111110011111010000000000000000 000111100001010 11111010000011001001 00100111111100000000 111000010110010 11111010000011001001 01100111111100000000 111001010010000
will now look like this:
checksum payload header/preamble 010011111001011 000000000000000010111110011111010011 10010011000101011111 010100001111000 000000000000000010111110011111101000 10010011000101011111 010011010000111 00000000111111100100 10010011000001011111 000010010100111 00000000111111100110 10010011000001011111
The first thing I wanted to figure out, was how the checksum should be calculated, so I started by capturing and looking at thousands of frames to see if I could find a pattern.
Here are a few frame pairs where just the lowest bit in the payload are different:
111010001010001 00000000110010001010 10010011000001011111 110010101000001 00000000110010001011 10010011000001011111 110000011001000 00000000110100010010 10010011000001011111 111000111011000 00000000110100010011 10010011000001011111 010010010001000 00000000110100010110 10010011000001011111 011010110011000 00000000110100010111 10010011000001011111
If you look closely at the checksum, you might notice that the xor of the two checksums in each pair is the same value: 001000100010000.
More frames with just one flipped bit in the payload:
111111101010010 00000000111110111001 10010011000001011111 ^ 101110101110010 00000000111110111011 10010011000001011111 = 010001000100000 110100001000101 00000000111111001000 10010011000001011111 ^ 100101001100101 00000000111111001010 10010011000001011111 = 010001000100000
100010000111000 00000001000000000000 10010011000001011111 ^ 000000001111000 00000001000000000100 10010011000001011111 = 100010001000000 000110110111001 00000001000000011000 10010011000001011111 ^ 100100111111001 00000001000000011100 10010011000001011111 = 100010001000000
After some time I managed to find these patterns:
111110000000001 - payload bit 12 011011010000000 - payload bit 11 001101101000000 - payload bit 10 110110100100000 - payload bit 9 001011000010000 - payload bit 8 100101100001000 - payload bit 7 100010100000100 - payload bit 6 000001000000010 - payload bit 5 100000100000001 - payload bit 4 000100010000000 - payload bit 3 100010001000000 - payload bit 2 010001000100000 - payload bit 1 001000100010000 - payload bit 0 110100000001000 - header bit n 111010000000100 - header bit n-1 011101000000010 - header bit n-2
To me, it looked very much like these xor patterns were generated by a "many-to-many" linear feedback shift register (lfsr), but no matter now much I tried, I could not figure it out.
So to crack the lsfr, I wrote a c++ program that used a genetic algorithm to find the lsfr tabs:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
#include <algorithm>
typedef unsigned int uint;
uint patterns[] = {
0b111110000000001, 0b011011010000000, 0b001101101000000, 0b110110100100000,
0b001011000010000, 0b100101100001000, 0b100010100000100, 0b000001000000010,
0b100000100000001, 0b000100010000000, 0b100010001000000, 0b010001000100000,
0b001000100010000, 0b110100000001000, 0b111010000000100, 0b011101000000010,
};
static const uint pattern_cnt = (sizeof(patterns)/sizeof(patterns[0]));
uint calcErrors(uint mask[15])
{
unsigned errors = 0;
for(unsigned i=0; i<pattern_cnt-1; i++)
{
unsigned ipattern = patterns[i];
unsigned opattern = patterns[i+1];
unsigned pattern = ipattern;
pattern = (pattern>>1);
for(int biti=0; biti<15; biti++)
{
if(ipattern&(1<<biti))
pattern ^= mask[biti];
}
errors += __builtin_popcount(pattern^opattern);
}
return errors;
}
struct genome
{
uint mask[15];
uint errors;
bool operator<(const genome &other) const { return errors<other.errors; }
};
static const uint POP_SIZE = 10000;
int main()
{
srand(time(NULL));
static genome population[POP_SIZE];
for(uint i=0; i<POP_SIZE; i++)
for(uint j=0; j<15; j++)
population[i].mask[j] = rand()&0x7fff;
for(uint generation=0; generation<1000000; generation++)
{
for(uint i=0; i<POP_SIZE; i++)
population[i].errors = calcErrors(population[i].mask);
// sort genomes, so that the most fit will be in the beginning of the array
std::sort(population, population+POP_SIZE);
if(population[0].errors == 0)
{
for(uint j=0; j<15; j++) printf("%04x ", population[0].mask[j]);
printf("\n");
break;
}
static genome newpopulation[POP_SIZE];
for(uint i=0; i<POP_SIZE; i++)
{
uint parent1 = pow(double(rand())/RAND_MAX, 3.0)*POP_SIZE;
uint parent2 = pow(double(rand())/RAND_MAX, 3.0)*POP_SIZE;
// produce offspring:
memcpy(&newpopulation[i], &population[parent1], sizeof(newpopulation[i]));
for(uint j=0; j<15; j++)
if(rand()<RAND_MAX/2)
newpopulation[i].mask[j] = population[parent2].mask[j];
// mutate offspring
if(rand()<RAND_MAX/10)
{
uint bit = rand()%15;
uint mask = rand();
for(int j=0; j<15; j++)
if((mask>>j)&1)
newpopulation[i].mask[j] ^= 1<<(bit%15);
}
}
memcpy(population, newpopulation, sizeof(population));
}
return 0;
}
It only took the program around 15 seconds to find the correct "taps": 0x4880 0x0000 0x0000 0x0000 0x0000 0x0000 0x0000 0x0000 0x2080 0x4000 0x4000 0x4000 0x4000 0x4000 0x4000.
To verify that I now had enough information to verify the checksum of captured frames, I wrote another small python script that calculates the checksum for a frame, and checks itagains the checksum in the captured frame:
checksum_taps = (0x4880, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000,
0x2080, 0x4000, 0x4000, 0x4000, 0x4000, 0x4000, 0x4000)
def next_mask(mask):
next_mask = mask>>1
for i in range(15):
if mask&(1<<i):
next_mask ^= checksum_taps[i]
return next_mask
def verify(checksum, data, datalen):
mask = 0x0001
cchecksum = 0
for i in range(datalen-1, 7, -1):
mask = next_mask(mask)
if (data>>i)&1:
cchecksum ^= mask
assert checksum == cchecksum
# |checksum-----| |payload---------------------------||header----||preamb|
verify(0b010011111001011, 0b00000000000000001011111001111101001110010011000101011111, 36+20)
verify(0b010100001111000, 0b00000000000000001011111001111110100010010011000101011111, 36+20)
verify(0b010011010000111, 0b0000000011111110010010010011000001011111, 20+20)verify(0b000010010100111, 0b0000000011111110011010010011000001011111, 20+20
By trial and error, I also managed to find out that the preamble is 8 bits long, and not included in the checksum, so the packages now look like this:
checksum payload header preamble 010011111001011 000000000000000010111110011111010011 100100110001 01011111 010100001111000 000000000000000010111110011111101000 100100110001 01011111 010011010000111 00000000111111100100 100100110000 01011111 000010010100111 00000000111111100110 100100110000 01011111
Now that I can generate frames with correct checksums, I can start sending my own frames to the NG101 receiver and see how it reacts when the different bits are set. This will make it easier to discover what all the bits the the header and payload are used for.
But that will have to wait for another day :)
No comments:
Post a Comment