PatentDe  


Dokumentenidentifikation DE102005028221A1 28.12.2006
Titel Vorrichtung und Verfahren zum Schutz der Integrität von Daten
Anmelder Infineon Technologies AG, 81669 München, DE
Erfinder Göttfert, Rainer, Dr., 81827 München, DE;
Gammel, Berndt, Dr., 85570 Markt Schwaben, DE
Vertreter Schoppe, Zimmermann, Stöckeler & Zinkler, 82049 Pullach
DE-Anmeldedatum 17.06.2005
DE-Aktenzeichen 102005028221
Offenlegungstag 28.12.2006
Veröffentlichungstag im Patentblatt 28.12.2006
IPC-Hauptklasse G06F 12/14(2006.01)A, F, I, 20051017, B, H, DE
Zusammenfassung Durch Anordnung einer Redundanzeinrichtung und einer Kontrolleinrichtung vor einer Verschlüsselungseinrichtung, welche die in einem externen Speicher zu speichernden Daten ver- und entschlüsselt, kann die Integrität von Daten sichergestellt werden, wenn die Erzeugung einer Redundanzinformation durch die Redundanzeinrichtung und die Erzeugung eines Syndrombitvektors durch die Kontrolleinrichtung, welcher eine eventuelle Veränderung der Daten anzeigt, realisiert wird. Bevorzugt wird eine Kontrollmatrix, die sich auf lauter idempotenten, dünnbesetzten, zirkulanten quadratischen Submatrizen aufbaut. Durch eine Redundanz- und eine Kontrolleinrichtung vor der Ver-/Entschlüsselungseinrichtung wird erreicht, dass sich sowohl Fehler in den verschlüsselten Daten nachweisen lassen als auch Fehler der unverschlüsselten Daten, sofern diese in dem Datenweg zwischen der Redundanz-/Kontrolleinrichtung und der Ver-/Entschlüsselungseinrichtung aufgetreten sind.

Beschreibung[de]

Die vorliegende Erfindung befasst sich mit einer Vorrichtung und einem Verfahren zum Schutz der Integrität von Daten, wie sie bei der Verarbeitung und Speicherung von Daten durch beispielsweise einen Mikrocontroller angewendet werden können.

In vielen Anwendungsszenarien ist es wünschenswert, gespeicherte Daten vor dem Zugriff unberechtigter Personen zu schützen, weswegen diese verschlüsselt in einem Speicher abgelegt werden. Die Daten können dabei bei ihrem Transfer über ein Bussystem oder während ihrer Verweildauer im Speicher durch zufällig auftretende Fehler, beispielsweise das Kippen eines einzelnen Bits, verändert werden. Ein Angreifer, der die Sicherheit eines Systems durch Fehlerangriffe (fault attacks) beeinträchtigen will, wird gespeicherte Daten mutwillig verändern, wobei bei Fehlerangriffen meist mehr als ein Bit eines gespeicherten oder über einen Bus übertragenen Datenpaketes verändert wird. Zusätzlich zur Verschlüsselung der gespeicherten Daten ist also eine Vorrichtung erforderlich, die eine zufällige oder absichtlich herbeigeführte Veränderung der Daten erkennen kann.

Um Angriffe auf ein System allgemein zu erkennen, werden stellenweise Sensoren eingesetzt. Diese Sensoren können beispielsweise Spannungsmessgeräte sein, um absichtlich in ein System eingespeiste Überspannungen zu erkennen. Des weiteren werden Temperatur- und Lichtsensoren eingesetzt, um etwa das Öffnen oder Aufschleifen eines Gehäuses zu erkennen.

Eine andere Möglichkeit der Absicherung besteht darin, Datenworte vor dem Abspeichern mit einer Redundanzinformation zu versehen, wobei es die Redundanzinformation erlaubt, die Veränderung von Bits eines digital gespeicherten Datenwortes zu detektieren und, je nach Eigenschaft der Redundanzinformation, die Veränderung auch zu korrigieren. Dabei wird üblicherweise die Redundanzinformation nach dem Verschlüsseln der Daten an die verschlüsselten Daten angebracht, um eine Veränderung der verschlüsselten Daten in einem externen Speicherbereich zu erkennen. Die Deutsche Patentanmeldung 10 2005 001953.6 beschreibt darüber hinaus ein Verfahren zur Überprüfung eines Datensatzes aus mehreren Datenworten, bei dem ein Redundanzdatenwort durch „XOR'ierung" aller Datenworte vor dem Verschlüsseln stattfindet, wobei nach der Redundanzbildung der Datensatz wortweise verschlüsselt und abgespeichert wird.

Das Detektieren eines Angriffs mittels Sensoren ermöglicht es nicht, „flächendeckend" einen Fehlerangriff zu erkennen und verursacht wesentlich höhere Kosten als beispielsweise eine rein digitale Schaltung. Flächendeckend bedeutet hierbei, dass nicht der gesamte Datenpfad ab dem Moment der Erzeugung der Daten mit physikalischen Sensoren überwacht werden kann. Das Hinzufügen der Redundanzinformation nach der Verschlüsselung der Daten hat den großen Nachteil, dass dadurch nur Fehler, die in dem externen Speicher auftreten, nachgewiesen werden können. Datenfehler die, zufällig oder durch einen Angriff, in den Daten zwischen der Recheneinheit und der Verschlüsselungseinheit auftreten, können nicht erkannt werden. Eine XOR'ierung der Daten vor der Verschlüsselung hat den Nachteil, dass aufgrund der mathematischen Einfachheit der XOR'ierung Angriffe nur dann festgestellt werden können, wenn eine ungerade Anzahl von Datenbits des Datensatzes durch den Angriff verändert wurden.

Die Aufgabe der vorliegenden Erfindung besteht darin, eine Vorrichtung und ein Verfahren zu schaffen, mit dem die Veränderung von Daten vor der Verschlüsselung und die Veränderung von verschlüsselten Daten nachgewiesen werden kann.

Diese Aufgabe wird durch eine Vorrichtung gemäß einem der Ansprüche 1, 9, 11 oder durch ein Verfahren gemäß einem der Ansprüche 13, 14 oder 15 gelöst.

Der Kerngedanke der vorliegenden Erfindung besteht darin, dass durch Anordnung einer Redundanzeinrichtung und einer Kontrolleinrichtung vor einer Verschlüsselungseinrichtung, welche in einem externen Speicher zu speichernde Daten ver- und entschlüsselt, die Integrität von Daten sichergestellt werden kann, wenn die Erzeugung einer Redundanzinformation durch die Redundanzeinrichtung und die Erzeugung eines Syndrombitvektors durch die Kontrolleinrichtung, welcher eine eventuelle Veränderung der Daten anzeigt, realisiert wird. Bevorzugt wird eine Kontrollmatrix, die sich aus lauter idempotenten, dünnbesetzten, zirkulanten quadratischen Submatrizen aufbaut. Durch eine Redundanz- und eine Kontrolleinrichtung vor der Ver-/Entschlüsselungseinrichtung wird erreicht, dass sich sowohl Fehler in den verschlüsselten Daten nachweisen lassen, als auch Fehler in den unverschlüsselten Daten, sofern diese in dem Datenweg zwischen der Redundanz-/Kontrolleinrichtung und der Ver-/Entschlüsselungseinrichtung aufgetreten sind. Die einen vorzugsweise linearen Code zum Schutz gegen Fehlerangriffe repräsentierende, speziell entworfene Kontrollmatrix aus idempotenten, dünnbesetzten, zirkulanten quadratischen Submatrizen gestattet es weiterhin, die Einrichtung bzw. das Verfahren in einer Computerhardware zu implementieren, wobei nur eine geringe Siliziumfläche benötigt wird und der Stromverbrauch der Implementierung sehr gering ist.

In einem speziellen Ausführungsbeispiel der vorliegenden Erfindung sind die Redundanzeinrichtung und die Kontrolleinrichtung innerhalb desselben Computerchips wie der Datenverarbeitungsprozessor angeordnet, wobei die zu speichernden Datenwörter unmittelbar nach ihrer Erzeugung durch den Datenverarbeitungsprozessor mit der Redundanzinformation versehen werden. Die Daten werden vor ihrer Speicherung in einem externen Speicher über Register und Zwischenspeicher an eine Verschlüsselungseinheit geleitet, welche die Daten verschlüsselt und die verschlüsselten Daten in dem externen Speicher ablegt. Diese Anordnung hat den großen Vorteil, dass die Daten des Datenverarbeitungsprozessors während des ganzen Weges durch das System geschützt sind, sodass eine Änderung der Daten bzw. ein Angriff auf das System also sowohl vor der Verschlüsselung der Daten als auch nach der Verschlüsselung der Daten nachgewiesen werden kann.

In einem weiteren Ausführungsbeispiel der vorliegenden Erfindung ist die Redundanzeinrichtung so ausgebildet, dass das Erzeugen der Redundanzinformationen für mehrere zusammengehörende Datenworte eines Datenblockes eine Matrixmultiplikation einer Erzeugermatrix mit einem Datenbitvektor, der aus den einzelnen Bits der Datenworte gebildet ist, beinhaltet. Die Erzeugermatrix ist dabei so gewählt, dass eine zweite Redundanzinformation eines zweiten Datenbitvektors auf einfache Weise gebildet werden kann, wenn sich der zweite Datenbitvektor von dem vorhergehenden ersten Datenbitvektor um einen Differenzbitvektor unterscheidet. Die zweite Redundanzinformation kann dann aus der ersten Redundanzinformation gebildet werden, wenn der Differenzbitvektor mit der Erzeugermatrix multipliziert wird und der sich so ergebende Differenzredundanzbitvektor mit dem ersten Redundanzbitvektor addiert wird. Unterscheiden sich zwei aufeinander folgende Datenbitvektoren nur um einige wenige Bits, kann durch diese Eigenschaft der Matrix bei einer Implementierung der Redundanzerzeugung in einer Hardware eine erhebliche Energieeinsparung erreicht werden, da nur die wenigen sich ändernden Bits einer Multiplikationsoperation unterzogen werden müssen.

In einem weiteren Ausführungsbeispiel der vorliegenden Erfindung werden die von einem externen Speicher gelesenen Daten auf Integrität geprüft, nachdem diese von einer Entschlüsselungseinheit entschlüsselt wurden. Durch die Redundanzeinrichtung wird mittels Multiplikation einer geeigneten Kontrollmatrix an die entschlüsselten Daten ein Syndrombitvektor erzeugt. Ist dieser Syndrombitvektor der Nullvektor, wird darauf geschlossen, dass die Daten weder während des Speicherns noch durch das Ver-/Entschlüsseln verändert wurden. Die gelesenen Daten werden somit als unmanipuliert angenommen. Ist der Syndrombitvektor ungleich dem Nullvektor, kann dadurch, dass die Redundanzinformation den Daten vor dem Verschlüsseln zugefügt wurde, ein Fehler eines Bits in den Daten immer korrigiert werden. Dies ist ein großer Vorteil da das Verschlüsseln der Daten eine hoch nicht-lineare Operation darstellt, sodass ein verschlüsseltes Datenwort, das an nur einer einzigen Bitstelle geändert wird, nach dem Entschlüsseln ein Datenwort ergibt, das von dem ursprünglichen Datenwort an mehreren Bitpositionen verändert sein wird. Durch die erfindungsgemäße Vorrichtung wird insbesondere sogar die Möglichkeit geschaffen, zu unterscheiden, ob die Daten durch einen zufälligen 1-Bit-Fehler verändert wurden, oder ob sie etwa durch einen Angriff auf das System an mehreren Bitpositionen geändert wurden.

In einem weiteren speziellen Ausführungsbeispiel der vorliegenden Erfindung wird jeder Nachrichtenblock, bestehend aus vier 32-Bit-Worten mit einer Zusatzinformation (einem Kontrollwort) ausgestattet, das aus dem Nachrichtenblock berechnet wird, wobei das zugehörige Kontrollwort ebenfalls 32 Bit Länge hat. Eine Überprüfung der Integrität der Daten geschieht dabei dadurch, dass man aus den vier Nachrichtenworten und dem Kontrollwort Syndrom berechnet. Das Syndrom ist dann ein weiteres 32-Bit-Wort. Wenn kein Fehler passiert ist, dann ist das Syndrom das Nullwort (oder der Nullvektor bestehend aus 32 Nullen). Umgekehrt interpretiert man die Tatsache „Syndrom = Nullvektor" so, dass kein Fehler passiert ist. Dieser Umkehrschluss ist korrekt mit der Wahrscheinlichkeit 1 – 1/232, vorausgesetzt ein beliebiger Fehler konnte passieren (beliebig viele der insgesamt 160 Bit wurden beim Fehlerangriff verändert). In bestimmten Angriffsszenarien, wie etwa bei durch Licht-, Laser-, oder Spikeangriffen erzeugten begrenzten Fehlern während dem Transfer der Nachricht über einen Bus oder bei Fehlern, die durch Forcen einer einzelnen Busleitung verursacht wurden, ist der Umkehrschluss aber absolut korrekt. Das heißt, solche Angriffe werden immer erkannt. Der Vorteil in der vorliegenden Erfindung besteht dabei darin, dass mit absoluter Sicherheit ein Angriff auf ein System nachgewiesen werden kann, wobei durch die erfindungsgemäße Ausgestaltung der Redundanzeinrichtung und der Kontrolleinrichtung zum Verarbeiten von 32 Bitworten die Möglichkeit geschaffen wird, die Vorrichtung zum Schutz der Integrität von Daten problemlos in eine bestehende 32-Bit Prozessorarchitektur zu integrieren.

Bevorzugte Ausführungsbeispiele der vorliegenden Erfindung werden nachfolgend Bezug nehmend auf die beiliegenden Zeichnungen detailliert erläutert. Es zeigen:

1 eine Vorrichtung zum Schutz der Integrität von Daten.

