CRC-16 lub podobne

kwia-Tec - 01-12-2006 00:51
CRC-16 lub podobne
Witam wszystkich grupowiczow.
Mam pewien problem. Komputer porozumiewa sie z maszyna za pomoca zlacza rs.
Komenda sklada sie z paczki 12 bajtow, z czego 2 ostatnie sa dla mnie
zupelnie nie zrozumiale. prawdopodobnie jest to CRC-16 lubo cos podobnego.
Chcialbym sie dowiadziec jak to wyliczyc, poniewaz moje zadanie polega na
zasymulowaniu oryginalnego programu. Jezeli zmieni sie jakikolwiek bit w
sygnale - maszyna nie odpowiada.
Ponizej podaje kilka przykladow takiego sygnalu.

00 01 10 00 00 00 00 00 00 00 A1 65
00 01 11 00 00 00 00 00 00 00 C4 55
00 01 12 00 00 00 00 00 00 00 6B 05
00 01 12 01 00 00 00 00 00 00 EB 65
00 01 12 02 00 00 00 00 00 00 0E C5
00 01 12 0A 00 00 00 00 00 00 FF B8
00 01 12 00 00 01 00 00 00 00 4B AE
00 01 12 00 00 01 00 00 00 00 4B AE
00 01 12 00 00 02 00 00 00 00 2B 78
00 01 12 00 00 0A 00 00 00 00 4E A7
00 01 12 0A 00 0A 00 00 00 00 DA 1A
00 01 12 B4 00 F0 00 00 00 00 53 18

Prosze o pomoc w jaki sposob mozna dojsc do tego jak wyliczyc ostatnie 2
bajty.
W ww przykladach moge zmieniac 4, 5, 6 i 7 bajt sygnalu. Moge jeszcze
podac inne przyklady, w ktorych wartosci sa juz z gory narzucone przez
wymogi maszyny.

00 01 22 14 BF 04 00 00 00 00 D4 8D
00 01 67 14 BF 04 00 00 00 00 89 A2
01 00 00 22 00 00 00 00 00 00 FF 13
01 00 71 22 92 00 00 00 00 04 41 0F
00 01 21 29 5F 02 00 00 00 00 D6 5F
00 01 67 29 5F 02 00 00 00 00 24 20
01 00 00 21 00 00 00 00 00 00 1A B3
01 00 02 21 00 BE 04 00 00 00 65 C4
00 01 22 29 5F 02 00 00 00 00 79 0F
00 01 67 29 5F 02 00 00 00 00 24 20
01 00 00 22 00 00 00 00 00 00 FF 13
01 00 71 22 92 00 00 00 00 04 41 0F
00 01 21 29 77 00 00 00 00 00 DB 4D
00 01 67 29 77 00 00 00 00 00 29 32
01 00 00 21 00 00 00 00 00 00 1A B3
01 00 02 21 00 EE 00 00 00 00 68 8C

Z gory dziekuja za pomoc

pozdrawiam
kwia-Tec

projekt - 01-12-2006 00:51

> Mam pewien problem. Komputer porozumiewa sie z maszyna za pomoca zlacza
> rs.
> Komenda sklada sie z paczki 12 bajtow, z czego 2 ostatnie sa dla mnie
> zupelnie nie zrozumiale. prawdopodobnie jest to CRC-16 lubo cos podobnego.
> Chcialbym sie dowiadziec jak to wyliczyc, poniewaz moje zadanie polega na
> zasymulowaniu oryginalnego programu. Jezeli zmieni sie jakikolwiek bit w
> sygnale - maszyna nie odpowiada.

Prawdopodobnie nie jest to crc16 lecz jakia suma kontrolna obliczana innym
sposobem, albo tez przy liczeniu sumy nie sa uwzgledniane wszystkie bajty
ciagu.
Jesli jest to zabezpieczenie (a rozumiem, ze jest) to bedzie ci ciezko
zgadnac jakiego algorytmu uzyl tworca urzadzenia. Najlatwiej w takiej
sytuacji uzyc metody bruteforce i dla wszystkich interesujacych cie ciagow
obliczyc sumy (sprawdzic kombinacje z zakresu 0000-FFFF, ktoras musi
pasowac) i zapisac je w tablicy.
Jesli chcesz poczytac o crc16 to to sa linki (google twoim przyjacielem):
http://www.tkdami.net/~roman72/pdf/dtr/dtr_sum_ctrl.pdf
http://www.maxim-ic.com/an27
a tu sa programy do liczenia crc16 (miedzy innymi):
http://www.lammertbies.nl/comm/info/...lculation.html
http://www.ustr.net/files/crc16.exe
Pozdrowka.
/PM

