PatentDe  


Dokumentenidentifikation DE69927395T2 14.06.2006
EP-Veröffentlichungsnummer 0001119940
Titel GEGENMASSNAHMENVERFAHREN IN EINEM ELEKTRONSICHEN BAUELEMENT, DAS EINEN ALGORITHMUS MIT EINEM PRIVATEN SCHLÜSSEL VERWENDET
Anmelder Gemplus, Gemenos, FR
Erfinder CLAVIER, Christophe, F-13420 Gemenos, FR;
BENOIT, Olivier, F-13400 Aubagne, FR
Vertreter HOFFMANN & EITLE, 81925 München
DE-Aktenzeichen 69927395
Vertragsstaaten DE, ES, FR, GB, IT
Sprache des Dokument FR
EP-Anmeldetag 15.09.1999
EP-Aktenzeichen 999429814
WO-Anmeldetag 15.09.1999
PCT-Aktenzeichen PCT/FR99/02199
WO-Veröffentlichungsnummer 0000024156
WO-Veröffentlichungsdatum 27.04.2000
EP-Offenlegungsdatum 01.08.2001
EP date of grant 21.09.2005
Veröffentlichungstag im Patentblatt 14.06.2006
IPC-Hauptklasse H04L 9/06(2006.01)A, F, I, 20051017, B, H, EP

Beschreibung[de]

Die vorliegende Erfindung betrifft ein einen kryptographischen Algorithmus mit geheimem Schlüssel umsetzendes Gegenmaßnahmenverfahren in einer elektronischen Komponente. Sie werden in Anwendungen eingesetzt, in denen der Zugriff auf Dienste oder Angaben streng kontrolliert wird. Sie haben eine um einen Mikroprozessor und Speicher, darunter einen Programmspeicher, der den geheimen Schlüssel enthält, gebildete Architektur.

Diese Komponenten werden insbesondere in Chipkarten bei bestimmten Anwendungen derselben eingesetzt. Das sind zum Beispiel Zugriffsanwendungen für bestimmte Datenbanken, Bankenanwendungen, Tele-Zahlungsanwendungen, zum Beispiel für das Fernsehen, die Ausgabe von Benzin oder auch von Autobahnmaud.

Diese Komponenten oder Karten setzen daher einen Kryptographie-Algorithmus mit geheimem Schlüssel um, dessen bekanntester der Algorithmus DES (aus Data Encryption Standard in der angelsächsischen Literatur) ist. Es gibt weitere Algorithmen mit geheimem Schlüssel, wie den Algorithmus RC5 oder auch den Algorithmus COMP128. Diese Liste erhebt selbstverständlich keinen Anspruch auf Vollständigkeit.

Allgemein und zusammenfassend besteht die Funktion dieser Algorithmen in der Berechnung einer chiffrierten Meldung ausgehend von einer am Eingang (in der Karte) durch ein Wirtssystem (Server, Bankautomat, usw.) angewendeten Meldung und dem in der Karte enthaltenen geheimen Schlüssel und in der Lieferung dieser chiffrierten Meldung an das Wirtssystem im Rücklauf, was dem Wirtssystem zum Beispiel die Authentifizierung der Komponente oder der Karte, den Austausch von Angaben, usw. erlaubt.

Es hat sich jedoch gezeigt, dass diese Komponenten oder diese Karten für aus einer Differentialanalyse des Stromverbrauchs bestehende Angriffe empfindlich sind, die es böswilligen Dritten erlauben, den geheimen Schlüssel herauszufinden. Diese Angriffe werden als DPA, das Akronom für das Angelsächsische Differential Power Analysis bezeichnet.

Das Prinzip dieser DPA-Angriffe besteht in der Tatsache, dass der Stromverbrauch des die Anweisungen ausführenden Mikroprozessors je nach der behandelten Angabe variiert.

Insbesondere erzeugt eine ein Datenbit behandelnde Anweisung des Mikroprozessors zwei unterschiedliche Stromprofile, je nachdem, ob das Bit „1" oder „0" wert ist. Im typischen Fall hat man in diesem Ausführungszeitpunkt eine erste Amplitude des verbrauchten Stroms, wenn die behandelte Anweisung „0" ist, und man hat eine von der ersten unterschiedliche zweite Amplitude des verbrauchten Stroms, wenn die behandelte Anweisung „1" ist.

Die Merkmale der Kryptographie-Algorithmen sind bekannt: durchgeführte Berechnungen, verwendete Parameter. Die einzige Unbekannte ist der im Speicherprogramm enthaltene Geheimschlüssel. Dieser kann nicht allein aus der Kenntnis der am Eingang angewendeten und von der im Rücklauf gelieferten chiffrierten Meldung abgeleitet werden.

In einem Kryptographie-Algorithmus hängen jedoch bestimmte berechnete Angaben nur von der im Eingang der Karte unverschlüsselt angewendeten Meldung und dem in der Karte enthaltenen Schlüssel ab. Weitere im Algorithmus berechnete Angaben können auch nur ausgehend von der (im Allgemeinen unverschlüsselt am Ausgang der Karte zum Wirtssystem gelieferten) chiffrierten Meldung und dem in der Karte enthaltenen geheimen Schlüssel nachgerechnet werden. Genauer gesagt kann jedes Bit dieser besonderen Angaben ausgehend von der Eingangs- oder Ausgangsmeldung und einer begrenzten Anzahl von besonderen Bits des Schlüssels bestimmt werden.

Somit entspricht jedem Bit einer besonderen Angabe ein durch eine besondere Gruppe von Bits des Schlüssels gebildeter Unterschlüssel.

Die Bits dieser besonderen Angaben, die vorausgesagt werden können, werden im Folgenden Ziel-Bits genannt.

Die Grundidee des DPA-Angriffs besteht somit im Einsatz der Differenz des Profils des Stromverbrauchs einer Anweisung danach, ob sie eine „1" oder eine „0" behandelt und der Möglichkeit der Berechnung eines Ziel-Bits durch die Anweisungen des Algorithmus ausgehend von einer bekannten Eingangs- oder Ausgangsmeldung und einer Hypothese über den entsprechenden Unterschlüssel.

Das Prinzip des DPA-Angriffs besteht daher im Testen einer Hypothese über einen bestimmten Unterschlüssel durch Anwendung einer booleischen Auswahlfunktion, einer für jede Kurve durch den vorgenannten Wert für ein Ziel-Bit definierte Funktion der Hypothese des Unterschlüssels auf eine große Anzahl von Strommesskurven.

Durch Erstellung einer Hypothese für den betroffenen Unterschlüssel ist man in der Tat in der Lage, den Wert „0" oder „1" vorauszusagen, den dieses Ziel-Bit für eine bestimmte Eingangs- oder Ausgangsmeldung annehmen wird.

Dann kann man als booleische Auswahlfunktion den durch das Ziel-Bit für die Hypothese des betrachteten Unterschlüssels vorausgesagten Wert „0" oder „1", um diese Kurven in zwei Paketen zu sortieren: ein erstes Paket fasst die Kurven zusammen, die zu der Behandlung des Ziel-Bits bei „0" gehören, und ein zweites Paket fasst die Kurven zusammen, die zur Behandlung des Ziel-Bits bei „1" gemäß der Unterschlüsselhypothese gehören. Durch Berechnung des Durchschnitts des Stromverbrauchs in jedem Paket erhält man eine Kurve des durchschnittlichen Stromverbrauchs M0(t) für das erste Paket und eine Kurve des durchschnittlichen Stromverbrauchs M1(t) für das zweite Paket.