2 ein Zustandsdiagramm, das die Zustände von Datenworten beim Schreibvorgang beschreibt.

3 ein Zustandsdiagramm, das die Zustände von Datenworten beim Lesen beschreibt.

4a–d Darstellung von idempotenten, dünn besetzten, zirkulanten quadratischen Matrizen.

5 ein Kodefeld zum Erzeugen eines Produktcodes.

In 1 ist eine erfindungsgemäße Vorrichtung zum Schutz der Integrität von Daten schematisch dargestellt. Gezeigt ist ein Hauptprozessor 2 und ein Speichersystem 4. Der Hauptprozessor umfasst ein Datenregister 6 zum Senden und Empfangen von Datenwörtern, einen Zentralprozessor 8, der aus einer Recheneinheit 10, einer Redundanzeinheit 12 und einer Kontrolleinheit 14 besteht. Das Speichersystem 4 umfasst einen schnellen Zwischenspeicher 16, den so genannten Cache, einen internen Speicher 18, eine Ver-/Entschlüsselungseinheit 20 und einen Massenspeicher 22. Die Redundanzeinheit 12 ist mit dem Datenregister 6 durch eine erste Datenverbindung 24 zum Senden von Datenworten an das Datenregister verbunden. Das Datenregister 6 ist über eine zweite Datenverbindung 26 mit der Kontrolleinheit 14 verbunden, um Datenworte von dem Datenregister 6 an die Kontrolleinheit 14 zu senden. Das Datenregister 6 ist mit dem Cache 16 über eine erste bidirektionale Datenverbindung 28 verbunden, um Datenwörter zwischen dem Datenregister 6 und dem Cache 16 austauschen zu können. Zum selben Zweck ist das Datenregister 6 über eine zweite bidirektionale Datenverbindung 30 mit dem internen Speicher 18 verbunden. Über eine dritte bidirektionale Datenverbindung 32 ist der Cache 16 mit der Ver-/Entschlüsselungseinheit 20 verbunden, die wiederum über eine vierte bidirektionale Datenverbindung 34 mit dem Massenspeicher 22 verbunden ist.

Die Funktionsweise des Ausführungsbeispiels in 1 wird im Folgenden kurz erläutert, für die genaue Beschreibung der Prozessschritte an den zu übertragenden Datenworten beim Lesen und beim Schreiben sei hier auf die Zustandsdiagramme in den 2 und 3 verwiesen.

Die von der Recheneinheit 10 berechneten Datenworte werden von der Redundanzeinheit 12 mit einem Redundanzdatenwort, welches von der Redundanzeinheit 12 berechnet wird, verknüpft, sodass die Datenworte und das Redundanzdatenwort über die erste Datenverbindung 24 in das Datenregister 6 übertragen werden. Das Datenregister 6 kann die Datenworte und das Redundanzdatenwort abhängig von der erforderlichen Speicherdauer zum einen über die bidirektionale Datenverbindung 30 in den internen Speicher 18 übertragen, zum anderen über die bidirektionale Datenverbindung 28 in den Cache 16. Die Datenworte und das Redundanzdatenwort werden von dem Cache 16 über die bidirektionale Datenverbindung 32 in die Ver-/Entschlüsselungseinheit 20 übertragen, wo sie von der Ver-/Entschlüsselungseinheit 20 in verschlüsselte Datenworte und ein verschlüsseltes Redundanzdatenwort umgewandelt werden, wobei jedes der Datenworte separat in ein verschlüsseltes Datenwort transformiert wird. Die verschlüsselten Datenworte und das verschlüsselte Redundanzdatenwort werden sodann über die bidirektionale Datenverbindung 34 in den Massenspeicher übertragen und dort gespeichert.

Beim Lesevorgang werden die verschlüsselten Datenworte und das verschlüsselte Redundanzdatenwort gemeinsam über die bidirektionale Datenverbindung 34 aus dem Massenspeicher 22 an die Ver-/Entschlüsselungseinheit 20 übermittelt und dort wortweise entschlüsselt. Die entschlüsselten Datenwörter und das entschlüsselte Redundanzdatenwort werden über die bidirektionale Datenverbindung 32 an den Cache 16 übermittelt, von wo sie über die bidirektionale Datenverbindung 28 in das Datenregister 6 übertragen werden. Von dem Datenregister 6 werden die entschlüsselten Datenworte und das entschlüsselte Redundanzdatenwort über die Datenverbindung 26 an die Kontrolleinheit 16 übermittelt, welche aus den Datenworten und dem Redundanzdatenwort einen Syndrombitvektor berechnet, anhand dessen entschieden werden kann, ob die Datenworte während ihrem Weg durch das Speichersystem 4 verändert worden sind.

Die Vorgänge beim Speichern der Daten sind im Folgenden Bezug nehmend auf 1 in dem Zustandsdiagramm in 2 näher erläutert. In 2 ist ein unverschlüsselter Datensatz 36 dargestellt, der aus den Datenworten m0 bis m3 besteht, wobei die Datenworte m0 bis m3 jeweils 32-Bit-Worte sind, d. h. als ein Vektor von 32 aufeinander folgenden Bits dargestellt werden kann. Der Datensatz 36 wird durch einen Datenbitvektor 38 dargestellt, der gebildet wird, indem die je 32 Bit der einzelnen Datenwörter m0 bis m3 hintereinander in einem Vektor angeordnet werden. Gezeigt ist ferner ein Kontrollbitvektor 40, ein Gesamtbitvektor 42 und ein verschlüsselter Gesamtbitvektor 44. Beim Schreibvorgang werden die Datenwörter von der Recheneinheit 10 berechnet und als Datenbitvektor 38 an die Redundanzeinheit 12 übergeben. Die Redundanzeinheit 12 erzeugt durch Multiplikation des Datenbitvektors 38 mit einer Erzeugermatrix in einem Redundanzbildungsschritt 46 den Kontrollbitvektor 40. Während der Gesamtbitvektorerzeugung 48 wird von der Redundanzeinheit 12 der Kontrollbitvektor 40 und der Datenbitvektor 38 in dem Gesamtbitvektor 42 zusammengeführt, wozu der Kontrollbitvektor 40 als letzte 32 Bit des Gesamtbitvektors 42 an den Datenbitvektor 38 angefügt werden. Während des Verschlüsselungsschrittes 50 wird der Gesamtbitvektor 42 über das Datenregister 6 und den Cache 16 an die Ver-/Entschlüsselungseinheit 20 übertragen, wo diese wortweise verschlüsselt werden, sodass am Ausgang der Ver-/Entschlüsselungseinheit 20 der verschlüsselte Gesamtbitvektor 44 zur Verfügung steht, der in einem externen Speicher 22 abgespeichert wird. Da die Verschlüsselung wortweise geschieht, setzt sich verschlüsselte Gesamtbitvektor 44 aus den hintereinandergereihten Bitdarstellungen der verschlüsselten Worte m0 bis m3 und des verschlüsselten Kontrollbitvektors zusammen.

Die einzelnen Zustände der Datenworte eines aus dem Massenspeicher 22 gelesenen Datenwsatzes werden im Folgenden anhand von 3 näher erläutert, wobei auch darauf eingegangen wird, wie eine eventuell nachgewiesene Veränderung der gespeicherten Daten korrigiert werden kann. 3 zeigt einen verschlüsselten, gespeicherten Datensatz 52, der durch einen verschlüsselten Gesamtbitvektor 54 repräsentiert wird, einen entschlüsselten Gesamtbitvektor 56, einen Syndrombitvektor 58, entschlüsselte Datenwortvektoren 60a60e, substituierte Datenwortvektoren 62a62e, und verschlüsselte substituierte Datenwortvektoren 64a64e. Im Massenspeicher 22 ist der verschlüsselte Gesamtbitvektor 54 abgelegt, der in einem Entschlüsselungsschritt 66 von der Ver-/Entschlüsselungseinheit 20 wortweise entschlüsselt wird, sodass nach der Entschlüsselung der entschlüsselte Gesamtbitvektor 56 zur Verfügung steht, der aus den entschlüsselten Datenwortvektoren 60a60e besteht und der in einem Lesetransferschritt 68 von der Ver-/Entschlüsselungseinheit 20 über den Cache 16 und das Datenregister 6 an die Kontrolleinheit 14 übertragen wird. Die Kontrolleinheit 14 bildet aus dem entschlüsselten Gesamtbitvektor 56 durch Multiplikation des entschlüsselten Gesamtbitvektors 56 mit einer binären Kontrollmatrix einen Syndrombitvektor 58, anhand dessen die Integrität des entschlüsselten Gesamtbitvektors 56 überprüft werden kann. Ist der Syndrombitvektor 58 der Nullvektor, d. h. sind alle seine 32 Bit gleich 0, wird in einem Bestätigungsschritt 69 darauf geschlossen, dass die Daten weder in dem Massenspeicher 22 noch während des Lesetransferschritts 68 verändert wurden, und es wird angenommen, dass der entschlüsselte Gesamtbitvektor 56 dem während des Schreibvorganges erstellten Gesamtbitvektors 42 entspricht.

Ist der Syndrombitvektor ungleich dem Nullvektor, wurden die Daten seit dem Erstellen des Kontrollbitvektors 40 während des Schreibvorganges verändert. Dabei wird zunächst davon ausgegangen, dass sich während der Verweildauer der Daten im Massenspeicher 22 ein Bit eines der Datenworte zufällig geändert hat. Durch die hoch nicht-lineare Entschlüsselungsoperation der Ver-/Entschlüsselungseinheit 20 während des Entschlüsselungsschrittes 66 wird sich ein einzelnes geändertes Bit vor der Entschlüsselung eines Datenwortvektors in einer Mehrzahl von geänderten Bits eines entschlüsselten Datenwortvektors äußern, d. h. ein solcher entschlüsselter Datenwortvektor unterscheidet sich in einer Mehrzahl von Bits von dem ihm zugrunde liegenden Datenbitvektor. Mit der erfindungsgemäßen Vorrichtung ist es nun trotzdem möglich, einen Ein-Bit-Fehler in einem der verschlüsselten Datenwortvektoren zu erkennen und diesen zu korrigieren. Dies ist aufgrund der Redundanzinformation, die dem unverschlüsselten Datensatz während des Schreibens beigefügt wurde, möglich, wie im Folgenden beschrieben wird.

Ist der Syndrombitvektor 58 ungleich dem Nullvektor, werden zunächst in einem Substitutionsschritt 70 von der Kontrolleinheit 14 substituierte Datenwortvektoren 62a62e gebildet, wobei die substituierten Datenwortvektoren 62a62e in Abhängigkeit von den entschlüsselten Datenwortvektoren 60a60e gebildet werden, was aufgrund der zusätzlichen Redundanzinformation möglich ist. Unserer Annahme folgend, dass nur ein einzelnes der Datenworte des verschlüsselten Gesamtbitvektors 54 von einem Bitfehler betroffen ist, gibt es dann genau einen substituierten Datenwortvektor 62a62e, der nur von den 4 fehlerfrei entschlüsselten Datenworten der Datenwortvektoren 60a60e abhängt.

In einem Überprüfschritt 72 werden die substituierten Datenwortvektoren 62a62e wortweise von der Ver-/Entschlüsselungseinheit 20 verschlüsselt, sodass sich die verschlüsselten substituierten Datenwortvektoren 64a64e ergeben. In einem Vergleichsschritt 74 werden nun von der Kontrolleinheit 14 die Hammingabstände der verschlüsselten substituierten Datenwortvektoren 64a64e von den ihnen zugeordneten Datenworten des verschlüsselten Gesamtbitvektors 54 gebildet. Wurde ein Fehler in einem Datenwort des verschlüsselten Gesamtbitvektors 54 durch einen einzelnen Bitfehler hervorgerufen, wird der Hammingabstand des betreffende Datenwortes zu seinem verschlüsselten substituierten Partner genau 1 betragen und der entschlüsselte Gesamtbitvektor 56 kann in einem Rekonstruktionsschritt 76 vollständig fehlerfrei rekonstruiert werden. Weist keines der Datenworte des verschlüsselten Datensatzes 52 einen Hammingabstand von 1 zu seinem ihm zugeordneten verschlüsselten substituierten Datenwortvektor auf, wird in einem Fehlerschritt 78 davon ausgegangen, dass mehr als 1 Bit des verschlüsselten Datensatzes 52 durch einen Angriff verändert wurde, sodass geeignete Maßnahmen getroffen werden können, um dem Angriff zu begegnen.

In einem weiteren speziellen Ausführungsbeispiel der vorliegenden Erfindung ist ein linearer Code zum Schutz gegen Fehlerangriffe durch eine speziell entworfene Kontrollmatrix definiert bzw. realisiert. Die für die Konzeption der erfindungsgemäßen Vorrichtung zum Schutz der Integration von Daten notwendigen prinzipiellen Überlegungen sind im Folgenden kurz dargestellt. Die grundlegende Voraussetzung um eine Fehlererkennung (EDC) oder einen Fehlerkorrekturcode (ECC) für ein System zu entwickeln, ist die Annahme eines Fehlermodells. Das Fehlermodell ist eine mathematische Abstraktion möglicher Fehler. Im vorliegenden Fall muss das Fehlermodell die Auswirkungen möglicher Angriffe auf das System berücksichtigen. Da ein Mikrocontroller ein extrem kompliziertes System ist, wird das System zunächst in kleine Subsysteme unterteilt, deren Verhalten einfacher modelliert werden kann. Am Schluss der Überlegungen muss ein generelles Fehlermodell des gesamten Systems wieder aus den einzelnen Funktionsblöcken der Subsysteme synthetisiert werden. In dem vorliegenden Ausführungsbeispiel wird ein im Datenpfad befindliches Datenregister 6, ein Cache 16, ein interner Speicher 18, eine Ver-/Entschlüsselungseinheit 20 und ein Massenspeicher 22 berücksichtigt, wie sie in 1 zu sehen sind.

