Prüfsumme - Checksum

Wirkung einer typischen Prüfsummenfunktion (das Unix- Dienstprogramm cksum )

Eine Prüfsumme ist ein kleiner Block von Daten von einem anderen Block der abgeleiteten digitaler Daten zum Zweck der Feststellung von Fehlern , die während seiner eingeführt worden seine Übertragung oder Speicherung . Für sich genommen werden Prüfsummen häufig verwendet , die Datenintegrität zu überprüfen , sondern verließ sich nicht auf die Daten überprüfen Authentizität .

Die Prozedur , die diese Prüfsumme erzeugt, wird als Prüfsummenfunktion oder Prüfsummenalgorithmus bezeichnet . Abhängig von seinen Designzielen gibt ein guter Prüfsummenalgorithmus normalerweise einen deutlich anderen Wert aus, selbst bei kleinen Änderungen an der Eingabe. Dies gilt insbesondere für kryptographische Hash - Funktionen , die verwendet werden können viele Informationen über Korruption , Fehler zu erkennen und insgesamt überprüfen Datenintegrität ; Wenn die berechnete Prüfsumme für die aktuelle Dateneingabe mit dem gespeicherten Wert einer zuvor berechneten Prüfsumme übereinstimmt, besteht eine sehr hohe Wahrscheinlichkeit, dass die Daten nicht versehentlich geändert oder beschädigt wurden.

Prüfsummenfunktionen beziehen sich auf Hashfunktionen , Fingerabdrücke , Randomisierungsfunktionen und kryptografische Hashfunktionen . Jedes dieser Konzepte hat jedoch unterschiedliche Anwendungen und daher unterschiedliche Designziele. Zum Beispiel kann eine Funktion, die den Anfang eines Strings zurückgibt, einen Hash bereitstellen, der für einige Anwendungen geeignet ist, aber niemals eine geeignete Prüfsumme sein wird. Prüfsummen werden als kryptografische Primitive in größeren Authentifizierungsalgorithmen verwendet. Informationen zu kryptografischen Systemen mit diesen beiden spezifischen Designzielen finden Sie unter HMAC .

Prüfziffern und Paritätsbits sind Sonderfälle von Prüfsummen, die für kleine Datenblöcke geeignet sind (wie Sozialversicherungsnummern , Bankkontonummern , Computerwörter , einzelne Bytes usw.). Einige fehlerkorrigierende Codes basieren auf speziellen Prüfsummen, die nicht nur häufige Fehler erkennen, sondern in bestimmten Fällen auch die Wiederherstellung der Originaldaten ermöglichen.

Algorithmen

Paritätsbyte oder Paritätswort

Der einfachste Prüfsummenalgorithmus ist die sogenannte Längsparitätsprüfung , die die Daten in "Wörter" mit einer festen Anzahl n von Bits zerlegt und dann das Exklusiv-Oder (XOR) all dieser Wörter berechnet . Das Ergebnis wird als zusätzliches Wort an die Nachricht angehängt. Um die Integrität einer Nachricht zu überprüfen, berechnet der Empfänger das exklusive oder aller seiner Wörter, einschließlich der Prüfsumme; ist das Ergebnis kein Wort, das aus n Nullen besteht, weiß der Empfänger, dass ein Übertragungsfehler aufgetreten ist.

Mit dieser Prüfsumme wird jeder Übertragungsfehler, der ein einzelnes Bit der Nachricht oder eine ungerade Anzahl von Bits kippt, als falsche Prüfsumme erkannt. Ein Fehler, der zwei Bits betrifft, wird jedoch nicht erkannt, wenn diese Bits in zwei verschiedenen Wörtern an derselben Position liegen. Auch das Vertauschen von zwei oder mehr Wörtern wird nicht erkannt. Wenn die betroffenen Bits unabhängig zufällig ausgewählt werden, beträgt die Wahrscheinlichkeit, dass ein Zwei-Bit-Fehler nicht erkannt wird, 1/ n .

Summenkomplement

