Technischer Beitrag
So berechnen Sie eine Prüfsumme
Prüfsummen verschiedener Art werden in Datenkommunikationsprotokollen häufig eingesetzt, damit der Empfänger einer Nachricht schnell und einfach feststellen kann, ob die Daten während der Übertragung möglicherweise verfälscht wurden. Wenn man alle Bytes einer Nachricht addiert und dabei (ohne Überlauf zu berücksichtigen) den Wert 96 erhält, hängt man diese Zahl vor dem Versenden an die Nachricht an. Der Empfänger kann dann die Summe der ersten N – 1 Bytes der Nachricht erneut berechnen und das Ergebnis mit dem letzten Byte vergleichen, um zu prüfen, ob es 96 ergibt. Ist dies der Fall, kann der Empfänger daraus schließen, dass die Nachricht während der Übertragung wahrscheinlich (zumindest mit hoher Wahrscheinlichkeit) nicht verändert wurde.
In der Praxis findet man eine Vielzahl von Prüfsummenverfahren. Drei der gängigsten sind die konventionelle Prüfsumme, LRC (Longitudinal Redundancy Check) und CRC (Cyclic Redundancy Check). Letzteres ist im eigentlichen Sinne keine Prüfsumme, sondern ein Beispiel für eine Einwegfunktion ( Hash ), die zur Familie der „linearen Kongruenzgeneratoren" gehört.
Wie bereits erwähnt, können diese Datenintegritätsverfahren lediglich angeben, ob Daten „wahrscheinlich verfälscht wurden". Kein Prüfsummenverfahren ist im allgemeinen Fall – bei Daten beliebiger Länge – hundertprozentig zuverlässig. Dennoch gibt es deutliche Unterschiede in der Güte der einzelnen Verfahren.
Sehen wir uns an, wie LRC, Prüfsumme und CRC mithilfe von JavaScript berechnet werden können.
Herkömmliche Berechnung einer Prüfsumme
Die konventionelle 8-Bit-Prüfsumme ist genau das, was der Name vermuten lässt: die Summe aller Bytewerte der Eingabe, wobei ein etwaiger Überlauf (durch Übertragsoperationen) verworfen wird. In JavaScript:
Die Eingabe dieser Funktion sollte ein Hex-String sein, der etwa so aussieht: „48656C6C6F20776F726C6421" (in diesem Fall die hexadezimale Darstellung des ASCII-Strings „Hello world!"). Verwendet man „48656C6C6F20776F726C6421" als Eingabe für die obige Funktion, lautet die Ausgabe „5d" – das ist der Hexadezimalwert der abschließenden 8-Bit-Summe.
Der Code ist sehr einfach aufgebaut. Zunächst (in Zeile 3) wird die hexadezimale Eingabe mithilfe des regulären Ausdrucks /../g in Zwei-Nibble-Blöcke aufgeteilt. Dieser Ausdruck bedeutet: Suche Teilstrings, die dem Muster „beliebiges Zeichen gefolgt von einem beliebigen Zeichen" entsprechen (das ist die Bedeutung der beiden Punkte), und zwar über die gesamte Zeichenkette hinweg (dafür steht das ‚g' für „global"). Das Ergebnis ist ein Array, s, aus zweistelligen Hex-Werten.
In Zeile 5 beginnen wir eine Schleife (mithilfe des Iterationskonstrukts forEach ), in der wir die Zeichenkettendarstellung eines zweistelligen Hex-Werts in eine tatsächliche Zahl umwandeln, mit der wir arbeiten können. In Zeile 7 erfolgt die eigentliche Summierung. Zu beachten ist, dass die Variable sum intern im Wesentlichen als 32-Bit-Integer behandelt wird, was bedeutet, dass unser Endergebnis deutlich größer als 255 sein kann. Nach Abschluss der Schleife muss die Summe auf einen 8-Bit-Wert begrenzt werden. Dies geschieht in Zeile 9 durch eine logische UND-Verknüpfung mit 255. Gleichzeitig konvertieren wir den Wert zurück in eine Hex-Darstellung, indem wir die Methode toString() mit dem Argument 16 aufrufen (da wir die Basis 16, also „Hexadezimal", für die endgültige Darstellung der Zahl verwenden möchten).
In den Zeilen 10 und 11 prüfen wir, ob der abschließende Hex-Wert tatsächlich zwei Stellen hat. Die Methode toString(16) in JavaScript gibt für Werte kleiner als 10 nur eine einstellige Darstellung zurück. In diesem Fall muss der Antwort eine führende '0' vorangestellt werden.
Wenn Sie den Code ausprobieren möchten, kopieren Sie ihn in Ihre JS-Konsole (in Chrome öffnen Sie diese mit Shift-Cmd-J), und fügen Sie am Ende (außerhalb der Funktion) folgende Zeile ein: CHECKSUM("48656C6C6F20776F726C6421"). Nach Drücken der Eingabetaste sollte die Konsole '5d' als Rückgabewert anzeigen.
So berechnen Sie eine Prüfsumme mit LRC
Die Längsprüfsumme (Longitudinal Redundancy Check, LRC) ist eine Variante der 8-Bit-Prüfsumme und unterscheidet sich lediglich darin, dass die „Summierung" mittels XOR statt durch numerische Addition erfolgt.
In Zeile 6 ist der XOR-Zuweisungsoperator (^=) zu sehen.
Da XOR nie zu einem Überlauf führt, muss das Endergebnis nicht per AND auf 8 Bit beschränkt werden. Es wird lediglich auf eine zweistellige Nibble-Länge geprüft und anschließend der Endwert zurückgegeben.
Wenn Sie den Code in der Konsole mit der weiter oben gezeigten Zeichenkette ausprobieren, sollten Sie als Ergebnis „21" erhalten.
Kritik an Prüfsumme und LRC
Weder Prüfsumme noch LRC können als zuverlässiger Schutz gegen Nachrichtenkorruption gelten. Betrachten wir beispielsweise die ursprüngliche Nachricht („48656C6C6F20776F726C6421"): Ändern wir die letzten zwei Bytes von 6421 auf 6520, bleiben sowohl LRC als auch Prüfsumme unverändert! (Es wurde lediglich ein Bit in einem vorgelagerten Byte eingeschaltet und dasselbe Bit in einem nachgelagerten Byte ausgeschaltet – zwei Änderungen, die sich bei der Prüfsummenberechnung gegenseitig aufheben.)
Ebenso bleibt LRC und Prüfsumme identisch, wenn die Nachricht byteweise umgekehrt wird (sodass sie mit 21 beginnt und mit 48 endet). Der Grund dafür ist, dass XOR und Addition kommutativ sind: A + B ergibt stets dasselbe wie B + A.
Darüber hinaus ist zu bedenken, dass ein 8-Bit-LRC oder eine 8-Bit-Prüfsumme nur 256 verschiedene Werte annehmen kann. Damit besteht eine Wahrscheinlichkeit von 1 zu 256, dass eine beliebige Nachricht denselben LRC (oder dieselbe Prüfsumme) ergibt wie eine zufällig gewählte andere Nachricht.
Prüfsummen- und LRC-Algorithmen lassen sich generell sehr leicht „austricksen" und sind daher für die Überprüfung der Nachrichtenintegrität nur bedingt geeignet.
Glücklicherweise gibt es für die Integritätsprüfung bessere Verfahren als LRC oder Prüfsumme – allerdings sind diese mit einem höheren Rechenaufwand verbunden.
Prüfsummenberechnung mit CRC
Wenn es wirklich auf Integritätsprüfung ankommt, ist in der Regel ein nicht-kommutativer Hash-Algorithmus erforderlich. Häufig handelt es sich dabei um einen kryptografischen Hash wie SHA-1 oder MD5 – diese sind jedoch rechenintensiv und in vielen Situationen als überdimensioniert zu betrachten.
Einen guten Kompromiss zwischen Rechenaufwand und Zuverlässigkeit bietet die Zyklische Redundanzprüfung (Cyclic Redundancy Check), die in verschiedenen Varianten verfügbar ist. Der nachfolgend beschriebene 16-Bit-CRC ist für kurze Nachrichten (bis ca. 4 Kilobyte) ausreichend und weit verbreitet.
CRC ist ein vielschichtiges Thema, das hier aus Platzgründen nicht umfassend behandelt werden kann. (Weiterführende Informationen finden sich über Google.) Aus praktischer Sicht lässt sich festhalten: Ein zwei Byte langer CRC-Wert reagiert sehr empfindlich auf zufällige Bitfehler in den Daten und liefert bei Mehrfachbitfehlern kaum falsch-positive Ergebnisse. Aufgrund dieser Eigenschaften sowie der einfachen Implementierbarkeit in Hard- und Software bei geringem Speicherbedarf und hoher Ausführungsgeschwindigkeit findet CRC in zahlreichen Datenkommunikationsumgebungen Anwendung – darunter Festplattentreiber (bei denen Lesefehler häufig per CRC erkannt werden), Modems sowie kleine elektronische Geräte (einschließlich aller ViVOpay-Kartenlesegeräte von ID TECH).
Der folgende JavaScript-Code zeigt, wie ein 16-Bit-CRC-Wert berechnet wird (ausgegeben als vier Nibbles in Hex-ASCII).
CRC implementiert einen Hash-Algorithmus, der sich vereinfacht wie folgt beschreiben lässt:
- Den Startwert für crc auf 0xFFFF setzen — Zeile 10
- Ein Byte Eingabedaten (als 8-Bit-Zahl) einlesen — Zeile 13
- Den vorhandenen crc -Wert um 8 Bit nach rechts verschieben — Zeile 14
- Den nach rechts verschobenen crc-Wert mit dem Eingabebyte XOR-verknüpfen — Zeile 14
- Den resultierenden Wert j (nur die unteren 8 Bit) als Tabellenindex verwenden, um ein „Substitutionsbyte" aus der Tabelle namens crcTable — Zeile 15
- Den crc -Wert um 8 Bit nach LINKS verschieben und mit dem „Substitutionsbyte" XOR-verknüpfen — Zeile 15
- Diese Operationen ab Zeile 13 mit dem nächsten Eingabebyte wiederholen
- Nachdem alle Eingabedaten auf diese Weise verarbeitet wurden, das Ergebnis mit null XOR-verknüpfen und die unteren 16 Bits des CRC beibehalten — Zeile 17
Wir verwenden eine kleine Hilfsfunktion, um die endgültige Zahl von einem Integer in einen Hex-String umzuwandeln:
Wenn Sie beide Funktionen (numToHex und CRC) in die JS-Konsole Ihres Browsers laden und CRC( "48656C6C6F20776F726C6421" )ausführen, sollten Sie für unsere Eingabedaten „Hello world!" einen CRC von 'BD22' erhalten.
Als Übung können Sie versuchen, ein Bit in der Eingabe zu kippen, um zu beobachten, wie sich dies auf die Ausgabe auswirkt. Wenn Sie beispielsweise unseren „Hello world!"-String als Eingabe verwenden und das letzte Byte der Daten von 21 auf 20 ändern, ändert sich der CRC auf 'AD03' – ein Wert, der keinerlei Bezug zu 'BD22' aufweist. Wenn Sie die letzten zwei Bytes auf '6520' ändern, ergibt sich ein CRC von '9E32'. (Zur Erinnerung: Dieselbe Änderung hatte keinen Einfluss auf LRC oder Prüfsumme.)
Betrachten Sie einen String, der zehn Null-Bytes (Nullzeichen) repräsentiert. Der LRC-Wert eines solchen Strings wäre null. Die Prüfsumme wäre offensichtlich ebenfalls null. Der CRC hingegen würde E139 ergeben.
Sie können sich leicht davon überzeugen, dass eine Umkehrung der Eingabe zu einem völlig anderen CRC führt als die Verwendung der Originaleingabe. (Was für LRC oder Prüfsummen nicht zutraf.) CRC ist nicht kommutativ, da die oberen 8 Bits des CRC mit dem Eingabebyte per XOR verknüpft werden, bevor alles nach links verschoben wird – ähnlich wie beim Cipher Block Chaining , mit dem Unterschied, dass die „Cipher-Block"-Größe hier 8 Bit beträgt.
Zu beachten ist: Obwohl CRC ein Einweg-Hash ist, handelt es sich nicht im eigentlichen Sinne um einen kryptografischen Hash – denn es ist vergleichsweise einfach, einen „Korrekturwert" zu berechnen, der, an die Daten angehängt, eine gezielte Veränderung der Daten so erscheinen lässt, als würde der gewünschte CRC erzeugt. (Dies gilt nicht für sogenannte kryptografische Hashes, bei denen es praktisch unmöglich ist, einen solchen „Korrekturfaktor" zu berechnen.) CRC eignet sich daher zur Erkennung unbeabsichtigter Datenverfälschungen.
Fazit
Es gibt keine Mangel an „Integritätsprüfungs"-Algorithmen zur Überwachung von Datenpaketen auf Fehler. In manchen Fällen genügt eine einfache Prüfsumme oder ein LRC. Doch bei größeren Datenmengen und strengen Anforderungen an die Datenintegrität kommt man kaum umhin, auf einen Algorithmus vom Typ „Linearer Kongruenzgenerator" zurückzugreifen. Die CRC-Algorithmen sind sorgfältig abgestimmt und optimiert, um eine zuverlässige Integritätserkennung mit einfacher Implementierung, schneller Ausführung und geringem Speicherbedarf zu verbinden – was CRC für ein breites Spektrum an Datenprüfszenarien attraktiv macht, das von Festplatten bis hin zu Kreditkartenlesegeräten reicht.