Im Folgenden werden kurz die für die Entwicklung der vorliegenden Erfindung gemachten Annahmen bezüglich des Angriffsszenarios dargelegt.

Es gibt viele Angriffsformen, die lokalen Charakter haben, d. h. wo der Angreifer die Möglichkeit hat, einzelne Bits zu ändern. Ein professioneller Angreifer könnte die Möglichkeit haben, kontrolliert einzelne Bits zu verändern (indem er beispielsweise eine fokussierten Laserstrahl verwendet) oder Mikroproben zu verwenden. Andere Angriffsformen verändern einzelne Bits oder Bitgruppen zufällig. Wenn der Angreifer beispielsweise ionisierende Strahlung in Verbindung mit einer Blendenvorrichtung verwendet um einzelne Bitgruppen auszuwählen, ist er in der Lage, einzelne Bitgruppen zufällig zu verändern. Eine Anpassung der Strahlungsintensität könnte es sogar ermöglichen, den Angriff dahingehend zu verfeinern, dass das Gewicht eines Fehlervektors maximiert wird. Dabei ist der Fehlervektor ein Vektor aus Binärzahlen, der an den Positionen der veränderten Bits eine 1 aufweist und an den übrigen Positionen eine 0. Kurzzeitig auftretende elektrische Überspannungen oder Angriffe mit starker lokaler Überhitzung (z.B. temperaturinduzierte Spannungsänderungen) können zu zufälligen Bitfehlern führen. Weniger ausgefeilte (nichtsdestotrotz sehr effiziente) Angriffe wie eine Bestrahlung eines Systems mit Licht (flash light attacks) oder Übertakten eines Schaltkreises können zu „Burst"-Fehlern führen, d. h. eine größere Anzahl von Bits werden in denselben logischen Zustand, also 1 oder 0, gebracht. Es gibt zwar keine fundierte Kenntnis über die Charakteristiken oder die Zusammenhänge, die zu Burst-Fehlern führen, jedoch gibt es einige Hinweise, dass in vielen solcher Angriffe benachbarte Bits mit höherer Wahrscheinlichkeit in denselben Zustand schalten. Daher nehmen wir für die zukünftigen Betrachtungen den schlimmsten denkbaren Fall an, dass alle Fehler mit Gewichten von 1 bis 160 gleich wahrscheinlich sind, d. h. also dass nach einem Angriff jedwede Bitkombination eines Datenbitvektors mit der Länge 160 Bit gleich wahrscheinlich auftritt.

Auf Basis dieser Annahme werden im Folgenden kurz die Sicherheitsanforderungen für eine effiziente Fehlererkennung und Fehlerkorrektur diskutiert. Zunächst wird angenommen, dass ein Angreifer einen automatisierten Angriff durchführt, wobei er 10 Fehlerattacken pro Sekunde durchführen kann und die Angriffe kontinuierlich über den Zeitraum eines Monats laufen lässt, wodurch sich eine Gesamtzahl von 10·30·24·3600 = 2,59·107 < 225

Angriffen ergibt. Die Wahrscheinlichkeit, dass ein einzelner Angriff nicht erkannt wird, ist 1:232. Somit ist die Wahrscheinlichkeit dass ein Angriff innerhalb eines ganzen Monats nicht entdeckt wird weniger als 1%, wenn man oben geschildertes Angriffsszenario betrachtet.

Im Folgenden wird eine kurze Übersicht über verschiedene Möglichkeiten, ein Fehlerkorrekturverfahren zu implementieren, gegeben. Zunächst sollen dabei im Detail die linearen Fehlercodes betrachtet werden. Bei einem systematischen Code sind k Informationsbits a1a2...ak mittels n – k Kontroll- oder Checkbits ak+1ak+2...an angereichert, um ein Codewort c = a1a2...an der Länge n zu formen. Es gilt also

Die Menge C aller Codeworte ist eine Untermenge von IF, wobei IF2 = {0,1} die Menge der binären Zahlen ist. Wenn C ⫅ IF ein linearer Unterraum von IF mit der Dimension k ist, spricht man von einem (binären systematischen) linearen (n, k)-Code. Im Folgenden werden solche Codes behandelt, bei denen n = 160 und k = 128 ist. Für Illustrationszwecke wird ferner ein vereinfachendes Beispiel eines linearen (n, k)-Codes mit n = 7 und k = 4 verwendet. Ein linearer (n, k)-Code kann eindeutig mittels seiner Paritätsprüfmatrix (parity check matrix) H beschrieben werden. Die Paritätsprüfmatrix H ist eine binäre (n – k) × n Matrix mit Rang n – k. Sie hat die Form H = (A, In–k), wobei In–k die (n – k) × (n – k) Einheitsmatrix ist. Der Zeilenvektor c ∈ IF ist ein Codewort wenn und nur wenn HcT = 0.

Hier bedeutet cT das Transponierte von c. Wenn c ein Zeilenvektor ist, dann ist cT ein Spaltenvektor.

Als Beispiel dient ab jetzt ein linearer (7, 4)-Code der durch seine Paritätsprüfmatrix definiert wird. Man bemerkt, dass die ersten vier Spalten von H eine Matrix A bilden, wobei die letzten drei Spalten die Einheitsmatrix I3 bilden. Man kann leicht überprüfen, dass c = (1, 1, 0, 0, 1, 0, 0) ein Codewort ist, da HcT = (0, 0, 0)T gilt, das Ergebnis vorhergehender Operation also der Nullvektor ist.

Im Folgenden soll der Vorgang des Bildens des Redundanzwortes, des so genannten Encodens näher beschrieben werden. Wenn H = (A, In–k) die Paritätsprüfmatrix eines binären linearen (n, k)-Codes ist, nennt man die k × n Matrix G = (Ik, AT) die kanonische Erzeugermatrix des Codes. Das Encoden des Datenwortes a = a1a2...ak in das korrespondierende Codewort c = a1a2...akak+1...an wird mittels einer Matrixmultiplikation aG = c durchgeführt. Dies ist gleichbedeutend mit

Das vorhergehende Beispiel aufgreifend ist für die Paritätsprüfmatrix H des Beispiels die korrespondierende kanonische Erzeugermatrix G also die 4 × 7 Matrix

Das Datenwort (a1, a2, a3, a4) ∈ IF wird also durch folgende Operation in das Codewort encodet: c = (a1, a2, a3, a4)G = (a1, a2, a3, a4, a1 + a3 + a4, a1 + a2 + a3, a1 + a2 + a3)

Dies ist gleichbedeutend damit, dass aus den Informationsbits a1a2a3a4 die korrespondierenden Kontrollbits gemäß folgender Vorschrift berechnet werden:

Bemerkung: Man beachte, dass die Paritätsprüfmatrix H eine gleiche Anzahl von Einsen in jeder ihrer drei Zeilen hat. Diese Eigenschaft ist für eine effiziente Hardwareimplementierung der Prozedur des Encodens gewünscht. Genau dann ist es nämlich der Fall, dass die Berechnung eines jeden der (n – k) Kontrollbits die gleiche Anzahl von XOR-Verknüpfungen benötigt, d. h. die gleiche logische Tiefe hat. Eine andere wünschenswerte Eigenschaft ist, dass H dünnbesetzt ist, wobei eine binäre Matrix H dünnbesetzt genannt wird, wenn sie relativ wenige Einsen aufweist.

Im Folgenden wird der Vorgang des Decodens, also des Überprüfens eines zu überprüfenden Datenwortes auf eine Veränderung hin näher betrachtet, wie er in dem erfindungsgemäßen Ausführungsbeispiel in 1 von der Kontrolleinheit 14 durchgeführt wird.

Es seien x, y für die folgenden Betrachtungen zwei binäre Vektoren. Der Hamming-Abstand d(x, y) zwischen x und y ist die Anzahl derjenigen Koordinaten in denen x und y sich unterscheiden. Das Hamming-Gewicht w(x) von x ist die Anzahl der Koordinaten des Vektors x, die nicht 0 sind. Demzufolge ist also w(x) = d(x, 0) und d(x, y) = w(x – y).

Wenn C einen Code bezeichnet, dann nennt man die Zahl den minimalen Abstand von C.

Der minimale Abstand eines linearen Codes C ist das minimale Gewicht (Hamming-Gewicht) eines jeden Codewortes, das nicht 0 ist. Also gilt:

Wenn H die Paritätsprüfmatrix eines linearen Codes ist, dann und nur dann hat der Code einen minimalen Abstand d, wenn alle d – 1 Spalten von H linear unabhängig sind und alle d Spalten linear abhängig sind.

Dies ist im Fall von binären Codes äquivalent zur Definition des minimalen Abstandes d, wie sie im Vorhergehenden getroffen wurde. Diese Eigenschaften werden im Folgenden wiederum auf das oben eingeführte Beispiel angewendet, wobei die Paritätsprüfmatrix H betrachtet wird. Jedwede Kombination von drei Spalten von H sind linear unabhängig, wobei je vier Spalten linear abhängig sind. Somit hat der zu der Matrix H korrespondierende lineare Code den minimalen Abstand d = 4.

Ein linearer Code mit einem geradzahligen minimalen Abstand d kann gleichzeitig (d – 2)/2 Fehler korrigieren und d/2 Fehler erkennen.

Angenommen die Nachricht a ∈ IF wurde in das Codewort c ∈ IF codiert und danach über einen rauschbehafteten Kanal übertragen (oder in einem Massenspeicher abgelegt). Empfangen wird der Vektor y ∈ IF. Wenn während der Übertragung (oder der Speicherung) weniger als (d – 1)/2 Fehler auftreten, kann auf der Seite des Empfängers das korrekte Codewort c aus y rekonstruiert werden. Um dies zu erreichen ist das so genannte Syndrom vonnöten.

Das Syndrom ist wie folgt definiert: Es sei H die Paritätsprüfmatrix eines linearen (n, k)-Codes C. Dann nennt man den Spaltenvektor S(y) = HyT der Länge n – k das Syndrom von y ∈ IF.

Aufgrund der Definition der Paritätsprüfmatrix H ist y ∈ IF ein Codewort dann und nur dann, wenn S(y) der Nullvektor ist.

Daraus folgt auch, dass für einen binären Code das Syndrom gleich der Summe derjenigen Spalten der Paritätsprüfmatrix H ist, in denen Fehler aufgetreten sind. So erklärt sich auch der Name Syndrom von S(y), da das Syndrom die Symptome der Fehler (errors) angibt.

Im Folgenden soll obige Erkenntnis auf den linearen (7, 4)-Code unseres Beispiels, der durch die Paritätsprüfmatrix definiert ist, angewendet werden. Dazu werde zunächst angenommen, dass der Vektor y = (1, 0, 1, 0, 0, 0, 1) empfangen wird. Die Berechnung des Syndroms ergibt folgendes Ergebnis:

Das Syndrom S(y) stimmt mit dem zweiten Spaltenvektor der Matrix H überein, was anzeigt, dass die zweite Koordinate von y fehlerhaft ist. Also ist das korrekte Codewort c = (1, 1, 1, 0, 0, 0, 1) und die Informations-tragenden Bits sind 1110.

Bei dem Code, der in dem erfindungsgemäßen Ausführungsbeispiel weiter unten beschrieben wird, werden die Submatrizen, die die Paritätsprüfmatrix eines linearen Codes bilden, durch zirkulante Matrizen gebildet, weswegen die für die Erfindung relevanten Eigenschaften der zirkulanten Matrizen im Folgenden kurz diskutiert werden.

Eine zirkulante Matrix der Ordnung n ist eine quadratische n × n-Matrix, die vollständig durch ihre erste Zeile bestimmt ist. In jeder auf die erste Zeile folgenden Zeile werden die einzelnen Matrixelemente genau eine Position nach rechts geschoben, wobei die rechts aus der Matrix herausbewegten Matrixelemente auf der linken Seite wieder in die Reihe eingefügt werden. Zum Beispiel ist also: eine zirkulante Matrix der Ordnung 5. Für diese Matrix wird im Folgenden ebenso die Notation Z = [a, b, c, d, e] verwendet.

Wenn A und B zwei zirkulante Matrizen der Ordnung n sind, dann ist das Produkt C = AB wiederum eine zirkulante Matrix der Ordnung n.

Die Menge aller nicht singulären (d. h. invertierbaren) binären n × n-Matrizen bilden eine Gruppe unter Matrix-Multiplikation, die allgemeine lineare Gruppe GL(n, IF2). Die Menge aller binären nicht singulären zirkulanten Matrizen ist eine Untergruppe von GL(n, IF2). Wenn A eine nicht singuläre binäre zirkulante n × n-Matrix ist, dann gibt es mindestens eine positive ganze Zahl e, sodass Ae = In, wobei In die n × n-Einheitsmatrix bezeichnet. Daraus folgt, dass Ae –1 das Inverse der Matrix A sein muss, das auch mit A–1 bezeichnet wird.

Eine Eigenschaft der zirkularen Matrizen ist, dass das Inverse einer nicht singulären zirkulanten Matrix wiederum eine zirkulante Matrix ist. Die Berechnung des Produktes einer zirkulanten Matrix A und eines Spaltenvektors u kann mittels einer Logikschaltung in Hardware Platz- und Strom sparend implementiert werden. Es sei Au = x, also

Dies ist gleichbedeutend mit

Um obige Gleichungen in Hardware zu implementieren, benötigt man ein Register mit n Flip-Flops, das die Einträge der Koordinaten von u enthält. Jedes Flip-Flop hat einen Ausgang, der mit einem Konstanten-Multiplizierer verbunden ist. Dieser Konstanten-Multiplizierer hat einen Eingang und liefert als Ergebnis einer Operation das Produkt des Eingangs mit einer binären Konstante ai. Die Ausgänge aller n Konstanten-Multiplizierer werden miteinander XOR'iert, um so ein gemeinsames einziges Ergebnis zu erzeugen.