Eine Variante des vorherigen Algorithmus besteht darin, alle "Wörter" als vorzeichenlose Binärzahlen zu addieren, alle Überlaufbits zu verwerfen und das Zweierkomplement der Gesamtsumme als Prüfsumme anzuhängen . Um eine Nachricht zu validieren, fügt der Empfänger alle Wörter auf die gleiche Weise hinzu, einschließlich der Prüfsumme; ist das Ergebnis kein Wort voller Nullen, muss ein Fehler aufgetreten sein. Auch diese Variante erkennt jeden Single-Bit-Fehler, aber in SAE J1708 wird die Pro-Modular-Summe verwendet .

Positionsabhängig

Die oben beschriebenen einfachen Prüfsummen können einige allgemeine Fehler nicht erkennen, die viele Bits gleichzeitig betreffen, wie beispielsweise das Ändern der Reihenfolge von Datenwörtern oder das Einfügen oder Löschen von Wörtern, bei denen alle Bits auf Null gesetzt sind. Die in der Praxis am häufigsten verwendeten Prüfsummenalgorithmen, wie Fletchers Prüfsumme , Adler-32 und zyklische Redundanzprüfungen (CRCs), adressieren diese Schwächen, indem sie nicht nur den Wert jedes Wortes, sondern auch seine Position in der Sequenz berücksichtigen. Dieses Merkmal erhöht im Allgemeinen die Kosten der Berechnung der Prüfsumme.

Unscharfe Prüfsumme

Die Idee der Fuzzy-Prüfsumme wurde zur Erkennung von E-Mail-Spam entwickelt, indem kooperative Datenbanken mehrerer ISPs für Spam-verdächtige E-Mails erstellt werden. Der Inhalt eines solchen Spams kann oft in seinen Details variieren, was eine normale Prüfsumme unwirksam machen würde. Im Gegensatz dazu reduziert eine "Fuzzy-Prüfsumme" den Fließtext auf sein charakteristisches Minimum und erzeugt dann in üblicher Weise eine Prüfsumme. Dies erhöht die Wahrscheinlichkeit, dass leicht unterschiedliche Spam-E-Mails dieselbe Prüfsumme erzeugen, erheblich. Die ISP-Spam-Erkennungssoftware wie SpamAssassin von kooperierenden ISPs übermittelt Prüfsummen aller E-Mails an den zentralen Dienst wie DCC . Wenn die Anzahl einer gesendeten Fuzzy-Prüfsumme einen bestimmten Schwellenwert überschreitet, stellt die Datenbank fest, dass dies wahrscheinlich auf Spam hindeutet. Benutzer von ISP-Diensten generieren in ähnlicher Weise eine Fuzzy-Prüfsumme für jede ihrer E-Mails und fordern den Dienst auf Spam-Wahrscheinlichkeit an.

Allgemeine Überlegungen

Eine m Bit lange Nachricht kann als Ecke des m- dimensionalen Hyperwürfels betrachtet werden. Die Wirkung eines Prüfsummenalgorithmus, der eine n- Bit-Prüfsumme ergibt, besteht darin, jede m- Bit-Nachricht auf eine Ecke eines größeren Hyperwürfels mit der Dimension m + n abzubilden . Die 2 m + n Ecken dieses Hyperwürfels repräsentieren alle möglichen empfangenen Nachrichten. Die gültigen empfangenen Nachrichten (mit der korrekten Prüfsumme) umfassen einen kleineren Satz mit nur 2 m Ecken.

Ein Einzelbit-Übertragungsfehler entspricht dann einer Verschiebung von einer gültigen Ecke (der richtigen Nachricht und Prüfsumme) zu einer der m benachbarten Ecken. Ein Fehler, der k Bits betrifft, verschiebt die Nachricht zu einer Ecke, die k Schritte von ihrer richtigen Ecke entfernt ist. Das Ziel eines guten Prüfsummenalgorithmus ist es, die gültigen Ecken so weit wie möglich voneinander zu verteilen, um die Wahrscheinlichkeit zu erhöhen, dass "typische" Übertragungsfehler in einer ungültigen Ecke landen.

Siehe auch

Hauptthema

Fehler Korrektur

Hash-Funktionen

Dateisysteme

  • ZFS  – ein Dateisystem, das mithilfe von Prüfsummen eine automatische Dateiintegritätsprüfung durchführt

Verwandte konzepte

Verweise

Externe Links