kwia-Tec - 01-12-2006 07:52

Użytkownik projekt <xxx@xxx.pl> w wiadomości do grup dyskusyjnych
napisał:ekng84$sek$1@nemesis.news.tpi.pl...

> Jesli jest to zabezpieczenie (a rozumiem, ze jest) to bedzie ci ciezko
> zgadnac jakiego algorytmu uzyl tworca urzadzenia.

Tez tak na poczatku myslalem, ale stwierdzilem, ze po co ktos mialby wymyslc
nowy algorytm, skoro jest tyle gotowcow. Wydaje mi sie, je jest to tylko
zabezpieczenie transmisji, zeby maszsyna nie wykonala jakiegos glupstwa przy
bledzie transmisji.

> Najlatwiej w takiej
> sytuacji uzyc metody bruteforce i dla wszystkich interesujacych cie ciagow
> obliczyc sumy (sprawdzic kombinacje z zakresu 0000-FFFF, ktoras musi
> pasowac) i zapisac je w tablicy.

Wg mnie to chyba nie bedzie suma, poniewaz przy minimalnyej zmianie jednego
z bajtow, wynik zmienia sie diametralnie.
Ale, czy noglbys jeszcze raz lopatologicznie wyjasnic sumy czego mam
obliczyc? Bo chyba uzyles jakiegos skrotu myslowegi i nie zaskoczylem :)
Bede probowal wszystkich mozliwosci.

> Jesli chcesz poczytac o crc16 to to sa linki (google twoim przyjacielem):
> http://www.tkdami.net/~roman72/pdf/dtr/dtr_sum_ctrl.pdf
> http://www.maxim-ic.com/an27
> a tu sa programy do liczenia crc16 (miedzy innymi):
> http://www.lammertbies.nl/comm/info/...lculation.html
> http://www.ustr.net/files/crc16.exe

Na temat crc juz troszke czytalem, ale wlasnie nie pasowaly mi wyniki, wiec
pomyslalem, ze zapytam fachowcow co to moze byc.

pozdrawiam
kwia-Tec

kwia-Tec - 01-12-2006 07:52

Jezeli ktos mam jakiekolwiek pomysly, jak to rozwiklac , bede wdzieczny za
pomoc :)

Z gory dziekuje i pozdrawiam
kwia-Tec

J.F. - 01-12-2006 10:45

On Fri, 1 Dec 2006 06:59:53 +0100, kwia-Tec wrote:
>Jezeli ktos mam jakiekolwiek pomysly, jak to rozwiklac , bede wdzieczny za
>pomoc :)

Zaczales dobrze - trzeba analizowac dane rozniace sie jednym bitem.

Mnie to wyglada faktycznie na CRC. Przydaloby sie zaczac
od samych zer i potem dodawac skrajne jedynki - na poczatek namierzyc
od ktorej strony bajtu bity sa wprowadzane i jak wyprowadzane -
bo na razie to mamy za duzo mozliwosci.

I zobacz jeszcze czy twoja funkcja jest xorowalna, tzn

f(03) = f(00) xor f(01) xor f(02)

I podobnie dla kombinacji bitow na innych pozycjach

Moze wystarczy ci tablica sum kontrolnych dla poszczegolnych bitow
danych, potem tylko xorujesz odpowiednie.
Bo namierzenie wielomianiu CRC i wartosci poczatkowej moze byc
klopotliwe.

J.

neuron - 01-12-2006 12:45

>
> Tez tak na poczatku myslalem, ale stwierdzilem, ze po co ktos mialby
> wymyslc
> nowy algorytm, skoro jest tyle gotowcow. Wydaje mi sie, je jest to tylko
> zabezpieczenie transmisji, zeby maszsyna nie wykonala jakiegos glupstwa
> przy
> bledzie transmisji.
>
A od drugiej strony ? Z czym sie laczysz ? Wiem z maszyną, ale chyba nie z
pompa hydrauliczna tylko ze sterownikiem. Jakim?
A co do algorytmu transmisji - tu tez moze byc roznie - crc 8 i crc 16
oieraja sie na tblicach danych co w czasie kiedy procesor mial do dyspozycji
2k na program mialo znaczenie - choc wtedy po co 2 bajty sumy. Moze tez byc
tak jak w moim golemie - suma kontrolna ma dwie funkcje - kontrole
poprawnosci i zabezpieczenie programu - koncentrator jest jednoczesnie
kluczem dla programu. choc ja mam jeszcze szyfrowanie transmisji i sygnatury
wogole nie sciagnisz.
Mozliwy jest jeszcze jeden trik - moze to byc suma crc8 lub suma xor -
pierwszy bajt i powtorzenie tego bajtu dla wtornej kontroli
np [suma], [ nx xor suma] albo [suma], [(not suma) xor nx ] itd itp
Sprawdz tez sume crc16 dla zakresu
00 01 [12 00 00 00 00 00 00 00] 6B 05 00 01 [12 00 00 00 00 00 00] 00 6B
05
bo moze byc tak ze ktos umyslil sobie ze ma ramke [start] [dane] [stop]
[suma] a suma jest tylko z danych