Am Beginn einer Matrizenoperation, wie sie oben dargestellt ist, wird das Register mit den Datenbits u1, u2,..., un gefüllt. Daher wird das durch obige Hardware beschriebene produzierte Ergebnis x1 sein. Im nächsten Schritt werden die Inhalte der Flip-Flops um eine Position nach links rotiert, sodass das Register nunmehr die Binärzahlen

u2, u3,..., un, u1

enthält. Das Ergebnis obiger Hardwareanordnung wird bei diesem Schritt also x2 sein. Dieser Vorgang wird wiederholt bis alle Koordinaten x1, x2,..., xn berechnet wurden.

In den folgenden Absätzen wird als ein spezielles Ausführungsbeispiel der vorliegenden Erfindung ein speziell konstruierter Code, der innerhalb der Redundanzeinheit 12 und der Kontrolleinheit 14 zur Anwendung kommt, beschrieben. Spezielle Designschwerpunkte waren dabei die Möglichkeit, den Code effizient in Hardware zu integrieren und bei Ausführung des Codes in der Redundanzeinheit und der Kontrolleinheit 14 einen möglichst geringen Stromverbrauch zu verursachen. Auf die Verwirklichung dieser speziellen Anforderung wird an gegebener Stelle noch besonders eingegangen.

Der erfindungsgemäße Code (ECC 160) ist ein spezieller systematischer linearer (160, 128, 4) -Code. Das bedeutet also, dass 128 Informationstragenden Bits 32 Kontrollbits beigeordnet sind, um zusammen ein Codewort der Länge 160 zu bilden. Der Hamming-Abstand zwischen einzelnen Codeworten ist mindestens 4. Die Paritätsprüfmatrix H = (A, I32) ist eine 32 × 160-Matrix, wobei I32 die 32 × 32-Einheitsmatrix beschreibt. H hat also 32 Zeilen und 160 Spalten. Die 32 × 128-Matrix A ist von der Gestalt A = (A0, A1, A2, A3), wobei für jedes j = 0, 1, 2, 3 die Submatrix Aj eine nicht singuläre dünnbesetzte zirkulante 32 × 32-Binärmatrix ist, die die Eigenschaft hat, dass A = I32. Diese Eigenschaft bedeutet, dass Aj identisch mit seinem Inversen A ist (idempotenz). Die Matrizen Aj sind dabei A0 = [10000100 00000000 00000100 00000000], A1 = [10000010 00000000 00000010 00000000], A2 = [10000001 00000000 00000001 00000000], A3 = [10000000 10000000 00000000 10000000], wobei die Konvention benutzt wurde, dass zirkulante Matrizen eindeutig durch Angabe ihrer ersten Zeile dargestellt werden können, wie im vorigen Absatz dargelegt wurde. Die Matrizen Aj werden dabei aus der Auswahl idempotenter zirkulanter Matrizen Pi, 0 ≤ i ≤ 14 ausgewählt, die in den 4a bis 4d angegeben sind.

Die 4a bis 4d zeigen dabei die 15 möglichen zirkulanten nicht singulären dünn besetzten 32 × 32 Binärmatrizen, die die Eigenschaft aufweisen, idempotent zu sein. Wie es anhand einer ersten Zeile 100 der Matrix P0 und einer zweiten Zeile 102 der Matrix zu sehen ist, entsteht eine der ersten Zeile 100 nachfolgende Zeile 102 der Matrix dadurch, dass die Einträge der zweiten Matrixzeile 102 gegenüber den Einträgen der ersten Matrixzeile 100 um jeweils eine Position nach rechts verschoben sind. Für den erfindungsgemäßen Code werden aus den möglichen Matrix folgende Matrizen ausgewählt:

A0 = P4, A1 = P5, A2 = P6, und A3 = P7.

Für die folgenden mathematischen Betrachtungen werden die folgenden Konventionen die Notation betreffend verwendet werden. Wenn v = (v0, v1,..., vn–1) ein Zeilenvektor ist, dann ist das Transponierte vT der zu v korrespondierende Spaltenvektor:

Wir schreiben für beide Fälle v ∈ IF und vT ∈ IF. Des Weiteren gilt, dass wenn A eine m × n-Matrix ist, das Transponierte von A, also AT, eine n × m-Matrix ist, deren j-te Spalte die Transponierte der j-ten Reihe von A ist, wobei 1 ≤ j ≤ m.

Dies soll anhand des folgenden Beispiels verdeutlicht werden:

Die grundlegenden anhand des ECC 160-Codes von der Redundanzeinheit 12 und der Kontrolleinheit 14 durchzuführenden Verarbeitungsschritte werden nun in den nachfolgenden Abschnitten dargestellt.

Zunächst wird das Encoden einer Nachricht mittels Kontrolleinheit 12 dargestellt, das in dem Zustandsdiagramm in 2 durch die Redundanzbildung 46 und die darauf folgende Gesamtbitvektorerzeugung 48 schematisch dargestellt ist. Als Beispiel dient eine Nachricht m ∈ IF, die aus vier 32-Bit-Worten besteht: m = (m0, m1, m2, m3)

Encoden bedeutet dabei, ein weiteres 32-Bit-Wort r zu berechnen, das man das Redundanzwort bzw. den Kontrollbitvektor 40 nennt, und das darauf folgende Anknüpfen des Redundanzwortes an die Nachricht m (bzw. den Datenbitvektor 38), um den Gesamtbitvektor 42 zu bilden. Der daraus resultierende 160-Bit Zeilenvektor c = (m, r) = (m0, m1, m2, m3, r), wird Codewort genannt. Das Redundanzwort r der Nachricht m wird gemäß folgender Formel berechnet:

Diese lässt sich alternativ auch folgendermaßen darstellen: r = m0AT0 + m1AT1 + m2AT2 + m3AT3.

Im Folgenden wird erläutert, wie von der Redundanzeinheit 12 überprüft wird, ob es sich bei einer empfangenen, 160 Bit langen Nachricht um ein Codewort handelt oder nicht. Dabei sind in einer idealen Welt, in der es keine zufälligen Bitfehler und keine Angreifer gibt, die mutwillig Fehler hervorrufen, alle innerhalb eines Mikroprozessor auftretenden Datenworte Codeworte. Tritt nun entweder ein 1-Bit-Fehler an beliebiger Stelle eines von der Redundanzeinheit 12 encodeten und in der Ver-/Entschlüsselungseinheit 20 verschlüsselten Datenwortes im Massenspeicher 22 oder ein 1-Bit-Fehler in einem beliebigen Bit der 160 Bit einer Nachricht y, beispielsweise im Cache 16, auf, dann wird dieser Fehler von dem Code ECC 160 erkannt und korrigiert. Größere Fehler (die beispielsweise durch eine Mikrosonde, Licht- oder Überspannungsangriffe usw. hervorgerufen wurden) werden mit einer Wahrscheinlichkeit von 1:232 erkannt.

Nehmen wir im Folgenden als 160-Bit Information y einen Zeilenvektor an, also y ∈ F.

Um zu überprüfen, ob y ein Codewort ist, wird von der Kontrolleinheit 14 das Syndrom S(y) von y, bzw. der Syndrombitvektor 58 berechnet, der ein 32-Bit Spaltenvektor ist. Der Vektor y ist genau dann ein Codewort, wenn S(y) der Null-Vektor ist. Dabei wird das Syndrom S(y) nach folgender Rechenvorschrift gebildet:

H ist die Paritätsprüfmatrix, wie sie in den vorhergehenden Abschnitten eingeführt wurde. Es gilt also folgender Zusammenhang:

Um die Wahrscheinlichkeit, mit der ein Angriff auf das System von dem Code nachgewiesen werden kann, besser zu verstehen, wird im Folgenden die Auswirkung auf ein System, die ein in das System eingebrachter Fehlervektor hat, kurz dargestellt. Dazu geht man zunächst von einem Codewort c ∈ IF aus. Wird c als Ergebnis eines externen Angriffs in y ∈ IF geändert, dann kann man das Ändern, also den Angriff, dadurch beschreiben, dass man einen Fehlervektor e ∈ IF zu dem Codewort c addiert (= bitweise XOR'ierung). Je nach Angriffsart kann der Fehlervektor e dabei ein zufälliger Vektor sein. Somit gilt also y = c + e und man erhält bei Syndrombildung: S(y) = HyT = HcT + HeT = HeT

Demzufolge bleibt ein Fehlerangriff dann und nur dann unbemerkt, wenn der Fehlervektor e ebenfalls ein Codewort ist. Ist e ein zufälliger 160-Bit Vektor, dann ist die Wahrscheinlichkeit, dass e ein Codewort ist, 1:232.

Eine weitere Eigenschaft, die der spezielle Code gemäß des Ausführungsbeispiels der vorliegenden Erfindung aufweist, ist die Möglichkeit, auf effiziente und schnelle Art und Weise einen 1-Bit-Fehler korrigieren zu können. Tritt ein 1-Bit-Fehler innerhalb der 160 Bits der Nachricht y irgendwo zwischen der Ver-/Entschlüsselungseinheit 20 und der Kontrolleinheit 14 auf, kann dieser Fehler von dem erfindungsgemäßen Code ECC 160 innerhalb einer oder zwei Rechenschritte korrigiert werden.

Dies wird im Folgenden kurz erläutert werden, wobei zunächst y ∈ F. Zur Überprüfung von y wird zunächst das Syndrom S(y) = HyT ∈ IF gebildet. Ist das Syndrom ungleich dem Nullvektor und ist S(y) gleich einem der 160 Spaltenvektoren der Paritätsprüfmatrix H = (A, I32) = (h0, h1,..., h159) beispielsweise gelte S(y) = hj, kann darauf geschlossen werden, dass die Koordinate yj von y = (y0, y1,..., y159) fehlerhaft ist. Um den Fehler zu korrigieren muss lediglich yj durch yj + 1 ersetzt werden. Aufgrund der speziellen Form der Paritätsprüfmatrix H erhält man die Eigenschaft, dass im Fehlerfall das Syndrom S(y) einer der 160 Spalten der Matrix H entspricht. Die Lokalisierung dieser speziellen Spalte innerhalb einer oder zwei Rechenschritte möglich, wenn man eine spezielle Logik zusätzlich in Hardware integriert.

Im Folgenden wird auf die Korrektur von 1-Bit-Fehlern, wie sie im Massenspeicher 22 auftreten, näher eingegangen, wobei diese 1-Bit-Fehler von der Kontrolleinheit 14 korrigiert werden können.

Für die folgenden Betrachtungen wird von einem Codewort c = (m0 + m1, m2, m3, r) ∈ F1602 ausgegangen. In einem nicht-flüchtigen Speicher 22 (NVM, RAM oder ROM) ist eine verschlüsselte Version des Codewortes gespeichert, wobei das Codewort von der Ver-/Entschlüsselungseinheit 20 (MED) verschlüsselt wurde. Für die hier gemachten Betrachtungen soll die Verschlüsselung den Raum IF auf sich selbst abbilden, was bedeutet: MED : a ∈ IF322 ⟼ MED(a) ∈ IF322.

Dabei soll von jetzt an MED–1 den zum Verschlüsseln inversen Vorgang der Ver-/Entschlüsselungseinheit 20 bezeichnen. Der Vorgang, in dem die MED auf ein Argument a ∈ IF angewendet wird, wird Verschlüsselung genannt. Die dazu inverse Operation, also die Anwendung von MED–1 auf ein Argument b ∈ F wird Entschlüsselung genannt.

Dabei ist ein bedeutendes sicherheitsrelevantes Merkmal der MED der so genannte Lawineneffekt: Wenn zwei Argumente a und a' in nur einer ihrer Bitpositionen unterschiedlich sind, dann werden MED (a) und MED (a') in etwa der Hälfte ihrer Bits unterschiedlich sein. Dazu äquivalent werden sich, wenn b und b' aus IF in einem Bit unterschiedlich sind, MED–1(b) und MED–1(b') im Allgemeinen in einer Anzahl von Bits unterscheiden, die im Mittel 16 ist.

Das Codewort c = (m0, m1, m2, m3, m4) ∈ IF mit m4 = r wird verschlüsselt indem die MED-Funktion auf jedes einzelne Wort mj ∈ IF separat angewendet wird. Dadurch wird während des Transferschritts 50 aus einem Gesamtbitvektor 42 ein verschlüsselter Gesamtbitvektor 44. Demzufolge wird der folgende Datenvektor in einem nicht-flüchtigen Speicher gespeichert werden: (MED(m0), MED(m1), MED(m2), MED(m3), MED(m4))

Hin und wieder wird es zu einem zufälligen 1-Bit-Fehler, einem so genannten „moving bit error" kommen. Da dies ein sehr selten auftretender Fall ist, kann man annehmen, dass in den meisten solcher Fälle lediglich ein einzelnes Bit der 160 Bit der gespeicherten Information verändert wird. Im Folgenden wird davon ausgegangen, dass ein Wort aus obiger Gleichung einen 1-Bit-Fehler aufweist, wobei die anderen vier Worte korrekt sind. Wird der oben beschriebene 160-Bit-Zeilenvektor gelesen, wird er von der MED entschlüsselt und die Kontrolleinheit 14 erhält den folgenden 160-Bit-Vektor als entschlüsselten Gesamtbitvektor 56: y = (y0, y1, y2, y3, y4)

Für vier der Indizes j ∈ {0, 1, 2, 3, 4} gilt, dass die ursprünglichen Datenworte den gelesenen und entschlüsselten Datenworten entsprechen, also dass yj = mj, jedoch gibt es einen Index j für den yj ≠ mj. Aufgrund des oben beschriebenen Lawineneffektes unterscheiden sich yj und mj in mehr als einer Bitposition.