Wenn die Unterschlüsselhypothese richtig ist, umfasst das erste Paket effektiv alle Kurven aus den N Kurven, die zur Behandlung des Ziel-Bits bis „0" gehören, und das zweite Paket umfasst effektiv alle Kurven aus de N Kurven, die zur Behandlung des Ziel-Bits bis „1" gehören. Die Kurve des durchschnittlichen Verbrauchs Mo(t) des ersten Pakets hat dann überall einen durchschnittlichen Verbrauch, mit Ausnahme der Zeitpunkte der Ausführung der kritischen Anwendungen mit einem für die Behandlung des Ziel-Bits bei „0" charakteristischen Profil des Stromverbrauchs (profil0). Mit anderen Worten, alle behandelten Bits haben bei allen diesen Kurven ebenso viele Chancen, „0" wert zu sein wie „1" wert, nur dass das Ziel-Bit immer den Wert „0" hatte. So dass man schreiben kann: M0(t) = [(profil0 + profil1)/2]t1tci + [profil0]tci, das heißt

M0(t) = {[Vmt]t1tci + [profil0]tci
wobei tci die kritischen Zeitpunkte darstellt, in denen eine kritische Anwendung durchgeführt wurde.

Ebenso entspricht die Kurve des durchschnittlichen Verbrauchs M1(t) des zweiten Pakets einem durchschnittlichen Verbrauch überall, mit Ausnahme der Zeitpunkte der Ausführung der kritischen Anweisungen, mit einem Profil des charakteristischen Stromverbrauchs der Behandlung des Ziel-Bits bei „1" (profil1). Man kann schreiben: M1(t) = [profil0] + profil1)/2]t1tci + [profil1]tci, das heißt

M1(t) = [Vmt)t1tci + [profil1]tci.

Wir haben gesehen, dass die beiden Profile proifil0 und profil1 nicht gleich sind. Der Unterschied der Kurven M0(t) und M1(t) ergibt dann ein Signal DPA(t), dessen Amplitude gleich profil0 – profil1 zu den dieses Bit behandelnden kritischen Ausführungszeitpunkten tci ist, das heißt, in dem in 1 dargestellten Beispiel, an den Stellen tc0 bis tc6, und dessen Amplitude außerhalb dieser kritischen Zeitpunkte ungefähr gleich Null ist.

Wenn die Unterschlüssehypothese falsch ist, entspricht die Sortierung nicht der Realität. Statistisch gibt es dann in jedem Paket ebenso viele Kurven, die effektiv zur Behandlung des Ziel-Bits bei „0" gehören, wie Kurven, die zur Behandlung des Ziel-Bits bei „1" gehören. Die resultierende durchschnittliche Kurve Mo(t) befindet sich dann um einen durch (profil0 + profil1)/2 = Vm gegebenen durchschnittlichen Wert, denn bei jeder Kurve haben alle behandelten Werte, unter Einschluss des Ziel-Bits, ebenso viele Chancen, „0"-wertig zu sein wie „1"-wertig.

Dieselbe Überlegung hinsichtlich des zweiten Pakets führt zu einer Kurve des durchschnittlichen Stromverbrauchs M1(t), deren Amplitude sich um einen durch (profil0 + profil1)/2 = Vm gegebenen durchschnittlichen Wert bewegt.

Das durch die Differenz Mo(t) – M1(t) gelieferte Signal DPA(t) ist in diesem Fall deutlich gleich Null. Das Signal DPA(t) im Fall einer falschen Unterschlüsselhypothese wird in 2 dargestellt.

Somit verwertet der DPA-Angriff die Differenz des Profils des Stromverbrauchs während der Ausführung einer Anweisung gemäß dem Wert des behandelten Bits aus, um eine Sortierung von Kurven des Stromverbrauchs gemäß einer booleischen Auswahlfunktion für eine bestimmte Unterschlüsselhypothese vorzunehmen. Durch die Durchführung einer Differentialanalyse des durchschnittlichen Stromverbrauchs zwischen den beiden erhaltenen Kurvenpaketen erhält man ein Informationssignal DPA(t).

Der Ablauf eines DPA-Angriffs besteht dann global:

  • a – in der Ermittlung von N zufälligen Meldungen (zum Beispiel N gleich 1000);
  • b – in der Ausführung des Algorithmus durch die Karte für jede der zufälligen Meldungen N durch Ermittlung der Kurve des Stromverbrauchs bei jedem Mal (gemessen an der Versorgungs-Anschlussklemme der Komponente);
  • c – in der Erstellung einer Hypothese über einen Unterschlüssel;
  • d – in der Voraussage des durch eines der Ziel-Bits angenommenen Wertes, deren Wert nicht von den Bits der (Eingangs- oder Ausgangs-) Meldung abhängt, für jede zufällige Meldung und des in der Hypothese angenommenen Unterschlüssels zum Erhalt der booleischen Auswahlfunktion.
  • e – in der Sortierung der Kurven gemäß dieser booleischen Auswahlfunktion (das heißt, gemäß dem für dieses Ziel-Bit für jede Kurve nach der Unterschlüsselhypothese vorausgesagten Wert „0" oder „1");
  • f – in der Berechnung der aus dem durchschnittlichen Stromverbrauch resultierenden Kurve in jedem Paket;
  • g – in der Ermittlung der Differenz dieser durchschnittlichen Kurven zum Erhalt des Signals DPA(t).

Wenn die Unterschlüsselhypothese richtig ist, ist die booleische Auswahlfunktion richtig und die Kurven des ersten Pakets entsprechen effektiv den Kurven, für die die angewendete Meldung am Eingang oder am Ausgang ein Ziel-Bit bei „0" in der Karte ergeben hat, und die Kurven des zweiten Pakets entsprechen effektiv den Kurven, für die die am Eingang oder am Ausgang angewendete Meldung ein Ziel-Bit bei „1" in der Karte ergeben hat.

Wir befinden uns im Fall der 1: das Signal DPA(t) ist also zu den der Ausführung der kritischen Anwendungen entsprechenden Zeitpunkten tc0 bis tc6 (diejenigen, die das Ziel-Bit behandeln) nicht Null. Es genügt, dass es in der Akquisitionsperiode wenigstens einen kritischen Zeitpunkt gibt.

Es ist anzumerken, dass der Angreifer die kritischen Zeitpunkte nicht präzise zu kennen braucht.

Wenn die Unterschlüsselhypothese nicht richtig ist, entspricht die Sortierung nicht der Realität, und dann hat man in jedem Paket ebenso viele in Wirklichkeit einem Ziel-Bit bei „0" entsprechende Kurven wie einem Ziel-Bit bei „1" entsprechende Kurven. Das Signal DPA(t) ist überall deutlich Null (in 2 dargestellter Fall). Man muss in die Stufe c– zurückkehren und eine neue Unterschlüsselhypothese aufstellen.

Wenn sich die Hypothese als richtig erweist, kann man zur Schätzung anderer Unterschlüssel übergehen, bis der Schlüssel maximal wieder zusammengesetzt ist. Mit einem Algorithmus DES setzt man zum Beispiel einen Schlüssel von 64 Bits ein, von dem nur 56 Bits nützlich sind. Bei einem DPA-Angriff kann man wenigstens 48 Bits der 56 nützlichen Bits wieder zusammensetzen.

Es können drei sich der Erfindung annähernde Dokumente genannt werden.

Das erste Dokument von Yi X., dessen englischer Titel „A method for obtaining cryptographically strong 8X8 S-BOXES" lautet und das bei der Konferenz über Telekommunikation in Phoenix, Arizona, Vereinigte Staaten von Amerika, vom 3. bis 8. November 1997 vorgestellt wurde, beschreibt ein Verfahren zur einfachen und wirkungsvollen Entwicklung von starken S-Boxen (Substitutions-Boxen) per Computer. Der Algorithmus DES könnte entschlüsselt werden, wenn schwache S-Boxen eingesetzt werden würden. Inverse Boxen sind ebenfalls stark. Das Verfahren dieses Dokuments beschreibt eine gut Eignung gegen Differentialangriffe, die durch den Einsatz von Konstantentabellen SBOX die Steigerung der Sicherheit kryptographischer Systeme erlaubt.

Das zweite Dokument von Miyaguchi S., dessen englischer Titel „Secret key ciphers that change the encipherment algorithm under the control of the key" lautet und das in der Revue „NTT REVIEW", Band 6, Nr. 4, vom 1. Juli 1994 veröffentlicht wurde, beschreibt einen geheimen Verschlüsselungs-Algorithmus, der sich unter dem Befehl des Chiffrierungsschlüssels durch Substitutionen/Permutationen zwischen den elementaren Konstantentabellen S1 bis S8 einer Konstantentabelle S-BOX dynamisch ändert. Das Verfahren ist unempfindlich gegen Angriffe, die durch Einsatz der unverschlüsselten Textpaare und ihres chiffrierten Textblocks den Schlüssel berechnen. Es enthält ein Beispiel mit einer geänderten Zahl von DES.

Das am 7. August 1992 veröffentlichte dritte Dokument, die Schrift FR 2 672 402, beschreibt ein Verfahren und eine Vorrichtung zur Erzeugung von ein die Realisierung von Chipkarten anwendendes kryptographisches Programm vom Typ DES einsetzenden einzigartigen, pseudo-zufälligen Zahlen.

Die Aufgabe der vorliegenden Erfindung besteht in der Umsetzung eines Gegenmaßnahmen-Verfahrens in einer elektronischen Komponente, das ein Signal DPA(t) Null selbst in dem Fall nach sich zieht, in dem die Unterschlüsselhypothese richtig ist.

Auf diese Weise erlaubt nichts die Unterscheidung des Falls der richtigen Unterschlüsselhypothese von den Fällen mit falscher Unterschlüsselhypothese. Durch diese Gegenmaßnahme wird die elektronische Komponente gegen DPA-Angriffe gewappnet.

Erfindungsgemäß erlaubt es das Gegenmaßnahmen-Verfahren, die Ziel-Bits, das heißt, die von den kritischen Anweisungen behandelten Angaben, unvorsehbar zu machen.

Aufgrund der für jede am Eingang angewendete Meldung Gegenmaßnahme nimmt ein durch eine kritische Anweisung behandeltes Ziel-Bit mit einer gleichen Wahrscheinlichkeit den Wert 0 oder 1 an. In jedem Kurvenpaket, das der Angreifer unter der gegebenen Unterschlüsselhypothese und mittels der booleischen Auswahlfunktion, die er berechnet hat, durchführt, gibt es ebenso viele Kurven, die effektiv ein Ziel-Bit „0" behandelt haben, wie es Kurven gibt, die effektiv ein Ziel-Bit bei „1" behandelt haben. Das Signal DPA(t) wird immer Null sein, ob die Unterschlüsselhypothese richtig ist oder nicht.

In der Erfindung interessieren wir uns insbesondere für den kryptographischen Algorithmus DES.

Ein derartiger Algorithmus umfasst sechzehn identische Berechnungssätze.

In einem derartigen Algorithmus konnte nachgewiesen werden, dass die durch einen Angreifer vorhersagbaren Daten sich im ersten Satz und im letzten Satz befinden und dass die im Sinne des DPA-Angriffs kritischen Anweisungen sich in den drei ersten Sätzen und den drei letzten Sätzen befinden.

In der Erfindung wurde insbesondere nach einem Mittel gesucht, um die die durch diese kritischen Anweisungen behandelten Angaben der drei ersten und der drei letzten Sätze bei gleichzeitigem Erhalt der richtigen chiffrierten Meldung am Ausgang unvorhersehbar zu machen.

Eine Aufgabe der Erfindung ist es daher, die von den kritischen Anweisungen behandelten Daten bei gleichzeitigem Erhalt des richtigen Endergebnisses (chiffrierte Meldung C) unvorhersehbar zu machen.

Eine Lösung zu diesen verschiedenen technischen Problemen wurde in der Bildung einer wenigstens die drei ersten Sätze und bildenden Gruppe (G1) und einer anderen, wenigstens die drei letzten Sätze umfassenden Gruppe (G4) und im Einsatz von Mitteln in diesen Gruppen gefunden, um die von den in diesen Sätzen enthaltenen kritischen Anweisungen behandelten Daten unvorhersehbar zu machen.

Erfindungsgemäß sind die Ergebnisse am Ausgang jeder Gruppe richtig.

Gemäß Kennzeichnung betrifft die Erfindung daher ein einen kryptographischen Algorithmus mit geheimem Schlüssel zur Berechnung einer chiffrierten Meldung ausgehend von einer Eingangsmeldung umsetzendes Gegenmaßnahmenverfahren in einer elektronischen Komponente, wobei die Umsetzung des Algorithmus sechzehn Berechnungssätze umfasst, wobei jeder Satz erste Mittel einsetzt, um eine Ausgangsangabe ausgehend von einer Eingangsangabe zu liefern, wobei die Ausgangs- und/oder die abgeleiteten Angaben durch im zu Beginn und am Ende des Algorithmus kritische Anweisungen in den der letzten Sätzen behandelt werden. Erfindungsgemäß bildet man eine wenigstens die drei ersten Sätze umfassende Gruppe und eine wenigstens die der letzten Sätze umfassende Gruppe und ordnet jeder dieser Gruppen eine die ersten Mittel in jedem Satz einsetzende erste Sequenz und eine weitere Mittel, wobei die genannten ersten und zweiten Sequenzen derart sind, dass sie ein und dasselbe Ergebnis am Ausgang des ersten Satzes jeder Gruppe für ein und die dieselbe bestimmte Eingangsmeldung liefern, wobei die Wahl der in den betroffenen Gruppen auszuführenden Sequenz von einem statistischen Wahrscheinlichkeitsgesetz ein Halb abhängt, um alle von den genannten kritischen Anweisungen behandelten Angaben unvorhersagbar zu machen.

In einer Ausführungsform bildet man vier Gruppen aus vier jeweils aufeinander folgenden Sätzen.

In einer anderen Ausführungsform bildet man zwei jeweils die drei ersten und die drei letzten Sätze umfassende Gruppen.

Weitere Merkmale und Vorteile der Erfindung werden in der nachfolgenden, zu Anschauungszwecken gegebenen und keineswegs einschränkenden Beschreibung unter Bezugnahme auf die beigefügten Zeichnungen im Einzelnen aufgeführt, in denen:

die bereits beschriebenen 1 und 2 das Signal DPA(t) darstellten, das man in Abhängigkeit einer Hypothese über einen Unterschlüssel des geheimen Schlüssels K gemäß eines DPA-Angriffs erhalten kann;

die 3 und 4 die ersten Sätze und die letzten Sätze des Algorithmus DES darstellende Organigramme sind;

5 ein Blockschema der im Algorithmus DES eingesetzten Operation SBOX ist;

6 ein elementares Konstantentabellenbeispiel an einem Eingang und einem Ausgang zeigt, die in der Operation SBOX verwendet werden;

7 ein erstes Ausführungs-Organigrammbeispiel des DES mit einem erfindungsgemäßen Gegenmaßnahmen-Verfahren zeigt;

8 ein Organigramm der ersten Sätze des DES gemäß einer zweiten Sequenz des Gegenmaßnahmen-Verfahrens gemäß dem ersten, in 7 dargestellten Beispiel ist;

die 9 und 10 jeweils eine zweite und dritte, in der Erfindung eingesetzte elementare Konstantentabelle darstellen;

11 ein zweites Ausführungs-Organisationsbeispiel des DES mit einem erfindungsgemäßen Gegenmaßnahmen-Verfahren darstellt;

die 12 und 13 Organigramme der ersten DES-Sätze jeweils gemäß der zweiten Sequenz und der ersten Sequenz des Gegenmaßnahmen-Verfahrens gemäß dem zweiten, in 11 dargestellten Beispiel sind;

die 14 und 15 Organigramme bezüglich eines dritten Anwendungsmodus des erfindungsgemäßen Gegenmaßnahmen-Verfahrens sind;

16 eine dritte, in diesem vierten Anwendungsmodus eingesetzte elementare Konstantentabelle darstellt;

17 ein Ausführungsorganigramm des DES gemäß einer Variante des dritten Anwendungsmodus des erfindungsgemäßen Gegenmaßnahmen-Verfahrens darstellt; und

18 ein vereinfachtes Blockschema einer Chipkarte mit einer elektronischen Komponente darstellt, in der das erfindungsgemäße Gegenmaßnahmen-Verfahren umgesetzt wird.

Der kryptographische Algorithmus mit geheimem Schlüssel DES (im Folgenden wird ganz einfach vom DES oder dem Algorithmus DES gesprochen) umfasst 16 Berechnungssätze, die, wie in den 3 und 4 dargestellt, mit T1 bis T16 bezeichnet werden.

Der DES beginnt mit einer Initialpermutation IP auf der Eingangsmeldung M (3). Die Eingangsmeldung M ist ein Wort f aus 64 Bits. Nach der Permutation erhält man ein Wort e aus 64 Bits, das man in zwei Teile unterteilt, um die Eingangsparameter L0 und R0 des ersten Satzes (T1) zu bilden. L0 ist ein aus die 32 Bits mit hohem Gewicht des Wortes e enthaltendes Wort d aus 32 Bits. R0 ist ein die 32 Bits geringen Gewichts des Wortes e enthaltendes Wort h aus 32 Bits.

Der geheime Schlüssel K, der ein Wort q aus 64 Bits ist, wird seinerseits einer Permutation und einer Kompression unterzogen, um ein Wort r aus 56 Bits zu liefern.

Der erste Satz umfasst eine aus einer Expansion und einer Permutation bestehende Operation EXP PERM auf dem Parameter R0, um am Ausgang ein Wort 1 aus 48 Bits zu liefern.

Dieses Wort 1 ist mit einem Parameter K1 in einer mit XOR gekennzeichneten Operation vom Typ EXKLUSIVES ODER kombiniert, um ein Wort b aus 48 Bits zu liefern. Der Parameter K1, der ein Wort m aus 48 Bits ist, wird aus dem Wort r durch eine Verschiebung einer Position (in den 3 und 4 als SHIFT bezeichnete Operation) erhalten, gefolgt von einer Permutation und einer Kompression (mit COMP PERM bezeichnete Operation).

Das Wort b wird auf eine mit SBOX bezeichnete Operation angewendet, an deren Ausgang man ein Wort a mit 32 Bits erhält. Diese besondere Operation wird in weiteren Einzelheiten in Verbindung mit den 5 und 6 erläutert.

Das Wort a wird einer am Ausgang das Wort c aus 32 Bits ergebenden Permutation P PERM unterzogen.

Dieses Wort c wird in einer mit XOR bezeichneten logischen Operation vom Typ EXKLUSIVES ODER, die am Ausgang das Wort g aus 32 Bit liefert, mit dem Eingangsparameter L0 des ersten Satzes T1 kombiniert.

Das Wort h (= R0) des ersten Satzes liefert den Eingangsparameter L1 des folgenden Satzes (T2) und das Wort g des ersten Satzes liefert den Eingangsparameter R1 des folgenden Satzes. Das Wort p des ersten Satzes liefert den Eingang r des folgenden Satzes.

Die anderen Sätze T2 bis T16 laufen auf ähnliche Weise ab, mit Ausnahme bei der Verschiebungsoperation SHIFT, die je nach den betrachteten Sätzen auf einer oder zwei Positionen erfolgt.

Jeder Satz Ti erhält somit am Eingang die Parameter Li-1, Ri-1 und r und liefert am Ausgang die Parameter Li und Ri und r für den nachfolgenden Satz Ti+1.

Am Ende des Algorithmus DES (4) wird die chiffrierte Meldung ausgehend von den vom letzten Satz T16 gelieferten Parametern L16 und R16 berechnet.

Diese Berechnung der chiffrierten Meldung C umfasst in der Praxis die folgenden Operationen:

  • – Bildung eines Wortes e' aus 64 Bits durch Umkehrung der Position der Wörter L16 und R16, dann durch ihre Verkettung;
  • – Anwendung der umgekehrte Permutation IP–1 von der am Anfang von DES zum Erhalt des die chiffrierte Meldung C bildenden Wortes f' aus 64 Bits.

Die Operation SBOX wird in den 5 und 6 im Einzelnen ausgeführt. Sie umfasst eine Konstantentabelle TC0 zur Lieferung einer Ausgangsangabe a in Abhängigkeit von einer Eingangsangabe b.

In der Praxis weist diese Konstantentabelle TC0 die Form von acht elementaren Konstantentabellen TC01 bis TC08 auf, wobei jede am Eingang nur 6 Bits des Wortes b empfängt, um am Ausgang nur 4 Bits des Wortes a zu liefern.

Somit empfängt die in 6 dargestellte elementare Konstantentabelle TC01 als Eingangsangabe die Bits b1 bis b6 des Wortes b und liefert als Ausgangsangabe die Bits a1 bis a4 des Wortes a.

In der Praxis werden diese acht elementaren Konstantentabellen TC01 bis TC08 im Programmspeicher der elektronischen Komponente gespeichert.

In der Operation SBOX des ersten Satzes T1 hängt ein besonderes Bit der Ausgangsangabe a der Konstantentabelle TC0 nur von 6 Bits der am Eingang angewendeten Angabe b ab, das heißt, nur 6 Bits des geheimen Schlüssels K und der Eingangsmeldung (M).

In der Operation SBOX des letzten Satzes T16 kann ein besonderes Bit der Ausgangsangabe a der Konstantentabelle TC0 ausgehend von nur 6 Bits des geheimen Schlüssels K und der chiffrierten Meldung (C) nachgerechnet werden.

Wenn man jedoch das Prinzip des DPA-Angriffs wieder aufnimmt, braucht man nur eine Hypothese für 6 Bits des Schlüssels K aufzustellen, um den Wert eines Ziel-Bits für eine bestimmte Eingangsmeldung (M) oder eine bestimmte Ausgangsmeldung (C) vorauszusagen, wenn man als Ziel-Bit ein Bit der Ausgangsangabe wählt. Mit anderen Worten, man braucht für den DES nur eine Hypothese über einen Unterschlüssel von 6 Bits aufzustellen.

Bei einem DPA-Angriff auf einem derartigen Algorithmus bei einem bestimmten Ziel-Bit muss man daher eine Unterschlüsselhypothese aus genau 64 möglichen Hypothesen diskriminieren.

Somit kann man, indem man nur acht Bits des Wortes a als Ziel-Bits nimmt, (ein Ausgangsbit pro elementarer Konstantentabelle TC01 bis TC08) bis zu 6 × 8 = 48 Bits des geheimen Schlüssels entdecken, indem man DPA-Angriffe auf jedem der Ziel-Bits durchführt.

In den DES findet man daher im Sinne von DPA-Angriffen kritische Anweisungen zu Beginn des Algorithmus und am Ende.

Zu Beginn des Algorithmus DES sind die Angaben, die ausgehend von einer Eingangsmeldung M und einer Unterschlüsselhypothese vorausgesagt werden können, die im ersten Satz (T1) berechneten Angaben a und g.

Die Angabe a des ersten Satzes T1 (3) ist die Ausgangsangabe der Operation SBOX des betrachteten Satzes. Die Angabe g wird ausgehend von der Angabe a durch Permutation (P PERM) und eine Operation EXKLUSIVES ODER mit dem Eingangsparameter L0 berechnet.

Die Angabe c des ersten Satzes ist in der Tat eine von der Angabe a des ersten Satzes abgeleitete Angabe. Die abgeleitete Angabe c entspricht einer einfachen Bits-Permutation der Angabe a.

Die Angabe 1 des zweiten Satzes ist eine von der Angabe g abgeleitete Angabe des ersten Satzes, denn sie entspricht einer Permutation der Bits des Wortes g, wobei bestimmte Bits des Wortes g darüber hinaus dupliziert werden.

Mit der Kenntnis von a und g kann man auch diese abgeleiteten Daten kennen.

Die kritischen Anweisungen zu Beginn des Algorithmus sind kritische Anweisungen, die entweder die Angabe behandeln, die man als die Angabe des ersten Satzes a voraussagen kann, oder eine abgeleitete Angabe.

Die die Angabe a des ersten Satzes T1 oder die abgeleitete Angabe c behandelnden Anweisungen sind somit Endanweisungen der Operation SBOX, der Operation P PERM und Anfangsanweisungen der Operation XOR des ersten Satzes T1.

Die die Angabe 9 oder abgeleitete Daten behandelnden kritischen Anweisungen sind alles Endanweisungen der Operation XOR des Endes des ersten Satzes T1 bis zu den Anfangsanweisungen der Operation SBOX des zweiten Satzes T2 und Anfangsanweisungen der Operation XOR am Ende des dritten Satzes T3 (L2 = h(T2) = g(T1)).

Am Algorithmusende DES sind die Daten, die ausgehend von einer chiffrierten Meldung C und einer Unterschlüsselhypothese vorausgesagt werden können, die Angabe a des sechzehnten Satzes T16 und der Angabe L15 gleich dem Wort h des vierten Satzes T14.

Die die Angabe a des sechzehnten Satzes oder der abgeleiteten Daten behandelnden Anweisungen sind die Anweisungen des sechzehnten Endsatzes der Operation SBOX, der Operationspermutation P PERM und der Anfangspermutation XOR.

Bei der Angabe L15 sind die diese Angabe oder die abgeleiteten Angaben behandelnden kritischen Anweisungen alle Anweisungen von den Endanweisungen der Operation XOR des vierzehnten Satzes T14 bis zu den Anfangsanweisungen der Operation SBOX des fünfzehnten Satzes T15 sowie die Anfangsanweisungen der Operation XOR des sechzehnten Satzes T16.

Das auf diesen Algorithmus DES angewendete erfindungsgemäße Gegenmaßnahmen-Verfahren besteht bei jeder kritischen Anweisung darin, ebenso viele Chancen zu haben, dass die kritische Anweisung eine Angabe behandelt, wie ihr Komplement. Somit hat man unabhängig vom Ziel-Bit, auf dem der DPA-Angriff erfolgen kann, ebenso viele Chancen, dass die kritischen Anweisungen, die dieses Bit behandeln, eine „1" oder eine „0" behandeln.

In der Praxis trifft dies auf jedes der potenziellen Ziel-Bits zu. Mit anderen Worten, da der Angreifer die Wahl zwischen unterschiedlichen möglichen Angriffen hat, das heißt zwischen mehreren möglichen booleischen Auswahlfunktionen zur Durchführung seiner Kurvensortierung, bei einer bestimmten Unterschlüsselhypothese, muss die Umsetzung des erfindungsgemäßen Gegenmaßnahmen-Verfahrens darauf abzielen, dass die von jeder der kritischen Anweisungen behandelten Angaben jedes zweite Mal zufällig einen Wert oder sein Komplement übernehmen. Was die Anwendung des erfindungsgemäßen Gegenmaßnahmen-Verfahrens auf den Algorithmus DES anbelangt, ist daher die Gegenmaßnahme auf die kritischen Anfangsanweisungen des DES und auf die kritischen Endanweisungen des DES anzuwenden, um vollkommen geschützt zu sein.

In dem DES sind alle von den kritischen Anweisungen behandelten Angaben eine Ausgangsangabe oder von einer Ausgangsangabe einer Operation SBOX abgeleitete Angaben.

Zu Beginn des DES sind nämlich die Angaben, die vorausgesagt werden können, die Angaben a und g des ersten Satzes T1. Die Angabe a ist die Ausgangsangabe der Operation SBOX des ersten Satzes. Die Angabe g wird ausgehend von der Angabe a berechnet, da g = P PERM(a) XOR L0. g ist daher eine von der Ausgangsangabe a der Operation SBOX des ersten Satzes abgeleitete Angabe. Somit ergeben sich alle von den kritischen Anfangsanweisungen von DES behandelten Daten direkt oder indirekt aus der Ausgangsangabe a der Operation SBOX des ersten Satzes.

Was das Ende von DES anbelangt, sind die Angaben, die vorausgesagt werden können, die Angabe a des sechzehnten Satzes T16 und die Angabe g des vierzehnten Satzes T14, wobei g gleich L15 ist.

Die Angabe a ist die Ausgangsangabe der Operation SBOX des sechzehnten Satzes T16.

Was die Angabe L15 anbelangt, wird sie in der normalen Ausführung des Algorithmus DES ausgehend von der Ausgangsangabe a der Operation SBOX des vierzehnten Satzes T14 : L15 = P PERM(a) XOR L14 berechnet.

Wenn man die Ausgangsangaben a dieser besonderen Operationen SBOX unvorhersagbar macht, macht man auch alle abgeleiteten Daten unvorhersagbar: Damit macht man alle von den kritischen Anweisungen des Algorithmus DES behandelten Angaben unvorhersagbar. Wenn man davon ausgeht, dass diese Operationen SBOX erste Mittel zur Lieferung einer Ausgangsangabe S = a ausgehend von einer Eingangsangabe E = b bilden, besteht das auf den Algorithmus DES angewendete Gegenmaßnahmen-Verfahren im Einsatz weiterer Mittel, um die Ausgangsangabe unvorhersagbar zu machen, so dass diese Ausgangsangabe und/oder abgeleiteten Angaben, die von den kritischen Anweisungen behandelt werden, alle unvorhersagbar sind.

Erfindungsgemäß bildet man eine aus wenigstens den drei ersten Sätzen gebildete Gruppe und eine andere, aus wenigstens den drei letzten Sätzen gebildete Gruppe. Diese Gruppen enthalten daher alle die kritische Anweisungen umfassenden Sätze.

Diesen beiden Gruppen wird eine die ersten Mittel für alle Sätze einsetzende erste Sequenz und eine die anderen Mittel für wenigstens bestimmte Sätze zweite Sequenz zugeordnet.

In den anderen Sätzen, die nicht in diesen Gruppen sind, kann man mit dem Einsatz der ersten Mittel fortfahren.

Der Einsatz dieser anderen Mittel ist derart, dass das Ergebnis am Ausgang, das heißt, die chiffrierte Meldung, richtig ist.

Diese anderen Mittel können mehrere unterschiedliche Mittel umfassen. Sie sind derart, dass sie bei der einen und/oder der anderen Angabe aus den Eingangsdaten und Ausgangsdaten der ersten Mittel zur Entsprechung der komplementierten Angabe hinwirken.

Wenn man eine große Anzahl von Ausführungen betrachtet, setzen die Gruppen somit im Durchschnitt jedes zweite Mal die erste Sequenz ein, die die normale Sequenz des Algorithmus ist, und jedes zweite Mal die andere Sequenz. Die von den kritischen Anweisungen in diesen Gruppen behandelten, bestimmten Zwischenergebnissen entsprechenden Angaben werden daher im Durchschnitt jedes zweite Mal komplementiert. Bei einer großen Anzahl von Kurven hat man daher statistisch gesehen ebenso viele Chancen, dass ein Ziel-Bit bei 1 ist wie bei 0.

7 stellt eine erste Ausführungsform der Erfindung dar.

In dieser Ausführungsform verteilt man die sechzehn Sätze des Algorithmus DES in vierzehn Gruppen G1 bis G4 aus vier aufeinander folgenden Sätzen auf. Die Gruppe G1 umfasst somit die Sätze T1 bis T4, die Gruppe G2 die Sätze T5 bis T8, die Gruppe G3 die Sätze T9 bis T12 und die Gruppe G4 die Sätze T13 bis T16.

Jeder Gruppe ordnet man zwei Sequenzen zu. Eine erste Sequenz SEQA besteht im Einsatz der ersten Mittel TC0 für jeden Satz. Eine zweite Sequenz SEQB besteht im Einsatz weiterer Mittel für wenigstens bestimmte Sätze.

Im dargestellten Beispiel umfassen diese anderen Mittel zweite Mittel TC2 und dritte Mittel TC1.

Die zweiten Mittel TC2 werden im zweiten Satz und im vorletzten Satz jeder Gruppe eingesetzt: das heißt, in T2, T3 von G1, T6, T7 von G2, T10, T11 von G3 und T14 und T15 von G4.

Die dritten Mittel TC1 werden im ersten Satz und letzten Satz jeder Gruppe eingesetzt. Das heißt in T1, T4 von G1, T5, T8 von G2, T9, T12 von G3 und T13, T16 von G4.

In der Praxis sind diese unterschiedlichen Mittel Konstantentabellen. Die ersten Mittel entsprechen der der normalen Ausführung des DES entsprechenden ersten Konstantentabelle TC0. Die anderen Mittel TC1 und TC2 werden im Verhältnis zu dieser ersten Konstantentabelle TC0 durch Komplementierung definiert.

Die zweiten Mittel TC2 sind derart, dass sie bei dem Komplement /E der Eingangsangabe E das Komplement der Ausgangsangabe S der ersten Mittel TC0 liefern. Ein Beispiel einer zweiten, der ersten elementaren Konstantentabelle TC01 entsprechenden elementaren Tabelle TC21 wird in 9 dargestellt. Es ist anzumerken, dass die im Text verwendete Bezeichnung des Komplements /E der Bezeichnung mit einem Schrägstrich oberhalb der in den Zeichnungen komplementierten Angabe entspricht.

Die dritten Mittel sind derart, dass sie bei der Eingangsangabe E das Komplement /S der Ausgangsangabe der ersten Mittel TC0 liefern. Ein Beispiel einer dritten, der ersten elementaren Konstantentabelle TC01 entsprechenden elementaren Tabelle TC11 wird in 10 dargestellt.

Das Berechnungsprogramm besteht dann am Anfang der Ausführung des Algorithmus in der Ermittlung eines zufälligen Wertes RND1 gleich 0 oder 1, dann im Testen dieses Wertes RND1. In dem Beispiel führt man, wenn RND1 1 wert ist, die Berechnung unter Einsatz der zweiten Sequenz SEQB für jede Gruppe G1 bis G4 aus.

Wenn RND1 0 wert ist, führt man die Berechnung unter Einsatz der ersten Sequenz SEQA für jede Gruppe aus.

Ganz gleich, ob man die erste oder die zweite Sequenz einsetzt, man erhält am Ausgang jeder Gruppe das richtige Ergebnis für die Ausgangsparameter. Somit sind die Ausgangsparameter L4 und R4 der ersten Gruppe G1, L8 und R8 der zweiten Gruppe G2, L12 und R12 der dritten Gruppe G3, L16 und R16 der vierten Gruppe G4 unabhängig von der verwendeten Sequenz richtig.

Wenn man alle Sätze ausgeführt hat, erhält man die richtigen Parameter L16 und R16, die die Berechnung der richtigen chiffrierten Meldung C erlauben.

Jedoch haben bestimmte Zwischenergebnisse innerhalb der Gruppen je nach den verwendeten Sequenzen nicht dieselben Werte, sondern komplementäre Werte, wie wir unter Bezugnahme auf die 3 und 8 aufzeigen werden.

Die bereits beschriebene 3 entspricht in der Tat dem Berechnungsorganigramm der vier Sätze T1, T2, T3 und T4 der ersten Gruppe G1 in der ersten Sequenz SEQA.

8 zeigt das detaillierte Organigramm der vier Sätze T1, T2, T3 und T4 der ersten Gruppe G1 in der zweiten Sequenz SEQB.

In dieser zweiten Sequenz setzt der Satz T1 die dritten Mittel TC1 ein. Am Ausgang der Operation SBOX erhält man daher die Angabe /a (8) anstatt der Angabe a mit der ersten Sequenz SEQA (3).

Die Operation P PERM des Satzes T1, die eine einfache Permutation ist, wird daher ebenfalls am Ausgang eine im Verhältnis zur Sequenz SEQA komplementierte Angabe /c liefern.

Die Angabe g, die durch ein EXKLUSIVES ODER zwischen einer komplementierten Angabe /c und einer nicht komplementierten Angabe L0 erhalten wird, wird ebenfalls am Ausgang eine komplementierte Angabe /g liefern.

Somit erhält man mit den dritten Mitteln des Satzes T1 alle folgenden komplementierten Angaben im Verhältnis zu den Angaben, die mit der Sequenz SEQA erhalten worden wären:

  • – im Satz T1: /a, /c, /g;
  • – im Satz T2: /R1, /h, /1, /b;
  • – im Satz T3: /L2.

Dann kommt kann auf die im Satz T2 verwendeten zweiten Mittel TC2. Nach ihrer Definition erhält man durch Anwendung der komplementierten Angabe /b am Ausgang die komplementierte Angabe /a. Durch Weiterverfolgung dieser Überlegung bis zum Ende des Satzes T4 erhält man unter der Feststellung, dass ein EXKLUSIVES ODER zwischen zwei komplementierten Angaben ein nicht komplementiertes Ergebnis ergibt (zum Beispiel /L3 XOR /c = g im Satz T4), am Ausgang des Satzes T4 die nicht komplementierten Daten L4, R4.

Darüber hinaus stellt man fest, dass die kritischen Anweisungen bei allen kritischen Anfangsanweisungen von DES die Angaben oder ihre Komplemente in Abhängigkeit von der Angabe RND1 auf zufällige Weise behandeln werden, je nachdem, ob die ausgeführte Sequenz die erste SEQA oder die zweite SEQB ist.

Das Gegenmaßnahmen-Verfahren in dieser ersten Ausführungsform ist daher sehr interessant. Es erfordert nur zwei zusätzliche Operationen im Berechnungsprogramm des DES, welches die Ermittlung des zufälligen Wertes und der Test dieses Wertes sind. Das Speicherprogramm muss seinerseits die drei eingesetzten unterschiedlichen Mittel enthalten, das heißt, die drei Konstantentabellen TC0, TC1, TC2.

Zurückkommend auf 7 kann man feststellen, dass man keine Gegenmaßnahme in den Gruppen des Milieus G2 und G3 benötigt, da sie keine kritischen Anweisungen im Sinne eines DPA-Angriffs enthalten. Man könnte daher das Gegenmaßnahmen-Verfahren mit seinen beiden Sequenzen SEQA und SEQB nur auf die erste und die letzte Gruppe G1 und G4 anwenden. Es würde genügen, die erste Sequenz SEQA systematisch auf die Gruppen G2 und G3 anzuwenden.

Aber die Tatsache, dass das Gegenmaßnahmen-Verfahren auf alle Gruppen angewendet wird, verleiht der Struktur eine Kohärenz.

Somit ordnet man bevorzugt die beiden Sequenzen SEQA und SEQB jeder der Gruppen G1 bis G4 zu.

Eine zweite Ausführungsform des erfindungsgemäßen Gegenmaßnahmen-Verfahrens wird in 11 dargestellt. Diese zweite Ausführungsform ist in der Tat eine Variante der ersten. Die Bedeutung dieser Variante besteht darin, als weitere Mittel in der Sequenz SEQB nur die zweiten Mittel TC2 einzusetzen. In der Tat haben wir gesehen, dass die unterschiedlichen Mittel TC0, TC1, TC2 in der Praxis jeweils acht elementare Konstantentabellen umfassende Konstantentabellen entsprechen, was einen nicht unbeachtlichen Raum im Speicherprogramm einnimmt.

Diese Variante besteht daher darin, ausschließlich die zweiten Mittel TC2 in der Sequenz SEQB zu verwenden. Zu diesem Zweck sieht man im Berechnungsprogramm der ersten und letzten Sätze jeder Gruppe eine zusätzliche Operation CP zur Komplementierung der auf die zweiten Mittel angewendeten Eingangsangabe vor. Diese zusätzliche Operation CP ist in der Praxis ein exklusives ODER der Eingangsangabe mit logischen 1en. Wenn man auf das detaillierte Organigramm der zweiten Sequenz SEQB zur Berechnung der vier Sätze T1 bis T4 der ersten Gruppe G1 darstellende 12 Bezug nimmt, handelt es sich um die Komplementierung der Angabe b vor der Anwendung am Eingang der Operation SBOX der Sätze T1 bis T4. Da die zweiten Mittel TC2 den Eingang komplementieren, entsprechen die Komplementierungsoperation CP plus die zweiten Mittel TC2 den in der ersten Ausführungsform der Erfindung eingesetzten dritten Mitteln TC1, das heißt einer nicht am Eingang komplementierten Angabe.

Aber damit das Gegenmaßnahmen-Verfahren gemäß dieser zweiten Ausführungsform wirkungsvoll ist, muss die Anzahl von Anweisungen genau dieselbe sein, ganz gleich, welche Berechnungssequenz eingesetzt wird. Wenn nämlich eine beliebige Differenz zwischen den beiden möglichen Sequenzen SEQA und SEQB bestehen würde, würde dann eine Möglichkeit zu einem erfolgreichen DPA-Angriff bestehen.

Aus diesem Grund und wie in 13 dargestellt, sieht man in den Sätzen T1 und T4 der ersten Sequenz SEQA eine Operation ID zum identischen Abkopieren vor, die in einem exklusiven ODER mit logischen Os am Eingang der Operation SBOX besteht, um die Eingangsangabe bei gleichzeitiger Anwendung derselben Anweisungen wie bei der zusätzlichen Operation CP nicht zu ändern.

Auf diese Weise hat man dieselbe Anzahl von Anweisungen in den beiden Sequenzen.

Diese Operationen CP oder ID sind daher am Eingang der in jedem ersten und letztem Satz jeder Gruppe G1 bis G4 eingesetzten Mittel vorgesehen.

14 stellt eine dritte Ausführungsform des erfindungsgemäßen Gegenmaßnahmen-Verfahrens dar.

In dieser Ausführungsform bildet man eine erste Gruppe G1 mit den drei ersten Sätzen T1, T2, T3 und eine andere Gruppe G4 mit den drei letzten Sätzen T14, T15, T16. Jeder Gruppe wird eine erste, die ersten Mittel TC0 für jeden Satz einsetzende Sequenz SEQA und eine zweite, weitere Mittel wenigstens für bestimmte Sätze einsetzende Sequenz zugeordnet.

Am Ausgang jeder Gruppe G1, G4 erhält man unabhängig von der eingesetzten Sequenz SEQA oder SEQB das richtige Ergebnis am Ausgang L3, R3 und L16, R16.

Die anderen Mittel sind in dem Beispiel die bereits im Zusammenhang mit der ersten Ausführungsform gesehenen dritten Mittel TC1 und die vierten Mittel TC3.

Diese vierten Mittel TC3 werden im Verhältnis zu den ersten Mitteln TC0 als Mittel definiert, die auf die Entsprechung der Ausgangsangabe S mit dem Komplement /E der Eingangsangabe E hinwirken. Eine entsprechende elementare Konstantentabelle TC31 wird in 16 dargestellt.

Bei den anderen, nicht in den Gruppen inbegriffenen Sätzen, das heißt bei den Sätzen T4 bis T13, wendet man die ersten Mittel TC0 an.

Somit testet man nach der Ermittlung des zufälligen Wertes RND1 diesen Wert zur Bestimmung der auf die erste Gruppe anzuwendenden Sequenz und fährt am Ausgang mit den berechneten Parametern L3, R3 unter Ausführung der folgenden Sätze mit den ersten Mitteln TC0 fort. Am Satzende T13 wendet man die durch den zufälligen Wert RND1 bestimmte Sequenz auf die Gruppe G4 an. Man erhält die Parameter L16, R16, die zur Berechnung der chiffrierten Meldung C dienen.

15 ist ein entsprechendes detailliertes Organigramm für die zweite Sequenz SEQB.

Aus diesem Organigramm geht deutlich hervor, dass man für alle kritischen Anweisungen dieser Sätze komplementierte Daten erhält (wobei die Komplementierung durch einen Schrägstrich oberhalb der Angabe bezeichnet wird). Und die Daten L3 und R3 am Ausgang des dritten Satzes werden nicht komplementiert. Man kann die Ausführung des Algorithmus durch Übergang zum Satz T4 fortführen, auf den man die ersten Mittel TC0 gemäß der normalen Ausführung des Algorithmus anwendet.

In dieser Figur kann man feststellen, dass man bei der Operation SBOX des dritten Satzes T3 durch Vorsehen einer zusätzlichen Komplementierungsoperation CP am Ausgang der Operation SBOX die ersten Mittel TC0 anstelle der dritten Mittel TC1 einsetzen könnte. Das ist eine äquivalente Lösung.

Dann muss darauf hingewirkt werden, dass dieser zusätzlichen Komplementierungsoperation in der Sequenz SEQB die zusätzliche Operation des identischen Abkopierens ID in der Sequenz SEQA entspricht.

17 stellt ein diese Variante einsetzendes Ausführungsdiagramm dar. Für den dritten Satz der zwei Gruppen G1 und G4 setzt man in der ersten Sequenz SEQA die ersten Mittel TC0 ein, am Ausgang gefolgt von der zusätzlichen Operation Id zum Abkopieren, was mit T3(TC0, ID) bezeichnet wird. In der zweiten Sequenz SEQB setzt man für den dritten Satz die ersten Mittel TC0 ein, am Ausgang gefolgt von der zusätzlichen Komplementierungsoperation CP, was mit T3(TC0, CP) bezeichnet wird.

Somit zeigen die zweite Ausführungsform und diese Variante der dritten Ausführungsform den Einsatz zusätzlicher Operationen am Eingang oder am Ausgang der unterschiedlichen Mittel.

Ganz allgemein kann man im erfindungsgemäßen Gegenmaßnahmen-Verfahren daher in der zweiten Sequenz SEQB und bei einem oder mehreren Sätzen eine zusätzliche Komplementierungsoperation CP am Eingang oder am Ausgang der eingesetzten Mittel vorsehen. Jeder zusätzlichen Komplementierungsoperation CP in der zweiten Sequenz entspricht dann eine zusätzliche Operation zum identischen Abkopieren ID in der ersten Sequenz SEQA.

Die vorliegende Erfindung findet auf den Kryptographie-Algorithmus mit geheimem Schlüssel DES Anwendung, für welchen mehrere nicht einschränkende Anwendungsbeispiele beschrieben wurden. Er findet ganz allgemein auf einen Kryptographie-Algorithmus mit geheimem Schlüssel mit sechzehn Berechnungssätzen Anwendung, dessen kritische Anweisungen sich unter den Anweisungen der drei ersten oder drei letzen Sätze befinden.

Eine ein erfindungsgemäßes Gegenmaßnahmen-Verfahren umsetzende elektronische Komponente 1 in einem Kryptographie-Algorithmus mit geheimem Schlüssel DES umfasst im typischen Fall, wie in 18 dargestellt, einen Mikroprozessor mP, einen Programmspeicher 2 und einen Arbeitsspeicher 3. Um den Einsatz der unterschiedlichen Mittel TC0, TC1, TC2, die in der Praxis im Programmspeicher gespeicherte Konstantentabellen sind, erfindungsgemäß verwalten zu können, sind Mittel 4 zum Erzeugen eines zufälligen Wertes zwischen 0 und 1 vorgesehen, die, wenn man auf die Organigramme der 7 und 11 Bezug nimmt, den Wert von RND1 bei jeder Ausführung des DES liefern werden. Eine derartige Komponente kann ganz besonders in einer Chipkarte 5 eingesetzt werden, um ihre Unverletztbarkeit zu verbessern.


Anspruch[de]
  1. Einen kryptographischen Algorithmus mit geheimem Schlüssel (K) vom Typ DES zur Berechnung einer chiffrierten Meldung (C) ausgehend von einer Eingangsmeldung (M) umsetzendes Gegenmaßnahmen-Verfahren in einer elektronischen Komponente, wobei die Umsetzung des Algorithmus sechzehn Berechnungssätze (T1, ..., T16) umfasst, wobei jeder Satz erste Mittel (TC0) vom Typ Konstantentabelle einsetzt, um eine Ausgangsangabe ausgehend von einer Eingangsangabe zu liefern, wobei die Ausgangs- und/oder die abgeleiteten Angaben durch im Sinne von Gegenmaßnahmen-Angriffen zu Beginn und am Ende des Algorithmus kritische Anweisungen in den drei letzten (T1, T2, T3) und den letzten drei Sätzen (T14, T15, T16) behandelt werden, dadurch gekennzeichnet, dass man eine die wenigstens die drei ersten Sätze umfassende Gruppe (G1) bildet und eine wenigstens die drei letzten Sätze umfassende andere Gruppe (G4) und dass man jeder dieser Gruppen (G1 und G4) eine die ersten Mittel (TC0) in jedem Satz einsetzende erste Sequenz (SEQA) und eine weitere Mittel (TC1, TC2, TC3) vom Typ Konstantentabelle wenigstens in bestimmten Berechnungen einsetzende zweite Sequenz (SEQB) zuordnet, wobei die anderen Mittel die eine und/oder die andere Eingangs- (E) und/oder Ausgangseingabe (S) der ersten Mittel komplementieren, wobei die genannten ersten und zweiten Sequenzen derart sind, dass sie ein und dasselbe Ergebnis am Ausgang des ersten Satzes jeder Gruppe für ein und die dieselbe bestimmte Eingangsmeldung (M) liefern, wobei die Wahl der in den betroffenen Gruppen auszuführenden Sequenz von einem statistischen Wahrscheinlichkeitsgesetz ein Halb abhängt, um alle von den genannten kritischen Anweisungen behandelten Angaben unvorhersagbar zu machen, und zwar zu Beginn der Ausführung des Algorithmus durch Ermittlung eines zufälligen Wertes (RND1), wobei die gewählte Sequenz diejenige ist, die in jeder der betroffenen Gruppen eingesetzt wird, und dass die Anzahlen von Anweisungen genau dieselben sind wie die eingesetzte Berechnungssequenz.
  2. Gegenmaßnahmen-Verfahren gemäß Anspruch 1, dadurch gekennzeichnet, dass die zweite Sequenz (SEQB) bei einem oder mehreren Sätzen eine zusätzliche Komplementierungsoperation (CP) am Eingang oder am Ausgang der eingesetzten Mittel umfasst und dass jeder zusätzlichen Komplementierungsoperation in der zweiten Sequenz eine zusätzliche Operation der identischen Kopie (ID) in der ersten Sequenz entspricht.
  3. Gegenmaßnahmenverfahren gemäß einem der vorherigen Ansprüche, dadurch gekennzeichnet, dass man vier Gruppen (G1, ..., G4) von vier jeweils aufeinander folgenden Sätzen (T1, ..., T4) bildet, dass man jeder Gruppe die erste Sequenz (SEQA) zuordnet und dass man wenigstens der ersten Gruppe (G1) und der letzten Gruppe (G4) die zweite Sequenz (SEQB) zuordnet.
  4. Gegenmaßnahmenverfahren gemäß Anspruch 3, dadurch gekennzeichnet, dass die zweite Sequenz (SEQB) jeder Gruppe (G1, ..., G4) zugeordnet ist.
  5. Gegenmaßnahmenverfahren gemäß Anspruch 1 bis 2, dadurch gekennzeichnet, dass die erste Gruppe (G1) aus den drei ersten Sätzen (T1, T2, T3) gebildet wird und dass die letzte Gruppe aus den drei letzten Sätzen (T14, T15, T16) gebildet wird.
  6. Elektronische Sicherheitskomponente mit einem Mikroprozessor &mgr;P, einem Programmspeicher (2) und einem Arbeitsspeicher (3), die die Umsetzung aller Stufen des Gegenmaßnahmen-Verfahrens gemäß einem der vorherigen Ansprüche erlaubt, dadurch gekennzeichnet, dass die unterschiedlichen Mittel (TC0, TC1, TC2) zur Lieferung einer Ausgangsangabe ausgehend von einer Eingangsangabe im Speicherprogramm der genannten Komponente fixiert sind und dass sie Mittel (4) zum Erzeugen eines zufälligen Wertes (RND1) von 0 bis 1 zum Verwalten des Einsatzes der genannten unterschiedlichen Mittel umfasst.
  7. Chipkarte mit einer elektronischen Sicherheitskomponente gemäß Anspruch 7.
Es folgen 13 Blatt Zeichnungen






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

Patent Zeichnungen (PDF)

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