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 beschädigt wurden. Wenn Sie alle Bytes einer Nachricht addieren und dabei (unter Vernachlässigung von Überläufen) den Wert 96 erhalten, fügen Sie diese Zahl vor dem Senden an die Nachricht an. Der Empfänger kann dann die gleiche Summierung für die ersten N – 1 Bytes der Nachricht durchführen und das Ergebnis mit dem letzten Byte vergleichen, um zu prüfen, ob es ebenfalls 96 ergibt. Ist dies der Fall, kann der Empfänger davon ausgehen, dass die Nachricht während der Übertragung wahrscheinlich nicht verändert wurde.
In der Praxis sind verschiedene Prüfsummenverfahren weit verbreitet. Zu den gängigsten zählen die konventionelle Prüfsumme, LRC (Longitudinal Redundancy Check) und CRC (Cyclic Redundancy Check). Letztere ist im eigentlichen Sinne keine Prüfsumme, sondern ein Beispiel für eine Einwegfunktion aus der Familie der Hash -Funktionen, die dem Prinzip des „linearen Kongruenzgenerators" folgt.
Wie bereits erwähnt, können diese Datenintegritätsverfahren lediglich anzeigen, ob Daten „wahrscheinlich beschädigt wurden". Kein Prüfsummenverfahren ist im allgemeinen Fall – bei Daten beliebiger Länge – zu 100 % zuverlässig. Dennoch sind manche Verfahren deutlich leistungsfähiger als andere.
Im Folgenden wird erläutert, wie LRC, Prüfsumme und CRC mithilfe von JavaScript berechnet werden können.
Traditionelle Berechnung der 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 Übertragoperationen) verworfen wird. In JavaScript:
Die Eingabe dieser Funktion wird als Hex-String erwartet, der beispielsweise so aussieht: „48656C6C6F20776F726C6421" (in diesem Fall die Hex-Darstellung des ASCII-Strings „Hello world!"). Wird „48656C6C6F20776F726C6421" als Eingabe für die obige Funktion verwendet, lautet die Ausgabe „5d" – der Hexadezimalwert der abschließenden 8-Bit-Summe.
Der Code ist sehr einfach aufgebaut. In Zeile 3 beginnen wir damit, die Hex-Eingabe mithilfe des regulären Ausdrucks /../g in Zwei-Nibble-Blöcke aufzuteilen – dieser Ausdruck sucht nach Teilzeichenfolgen, die dem Muster „beliebiges Zeichen gefolgt von einem weiteren beliebigen Zeichen" entsprechen (das ist die Bedeutung der beiden Punkte), und zwar global über die gesamte Zeichenfolge (das ist die Bedeutung des 'g'). Das Ergebnis ist ein Array, s, das zweistellige Hex-Werte enthält.
In Zeile 5 beginnt eine Schleife (unter Verwendung des Iterationskonstrukts forEach ), in der wir die Zeichenfolgenversion eines Zwei-Nibble-Hex-Wertes in eine tatsächliche Zahl umwandeln, mit der wir rechnen 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 der Endwert weit 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 erfolgt die Rückumwandlung in eine Hex-Darstellung mithilfe der Methode toString() mit dem Argument 16, was bedeutet, dass wir Basis 16 (Hexadezimalsystem) für die abschließende Darstellung der Zahl verwenden möchten.
In den Zeilen 10 und 11 muss geprüft werden, ob der endgültige Hex-Wert genau zwei Nibbles lang ist. Die JavaScript-Operation toString(16) gibt für Werte kleiner als 10 nur eine einstellige Zahl zurück. In diesem Fall muss dem Ergebnis eine '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 hinzu: CHECKSUM("48656C6C6F20776F726C6421"). Nach Drücken der Eingabetaste sollte die Konsole '5d' als Rückgabewert anzeigen.
Berechnung der Prüfsumme mit LRC
Die Längsprüfung (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 keinen Überlauf erzeugt, muss das Endergebnis nicht per AND auf 8 Bit begrenzt werden. Es wird lediglich geprüft, ob die Länge zwei Nibbles beträgt, und anschließend wird der endgültige Wert zurückgegeben.
Wenn Sie den Code in der Konsole mit der oben angegebenen Zeichenkette testen, sollten Sie als Ergebnis „21" erhalten.
Kritische Betrachtung von Prüfsumme und LRC
Weder Prüfsumme noch LRC können als zuverlässiger Schutz gegen Nachrichtenmanipulation gelten. Betrachten Sie beispielsweise die ursprüngliche Nachricht („48656C6C6F20776F726C6421"): Wenn die letzten zwei Bytes der Nachricht von 6421 auf 6520 geändert werden, bleiben sowohl LRC als auch Prüfsumme unverändert. Es wurde lediglich ein Bit in einem vorgelagerten Byte eingeschaltet und dasselbe Bit an einer nachgelagerten Stelle ausgeschaltet – zwei Änderungen, die sich bei der Prüfsummenberechnung gegenseitig aufheben.
Ebenso verhält es sich, wenn die Nachricht invertiert wird – also byteweise umgekehrt, sodass sie mit 21 beginnt und mit 48 endet. Auch in diesem Fall bleiben LRC und Prüfsumme identisch mit den Werten der ursprünglichen Nachricht. Der Grund dafür ist, dass XOR und Addition kommutativ sind: A + B ergibt stets dasselbe wie B + A.
Zu bedenken ist außerdem, 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- bzw. Prüfsummenwert ergibt wie eine zufällig gewählte andere Nachricht.
Im Allgemeinen lassen sich Prüfsummen- und LRC-Algorithmen leicht „täuschen", weshalb sie für die Überprüfung der Nachrichtenintegrität nur bedingt zuverlässig sind.
Zum Glück gibt es für die Integritätsprüfung bessere Algorithmen als LRC oder Prüfsummen – allerdings gehen diese mit einem höheren Rechenaufwand einher.
Berechnung der Prüfsumme mit CRC
Wenn die Integritätsprüfung wirklich entscheidend ist, muss in der Regel eine nicht-kommutative Hash-Funktion verwendet werden. Häufig kommt dabei ein kryptografischer Hash wie SHA-1 oder MD5 zum Einsatz – diese sind jedoch rechenintensiv und können in vielen Situationen als überdimensioniert gelten.
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 etwa 4 Kilobyte) ausreichend und weit verbreitet.
CRC ist ein vielschichtiges Thema, das hier nicht umfassend behandelt werden kann. (Weiterführende Informationen finden sich bei Google.) Aus praktischer Sicht lässt sich festhalten: Ein 2-Byte-CRC reagiert sehr empfindlich auf zufällige Bitfehler in den Daten und liefert bei mehreren Bitfehlern kaum falsch-positive Ergebnisse. Aufgrund dieser Eigenschaften sowie der einfachen Implementierbarkeit in Hard- und Software und der sehr schnellen Ausführung mit minimalem Speicherbedarf findet CRC in zahlreichen Datenkommunikationsumgebungen Anwendung – darunter Festplattentreiber (wo Lesefehler häufig per CRC erkannt werden), Modems sowie kleine elektronische Geräte (einschließlich aller Kreditkartenleser der ViVOpay-Serie von ID TECH).
Der folgende JavaScript-Code zeigt, wie ein 16-Bit-CRC-Wert berechnet wird (zurückgegeben als vier Nibbles in Hex-ASCII).
CRC implementiert einen Hash-Algorithmus, der sich in einfachen Worten wie folgt beschreiben lässt:
- Den Startwert von 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 mit dem Eingabebyte XOR-verknüpfen – Zeile 14
- Verwenden Sie den resultierenden Wert j (nur die unteren 8 Bits) als Tabellenoffset, um ein „Substitutionsbyte" aus der Tabelle nachzuschlagen, die als crcTable bekannt ist — Zeile 15
- Verschieben Sie den Wert crc um 8 Bits nach LINKS und verknüpfen Sie ihn per XOR mit dem „Substitutionsbyte" — Zeile 15
- Wiederholen Sie diese Operationen ab Zeile 13 mit dem nächsten Eingabebyte
- Nachdem alle Eingabedaten auf diese Weise verarbeitet wurden, verknüpfen Sie das Ergebnis per XOR mit null und behalten die unteren 16 Bits des CRC — 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 umzukehren, um zu beobachten, wie sich das auf die Ausgabe auswirkt. Wenn Sie beispielsweise unsere Zeichenkette „Hello world!" als Eingabe verwenden und das letzte Byte der Daten von 21 auf 20 ändern, ändert sich der CRC auf 'AD03' – ohne erkennbaren Zusammenhang zu 'BD22'. Wenn Sie die letzten beiden Bytes auf '6520' ändern, ergibt sich ein CRC von '9E32'. (Zur Erinnerung: Dieselbe Änderung hat LRC oder Prüfsumme nicht beeinflusst.)
Betrachten Sie eine Zeichenkette, die zehn Null-Bytes repräsentiert. Der LRC-Wert einer solchen Zeichenkette wäre null. Die Prüfsumme wäre offensichtlich ebenfalls null. Der CRC hingegen würde E139 ergeben.
Sie können sich leicht selbst davon überzeugen, dass eine Umkehrung der Eingabe einen völlig anderen CRC liefert als die Eingabe in ursprünglicher Reihenfolge. (Was für LRC oder Prüfsumme nicht der Fall war.) CRC ist nicht kommutativ, da die obersten 8 Bits des CRC vor dem Linksschieben aller Werte mit dem Eingabe-Byte XOR-verknüpft werden – ähnlich wie beim Cipher Block Chaining , mit dem Unterschied, dass die „Cipher-Block"-Größe in diesem Fall 8 Bits beträgt.
Zu beachten ist, dass CRC zwar eine Einweg-Hash-Funktion ist, jedoch kein kryptografischer Hash im eigentlichen Sinne – denn es ist vergleichsweise einfach, einen „Korrekturwert" zu berechnen, der, an die Daten angehängt, dafür sorgt, dass eine gezielte Manipulation der Daten den gewünschten CRC-Endwert ergibt. (Bei sogenannten kryptografischen Hashes ist dies nicht möglich, da es äußerst schwierig ist, einen Korrekturfaktor zu berechnen, der einen manipulierten Datenblock auf den gewünschten Hash zurückführt.) CRC eignet sich daher zur Erkennung unbeabsichtigter Datenverfälschungen.
Fazit
Es gibt eine Vielzahl von Integritätsprüfungsalgorithmen, mit denen sich Datenpakete auf Beschädigungen überwachen lassen. In manchen Fällen genügt eine einfache Prüfsumme oder ein LRC. Wenn jedoch größere Datenmengen im Spiel sind und strenge Anforderungen an die Datenintegrität bestehen, kommt man kaum umhin, auf einen Hash vom Typ „Linear Congruential Generator" zurückzugreifen. Die CRC-Algorithmen wurden sorgfältig optimiert, um eine zuverlässige Integritätsprüfung bei gleichzeitig einfacher Implementierung, schneller Ausführung und geringem Speicherbedarf zu gewährleisten. Damit ist CRC für ein breites Spektrum an Datenprüfungsszenarien geeignet – von Festplatten bis hin zu Kreditkartenlesegeräten.