Zur Überprüfung durch die Kontrolleinheit 14 wird zunächst angenommen, dass y ein aus der Ver-/Entschlüsselungseinheit 20 kommender, entschlüsselter Gesamtbitvektor 56 nach einer Leseoperation ist. Zunächst wird das Syndrom S(y) berechnet. Ist S(y) = 0, wird davon ausgegangen, dass kein Fehler, insbesondere kein moving bit error, aufgetreten ist. Ist S(y) ≠ 0, gibt es prinzipiell zwei Möglichkeiten:

  • i) es ist ein moving bit error aufgetreten;
  • ii) es sind mehrere Fehler aufgetreten, wahrscheinlich als Ergebnis eines Angriffs auf das System.

Um zu entscheiden, was der Fall ist und um in dem Fall i) den moving bit error zu korrigieren, wird von der erfindungsgemäßen Vorrichtung wie folgend beschrieben vorgegangen. Zunächst wird dabei von der Hypothese ausgegangen, dass ein moving bit error in dem gespeicherten Wort MED(r) aufgetreten ist. Dann ist y4 ≠ r, jedoch auch yj = mj für alle j = 0, 1, 2, 3.

Daher wird von der erfindungsgemäßen Vorrichtung folgender Algorithmus abgearbeitet:

  • 1. Berechne x4 = (y0, y1, y2, y3)AT.
  • 2. Berechne MED(x4) und MED(y4).
  • 3. Berechne d = dist(MED(x4), MED(y4)).
  • (Es sei hier daran erinnert, dass für u, v ∈ IF, dist (u, v) den Hamming-Abstand zwischen u und v bezeichnet.)

Ist d = 1, ist die oben gemachte Hypothese bestätigt. In diesem Fall wird y4 durch x4 ersetzt, um das dann korrigierte Codewort c[4] = (y0, y1, y2, y3, y4)∈ IF1602 zu erhalten, wodurch der moving bit error also korrigiert wurde.

Falls d ≠ 1, muss die obige Hypothese verworfen werden. Als nächste Hypothese wird dann angenommen, dass ein moving bit error in MED(m0) aufgetreten ist, sodass y0 ≠ m0 und yj = mj für alle j = 1, 2, 3, 4.