pozdrawiam wojtek
www.neuron.com.pl
CMMS Maszyna
Golem OEE
Produkt - Baza Wiedzy

Pawel \O'Pajak\ - 02-12-2006 00:45

Powitanko,

> Wg mnie to chyba nie bedzie suma, poniewaz przy minimalnyej zmianie jednego
> z bajtow, wynik zmienia sie diametralnie.

I tak powinno byc

> Na temat crc juz troszke czytalem, ale wlasnie nie pasowaly mi wyniki, wiec
> pomyslalem, ze zapytam fachowcow co to moze byc.

Dorzuce jeszcze pare sznurkow:
http://www.lammertbies.nl/comm/info/...510&method=hex
http://www.zorc.breitbandkatze.de/crc.html
Ktorys z tych 2 liczyl dobrze crc16. Jak kiedys rozpracowywalem temat,
to tych crc jest od groma, nawet AFAIR crc16 sa 2 rodzaje i inaczej sie
je liczy. Pozostaje podstawiac do kalkulatorow i sprawdzac.

Pozdroofka,
Pawel Chorzempa
--
"-Tato, po czym poznać małą szkodliwość społeczną?
-Po wielkiej szkodzie prywatnej" (kopyrajt: S. Mrożek)
******* >>> !!! UWAGA: ODPOWIADAM TYLKO NA MAILE ->:
> pavel(ten_smieszny_znaczek)klub.chip.pl <<<<*******

J.F. - 02-12-2006 01:46

On Fri, 01 Dec 2006 23:50:08 +0100, Pawel "O'Pajak" wrote:
>Powitanko,
>> Wg mnie to chyba nie bedzie suma, poniewaz przy minimalnyej zmianie jednego
>> z bajtow, wynik zmienia sie diametralnie.
>
>I tak powinno byc

A w dodatku nie "diametralnie" tylko o kilka bitow - i tak ma byc :-)

>Dorzuce jeszcze pare sznurkow:
>http://www.lammertbies.nl/comm/info/...510&method=hex
>http://www.zorc.breitbandkatze.de/crc.html
>Ktorys z tych 2 liczyl dobrze crc16. Jak kiedys rozpracowywalem temat,
>to tych crc jest od groma, nawet AFAIR crc16 sa 2 rodzaje i inaczej sie
>je liczy. Pozostaje podstawiac do kalkulatorow i sprawdzac.

http://en.wikipedia.org/wiki/Cyclic_redundancy_check

Przy czym cala masa innych wielomianow tez moze byc uzyta.

J.

lwh - 02-12-2006 15:46

Użytkownik "kwia-Tec" <Krzys@spam.wsieci.net> napisał w wiadomości
news:ekog81$m83$1@node4.news.atman.pl...
> > Tez tak na poczatku myslalem, ale stwierdzilem, ze po co ktos mialby
> > wymyslc
> nowy algorytm, skoro jest tyle gotowcow.

Po to , by utrudnić życie "oglądaczom" ?

kwia-Tec - 02-12-2006 21:45

Chyba dam sobie spokoj... zapisze sobie wszystkie potrzebne komendy do
tablicy i juz. W sumie to nie jest ich tak duzo... tylko 384 :)

Dzieki za checi i zainteresowanie.

pozdrawiam
kwia-Tec

Arkadiusz Kaczmarek - 03-12-2006 00:45

kwia-Tec wrote:
> Witam wszystkich grupowiczow.
> Mam pewien problem. Komputer porozumiewa sie z maszyna za pomoca
> zlacza rs. Komenda sklada sie z paczki 12 bajtow, z czego 2 ostatnie
> sa dla mnie zupelnie nie zrozumiale. prawdopodobnie jest to CRC-16
> lubo cos podobnego. Chcialbym sie dowiadziec jak to wyliczyc,
> poniewaz moje zadanie polega na zasymulowaniu oryginalnego programu.
> Jezeli zmieni sie jakikolwiek bit w sygnale - maszyna nie odpowiada.
> Ponizej podaje kilka przykladow takiego sygnalu.

Nie podałeś najważniejszego - jaki procek odbiera te dane :)
Większość możliwości można wykluczyć na tej podstawie.
Wiadomo przecież, że nikt nie zaimplementuje jakiegoś "chorego" algorytmu w
20C51.

