Hallo zusammen, ich möchte gerne einen ganzen Block von Daten in RAM meines µC mit einer CRC-Checksumme absichern. Dazu benutze ich die Hardware-CRC vom STM32, was auch ohne Probleme funktioniert. Da ich von CRC bisher keine wirkliche Ahnung habe und auch bisher nichts passendes dazu gefunden habe meine Frage: Wenn ich einen einzelnen Wert meines Datenblocks (32bit-Werte) ändere und die Checksumme anpassen will, muss ich dann die Summe über alle Werte neu berechnen, oder kann ich die CRC irgendwie anpassen wie es bei einer XOR-Checksumme möglich ist? Z.B. CRC vom alten Wert abziehen und CRC vom neuen addieren. Vielen Dank für eure Hilfe! Klaus
Naja, nicht unbedingt über alle - es reicht ab dem Wert, der geändert wurde. Da man aber diese Zwischenergebnisse meistens nicht speichert, dürfte es auf eine komplette Neuberechnung hinauslaufen. Schau Dir mal an, wie CRC-Summen üblicherweise berechnet werden (Schieberegister etc.) - dann wird schnell klar, dass es mit der "nachträglichen" Korrektur nichts wird.
Hallo, das ist ja gerade der "Trick" an CRC: dass bei der kleinsten Änderung etwas ganz anderes und unvorhersehbares rauskommt. Wenn man wüsste, wie sich CRC ändert, wenn man ein bit ändert, würde das das Knacken ungeheuer erleichtern. Gruss Reinhard
Reinhard Kern schrieb: > das ist ja gerade der "Trick" an CRC: dass bei der kleinsten Änderung > etwas ganz anderes und unvorhersehbares rauskommt. Wenn man wüsste, wie > sich CRC ändert, wenn man ein bit ändert, würde das das Knacken > ungeheuer erleichtern. Das widerlegt ja dann den Nutzwert einer CRC-Prüfsumme. Wenn man nicht wüsste was bei einer Veränderung eines Bits hinten raus kommt dann macht eine Prüfung einer CRC Prüfsumme am Ende der Datenübertragung keinerlei Sinn. Man kann sehr wohl bei einer CRC zB. gekippte Bits wieder reparieren, also den Originalzustand vor diesem Fehler restaurieren. Viele der ECC- Fehlerkorrekturcodes arbeiten mit der exakt gleichen Mathematik. Bei LFSRs mit maximaler Periode, sind mathm. ähnlich zu CRCs, kann man sehr wohl bei bekannten Startwerten und Polynomen mit Hilfe mathm. Verfahren eine jede Bitposition berechnen und den zu erwartenden Bitzustand voraus- und nachträglich berechnen. Das ist einer der Gründe warum man CRC/LFSRs und ähnliches eben nicht als sicher in der Kryptographie benutzen kann, weil sie vorhersagbar, reproduzierbar sind. Gruß hagen
Reinhard Kern schrieb: > Wenn man wüsste, wie > sich CRC ändert, wenn man ein bit ändert, würde das das Knacken > ungeheuer erleichtern. Was du meinst, ist ein secure hash. Bei dem möchte man, dass sich nicht auf einfache Art herausfinden lässt, welches mögliche andere Dokument den gleichen Hash erzeugt. Eine CRC ist viel kürzer. Ihr wesentliches Ziel ist es, Änderungen am Dokument, die unbeabsichtigt auftraten, erkennen zu können.
Jörg Wunsch schrieb: > Reinhard Kern schrieb: >> Wenn man wüsste, wie >> sich CRC ändert, wenn man ein bit ändert, würde das das Knacken >> ungeheuer erleichtern. > > Was du meinst, ist ein secure hash. Bei dem möchte man, dass sich > nicht auf einfache Art herausfinden lässt, welches mögliche andere > Dokument den gleichen Hash erzeugt. Naja auch dies ist nicht präzise genug formuliert. Man möchte einerseits das der "Wissende" sehr wohl in der Lage ist jede Berechnung reproduzieren zu können und das der "Unwissende" dazu mit einem vorher berechnenbarem Aufwand nicht in der Lage ist das gleiche wie der "Wissende" reproduzieren zu können. Insofern sind auch secure Hash Funktionen mathem. reproduzierbar und deterministisch berechenbar, aber man benötigt dazu alles nötige Wissen, wie Startwerte, verwendeter Algorithmus usw.
CRC ist linear: CRC(X exor Y) = CRC(X) exor CRC(Y) also ja, geht!
Tiramisu schrieb: > also ja, geht! Und wie? Konkret. Mit deiner Gleichung muss er trotzdem 2 mal einen CRC eines kompletten Blocks rechnen.
Hagen Re schrieb: > Das widerlegt ja dann den Nutzwert einer CRC-Prüfsumme. Wenn man nicht > wüsste was bei einer Veränderung eines Bits hinten raus kommt dann macht > eine Prüfung einer CRC Prüfsumme am Ende der Datenübertragung keinerlei > Sinn. Natürlich, aber das war nicht die Frage - die drehte sich darum, ob es einen verkürzten Weg gibt, ohne die CRC-Berechnung neu durchzuführen. Etwa in der Art wie bei einer einfachen Prüfsumme: irgendein Byte +1 -> Prüfsumme +1. So wie ich das sehe ist das CRC absichtlich nicht so, und das ist der eigentliche Grund, CRC zu verwenden und eben nicht die einfache Summe - die Hammingdistanz von CRCa und CRCb ist grösser als die der Strings a und b. Von mathematischen Feinheiten mal abgesehen: wer der Meinung ist, ich habe unrecht und es gibt eine solche Korrektur, die einfacher ist als CRC neu zu bilden, soll bitte angeben wie das geht. Gruss Reinhard
>Mit deiner Gleichung muss er trotzdem 2 mal einen CRC eines kompletten >Blocks rechnen. Nein, einmal, X und CRC(X) hat er ja schon! Vielleicht einmal statisch: Wenn X die urspruengliche Nachricht ist und immer der gleiche Wert (an genau dieser Stelle) in einen neuen Wert (X exor Y) geaendert wird, berechnet man einmal CRC(Y) an aendert den CRC von X exor Y analog der Rechenvorschrift. Das muss ich dann einmal (Compiletime) berechnen. Wenn nun jedes Mal eine neue Wertaenderung gemacht werden muss: Wenn der Startwert des CRC 000...0000 ist hat man bis zur Aenderungsstelle keinen Aufwand. (Mal am Beispiel nachrechnen!) Es wird also auch da einfacher. Die urspruengliche Frage war: >oder kann ich die CRC irgendwie anpassen wie es bei >einer XOR-Checksumme möglich ist Ja, die CRC kann ich aufgrund der Linearitaet anpassen. Ja, es ist mehr Aufwand wie eine kleine Addition/Subtraktion, schlimmstenfalls ist es der gleiche Aufwand wie eine Neuberechnung, aber um das genau zu beantworten fehlen im Ursprungspost die Details, wie: - welche CRC - Startwert - Nachrichtenformat - was soll wo in der Nachricht geaendert werden
Reinhard Kern schrieb: > Von mathematischen Feinheiten mal abgesehen: wer der Meinung ist, ich > habe unrecht und es gibt eine solche Korrektur, die einfacher ist als > CRC neu zu bilden, soll bitte angeben wie das geht. Da sind wir uns völlig einig. Deine Ausdrucksweise oben war nur etwas unglücklich, da sie so klang, als wäre das Ergebnis der CRC bei einer Änderung eines Bits prinzipiell nicht bestimmbar. Es ist natürlich bestimmbar, aber eben nur auf dem Weg einer Neuberechnung.
Reinhard Kern schrieb: > und es gibt eine solche Korrektur, die einfacher ist als > CRC neu zu bilden, Genau das ist der springende Punkt, der TO wollte die einfache Neuberechnung des CRCs vermeiden und suchte was NOCH einfacheres um den geänderten CRC zu berechnen. Hagen Re schrieb: > Bei > LFSRs mit maximaler Periode, sind mathm. ähnlich zu CRCs, kann man sehr > wohl bei bekannten Startwerten und Polynomen mit Hilfe mathm. Verfahren > eine jede Bitposition berechnen und den zu erwartenden Bitzustand > voraus- und nachträglich berechnen. Mag ja sein, aber ist das Verfahren einfacher als einfach den CRC neu zu berechnen?
Udo Schmitt schrieb: > Hagen Re schrieb: >> Bei >> LFSRs mit maximaler Periode, sind mathm. ähnlich zu CRCs, kann man sehr >> wohl bei bekannten Startwerten und Polynomen mit Hilfe mathm. Verfahren >> eine jede Bitposition berechnen und den zu erwartenden Bitzustand >> voraus- und nachträglich berechnen. > > Mag ja sein, aber ist das Verfahren einfacher als einfach den CRC neu zu > berechnen? Ja, wenn einfacher=kleineres Big O bedeutet, es gibt aber einen Breakeven Point ab wann sich welcher Algorithmus lohnt. Bei den LFSRs kenn ich mich aus und habe diesen Algo auch schon programmiert, allerdings ging es dabei um Shiftregister >= 2^128 Periode, also mehr als 128 Bits Breite und dann lohnt sich der Aufwand. Die Mathematik dahinter sollte aber bei CRCs identisch sein da beides mal in GF(2) mit nicht reduzierbaren Polynomringen gearbeitet wird. In jedem Fall benötigt man die Eingangsdaten und einen Startwert passend zu diesen Eingangsdaten. Dann kann man, statt die CRC komplett neu zu berechnen, erstmal die Eingangsdaten in GF(2) schneller reduzieren und über den verbleibenden Rest (Rest der modularen Multiplikation in GF(2)) die CRC berechnen.
Jörg Wunsch schrieb: > Deine Ausdrucksweise oben war nur > etwas unglücklich "unvorhersehbar" war unscharf bis falsch, es hätte zumindest heissen müssen "unvorhersehbar anders": man kann nicht aus der Änderung eines bytes auf die daraus folgende Änderung der CRC-Prüfsumme schliessen. Hagen Re schrieb: > Ja, wenn einfacher=kleineres Big O bedeutet, es gibt aber einen > Breakeven Point ab wann sich welcher Algorithmus lohnt. Da du dich damit beschäftigt hast, glaube ich dir das, was ich nicht glaube, ist dass das dem TO bei seiner Aufgabenstellung weiterhilft. Wenn du ihm deinen Algorithmus erläuterst, wird er reumütig auf seine normale CRC-Berechnung zurückgreifen, zumal er die ja schon hat. Gruss Reinhard
Reinhard Kern schrieb: >> Ja, wenn einfacher=kleineres Big O bedeutet, es gibt aber einen >> Breakeven Point ab wann sich welcher Algorithmus lohnt. > > Da du dich damit beschäftigt hast, glaube ich dir das, was ich nicht > glaube, ist dass das dem TO bei seiner Aufgabenstellung weiterhilft. > Wenn du ihm deinen Algorithmus erläuterst, wird er reumütig auf seine > normale CRC-Berechnung zurückgreifen, zumal er die ja schon hat. Da könntest du durchaus Recht haben, besonders weil ich keinen fertigen auf sein Problem zugeschnittenen Algo. aus dem Stegreif liefern kann. Damals mit den LFRSs habe ich mit super großen Integern gearbeitet die selber wiederum eine große Bibliothek waren. Die Mathematik sollte denoch identisch sein. Letzendlich sind die Ausgangsbedingungen die selben: man benötigt alle vorherigen Werte, eventuell Zwischenergebnisse der CRC, um rechnen zu können. Der Unterschied ist nur das die Komplexität der Verfahren sich unterscheidet, es gibt also schnellere mathm. Algorithmen zur Berechnung der gewünschten Werte als die komplette CRC erneut zu berechnen.
Das ist durchaus moeglich und ich habe dafuer auch hardware entwickelt, die das in Echtzeit macht. Wenn Du das n-te bit (von hinten) kippst, dann musst Du zur Pruefsumme (x^n) mod p drauf-XORen, um die CRC zu korrigieren. Dies laesst sich recht schnell berechnen, wenn man x^(2^i) mod p vorberechnet (in einer Tabelle), dann muss man nur die Werte, fuer die n ein Bit mit '1' hat in der Tabelle nachsehen, und dann die Werte aus der Tabelle (mod-p) miteinander multiplizieren. Hier ist ein kurzes paper: "Fast and Flexible CRC calculation" Electronic Letters, January 2004 Vol 40 No. 1, p. 10-11 Wenn Du das kommerziell brauchst, muesstet Ihr zahlen, wir haben da ein Patent, wieviel, weiss ich nicht. Andreas
Also - wie schon gesagt -, CRC ist linear. Ändert sich z.B. ein Bit, so muß man nur den CRC von dieser Bitstelle berechnen (alle anderen Bits sind null), und dann diesen CRC auf den alten CRC mod 2 aufaddieren. Schon hat man einen gültigen CRC von dem Ursprungsmuster mit dem geänderten Bit. Harald
>x^(2^i) mod p >vorberechnet (in einer Tabelle), dann muss man nur die >Werte, fuer die n ein Bit mit '1' hat in der Tabelle nachsehen, >und dann die Werte aus der Tabelle (mod-p) miteinander multiplizieren. Hmm... addieren! (im GF(2)-Koerper ist normalerweise die Addition das EXOR :-) >Wenn Du das kommerziell brauchst, muesstet Ihr zahlen, wir haben da ein >Patent, wieviel, weiss ich nicht. Und die Patent-Nr waere? Das Patent gilt fuer die Berechnung der CRC-Deltas in Hardware, SW sollte/duerfte nicht betroffen sein? Anderer Vorschlag: Wenn man immer genau eine Stelle hat (bspw. in einem "vollen 1500er" Ethernet-Paket, welches IP beeinhaltet, die TTL (time-to-live) reduziert), koennte es sich lohnen, die Aenderungsfunktion (im Bsp. bzgl. der TTL Stelle) algebraisch partiell zu evaluieren.
> Hmm... addieren! (im GF(2)-Koerper ist normalerweise die Addition das > EXOR :-) Wenn Du x^n (mod p) berechnest, indem Du Werte fuer x^(2^i) verwendest, dann wird n als Summe dargestellt, aber die Potenz von x ist dann ein Produkt. Wenn n zum Beispiel 312=256+32+16+8 ist, dann ist x^312 = x^256 * x^32 * x^16 * x^8 (mod p). Sinnvollerweise macht man das byte/wort/ ... weise. > Und die Patent-Nr waere? US 2005/0010630 A1 Koennte sein, dass es auch noch eines am Europaeischen Patentamt gibt. > Das Patent gilt fuer die Berechnung der > CRC-Deltas in Hardware, SW sollte/duerfte nicht betroffen sein? Ich weiss nicht genau, es heisst "Method and Apparatus ..." > algebraisch partiell zu evaluieren. Wie meinst Du das? Was ich mir vorstellen kann, ist, dass man je nach Anwendung andere Faktoren als Zweierpotenzen nimmt, wenn man genauer weiss, welche Faktoren besonders oft vorkommen. Andreas
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.