Der abzuarbeitende Algorithmus lautet dann wie folgt:

  • 1. Ersetze in (y0, y1, y2, y3) das Wort y0 durch das Nullwort 0 ∈ FZ und berechne q = (0, y1, y2, y3)AT.
  • 2. Berechne b = q + r wobei r = y4.
  • (Das „+" Zeichen beschreibt dabei die bitweise Addition modulo 2, d. h. bitweise XOR'ierung.)
  • 3. Berechne x = A0bT, wobei A0 die 32 × 32 Submatrix aus der Paritätsprüfmatrix H ist.
  • 4. Berechne MED(x0) und MED(y0).
  • 5. Berechne d = dist(MED(x0), MED(y0)).

Ist d = 1 ist die Hypothese bestätigt. In diesem Fall wird das Datenwort y0 durch x0 ersetzt und man erhält als rekonstruierten 160-Bit-Zeilenvektor c[0] = (x0, y1, y2, y3, y4) ∈ IF1602

c[0] ist also ein Codewort und der moving bit error wurde korrigiert. Ist d ≠ 1 muss die Hypothese verworfen werden.

Sollte es notwendig sein, wird der oben beschriebene Algorithmus für alle j = 1, 2, 3 durchgeführt, wobei die offensichtlichen Anpassungen zu treffen sind. Zum Beispiel wird im Fall j = 1 die Hypothese gemacht, dass ein moving bit error in MED(m1) aufgetreten ist. Im ersten Schritt des obigen Algorithmusses wird nun innerhalb des Wortes (y0, y1, y2, y3) y1 durch das Nullwort 0 ersetzt. Im dritten Schritt wird dann die Submatrix A1 (anstelle von A0) benutzt und der daraus errechnete Vektor ist x1.

Sollte die Hypothese wiederum nicht bestätigt werden können, werden die dazu analogen Hypothesen für j = 2 und j = 3 überprüft. Sollten alle (5) Hypothesen falsch sein, wird darauf geschlossen, dass ein multi bit error, also ein gleichzeitiges Verändern mehrerer gespeicherter Datenbits, aufgetreten ist, was hoher Wahrscheinlichkeit nach die Folge eines Angriffs ist.

Der erfindungsgemäße Code hat zusätzlich die wichtige Eigenschaft, dass er das Verändern mehrerer einander benachbarter Bits sicher erkennen kann.

Um dies zu verifizieren betrachtet man zunächst die 32 × 160 Paritätsprüfmatrix H = (A, I32) = (h0, h1,..., h159), die gemäß der in vorherigen Abschnitten gemachten theoretischen Annahmen den Code ECC 160 vollständig beschreibt. Man kann zeigen, dass jedwede Kombination von k ≤ 32 aufeinander folgenden Spaltenvektoren hj der Matrix H linear unabhängig sind. Das heißt in anderen Worten, dass für jedes 0 ≤ i ≤ 159 und für jedes 1 ≤ k ≤ 32 der Satz von Spaltenvektoren

{hi, hi+1,..., hi+k–1} (mit Indizes modulo 160) niemals eine Untermenge von Spaltenvektoren enthält, die sich zu dem Nullvektor addieren.

Diese bemerkenswerte Eigenschaft der Paritätsprüfmatrix H impliziert, dass der ECC 160 mit absoluter Sicherheit jeden burst error der Länge ≤ 32 erkennen kann. Das bedeutet in anderen Worten, dass wenn in einem Codewort c = (c0, c1,..., c159) maximal k ≤ 32 Bits fehlerhaft werden und wenn das erste und das letzte fehlerhafte Bit nicht weiter als 32 Positionen auseinander liegen, das Vorhandensein eines e ∈ IF mit absoluter Sicherheit erkannt wird. In diesem Fall wird das Syndrom S(y) von y = c + e nicht 0 sein.

Die Fähigkeit, burst error zu detektieren, ist ein wesentliches Merkmal des Codes. Um dies zu verdeutlichen betrachten wir ein Codewort c = (m0, m1, m2, m3, r) ∈ IF, das über einen Datenbus der aus 32 Datenpfaden besteht, übertragen wird. Dabei werden nacheinander die Datenwörter m0,..., m3 ∈ IF und das Redundanzwort r ∈ IF übermittelt. Wenn durch eine Licht-, Laser- oder Überspannungsattacke ein einzelnes Wort auf zufällige Art und Weise verändert wird, während die anderen vier Worte unverändert bleiben, wird der Angriff durch den folgenden Syndromtest erkannt.

In einem anderen Szenario betrachten wir den Cache 16 oder den Pufferspeicher, in dem die Codeworte im Wesentlichen in einer linearen Art und Weise gespeichert sind, aufeinander folgende logische Bits also auch aufeinander folgenden physischen Bits entsprechen. Durch einen Licht- oder Laserangriff werden die Bits in so genannten Clustern, also in Gruppen nebeneinander liegender Speicherbits, verändert. So lange die Größe des Clusters auf eine Länge von maximal 32 Bit limitiert ist, wird dieser Angriff ebenfalls mit absoluter Sicherheit erkannt werden.

Der erfindungsgemäße Code hat des Weiteren die so genannte Delta-Eigenschaft, die für eine Strom sparende Implementierung des Codes in Hardware von wesentlichem Vorteil ist und im Folgenden kurz erläutert werden soll. Dazu wird ein Codewort c = (m, r) ∈ IF betrachtet. Zerlegt man die Nachricht m ∈ IF in einzelne Bytes bj ∈ IF, so kann man das Codewort auch wie folgt schreiben: c = (m, r) = (b0, b1,..., b15, r).

Ein häufig auftretender Fall ist, dass ein Byte bj der Nachricht m durch ein anderes Byte b'j ersetzt werden soll. Das Encoden des vollständigen neuen Nachrichtenblocks m' = (b0,..., bj–1, b'j, bj+1,..., b15) liefert das neue Codewort c' = (m', r') = (b0,..., bj–1, b'j, bj+1,..., b15, r').

Die Aufgabe, die es zu lösen gilt ist, wie sich das Redundanzwort r' auf eine weniger Strom verbrauchende Art und Weise berechnen lässt.

Zunächst gilt r = mAT und r' = m'AT.

Also, r' = m'AT = (m' – m)AT + mAT = &Dgr;AT + r, wobei &Dgr; = m' – m = (0,..., 0, &Dgr;j, 0,..., 0) ∈ IF1282 und wobei &increment;j = b'j – bj = b'j + bj die Differenz (oder Summe, d. h. bitweise XOR'ierung) des alten und des neuen Bytes ist.

Im Folgenden wird dargelegt, wie die Deltaeigenschaft des ECC 160 Codes in Form eines Algorithmusses in die erfindungsgemäße Hardware implementiert ist.

Ausgegangen wird dabei von einem Codewort c = (m, r), bei dem das j-te Byte bj des Nachrichtenblockes m durch das Byte b'j ausgetauscht wird, woraufhin das Redundanzwort aktualisiert werden soll. Dazu sind folgende Schritte erforderlich:

  • 1. Berechne &Dgr;j = bj + b'j.
  • 2. Berechne s = (0,..., 0, &Dgr;j, 0,..., 0)AT.
  • 3. Berechne r' = s + r.

Das Datenwort r' ist dann genau das aktualisierte Redundanzwort.

Dies kann mathematisch auch anders formuliert werden. Dazu werden die 32 × 32 Matrizen A0, A1, A2, A3, die in der Paritätsprüfmatrix H auftreten, in 32 × 8 Submatrizen Bj so unterteilt, dass

A0 = (B0, B1, B2, B3), A1= (B4, B5, B6, B7),

A2 = (B8, B9, B10, B11), A3= (B12, B13, B14, B15),

Dann kann man schreiben: wobei die B 8 × 32 Matrizen sind. Der Vektor s ∈ IF, der in der Implementierung der Delta-Eigenschaft erforderlich ist, kann dann folgendermaßen berechnet werden:

Die Designkriterien, die für die Entwicklung des ECC 160-Codes wichtig waren, sind, dass die Implementierung des Codes in Hardware eine geringe Fläche auf dem Chip beansprucht und dass der Code während des Betriebs nur einen geringen Stromverbrauch hervorruft. In der Tat gibt es keinen linearen (160, 128)-Code mit minimalem Hamming-Abstand von d = 4, dessen Implementierung weniger Chipfläche beansprucht (d. h. dessen Paritätsprüfmatrix weniger Einsen enthält) oder dessen Betrieb (Encodieren und Syndromberechnung) weniger Stromverbrauch hervorruft. Es gibt allerdings einen linearen (160, 128)-Code mit minimalem Hamming-Abstand d = 2, der auf einer geringeren Chipfläche implementiert werden kann und der weniger Strom verbraucht, als der ECC 160-Code. Dieser Code wird durch die folgende Paritätsprüfmatrix definiert:

H =(I32, I32, I32, I32, I32) wobei I32 die 32 × 32 Einheitsmatrix bezeichnet. Für diesen speziellen Code wird das Redundanzwort r ∈ IF durch XOR'ierung der vier Datenwörter m0,..., m3 erhalten, es ist also r = m0 + m1 + m2 + m3.

Dieser Code bietet jedoch nur sehr geringen Schutz gegen Angriffe, bei denen einzelne Busleitungen abgehört bzw. verändert („forcing") werden. Verändert beispielsweise ein Angreifer eine Datenleitung während ein Codewort übermittelt wird, kann der Angriff nicht bemerkt werden, wenn zwei oder vier Bits geändert werden. Werden 1, 3 oder 5 Bits geändert, wird ein nachfolgender Syndromtest den Angriff mittels dieses Codes nachweisen können. Solch eine Attacke wird also lediglich mit einer Wahrscheinlichkeit von 3/5 = 60% detektiert. Im Gegensatz dazu kann der ECC 160-Code einen oben beschriebenen Angriff mit absoluter Sicherheit durch einen Syndromtest nachweisen. (Aufgrund der speziellen Struktur der Paritätsmatrix H = (h0, h1,..., h159), die den ECC 160-Code definiert sind, alle Untermengen der Form {hj, hj+32, hj+64, hj+96, hj+128} mit 0 ≤ j ≤ 31 linear unabhängig.)

Im Folgenden sollen die Kriterien, die zur Konstruktion des erfindungsgemäßen Codes zu beachten waren, im Hinblick auf deren Hardwareimplementierung näher erläutert werden.

Die wesentlichen Charakteristiken eines Fehlerkorrekturcodes sind die Codedimension k, die Codelänge m, der Codeabstand dmin, die Fehlerkorrekturfähigkeit t, die Codeeffizienz r und die Wahrscheinlichkeit, einen Fehler nicht zu detektieren pu. Die Zahl der Prüfbits m berechnet sich zu m = n – k.

Die Codeeffizienz ist als das Verhältnis der Zahl der Prüfbits zur Zahl der Nachrichtenbits definiert, d. h. sie ist ein Maß für den Overhead, der sich aufgrund des Schutzes ergibt. Die erste Anforderung an einen Code ist, dass er in einer systematischen Form beschrieben werden kann. Das bedeutet, dass jedes einzelne Codewort c in eine Form c = (m, p) separierbar sein muss, wobei m der Nachrichtenbitvektor und p der Korrekturbitvektor ist.

Des Weiteren nehmen wir an, der Code bestehe aus Elementen von F2. Im Allgemeinen werden binäre Codes für effiziente Hardwareimplementierungen bevorzugt, da Codes, die auf anderen zugrunde liegenden Datenmengen beruhen, normalerweise die Implementierung von teurer Galois-Feld Arithmetik bedingen. Aus demselben Grund werden lineare Codes bevorzugt.

Die Gesamtanzahl der Nummer von Einsen in jeder einzelnen Reihe der Paritätskontrollmatrix H steht in direkter Beziehung zu der Logiktiefe des Schaltkreises, der in einer Hardwareimplementierung dazu benutzt wird, das Kontrollbit oder das Syndrombit der betreffenden Zeile zu bilden. Ist ei die Gesamtanzahl der Einsen in der i-ten Reihe, so ist die Logiktiefe des Schaltkreises, der ein Prüfbit errechnet, durch folgende Formel gegeben: lc(i) = ⌈ logp(ei – 1)⌉.

Die Logiktiefe des Syndrombit-Schaltkreises ist dann durch ls(i) = ⌈ logp(ei)⌉ gegeben, wobei p die Anzahl der Eingänge der XOR-Zellen beschreibt, die in der Hardwareimplementierung verwendet werden (z. B. 2 oder 3).

Dies bedeutet für eine Hardwareimplementierung der Paritätsprüfmatrix H, dass minimale Hardwarekosten, ein minimaler Stromverbrauch und eine minimale Abarbeitungszeit durch eine Minimierung der Anzahl von Einsen in jeder Reihe der Paritätsprüfmatrix erreicht werden kann.

Eine zweite Anforderung ist, dass die Anzahl von Einsen in jeder Reihe so nah wie möglich an der durchschnittlichen Anzahl von Einsen pro Reihe liegt. Dieses Gleichverteilen der Einsen stellt sicher, dass kein langer, kritischer Abarbeitungspfad in dem encodierenden oder das Syndrombit berechnenden Schaltkreis auftritt.

Generell gilt: Wenn C ein linearer Code mit zugeordneter Paritätsprüfmatrix H ist, dann ist der Hamming-Abstand von C gleich der kleinsten Anzahl von Spalten von H, die sich zum Nullvektor addieren.

Für den Fall dass jede Spalte von H eine ungerade Anzahl von Einsen enthält, folgt aus obiger Aussage, dass der Hamming-Abstand des Codes mindestens 4 sein muss. Codes, die den drei obigen Prinzipien folgen (minimale Anzahl von Einsen, gleiche Anzahl von Einsen in jeder Reihe der Matrix H, ungerade Anzahl von Einsen in jeder Spalte der Matrix H), nennt man Hsiao Codes. Diese Codeklasse garantiert somit eine optimale Effizienz bei Integration in eine Computerhardware.

Eine weitere Konsequenz obiger allgemeiner Aussage ist, dass ein größerer Hamming-Abstand eines Codes generell zu einer größeren Anzahl von Einsen in einer Paritätsprüfmatrix führt (obwohl es keinen strengen mathematischen Zusammenhang gibt).

Der erfindungsgemäße Code folgt obigen Prinzipien und hat zusätzlich die Delta-Eigenschaft und ist darüber hinaus MED kompatibel, Eigenschaften die für eine Strom- und Platzsparende Implementierung in Sicherheitscontroller zwingende Voraussetzung sind.

Die Codeeffizienz r des ECC 160 ist r = 25%. Sollte der daraus resultierende Overhead für eine geplante Anwendung zu groß sein, kann zusätzlich aus der erfindungsgemäßen Codefamilie ein Code implementiert werden, der eine Codeeffizienz r = 12,5% aufweist, wobei zur Konstruktion der Matrix H acht der zirkulanten Matrizen, die in den 4a4e dargestellt sind, zu verwenden sind. Die Schaltkreise zur Fehlerdetektion, zur Syndromberechnung, zur Umsetzung der Delta-Eigenschaft und zur Fehlerkorrektur müssen dann in nahe liegender Weise angepasst werden.

Die besonders hardwareeffiziente Implementierbarkeit des erfindungsgemäßen Fehlercodes ECC 160 wird im Folgenden noch einmal kurz herausgestellt.

Die Implementierung der Matrix-Multiplikation in Gleichung 1 erfordert 32 × 16 = 512 XOR-Gates mit zwei Eingängen und hat die Logiktiefe 4. Verwendet man eine Mischung aus XOR-Gates mit zwei und drei Eingängen, sind 32 × 9 = 288 Gates notwendig und die Logiktiefe reduziert sich auf 3.

Die Berechnung des Syndroms kann dabei jeweils von derselben Hardware ausgeführt werden, wobei für genaue Herleitung des Zusammenhangs auf die nachfolgenden Absätze verwiesen wird.

Die Delta-Eigenschaft und der Algorithmus zur Implementierung derselben kann ebenfalls von derselben Hardware ausgeführt werden. In diesem Fall wird lediglich eine Gruppe von acht benachbarten Zeilen der Matrix mit dem geänderten Byte multipliziert. Dabei muss aus Strombilanzgründen dafür Sorge getragen werden, dass der Teil des Schaltkreises, der den ungeänderten Bytes zugeordnet ist, nicht in einen undefinierten Zustand gerät. Kann das sichergestellt werden, wird der Stromverbrauch eines Updates eines Bytes bei Ausnutzung der Delta-Eigenschaft nur etwa 10% des Stromverbrauchs betragen, der bei dem Encoden eines gesamten Nachrichtenblocks anfällt.

In den vorhergehenden Gleichungen werden sowohl Matrizen als auch die zu den Matrizen transponierten Matrizen verwendet. Dies ist der Fall, da in den vorhergehenden Beschreibungen des erfindungsgemäßen linearen Codes so weit dies möglich ist die Standardkonventionen insbesondere im Hinblick auf die Repräsentation der relevanten Matrizen eingehalten wurden. In einer typischen Anwendung wird an einer Stelle die Matrix M und an einer anderen Stelle die zu ihr transponierte Matrix MT verwendet. Um eine effiziente Implementierung (beispielsweise in der Hardwarebeschreibungssprache VHDL des Codes zu gewährleisten, kann nur in einem bevorzugten Ausführungsbeispiel der vorliegenden Erfindung davon Abstand genommen werden, sowohl M als auch MT zu verwenden. In der Tat kann man das Verwenden der Transponierten aller Matrizen vollständig vermeiden, indem man folgende Regeln beachtet (auch wenn dadurch der zusätzliche Aufwand entsteht, dass man sowohl mit Zeilen- als auch mit Spaltenvektoren rechnen muss): (AT)T = A and (AB)T = BTAT

Unter Verwendung der obigen Gleichungen können die Formeln, die die Encodierung und den Syndromtest beschreiben, auf folgende Art und Weise umgeformt werden: rT = AmT rr = A0mT0 + A1mT1 + A2mT2 + A3mT3

In einem weiteren speziellen Ausführungsbeispiel der vorliegenden Erfindung wird der eben beschriebene ECC 160 Code modifizert. In dieser Modifikation ist die Fehlerkorrektur mittels des Codes schneller möglich, was auf Kosten eines leicht erhöhten Hardwareaufwandes ermöglicht wird. Im Folgenden wird gezeigt werden, dass es für diese Variante des Codes günstiger ist, die Paritätsprüfmatrix H aus vier dünn besetzten, zirkulanten Matrizen zu konstruieren, die nicht selbstinvers sind, sondern statt dessen jeweils zwei paarweise zueinander inverse Matrizen zu verwenden.

In den folgenden Betrachtungen ist m eine Nachricht der Dimension k = 128 Bit, die in Worten von 32 Bit Länge organisiert ist. Die Länge eines Codewortes ist n = 160 Bit und die Länge des Prüfbitvektors ist demnach n – k = 32 Bit. m = (m0, m1, m2, m3) mit mi ∈ (0, 1)32.

Die kanonische Generatormatrix dieses systematischen linearen Codes ist durch gegeben, wobei p eine 128 × 32 Matrix und Pi 32 × 32 Matrizen sind. Der Prüfbitvektor p berechnet sich aus p = m·P und das Codewort ist u = m·G = (m, p).

Die Paritätsprüfmatrix H ist also H = (–PT, In–k) = (PT0, PT1, PT2, PT3, I32).

Die Generatormatrix G ist der Nullraum der Paritätsprüfmatrix, d. h. G·HT = 0.

Wir bezeichnen das möglicherweise veränderte Codewort durch v = u + e, wobei e der Fehlervektor ist. Der Syndromvektor s wird gemäß folgender Formel errechnet: s = v·HT = (u + e)·HT = e·HT.

Wenn es keinen Fehlerbitvektor gibt, wird der Syndrombitvektor der Nullvektor 0 sein. In der folgenden Notation wird der &rgr; benutzt werden, um einen beliebigen und nicht immer denselben beliebigen Vektor aus der Menge der Vektoren (0, 1)32 zu bezeichnen.

Um den erfindungsgemäßen Code zu veranschaulichen, wird im Folgenden schrittweise zunächst die von der Redundanzeinheit 12 zu berechnende Redundanzinformation und das Speichern und Verschlüsseln durch die Ver-/Entschlüsselungseinrichtung 20 beschrieben werden.

  • 1. Berechnen des Prüfbitvektors p = m·P = m0P0 + m1P1 + m2P2 + m3P3
  • 2. Bildung des Codewortes u = (m·p) ≡ (u0, u1, u2, u3, u) = (m0, m1, m2, m3, p)
  • 3. Verschlüsseln des Codewortes unter Benutzung der MED bzw. der Ver-/Entschlüsselungseinrichtung 20. Dabei soll im Folgenden ek(x) einen Verschlüsselungsvorgang der MED bezeichnen, wobei ein 32-Bit-Wort x mit einem Schlüssel k verschlüsselt wird. Die wortweise Verschlüsselung lässt sich also folgendermaßen schreiben: uei = ek(ui) for i = 1, 2, 3, 4, 5...
  • 4. Bildung des verschlüsselten Codevektors: ue = (ue0, ue1, ue2, ue3, ue4).
  • 5. Speichern des verschlüsselten Codevektors ue in beispielsweise dem Massenspeicher 22.

Der Prozess des Lesens aus dem Speicher und des Rekonstruierens eines fehlerhaften Bits durch die Kontrolleinheit 14 wird im Folgenden ebenfalls schrittweise wiedergegeben.

Dabei wird zunächst der Fall eines korrigierbaren 1-Bit-Fehlers, z. B. eines moving Bit-Fehlers in einem nichtflüchtigen Speicher wie dem Massenspeicher 22 behandelt. Dabei wird ohne Beschränkung der Allgemeinheit angenommen, dass der 1-Bit-Fehler sich im zweiten 32-Bit-Wort an der Position f befindet. Der verschlüsselte Codevektor, bzw. der verschlüsselte Gesamtbitvektor 54, der aus dem Speicher ausgelesen wird, wird mit v bezeichnet. Er ist v = ue + e mit e = (e0, e1, e2, e3, e4) = (0, ei, 0, 0, 0) und e1 = (0,..., 0, 1, 0,..., 0).

  • 1. Lesen der verschlüsselten Nachricht v aus dem Speicher. v = (v0, v1, v2, v3, v4) = (ue0, ue1 + e1, ue2, ue3, ue4)
  • Entschlüsseln der Nachricht in dem Entschlüsselungsschritt 66 durch die MED. In Analogie zum oben beschriebenen Fall, bezeichnet dk(x) eine MED Entschlüsselung eines 32-Bit-Wortes x mittels des Schlüssels k. Also wird beim Vorgang des Entschlüsselns folgende Berechnung ausgeführt: v = dk(vi) for i = 1, 2, 3, 4, 5.
  • Für den oben beschriebenen Fehlerfall ist das Ergebnis vorstehender Operation im Besonderen: vd0 = dk(v0) = dk(ue0) = dk(ek(u0)) = m0 vd1 = dk(v1) = dk(ue1 + e1) = &rgr; vd2 = m2 vd3 = m3 vd4 = p
  • Aufgrund der perfekten Dekorrelation benachbarter Bits durch den MED-Algorithmus, wird v ein zufälliger 32-Bit langer Bitvektor sein.
  • 3. Berechnen des Syndrombitvektors 58: s = vd·HT= vd0PT0 + vd1PT1 + vd2PT2 + vd3PT3 + p = m0PT0 + &rgr;PT1 + m2PT2 + m3PT3 + p = &rgr;
  • Der Syndrombitvektor wird mit einer Wahrscheinlichkeit von p ≈ 2–32 gleich dem Nullvektor sein. Die Wahrscheinlichkeit, einen Bitfehler nicht zu detektieren ist also p ≈ 2–32.
  • 4. Herausfinden des fehlerhaften Wortes.
  • Ein nicht-trivialer Schritt ist die Lokalisierung des fehlerhaften Wortes und die Korrektur des Fehlers, da der fehlerkorrigierende Code ja vor der Verschlüsselung angewendet wird. Betrachtet man die Paritätsprüfgleichung s = v·H = 0, so kann diese Gleichung für jedes der 32-Bit-Worte der Nachricht aufgelöst werden: v'0 = (v1P1 + v2P2 + v3P3 + v4)·P–10v'1 = (v0P0 + v2P2 + v3P3 + v4)·P–11v'2 = (v0P0 + v1P1 + v3P3 + v4)·P–12v'3 = (v0P0 + v1P1 + v2P2 + v4)·P–13v'4 = v0P0 + v1P1 + v2P2 + v3P3Gleichung 2
  • In dem Substitutionsschritt 70 werden die obigen entschlüsselten substituierten Datenwortvektoren 62a62e gebildet. Man kann also aufgrund der Kenntnis von vier der fünf Datenworte das verbleibende fünfte Datenwort rekonstruieren. Die rekonstruierten Worte sind dabei mit einem Apostroph gekennzeichnet.
  • Für unser betrachtetes Beispiel erhält man als erstes 32-Bit-Wort: m'0 = (vd1P1 + vd2P2 + vd3P3 + vd4)·P–10= (&rgr;P1 + m2P2 + m3P3 + p)·P–10= &rgr;
  • Nun wird das rekonstruierte bzw. substituierte Wort wiederum verschlüsselt, m' = ek(m'0) und es wird der Hamming-Abstand von m' zu dem Wort v0, das ursprünglich aus dem Speicher gelesen wurde gebildet: d0 = d(m'e0, v0)
  • Im Beispielfall erhält man d0 = d(&rgr;, v0), wobei d0 > 1 mit einer Wahrscheinlichkeit von p ≈ 232/32 = 228.
  • Da d0 ungleich 1 ist, wird geschlossen, dass v0 nicht das Wort ist, das den Bitfehler enthält.
  • In einem nächsten Schritt wird dieselbe Prozedur für das zweite Datenwort angewendet: m'1 = (vd0P0 + vd2P2 + vd3P3 + vd4)·P–11= (m0P0 + m2P2 + m3P3 + p)·P–11= m1
  • Nun wird das rekonstruierte Wort wiederum verschlüsselt m' = ek(m'1) und der Hamming-Abstand von m' zu dem ursprünglich aus dem Speicher gelesenen Datenwort v1 berechnet: d1 = d(m'e1, v1) = d(m'e1, ue1 + e1) = d(m'e1, me1 + e1) = 1.
  • 5. Korrektur des Fehlers
  • Wegen d1 = 1 ist nun bekannt, dass der 1-Bit-Fehler in dem zweiten Datenwort lokalisiert war und man kann schlussendlich das korrigierte Wort m' an die Speicherposition des v1 schreiben.

Im allgemeinen Fall wird die Rekonstruktion der Datenwörter in dem Substitutionsschritt 70 nacheinander für m0, m1, m2, m3, m4 durchgeführt. Beim ersten Auftreten eines Hamming-Abstandes von 1 ist die Position des Fehlers bestimmt und der Prozess wird gestoppt. In dem Fall, dass kein Hamming-Abstand von 1 gefunden werden kann, ist ein Fehler, bei dem mehrere Bits gleichzeitig verändert wurden, aufgetreten, und es wird ein Angriff auf das System vermutet.

Der besondere Vorteil des erfindungsgemäßen Ausführungsbeispiels, in dem der ECC 160-Code modifiziert wird, liegt darin, dass die Korrektur fehlerhafter Daten mit einer höheren Verarbeitungsgeschwindigkeit ausgeführt werden kann weswegen für das eben beschriebene Ausführungsbeispiel der vorliegenden Erfindung die Komplexität der Hardwareimplementierung noch einmal gesondert betrachtet werden soll.

Auf den ersten Blick erscheint die Implementierung der Gleichungen 2, die die verschlüsselten substituierten Datenwortvektoren beschreiben, kompliziert, da in diesen invertierten Matrizen auftreten.

Im Folgenden soll gezeigt werden, dass die Implementierung nicht aufwendiger als die Implementierung der Berechnung des Syndrombitvektors ist. Die in den 4a4e, angegebenen zyklischen zirkulanten Matrizen des Ranges 32 haben die Eigenschaft, selbstinvers zu sein und jeweils drei Einsen in den sie bildenden Spaltenvektoren aufzuweisen. Das bedeutet, dass das Inverse der Matrizen nicht dicht ist, also eine Matrix mit vielen Einsen ergibt, wie man dies normalerweise für die Inversion einer zufällig gewählten dünnbesetzten Matrix erwarten würde. Für diese Matrizen sind die Produkte Pi·P, i ≠ j also ebenfalls dünnbesetzt. Insbesondere ist das Gewicht der 5-bändigen zyklischen Produktmatrizen 160 (für die ursprünglichen Matrizen Pi ist das Gewicht 96).

Es gibt insgesamt sechs Produktmatrizen Pi·P, i ≠ j, wobei jede Produktmatrix fünf Bänder hat, d. h. eine Anzahl von fünf Einsen in jeder Zeile aufweist. Daher ist die Komplexität der Implementierung in Hardware in etwa

(6·⌈log3(5)⌉ + 4·⌈log3(3)⌉)·32 = 512 AND 3-Gates + 4 × 32 = 128 XOR 3-Gates. Die Logiktiefe ist 3.

Eine weitere Verbesserung wird möglich, wenn man paarweise inverse Matrizen Pi benutzt. In diesem Fall gibt es lediglich vier Matrixprodukte, und man erhält eine Komplexität von (4·⌈log3(5)⌉ + 4·⌈log3(3)⌉)·32 = 384 AND 3-Gates + 4 × 32 = 128 XOR 3-Gates. Die logische Tiefe ist ebenfalls 3. Für die spezielle Ausführungsform von der vorliegenden Erfindung wird P0 = P und P2 = P gewählt.

Um eine erfindungsgemäße Vorrichtung zur Prüfung von Integrität von Daten zu implementieren, sind prinzipiell auch andere Fehlercodes möglich, wie z. B. zyklische Codes, speziell der BCH-Code und Produktcodes.

Bei Produktcodes können mächtige Codes mit größeren Hamming-Abständen aus Codes, die geringeren Hamming-Abstand haben, dadurch gebildet werden, dass man so genannte Produktcodes erzeugt. Wenn C1 ein linearer (n1, k1) Code und C2 ein linearer (n2, k2) Code ist, dann kann ein (n1n2, k1k2) Code gebildet werden, wie es in 5 dargestellt ist, wobei hier systematische Codes angenommen werden.

In 5 ist ein Datenbitblock 200 gezeigt, sowie erste Prüfbitvektoren 202 und zweite Prüfbitvektoren 204. Eine Anzahl k1 von Datenworten der Länge k2 ist in dem Datenbitblock 200 so angeordnet, dass jeweils ein Datenwort eine Zeile des Datenbitblockes m bildet und die k1 unterschiedlichen Datenworte innerhalb des Datenbitblocks 200 untereinander angeordnet sind, wie es in 5 anhand des schematisch dargestellten Datenwortes 206 ersichtlich ist. Auf den Datenblock 200 werden zwei lineare Codes C1 und C2 derart angewendet, dass jede Reihe ein Codewort der Länge n1 in C1 und jede Spalte ein Codewort der Länge n2 in C2 ist. Der rechteckige Kontrollbereich 208 in 5a beinhaltet die Prüfbits, die ein Anwenden von C1 auf die Prüfbits von C2 ergeben und umgekehrt. Der minimale Hamming-Abstand eines solchen Produktcodes ist dmin = d(1)min·d(2)min, der Code ist somit in der Lage, t = ⌊(d(1)min·d(2)min – 1)/2⌋

Fehler zu korrigieren. Eine Variation eines Produktcodes ist der so genannte unvollständige Produktcode, wie er in 5b gezeigt ist. 5b unterscheidet sich dabei von 5a dadurch, dass der Kontrollbereich 208 weggelassen ist, der daraus resultierende (k1n2 + k2n1 – k1k2, k1k2) lineare Produktcode ist schwächer und hat einen minimalen Hamming-Abstand von lediglich dmin = d + d – 1.

Ein unvollständiger Produktcode wird auch als linearer Summencode bezeichnet.

Der unvollständige Produktcode von zwei einfachen Paritätscodes (single parity code, SPC) wird gemeinhin bei industriellen RAM-Designs und in Mikroprozessoren, beispielsweise in dem Design der Register, eingesetzt. Diese Codes werden oftmals auch als horizontaler und vertikaler Paritätscode (horizontal und vertical parity code) bezeichnet. Bildet man den vollständigen Produktcode von zwei SPC's, ist der minimale Hamming-Abstand dmin = 4.

Als Beispiel für die Umsetzung von unvollständigen Produktcodes können unterschiedliche DRAM-Designs dienen. In Erweiterung durch eine in der Diagonalen gebildete Parität (cross parity) sei hier ferner das SUN Sparc Register File erwähnt.

In unserem speziellen Fall wären zwei lineare Codes, die eine Mehrzahl von Kontrollbits aufweisen, notwendig, um die hohen Anforderungen, die an den Code bezüglich des Nichtentdeckens eines Fehlers gestellt werden, zu erfüllen. Da die Datenblockgröße von 128 oder 256 Bits relativ klein ist, würde ein solcher Code einen signifikanten overhead produzieren. Um dies zu verdeutlichen sei im Folgenden eine Datenblockgröße k = 256 angenommen. Der Datenblock 200 wird dabei in einem Feld von acht Zeilen und 32 Spalten (also 32-Bit-Worten) angeordnet. Der kleinste lineare Blockcode für ein 32-Bit-Datenwort, der einen Hamming-Abstand dmin ≥ 3 unter Berücksichtigung der Hamming-Grenze ermöglicht, ist ein linearer (38, 32)-Code. Man kann zeigen, dass der kleinstmögliche Hsiao-Code ein (39, 32)-Code ist. Kombiniert man den (39, 32) Hsiao-Code, der auf die Zeilen angewendet wird, mit einem (9, 8) SPC-Code, der auf die Spalten angewendet wird, erhält man einen (351, 256) Produktcode. Dieser Code zeichnet sich durch dmin = 4·2 = 8 und r = 73% aus, die Wahrscheinlichkeit eines undetektierten Fehlers liegt In der Größenordnung pu ≈ 2n–k = 2–95.

Die Paritätsprüfmatrix für den (39, 32) -Hsiao-Code ist:

Solche Produktcodes sind für die gewünschte effiziente Hardwareimplementierung nicht geeignet, da sie mit r = 73% einen signifikanten Overhead besitzen.

Als weitere Möglichkeit für die Implementierung eines Codes in eine Vorrichtung zur Überprüfung der Integrität von Daten werden im Folgenden kurz BCH-Codes beschrieben.

Ein BCH-Code mit einer geringen Wahrscheinlichkeit eines undetektierten Fehlers wird durch das Generatorpolynom p(x) = x27 + x26 + x24 + x22 + x21 + x16 + x13 + x11 + x9 + x8 + x6 + x5 + x4 + x3 + 1 gebildet, das das Produkt von drei primitiven Polynomen p1(x) = x9 + x6 + x4 + x3 + 1, p2(x) = x9 + x8 + x5 + x4 + 1, p3(x) = x9 + x4 + 1. ist. Dieser Code hat den minimalen Hamming-Abstand dmin = 7 die Länge n = 511, die Dimension k = 484 und m = n – k = 27 Prüfbits. Für die Wahrscheinlichkeit eines undetektierten Fehlers kann als obere Grenze pu ≤ 227 angegeben werden. BCH-Codes haben eine zyklische Struktur. Diese Eigenschaft wird für eine schnelle Ausführung der Fehlerüberprüfung nicht benötigt, wobei das Encoden und das Generieren des Syndroms als lineares Schieberegister implementiert werden kann. Wenn eine schnelle, voll parallele Implementierung in einem Schaltkreis erforderlich ist, wäre dieser Schaltkreis sehr groß, da die resultierende Paritätsprüfmatrix in einer systematischen Form in etwa 50% Einsen aufweisen würde. Die Schieberegisterimplementierung hat zusätzlich den Nachteil, dass die notwendige Delta-Eigenschaft des Codes nur durch einen erheblichen zusätzlichen Hardwareaufwand möglich wird, was im Allgemeinen für alle zyklischen Codes gilt. Daher ist dieser Code für die erfindungsgemäße effiziente und schnelle Hardwareimplementierung nicht geeignet.

Der Vorteil der Ausführungsbeispiele der vorliegenden Erfindung besteht also darin, dass ein linearer Code zum Schutz gegen Fehlerangriffe durch eine speziell entworfene Kontrollmatrix definiert bzw. realisiert wird. Diese baut sich aus lauter idempotenten dünnbesetzten zirkulanten quadratischen Submatrizen auf. Dünnbesetzt bedeutet, dass die Matrizen wenig Einsen enthalten und hauptsächlich Nullen. Dies entspricht in der Hardwareimplementierung des Codes einer geringen Siliziumfläche und im Betrieb einem geringen Stromverbrauch.

Zirkulante Matrizen sind quadratische Matrizen, die durch ihre erste Zeile bereits eindeutig bestimmt sind. Die nachfolgenden Zeilen ergeben sich aus einer zyklischen Verschiebung dieser ersten Zeile. Durch den Aufbau der Kontrollmatrix aus lauter zirkulanten Matrizen wird insbesondere erreicht, dass jede Zeile der Kontrollmatrix gleich viele Einsen enthält.

Dies bedeutet, dass bei Berechnung der einzelnen Bits des Kontrollwortes oder des Syndroms jeweils dieselbe Gattertiefe durchlaufen werden muss. Das ist für eine effiziente Hardwareimplementierung wichtig. Eine quadratische Matrix heißt idempotent, wenn sie invertierbar ist und die inverse Matrix identisch ist mit der ursprünglichen Matrix (die Matrix ist „selbstinvers"). Die Idempotenz der verwendeten Submatrizen des erfindungsgemäßen Codes erlaubt in hardwaresparender Weise ein fehlerhaftes Wort aus dem Datenblock aus den anderen (fehlerfreien) Worten plus dem Kontrollwort zu rekonstruieren. Diese Eigenschaft wird gebraucht um 1-Bit-Fehler (so genannte moving bit errors) – wie sie im EEPROM von Zeit zu Zeit passieren – korrigieren zu können. Beim Auslesen aus dem EEPROM wird nämlich ein solcher 1-Bit-Fehler in einem abgespeicherten Wert entschlüsselt. Die Entschlüsselungsvorrichtung hat einen so genannten Lawineneffekt: Beim Ver- oder Entschlüsseln eines 32-Bit-Wortes wird aus einem 1-Bit-Fehler ein Mehrbitfehler (typischerweise 10–20 Bitfehler). Nach dem Auslesen kommt der lineare Code zum Einsatz. Das Syndrom ist ungleich 0, ein Hinweis, dass entweder ein Fehlerangriff stattfand oder aber ein moving bit error im Speicher passierte. Nun muss das fehlerhafte Wort aus den anderen (fehlerfreien) Worten des entschlüsselten Datenblocks rekonstruiert werden. Als spezielles Ausführungsbeispiel der erfindungsgemäßen Codeklasse wurde in den vorhergehenden Abschnitten ein linearer Code der Länge 160 für eine Wortbreite von 32 detailliert beschrieben, wobei dieser Code als ECC 160 bezeichnet wird.

Obwohl in dem Ausführungsbeispiel der vorliegenden Erfindung, das in 1 dargestellt ist, die Redundanzeinrichtung 12 und die Kontrolleinrichtung 14 direkt in den Prozessor bzw. in die Recheneinheit 10 integriert ist, können die Redundanzeinrichtung 12 und die Kontrolleinrichtung 14 erfindungsgemäß an beliebiger Stelle entlang des Datenpfades vor der Ver-/Entschlüsselungseinrichtung 20 angeordnet werden. Auf flexible Art und Weise kann die Erfindungsgemäße Redundanzeinrichtung 12 und die Kontrolleinrichtung 14 an einer Stelle im Datenpfad angebracht werden, die vom gewünschten Schutzumfang bestimmt wird. Will man beispielsweise nur den Transfer in den Massenspeicher schützen, können Redundanzeinrichtung 12 und Kontrolleinrichtung 14 zwischen dem Cache 16 und der Ver-/Entschlüsselungseinrichtung 20 angeordnet sein, soll der Cache mit überwacht werden, ist eine Anordnung zwischen dem Datenregister 6 und dem Cache 16 ohne weiteres implementierbar.

Abhängig von den Gegebenheiten kann das erfindungsgemäße Verfahren zum Schutz der Integrität von Daten in Hardware oder in Software implementiert werden. Die Implementierung kann auf einem digitalen Speichermedium, insbesondere einer Diskette oder CD mit elektronisch auslesbaren Steuersignalen erfolgen, die so mit einem programmierbaren Computersystem zusammenwirken können, dass das erfindungsgemäße Verfahren zum Schutz der Integrität von Daten ausgeführt wird. Allgemein besteht die Erfindung somit auch in einem Computer-Programm-Produkt mit einem auf einem maschinenlesbaren Träger gespeicherten Programmcode zur Durchführung des erfindungsgemäßen Verfahrens, wenn das Computer-Programm-Produkt auf einem Rechner abläuft. In anderen Worten ausgedrückt kann die Erfindung somit als ein Computer-Programm mit einem Programmcode zur Durchführung des Verfahrens realisiert werden, wenn das Computer-Programm auf einem Computer abläuft.

2
Hauptprozessor
4
Speichersystem
6
Datenregister
8
Zentralprozessor
10
Recheneinheit
12
Redundanzeinheit
14
Kontrolleinheit
16
Cache
18
interner Speicher
20
Ver-/Entschlüsselungseinheit
22
Massenspeicher
24
erste Datenverbindung
26
zweite Datenverbindung
28
erste bidirektionale Datenverbindung
30
zweite bidirektionale Datenverbindung
32
dritte bidirektionale Datenverbindung
34
vierte bidirektionale Datenverbindung
36
unverschlüsselter Datensatz
38
Datenbitvektor
40
Kontrollbitvektor
42
Gesamtbitvektor
44
verschlüsselter Gesamtbitvektor
46
Redundanzbildung
48
Gesamtbitvektorerzeugung
50
Verschlüsselungsschritt
52
verschlüsselter Datensatz
54
verschlüsselter Gesamtbitvektor
56
entschlüsselter Gesamtbitvektor
58
Syndrombitvektor
60a–60e
entschlüsselte Datenwortvektoren
62a–62e
entschlüsselte substituierte Datenwortvektoren
64a–64e
verschlüsselte substituierte Datenwortvektoren
66
Entschlüsselungsschritt
68
Lesetransferschritt
69
Bestätigungsschritt
70
Substitutionsschritt
72
Überprüfschritt
74
Vergleichsschritt
76
Rekonstruktionsschritt
78
Fehlerschritt
100
erste Matrixzeile
102
zweite Matrixzeile
200
Datenbitblock
202
erste Prüfbitvektoren
204
zweite Prüfbitvektoren
206
Datenwort
208
Kontrollbereich


Anspruch[de]
Vorrichtung zum Schutz der Integrität von Daten, mit folgenden Merkmalen:

einer Redundanzeinrichtung (12), um aus einer Mehrzahl von Datenwörtern eines Datenblockes (36) einen Datenbitvektor (38) zu bilden und durch Multiplikation des Datenbitvektors (38) mit einer binären Erzeugermatrix einen Kontrollbitvektor (40) zu erzeugen;

einer Ver-/Entschlüsselungseinrichtung (20) zum Verschlüsseln jedes der Datenwörter, um verschlüsselte Datenwörter zu erhalten und zum Verschlüsseln des Kontrollbitvektors, um einen verschlüsselten Kontrollbitvektor zu erhalten, und zum Entschlüsseln jedes der verschlüsselten Datenwörter, um entschlüsselte Datenwörter (60a–d) zu erhalten, und zum Entschlüsseln des verschlüsselten Kontrollbitvektors, um einen entschlüsselten Kontrollbitvektor (60e) zu erhalten;

einer Kontrolleinrichtung (14), um aus den entschlüsselten Datenwörtern (60a–d) oder aus den entschlüsselten Datenwörtern (60a–d) und dem entschlüsselten Kontrollbitvektor (60e) einen Gesamtbitvektor (56) zu bilden und durch Multiplikation einer binären Kontrollmatrix mit dem Gesamtbitvektor (56) einen Syndrombitvektor (58) zu erstellen, sodass anhand des Syndrombitvektors (58) die Integrität des Gesamtbitvektors (56) überprüfbar ist.
Vorrichtung gemäß Anspruch 1, bei der die Redundanzeinrichtung (12) ausgebildet ist, um eine Erzeugermatrix zu verwenden, die quadratische, zirkulante Submatrizen umfasst, und bei der die Kontrolleinrichtung (14) ausgebildet ist, um eine Kontrollmatrix zu verwenden, die quadratische, zirkulante Submatrizen umfasst. Vorrichtung gemäß Anspruch 1 oder 2, bei der die Redundanzeinrichtung (12) ausgebildet ist, um eine Erzeugermatrix zu verwenden, die idempotente Submatrizen aufweist. Vorrichtung gemäß einem der Ansprüche 1 bis 3, bei der die Redundanzeinrichtung (12) ausgebildet ist, um eine Erzeugermatrix zu verwenden, die 2, 4, 8 oder 16 quadratische zirkulante Submatrizen umfasst und um 2, 4, 8 oder 16 Datenwörter zu verarbeiten, und bei der die Kontrolleinrichtung (14) ausgebildet ist, um eine Kontrollmatrix zu verwenden, die 2, 4, 8 oder 16 quadratische zirkulante Submatrizen umfasst und um 2, 4, 8 oder 16 Datenwörter zu verarbeiten. Vorrichtung gemäß Anspruch 4, bei der die Redundanzeinrichtung (12) ausgebildet ist, um eine Erzeugermatrix zu verwenden, bei der ein erstes und ein zweites Paar von jeweils zwei der vier Submatrizen paarweise zueinander inverse Submatrizen umfassen und bei der die Kontrolleinrichtung (14) ausgebildet ist, um eine Kontrollmatrix zu verwenden, bei der Paare von jeweils zwei einer geradzahligen Anzahl von Submatrizen paarweise zueinander inverse Submatrizen umfassen. Vorrichtung gemäß einem der Ansprüche 4 oder 5, bei der die Redundanzeinrichtung (12) ausgebildet ist, um Datenwörter der Länge 32 Bit und eine Erzeugermatrix zu verwenden, die 4 quadratische 32 × 32 Matrizen als Submatrizen umfasst, und bei der die Kontrolleinrichtung (14) ausgebildet ist, um Datenwörter der Länge 32 Bit und eine Kontrollmatrix zu verwenden, die 4 quadratische 32 × 32 Matrizen als Submatrizen umfasst. Vorrichtung gemäß einem der obigen Ansprüche, die zusätzlich eine Syndrombitvektorüberwachungseinrichtung zum Zählen von Nullen des Syndrombitvektors (58) aufweist, um eine Alarmaktion auszulösen, wenn eine Anzahl Nullen größer als eine vorbestimmte Schwelle ist. Vorrichtung gemäß Anspruch 7, bei der die Syndrombitvektorüberwachungseinrichtung ausgebildet ist, um bei der Alarmaktion folgende Schritte auszuführen:

– Erzeugen von neuen Datenwörtern aus den entschlüsselten Datenwörtern

– Verschlüsseln der neuen Datenwörter, um verschlüsselte neue Datenwörter zu erhalten

– Vergleichen der verschlüsselten neuen Datenwörter mit den verschlüsselten Datenwörtern

– Auslösen eines Angriffsalarms, wenn der Schritt des Vergleichens eine Abweichung um mehr als ein Bit für jedes Paar von verschlüsseltem Datenwort und verschlüsseltem neuen Datenwort feststellt, oder Freigabe der Daten, wenn der Schritt des Vergleichens eine Abweichung um ein Bit für ein Paar von verschlüsseltem Datenwort und verschlüsseltem neuen Datenwort feststellt.
Vorrichtung zum Schutz der Integrität von Daten mit folgenden Merkmalen:

einer Entschlüsselungseinrichtung (20) zum Entschlüsseln verschlüsselter Datenwörter, um entschlüsselte Datenwörter (60a60d) zu erhalten und zum Entschlüsseln eines verschlüsselten Kontrollbitvektors, um einen entschlüsselten Kontrollbitvektor (60e) zu erhalten; und

einer Kontrolleinrichtung (14), um aus den entschlüsselten Datenwörtern (60a–d) oder aus den entschlüsselten Datenwörtern (60a–d) und dem entschlüsselten Kontrollbitvektor (60e) einen Gesamtbitvektor (56) zu bilden und durch Multiplikation einer binären Kontrollmatrix mit dem Gesamtbitvektor (56) einen Syndrombitvektor (58) zu erstellen, sodass anhand des Syndrombitvektors (58) die Integrität des Gesamtbitvektors (56) überprüfbar ist.
Vorrichtung gemäß einem der Ansprüche 1 bis 9, bei der die Redundanzeinrichtung (12) derart ausgebildet ist, dass die Kontrollmatrix so ausgebildet ist, dass der Syndrombitvektor (58) einer Linearkombination von Spaltenvektoren mit den Bits der Datenwörter (60a60d) als Koeffizienten plus dem Kontrollbitvektor (60e) entspricht, wobei

jeder Spaltenvektor ein ungerades Hamming-Gewicht besitzt; und

alle Spaltenvektoren dasselbe Hamming-Gewicht besitzen.
Vorrichtung zum Schutz der Integrität von Daten mit folgenden Merkmalen:

einer Redundanzeinrichtung (12) um aus einer Mehrzahl von Datenwörtern eines Datenblocks (36) einen Datenbitvektor (38) zu bilden und durch Multiplikation des Datenbitvektors (38) mit einer binären Erzeugermatrix einen Kontrollbitvektor (40) zu erzeugen;

einer Verschlüsselungseinrichtung (20) zum Verschlüsseln jedes der Datenwörter, um verschlüsselte Datenwörter zu erhalten und zum Verschlüsseln des Kontrollbitvektors, um einen verschlüsselten Kontrollbitvektor zu erhalten.
Vorrichtung gemäß einem der Ansprüche 1 bis 8 oder Anspruch 11, bei der die Redundanzeinrichtung (12) ausgebildet ist, um bei einem folgenden Datenbitvektor, der sich um einen Differenzvektor vom Datenbitvektor (38) unterscheidet, durch Multiplikation des Differenzvektors mit der Erzeugermatrix ein Differenzkontrollbitwort zu erzeugen und ein folgendes Kontrollbitwort aus der Summe des Kontrollbitwortes (40) und dem Differenzkontrollbitwort zu bilden. Verfahren zum Schutz der Integrität von Daten mit folgenden Schritten:

Entschlüsseln von verschlüsselten Datenwörtern, um entschlüsselte Datenwörter (60a60d) zu erhalten und Entschlüsseln eines verschlüsselten Kontrollbitvektors, um einen entschlüsselten Kontrollbitvektor (60e) zu erhalten;

Bilden eines Gesamtbitvektors (56) aus den entschlüsselten Datenwörtern (60a60d) und dem entschlüsselten Kontrollbitvektor (60e); und

Multiplizieren einer binären Kontrollmatrix mit dem Gesamtbitvektor (56), um einen Syndrombitvektor (58) zu erstellen, sodass anhand des Syndrombitvektors (58) die Integrität der Datenworte (60a60e) überprüfbar ist.
Verfahren zum Schutz der Integrität von Daten mit folgenden Schritten:

Bilden eines Datenbitvektors (38) aus einer Mehrzahl von Datenwörtern eines Datenblockes (36);

Multiplizieren des Datenbitvektors (38) mit einer binären Erzeugermatrix um einen Kontrollbitvektor (40) zu erzeugen; und

Verschlüsseln jedes der Datenwörter, um verschlüsselte Datenwörter zu erhalten und Verschlüsseln des Kontrollbitvektors (40), um einen verschlüsselten Kontrollbitvektor zu erhalten.
Computerprogramm mit einem Programmcode zur Durchführung des Verfahrens nach Anspruch 11 oder 12, wenn das Programm auf einem Computer abläuft.






IPC
A Täglicher Lebensbedarf
B Arbeitsverfahren; Transportieren
C Chemie; Hüttenwesen
D Textilien; Papier
E Bauwesen; Erdbohren; Bergbau
F Maschinenbau; Beleuchtung; Heizung; Waffen; Sprengen
G Physik
H Elektrotechnik

Anmelder
Datum

Patentrecherche

  Patente PDF

Copyright © 2008 Patent-De Alle Rechte vorbehalten. eMail: info@patent-de.com