J.F. - 03-12-2006 10:46

On Sat, 2 Dec 2006 23:15:30 +0100, Arkadiusz Kaczmarek wrote:
>Nie podałeś najważniejszego - jaki procek odbiera te dane :)
>Większość możliwości można wykluczyć na tej podstawie.
>Wiadomo przecież, że nikt nie zaimplementuje jakiegoś "chorego" algorytmu w
>20C51.

Akurat crc na '51 bardzo prosto sie robi. Moze nawet prosciej niz na
innych - choc dluzej.

J.

projekt - 03-12-2006 14:45

> Chyba dam sobie spokoj... zapisze sobie wszystkie potrzebne komendy do
> tablicy i juz. W sumie to nie jest ich tak duzo... tylko 384 :)

O tym wlasnie mowilem w pierwszym poscie
/PM

projekt - 03-12-2006 15:46

> Ale, czy noglbys jeszcze raz lopatologicznie wyjasnic sumy czego mam
> obliczyc? Bo chyba uzyles jakiegos skrotu myslowegi i nie zaskoczylem :)
> Bede probowal wszystkich mozliwosci.

Powiedzmy, ze wysylasz do urzadzenia taki ciag:
00 01 10 00 00 00 00 00 00 00 [XX] [XX]
ale nie wiesz jaka wartosc powinny miec ostatnie 2 bajty, czyli [XX][XX]
W takim razie podstawiasz za [XX][XX] wszyskie kombinacje od [00][00] do
[FF][FF] (szesnastkowo)
Ciag zakonczony ktoras z tych kombinacji zostanie zaakceptowany i ta
koncowke zapisujesz sobie w tablicy. Sumy w tablicy trzeba oczywiscie jakos
zaindeksowac. Aby tablica byla jak najmniejsza, mozesz robic zwykle crc8 lub
crc16 dla kazdego ciagu ktory sprawdzasz, w tym wypadku dla ciagu 00 01 10
00 00 00 00 00 00 00 obliczasz crc16 (np) i to bedzie indeks. Do tego
indeksu bedzie przypisana wlasciwa koncowka [XX][XX] ktora wczesniej
"znalazles". Tablice wystarczy posortowac wedlug indeksow (np od
najmniejszego do najwiekszego).
Teraz jesli wysylasz do swojego urzadzenia jakis ciag i nie znasz koncowki,
to robisz po kolei:
1.obliczasz dla niego zwykle crc16
2.dla tego obliczonego crc16 szukasz w tablicy odpowiedniej koncowki.
3.uzupelniony ciag mozesz wyslac do urzadzenia.
Pozdrawiam.
/PM

Gregor - 03-12-2006 15:46

"kwia-Tec" napisal:
>
>Tez tak na poczatku myslalem, ale stwierdzilem, ze po co ktos mialby wymyslc
>nowy algorytm, skoro jest tyle gotowcow. Wydaje mi sie, je jest to tylko
>zabezpieczenie transmisji, zeby maszsyna nie wykonala jakiegos glupstwa przy
>bledzie transmisji.

Np. dlatego że nie potrafi zaimplementować CRC albo chce utrudnić życie komuś
takiemu jak ty :)

>Na temat crc juz troszke czytalem, ale wlasnie nie pasowaly mi wyniki, wiec
>pomyslalem, ze zapytam fachowcow co to moze byc.

Zawsze możliwe że autor oryginału walnął się w implementacji - np. mnie się
coś takiego przytrafiło - liczyłem crc32 z niewłaściwym endianem, wszystko
było w porządku dopóki maszynki gadały tylko z "rodziną", aż któregoś dnia
dołączono do systemu urządzenie innej firmy... ale był obciach.
GRG

Arkadiusz Kaczmarek - 03-12-2006 23:45

J.F. wrote:
> On Sat, 2 Dec 2006 23:15:30 +0100, Arkadiusz Kaczmarek wrote:
>> Nie podałeś najważniejszego - jaki procek odbiera te dane :)
>> Większość możliwości można wykluczyć na tej podstawie.
>> Wiadomo przecież, że nikt nie zaimplementuje jakiegoś "chorego"
>> algorytmu w 20C51.
>
> Akurat crc na '51 bardzo prosto sie robi. Moze nawet prosciej niz na
> innych - choc dluzej.

crc OK. - Ale możemy wykluczyć :straszne algorytmy" wykorzystujące "ogromne
tablice"

Mi naprawdę pomagała (nie jeden raz) informacja odnośnie "procka " w
systemie docelowym :)

PS. Myślę,że max 2 dni i byłoby "rozwalone" (pod warunkiem, że jest dostęp
do odbiornika"