Die Erfindung betrifft ein Verfahren zum Durchführen einer kryptographischen Berechnung unter Verwendung eines kryptographischen Schlüssels, das gegen Ausspähen des Schlüssels über Seitenkanalangriffe geschützt ist.The invention relates to a method of performing a cryptographic computation using a cryptographic key protected against spying on the key via side channel attacks.
Kryptographische Berechnungen werden z. B. von allgemeinen Prozessoren (CPUs) durchgeführt, alternativ häufig von Krypto-Coprozessoren, die den allgemeinen Prozessoren zugeordnete spezielle Prozessoren sind. Insbesondere Chipkarten für Zahlungsverkehr- oder Mobilfunkanwendungen haben häufig Prozessoren (CPUs) mit Krypto-Coprozessoren. Viele Chipkarten für Zahlungsverkehr- oder Mobilfunkanwendungen haben speziell für DES oder AES ausgelegte Krypto-Coprozessoren (siehe nächster Absatz).Cryptographic calculations are z. Frequently performed by general purpose processors (CPUs), alternatively often by crypto co-processors, which are dedicated processors to the general processors. In particular, smart cards for payment or mobile applications often have processors (CPUs) with crypto coprocessors. Many smart cards for payment or mobile applications have crypto coprocessors specifically designed for DES or AES (see next paragraph).
Durch eine kryptographische Berechnung werden Eingangsdaten unter Verwendung eines geheimen Schlüssels zu Ausgangsdaten verarbeitet, z. B. Klartextdaten (Eingangsdaten) mit einem Schlüssel zu Chiffredaten (Ausgangsdaten) verschlüsselt oder umgekehrt Chiffredaten (Eingangsdaten) mit einem Schlüssel zu Klartextdaten (Ausgangsdaten) entschlüsselt. Beispiele für symmetrische (Verschlüsselungs-Schlüssel = Entschlüsselungs-Schlüssel) kryptographische Berechnungen sind die Algorithmen DES (Data Encryption Standard) und AES (Advanced Encryption Standard).Through a cryptographic calculation, input data is processed into output data using a secret key, e.g. For example, plain text data (input data) is encrypted with a key to cipher data (output data) or, conversely, cipher data (input data) is decrypted with a key to plain text data (output data). Examples of symmetric (encryption key = decryption key) cryptographic calculations are the algorithms DES (Data Encryption Standard) and AES (Advanced Encryption Standard).
Beim AES, der in mehrere Runden (z. B. 10, 12 oder 14) unterteilt ist, werden die Eingangsdaten und der Schlüssel in Blöcke unterteilt und blockweise verarbeitet. Innerhalb jeder Runde werden die Daten byteweise verarbeitet, so dass im Detail jeweils ein Eingangsdatenbyte (Klartextbyte bei Verschlüsselung bzw. Chiffretextbyte bei Entschlüsselung) mit einem Schlüsselbyte verarbeitet wird.In the AES, which is divided into several rounds (eg 10, 12 or 14), the input data and the key are divided into blocks and processed in blocks. Within each round, the data is processed byte by byte, so that in each case an input data byte (plaintext byte for encryption or cipher text byte for decryption) is processed with a key byte.
So wird z. B. bei einer AES Verschlüsselung, die in 2 auszugsweise schematisch gezeigt ist, ein Klartext P mit einem Schlüssel K zu einem Chiffretext C verschlüsselt. Der Klartext P = pp...ppp besteht aus einer Folge von Klartextbytes p, der Schlüssel K = kk...kkk aus einer Folge von Schlüsselbytes k. Am Eingang jeder Runde (in 2 auszugsweise gezeigt sind die ersten beiden Runden R = 1 und R = 2) wird eine Teilberechnung durchgeführt, anhand der später beispielhaft ein DPA Angriff beschrieben wird. Bei der Teilberechnung wird ein Klartextbyte p mit einem Schlüsselbyte k verxort (p ⊕ k), das Ergebnis der Verxorung in eine (Substitution-)Tabelle S (S-Box) eingesetzt und hierdurch durch einen Tabellenzugriff auf die Tabelle S ein Zwischenwert x = S[p ⊕ k] berechnet. Der Zwischenwert x wird innerhalb der Runde weiteren Rechenschritten wie ShiftRow, MixColumn zugeführt, die in 2 nicht gezeigt sind. Schlüsselexpansionen und Auswahl von Schlüsselbits, die bei AES durchgeführt werden, sind in 2 ebenfalls nicht gezeigt. Tabellenzugriffe sind besonders gefährdet durch DPA Angriffe.So z. For example, with an AES encryption that is in 2 is shown schematically in excerpts, a plaintext P with a key K to a ciphertext C encrypted. The plaintext P = pp ... ppp consists of a sequence of plaintext bytes p, the key K = kk ... kkk from a sequence of key bytes k. At the entrance of each round (in 2 shown in extracts are the first two rounds R = 1 and R = 2), a partial calculation is carried out, based on the example of a DPA attack is described later. In the sub-calculation, a plaintext byte p with a key byte k is used (p ⊕ k), the result of the corruption is inserted in a (substitution) table S (S-box) and thereby an intermediate value x = S through a table access to the table S [p ⊕ k] is calculated. The intermediate value x is fed within the round to further computation steps such as ShiftRow, MixColumn, in 2 not shown. Key expansions and selection of key bits performed at AES are in 2 also not shown. Table accesses are particularly vulnerable to DPA attacks.
Da der Stromverbrauch eines Prozessors (z. B. in einer Chipkarte) von den verarbeiteten Daten abhängt, sind auf Prozessoren implementierte kryptographische Berechnungen anfällig gegenüber Seitenkanalangriffen, bei denen der zeitaufgelöste Stromverbrauch des Prozessors während der Durchführung der Berechnung gemessen wird. Meisten ist der Stromverbrauch genauer vom Hamminggewicht der Daten abhängig, d. h. von der Anzahl Einen in den Daten in der Binärdarstellung. Der Stromverbrauch des Prozessors während der Durchführung der Berechnung, aufgezeichnet gegenüber der während der Berechnung verstrichenen Zeit, wird als Stromkurve bezeichnet. Stromkurven eines Prozessors für eine Berechnung werden beispielsweise mittels eines Oszilloskops aufgezeichnet.Because the power consumption of a processor (eg, in a smart card) depends on the data being processed, processor-implemented cryptographic computations are prone to side-channel attacks in which the time-resolved power consumption of the processor is measured while performing the computation. Most of the power consumption depends more exactly on the Hamminggewicht of the data, d. H. from the number one in the data in binary representation. The power consumption of the processor during the execution of the calculation, recorded against the elapsed time during the calculation, is called the current curve. Current curves of a processor for a calculation are recorded, for example, by means of an oscilloscope.
Bei einem DPA (Differential Power Analysis) Angriff, teilweise auch Correlation Power Attack (CPA) genannt, wird eine Mehrzahl von Stromkurven (z. B. ungefähr 1000) für strukturell gleiche, mit zufällig variierenden Eingangsdaten durchgeführte Berechnung aufgezeichnet und synchronisiert. Bei der Berechnung werden mit bekannten Eingangsdaten und einem geheimen Schlüssel Ausgangsdaten berechnet. Für jeden möglichen Wert des Schlüssels wird eine zeitaufgelöste Korrelationskurve zwischen den synchronisierten Stromkurven und dem Hamminggewicht HW der mit dem jeweiligen Schlüssel erzielten Ausgangsdaten berechnet. Die Korrelationskurven für falsche Schlüssel bestehen aus einem mehr oder weniger gleichmäßigen Rauschen, ähnlich wie die in 1b gezeigte Korrelationskurve. Die Korrelationskurve für den Schlüssel, mit dem die Berechnung durchgeführt wurde, hat an einem zuvor unbekannten Zeitpunkt eine statistische Auffälligkeit in Form eines Ausschlags („Peaks”), ähnlich wie die in 1a gezeigte Korrelationskurve.In a DPA (Differential Power Analysis) attack, sometimes referred to as Correlation Power Attack (CPA), a plurality of current waveforms (eg, about 1000) are recorded and synchronized for structurally equal computation performed with randomly varying input data. In the calculation, output data is calculated using known input data and a secret key. For each possible value of the key, a time-resolved correlation curve between the synchronized current curves and the Hamming weight HW of the output data obtained with each key is calculated. The correlation curves for wrong keys consist of a more or less uniform noise, similar to the one in 1b shown correlation curve. The correlation curve for the key with which the calculation was performed has a statistical abnormality in the form of a peak ("peak") at a previously unknown time, similar to the one in 1a shown correlation curve.
Bei einem DPA Angriff höherer (zweiter, dritter, vierter, ...) Ordnung werden Stromkurven an mehreren (zwei, drei, vier, ...) Zeitpunkten im zeitlichen Ablauf der Berechnung aufgenommen. [PRB10] beschreibt eine DPA Angriff zweiter Ordnung.In a DPA attack of higher (second, third, fourth, ...) order, current curves are recorded at several (two, three, four, ...) times in the time course of the calculation. [PRB10] describes a second-order DPA attack.
Bei einem DPA Angriff auf die Teilberechnung des AES aus 2 wird ein Klartextbyte p des bekannten Schlüssels K mit einem Schlüsselbyte k des geheimen Schlüssels K verxort (p ⊕ k), das Ergebnis der Verxorung in die 256-Byte Substitutionstabelle S (S-Box) eingesetzt und hierdurch durch Tabellenzugriff der Zwischenwert x = S[p ⊕ k] berechnet. Der Angreifer zeichnet ungefähr 1000 Stromkurven der Teilberechnung auf (p variiert dabei, k bleibt gleich), synchronisiert sie und berechnet für jeden möglichen Wert 0,...,255 des Schlüsselbytes k die Korrelationskurve zwischen den synchronisierten gemessenen Stromkurven und dem Hamminggewicht HW(x) des mit dem jeweiligen Schlüsselbyte k berechneten Zwischenwerts x. Die Korrelationskurven für falsche Schlüsselbytes bestehen aus einem mehr oder weniger gleichmäßigen Rauschen, ähnlich wie die in 1b gezeigte Korrelationskurve. Die Korrelationskurve für das richtige Schlüsselbyte, mit dem die Berechnung durchgeführt wurde, hat an einem zuvor unbekannten Zeitpunkt einen Ausschlag, ähnlich wie die in 1a gezeigte Korrelationskurve. Dieses Verfahren wird mit jedem Schlüsselbyte k des Schlüssels K durchgeführt, bis der Schlüssel K Byte für Byte rekonstruiert ist. In case of a DPA attack on the partial calculation of the AES 2 a plaintext byte p of the known key K with a key byte k of the secret key K verxort (p ⊕ k), the result of Verxorung in the 256-byte substitution table S (S-box) is inserted and thereby by table access the intermediate value x = S [ p ⊕ k]. The attacker records approximately 1000 partial calculation power curves (p varies, k remains the same), synchronizes them, and calculates the correlation curve between the synchronized measured current curves and the Hamming weight HW (x ) of the intermediate value x calculated with the respective key byte k. The correlation curves for wrong key bytes consist of a more or less uniform noise, similar to the ones in 1b shown correlation curve. The correlation curve for the correct key byte that performed the calculation has a rash at a previously unknown time, similar to the one in 1a shown correlation curve. This procedure is performed with each key byte k of the key K until the key K is reconstructed byte by byte.
Gemäß einem firmeninternen unveröffentlichten Stand der Technik wird als Gegenmaßnahme gegen DPA Angriffe die „00/FF-Maskierung” vorgesehen. Hierbei wird ein Zwischenergebnis einer Teilberechnung in der Berechnung zufallsgesteuert entweder direkt berechnet, so dass das Zwischenergebnis erzeugt wird, oder komplementiert berechnet, so dass das Einerkomplement des Zwischenergebnisses berechnet wird. Bedarfsweise müssen dabei die Eingangsdaten (Klartext oder Chiffretext) und der Schlüssel unabhängig voneinander zufallsgesteuert komplementiert werden und am Ausgang der Berechnung die Ausgangsdaten (Chiffretext bzw. Klartext) komplementiert werden. Beispielsweise wird also zufallsgesteuert die Berechnung so durchgeführt, dass eine Teilberechnung x = S[p ⊕ k] durchgeführt wird, oder eine komplementierende Teilberechnung x = S'[p ⊕ k] durchgeführt wird, mit einer einerkomplementierten S-Box S'[x] = und einerkomplementierten Klartextbytes und Schlüsselbytes. Werden für einen Angriff ungefähr 1000 Durchführungen der kryptographischen Berechnung durchgeführt, wird statistisch in je der Hälfte mit dem Zwischenwert x und dem Einerkomplement x gerechnet. Für das Hamminggewicht HW(x) der komplementierenden Teilberechnung x = S'[p ⊕ k] gilt die Formel HW(x) = 8 – HW(x), in der das Hamminggewicht HW(x) der nicht-komplementierten Berechnung mit negativem Vorzeichen vorkommt. Hierdurch heben sich bei Zufallssteuerung im Mittel Korrelationen zwischen den Stromkurven und dem mit dem Schlüssel erzielten Rechenergebnis auf. Somit ergibt sich für zufallsgesteuertes Rechnen mit dem Zwischenwert x = S[p ⊕ k] oder dem komplementierten Zwischenwert x = S'[p ⊕ k] auch beim Rechnen mit dem richtigen Schlüsselbyte eine Korrelationskurve wie die in 1b gezeigte, wie sie ohne Abwehrmaßnahmen nur für ein falsch geratenes Schlüsselbit entsteht. Die Durchführung der Berechnung zufallsgesteuert mit dem Zwischenwert x = S[p ⊕ k] oder dem komplementierten Zwischenwert x = S'[p ⊕ k] ist somit resistent gegen den oben beschriebenen DPA-Seitenkanalangriff mit Korrelationsberechnung. Zudem ist die 00/FF-Maskierung speichersparend.According to an in-house unpublished state of the art, "00 / FF masking" is provided as a countermeasure against DPA attacks. In this case, an intermediate result of a partial calculation in the calculation is randomly calculated either directly, so that the intermediate result is generated, or computed computed, so that the one's complement of the intermediate result is calculated. If necessary, the input data (plaintext or ciphertext) and the key have to be complemented randomly independently of each other and the output data (ciphertext or plaintext) must be complemented at the output of the calculation. For example, the calculation is thus carried out randomly in such a way that a partial calculation x = S [p ⊕ k] is carried out, or a complementary partial calculation x = S '[ p ⊕ k ] is performed with a complemented S-box S '[x] = and one complemented plaintext bytes and key bytes. If approximately 1000 executions of the cryptographic computation are performed for an attack, it will be statistically divided into half each with the intermediate value x and the one's complement x expected. For the Hamming weight HW ( x ) the complementing part calculation x = S '[ p ⊕ k ] the formula applies HW ( x ) = 8 - HW (x), in the Hamming weight HW ( x ) the non-complemented calculation with a negative sign occurs. As a result, correlations between the current curves and the calculated result obtained with the key cancel each other out at random control on average. This results in randomized arithmetic with the intermediate value x = S [p ⊕ k] or the complemented intermediate value x = S '[ p ⊕ k ] even when calculating with the right key byte a correlation curve like the one in 1b showed how it arises without defensive measures only for a wrong guess key bit. Performing the calculation randomly with the intermediate value x = S [p ⊕ k] or the complemented intermediate value x = S '[ p ⊕ k ] is thus resistant to the DPA side channel attack with correlation calculation described above. In addition, the 00 / FF masking saves memory.
Die Berechnung des 1er-Komplements eines Werts wird wahlweise durch Verxoren des Werts mit hexadezimal FF (andere Schreibweise: 0xff) durchgeführt, die Bereitstellung des Werts selbst wird in diesem Fall wahlweise durch Verxoren mit 0 an derselben Stelle im Berechnungsablauf, an der beim 1er-Komplement mit FF verxort wird, durchgeführt. Durch Verxoren mit FF wird ein Wert komplementiert. Durch Verxoren mit Null bleibt der Wert unverändert. Durch die Durchführung einer Verxorung in beiden Fällen wird verschleiert, wann der Wert und wann das 1er-Komplement des Werts verwendet wird. Aus dieser Art der Durchführung der Zufallssteuerung resultiert der Name „00/FF-Maskierung”.The calculation of the 1's complement of a value is carried out optionally by forcing the value with hexadecimal FF (other notation: 0xff), the provision of the value itself in this case optionally by verifying with 0 at the same place in the calculation process, at the 1er Complement with FF is being carried out. Verxoring with FF complements a value. By zeroing the value remains unchanged. Performing a forgery in both cases disguises when the value and when the 1's complement of the value is used. From this way of carrying out the random control results the name "00 / FF masking".
Bei einem variierten DPA Angriff wird statt der Korrelation eine andere Statistik berechnet, beispielsweise die Varianz oder eine eindimensionale Kolmogorov-Smirnov Statistik. Hierdurch mitteln sich die statistischen Auffälligkeiten bei Verwendung des richtigen Schlüsselbytes auch dann nicht heraus, wenn zufallsgesteuert mit dem Zwischenwert x = S[p ⊕ k] oder dem komplementierten Zwischenwert x = S'[p ⊕ k] gerechnet wird. Somit ist dennoch erkennbar, wann mit dem richtigen Schlüssel gerechnet wird.In a varied DPA attack, instead of the correlation, another statistic is computed, such as variance or a one-dimensional Kolmogorov-Smirnov statistic. As a result, the statistical abnormalities do not average out when using the correct key byte, even if randomly with the intermediate value x = S [p ⊕ k] or the complemented intermediate value x = S '[ p ⊕ k ] is expected. Thus, it is still recognizable when the right key is expected.
Eine weitere Gegenmaßnahme gegen DPA Angriffe besteht in der XOR-Maskierung, die beispielsweise in DE 198 22 217 A1 beschrieben ist, und wobei statt Eingangsdaten E mit einer Zufallszahl r verxorte Eingangsdaten E' = E ⊕ r verarbeitet werden.Another countermeasure against DPA attacks is XOR masking, which can be found in, for example, DE 198 22 217 A1 is described, and wherein instead of input data E with a random number r verxorte input data E '= E ⊕ r are processed.
Bei der XOR-Maskierung ist es wichtig, dass stets alle Zwischenwerte maskiert sind. Wird unvorsichtig maskiert, ist dies nicht der Fall. Wird beim AES in einer Teilberechnung, z. B. derjenigen aus 2, eine Verschlüsselung eines maskierten Klartextbytes p' = p ⊕ r mit einem maskierten Schlüsselbyte k' = k ⊕ r durchgeführt, ergibt sich (p ⊕ r) ⊕ (k ⊕ r) = p ⊕ k = x, also ein unmaskiertes Verschlüsselungsergebnis bzw. Zwischenergebnis x. Dass alle Zwischenergebnisse maskiert sind, und niemals unmaskierte Zwischenergebnisse auftreten, wird beispielsweise durch unterschiedliche Maskierung von Eingangsdaten und Schlüssel erreicht. Beispielsweise werden die Eingangsdaten (Klartext oder Chiffretext) mit zwei Zufallszahlen r, s maskiert, der Schlüssel mit nur einer Zufallszahl r maskiert und eine Kompensationsmaskierung durchgeführt. Beispielsweise wird die Maskierung durchgeführt gemäß (((p ⊕ r) ⊕ s) ⊕ (k ⊕ r)) ⊕ (r ⊕ s) = p ⊕ k ⊕ r = x ⊕r = xXOR. Das Klartextbyte p wird also mit r und s maskiert, das Schlüsselbyte wird nur mit s maskiert, und zudem die Kompensationsmaskierung mit beiden Zufallszahlen r, s durchgeführt. Hierdurch taucht statt des Zwischenergebnisses x ein mit r maskiertes Zwischenergebnis xXOR = x ⊕ r auf, vgl. 3. Eine Berechnung mit sorgfältiger XOR-Maskierung ist resistent gegen den oben beschriebenen DPA Angriff, unabhängig von der verwendeten Statistik (z. B. Korrelation, Varianz, eindimensionale Kolmogorov-Smirnov Statistik). Das Zwischenergebnis der Teilberechnung aus 2 wird berechnet gemäß S'[x] = S[x ⊕ r1] ⊕ r2, mit r1, r2 unabhängigen Zufallszahlen. Hieraus ist ersichtlich, dass für alle Werte der Zufallszahlen r1 und r2 eine eigene Substitutionstabelle (S-Box) S' benötigt wird. Wahlweise wird für jeden möglichen Wert der Zufallszahl r (= r1 bzw. r2) eine mit r maskierte Substitutionstabelle (S-Box) S' abgespeichert (z. B. in der Chipkarte bzw. dem Prozessor), also bei einer 256 Byte großen Substitutionstabelle (S-Box) z. B. 256 verschiedene 256-Byte-Tabellen. Alternativ wird die Substitutionstabelle (S-Box) erst nach der Festlegung der Zufallszahl r berechnet, vorzugsweise in einem dem Prozessor zugeordneten Arbeitsspeicher RAM. Dies kostet allerdings Rechenzeit und ggf. Speicherplatz im Arbeitsspeicher RAM. Im Verlauf der Durchführung des Algorithmus, z. B. des AES, und sobald die Zufallszahl festgelegt ist, wird dagegen stets dieselbe Substitutionstabelle verwendet. Beim Beispiel aus 2 wird also für alle Klartextbytes p des Klartexts P und Schlüsselbytes k des Schlüssels K dieselbe Substitutionstabelle verwendet. Hierdurch sind bei der Teilberechnung aus 2, durchgeführt für unterschiedliche Klartextbytes p, p' und Schlüsselbytes k, k', d. h. an unterschiedlichen Zeitpunkt t, t' im AES, der berechnete Zwischenwert xXOR = S[p ⊕ k] ⊕ r bzw. x'XOR = S[p' ⊕ k'] ⊕ r durch dieselbe Zugriffszahl r maskiert, was einen Schwachpunkt darstellt.For XOR masking, it is important that all intermediate values are always masked. If carelessly masked, this is not the case. Is the AES in a sub-calculation, z. B. those from 2 , an encryption of a masked plaintext byte p '= p ⊕ r performed with a masked key byte k' = k ⊕ r, (p ⊕ r) ⊕ (k ⊕ r) = p ⊕ k = x, that is an unmasked encryption result or Intermediate result x. That all intermediate results are masked, and never unmasked intermediate results occur, for example, achieved by different masking of input data and keys. For example, the input data (plaintext or ciphertext) with two random numbers r, s masked, the key is masked with only a random number r and a compensation masking performed. For example, masking is performed according to (((p⊕r) ⊕s) ⊕ (k⊕r)) ⊕ (r⊕s) = p⊕k⊕r = x⊕r = x XOR . The plaintext byte p is thus masked with r and s, the key byte is masked only with s, and in addition the compensation masking with both random numbers r, s is performed. As a result, instead of the intermediate result x, an intermediate result x XOR = x ⊕ r masked with r appears, cf. 3 , A calculation with careful XOR masking is resistant to the DPA attack described above, regardless of the statistics used (eg, correlation, variance, one-dimensional Kolmogorov-Smirnov statistic). The intermediate result of the partial calculation 2 is calculated according to S '[x] = S [x ⊕ r1] ⊕ r2, with r1, r2 independent random numbers. From this it can be seen that a separate substitution table (S-box) S 'is required for all values of the random numbers r1 and r2. Optionally, for each possible value of the random number r (= r1 or r2), a substitution table (S-box) S 'masked with r is stored (eg in the chip card or the processor), ie in a 256-byte substitution table (S-box) z. For example, 256 different 256-byte tables. Alternatively, the substitution table (S-box) is calculated only after the determination of the random number r, preferably in a RAM allocated to the processor. However, this costs computing time and possibly memory space in the RAM RAM. In the course of the implementation of the algorithm, for. AES, for example, and once the random number is set, the same substitution table will always be used. In the example off 2 Thus, the same substitution table is used for all plaintext bytes p of the plaintext P and key bytes k of the key K. As a result, are in the sub-calculation off 2 , carried out for different plaintext bytes p, p 'and key bytes k, k', ie at different times t, t 'in the AES, the calculated intermediate value x XOR = S [p ⊕ k] ⊕ r or x' XOR = S [p '⊕ k'] ⊕ r is masked by the same access number r, which is a weak point.
Die Tatsache, dass bei der XOR-Maskierung bei allen Tabellenaufrufen dieselbe Tabelle (z. B. AES S-Box) verwendet wird, kann für einen DPA Angriff höherer Ordnung genutzt werden, wie er für AES z. B. in [PRB10] beschrieben ist. Beim DPA Angriff zweiter Ordnung aus [PRB10] wird der Stromverbrauch j(t), j(t') an zwei Zeitpunkten t, t' gemessen und normiert zu j(t), j(t'). Die Korrelation zwischen dem Produkt j(t)·j(t') und dem Hamminggewicht des Werts x ⊕ x'= S[p ⊕ k] ⊕ S[p' ⊕ k'] wird für jedes mögliche Schlüsselpaar k, k' und jede Paar von Zeitpunkten t, t' dazu berechnet. Für den richtigen Schlüssel ergibt sich eine Korrelationskurve wie die in 1a gezeigte, mit dem signifikanten Ausschlag an einem Zeitpunkt. Der Rechenaufwand für den Angriff zweiter Ordnung aus [PRB10] steigt mit der Anzahl zu berücksichtigender Zeitpunkte und Schlüssel quadratisch an und ist somit erheblich.The fact that the same table (eg AES S-Box) is used in all table calls during XOR masking can be used for a higher-order DPA attack, as used for AES z. As described in [PRB10]. In the second-order DPA attack from [PRB10], the current consumption j (t), j (t ') is measured and normalized at two points in time t, t' j (T), j (T '). The correlation between the product j (T) · j (T ') and the Hamming weight of the value x ⊕ x '= S [p ⊕ k] ⊕ S [p' ⊕ k '] is calculated for each possible key pair k, k' and each pair of times t, t 'thereto. For the right key, there is a correlation curve like the one in 1a shown, with the significant rash at a time. The computational effort for the second-order attack from [PRB10] increases quadratically with the number of times and keys to be taken into account and is therefore significant.
In der deutschen Patentanmeldung DE 10 2012 018 924.9 der Anmelderin der vorliegenden Anmeldung ist ein intern „erweitere Maskierung” genanntes Verfahren zum Durchführen einer kryptographischen Berechnung unter Verwendung eines kryptographischen Schlüssels angegeben, das gegen Ausspähen des Schlüssels über Seitenkanalangriffe, insbesondere DPA Angriffe höherer Ordnung, geschützt ist, so dass die Schlüsselausspähung verhindert ist oder zumindest stark erschwert ist, und das zugleich effizient ist.In the German patent application DE 10 2012 018 924.9 Applicant of the present application is provided an internally "extended masking" method for performing cryptographic computation using a cryptographic key that is protected against spying the key via side channel attacks, in particular higher order DPA attacks, such that key spying is prevented or is at least severely hampered, and that is at the same time efficient.
Das in 10 2012 018 924.9 angegebene Verfahren hat vom Grundsatz her die Struktur einer Kombination einer Basismaskierung – z. B. XOR-Maskierung- und einer 00/FF-Maskierung, angewandt auf eine kryptographische Berechnung, um geheime Daten der Berechnung vor Ausspähung zu schützen. Die erfindungsgemäße Maskierung wird intern bei der Anmelderin auch erweiterte Maskierung genannt.This in 10 2012 018 924.9 specified method has in principle the structure of a combination of a base masking - z. XOR masking and 00 / FF masking applied to a cryptographic computation to protect secret data from being spied out. The mask according to the invention is also called internal masking by the applicant.
Das Verfahren aus 10 2012 018 924.9 ist zur Ausführung in einem Prozessor (z. B. Mikroprozessor, CPU, Krypto-Coprozessor, Krypto-Beschleuniger) eingerichtet, der zum Durchführen einer kryptographischen Berechnung eingerichtet ist, bei der aus Eingangsdaten unter Verwendung eines kryptographischen Schlüssels und über die Erzeugung von Zwischenwerten Ausgangsdaten erzeugt werden. Ein Beispiel einer solchen kryptographischen Berechnung ist der AES. Bei der Durchführung der Berechnung wird eine Basismaskierung angewandt, durch welche zumindest manche, vorzugsweise alle, Zwischenwerte als maskierte Zwischenwerte in die Berechnung einfließen. Das Verfahren zeichnet sich dadurch aus, dass bei der Durchführung der Berechnung zusätzlich eine Sekundärmaskierung angewandt wird, wobei für jeden mittels der Basismaskierung maskierten Zwischenwert das Einerkomplement des maskierten Zwischenwerts gebildet wird, der maskierte Zwischenwert oder das Einerkomplement des maskierten Zwischenwerts bereitgestellt werden und zufallsgesteuert die Berechnung entweder mit dem maskierten Zwischenwert oder mit dem Einerkomplement des maskierten Zwischenwerts durchgeführt wird.The procedure off 10 2012 018 924.9 is adapted for execution in a processor (eg, microprocessor, CPU, crypto-coprocessor, crypto-accelerator) adapted to perform a cryptographic computation in which output data is obtained from input data using a cryptographic key and via the generation of intermediate values be generated. An example of such a cryptographic calculation is the AES. In carrying out the calculation, a base masking is applied by which at least some, preferably all, intermediate values are included as masked intermediate values in the calculation. The method is characterized in that, when performing the calculation, secondary secondary masking is additionally applied, wherein for each intermediate masked by the basic masking, the one's complement of the masked intermediate value is formed, the masked intermediate value or the one's complement of the masked intermediate value is provided, and the calculation is randomized is performed with either the masked intermediate value or the one's complement of the masked intermediate value.
Wie eingangs beschrieben, z. B. mit Verweis auf [PRB10], ist ein Ausspähen des geheimen Schlüssels einer XOR-maskierten kryptographischen Berechnung möglich mit einem DPA Angriff zweiter Ordnung, bei dem der Stromverbrauch j(t), j(t') an zwei Zeitpunkten t, t', d. h. bei zwei unterschiedlichen Rechenschritten innerhalb der Berechnung, gemessen und ausgewertet wird. Bei [PRB10] sind die betrachteten Rechenschritte innerhalb der Berechnung durch Tabellenzugriffe verwirklicht. Der Schwachpunkt, der bei dem Angriff ausgenutzt wird ist, dass an den beiden Zeitpunkten dieselbe Tabelle verwendet wird. Gemäß der Erfindung wird zusätzlich zur Basismaskierung (z. B. XOR) die Sekundärmaskierung angewandt, gemäß der zufallsgesteuert entweder mit dem Zwischenwert oder dem Einerkomplement des Zwischenwerts gerechnet wird. Hierdurch werden Rechenschritte an unterschiedlichen Zeitpunkten im Ablauf der Berechnung, die bei einer reinen XOR-Maskierung gleichartig wären, zufallsgesteuert unterschiedlich gemacht. Für eine als Tabellenzugriff verwirklichte Teilberechnung (Rechenschritt) bedeutet dies, dass für die unterschiedlichen Teilberechnungen – oder gleichbedeutend unterschiedlichen Zeitpunkte – innerhalb der Berechnung zufallsgesteuert unterschiedliche Tabellen verwendet werden. Eine statistische Auswertung des Stromverbrauchs j(t), j(t') an zwei (oder mehr) Zeitpunkten t, t' liefert somit, wie die Anmelderin experimentell bestätigen konnte, keine Information über den bei der Berechnung verwendeten geheimen Schlüssel. Insbesondere liefern Korrelationskurven wie die in 1 gezeigten auch bei Verwendung des richtigen Schlüssels das mehr oder weniger gleichmäßige Rauschen (vgl. 1b), das bei Verwendung eines falschen Schlüssels entsteht, nicht aber den prominenten Ausschlag (1a), der z. B. bei XOR-Maskierung und dem richtigen Schlüssel zu sehen ist.As described above, z. By reference to [PRB10], spying on the secret key of an XOR-masked cryptographic computation is possible with a second order DPA attack, in which the power consumption j (t), j (t ') at two times t, t' , ie when two different calculation steps within the calculation, measured and evaluated. At [PRB10] are considered Calculation steps within the calculation realized by table accesses. The weak point exploited in the attack is that the same table is used at both times. According to the invention, in addition to the basic masking (eg XOR), the secondary masking is used, according to which either the intermediate value or the one's complement of the intermediate value is calculated randomly. As a result, calculation steps at different points in time in the course of the calculation, which would be similar in the case of pure XOR masking, are made randomly differentiated. For a partial calculation (computation step) realized as a table access, this means that different tables are randomly used within the calculation for the different partial computations-or equally different times. A statistical evaluation of the power consumption j (t), j (t ') at two (or more) times t, t' thus provides, as the Applicant could confirm experimentally, no information about the secret key used in the calculation. In particular, correlation curves like those in 1 showed even with the use of the right key the more or less uniform noise (see. 1b ), which arises when using a wrong key, but not the prominent rash ( 1a ), the z. B. with XOR masking and the correct key can be seen.
Im Vergleich zu dem denkbaren Verfahren, bei XOR-Maskierung für jeden Tabellenaufruf eine neue XOR-Tabelle mit einer neuen XOR-Maske zu berechnen, muss bei der erfindungsgemäßen erweiterten Maskierung nur zu Beginn der Berechnung die Tabelle für den Tabellenzugriff um ein oder mehrere Komplementär-Tabellen erweitert werden (daher der Begriff erweiterte Maskierung). Bei nachfolgenden Tabellenaufrufen kann auf die vorausberechnete erweiterte Tabelle zurückgegriffen werden, ohne Neuberechnung für jeden Tabellenzugriff. Für andere Teilberechnungen (Rechenschritte) als Tabellenzugriffe, z. B. Berechnungen gemäß einer Rechenvorschrift (Operation), bei AES z. B. die Verschiebeoperationen „Shift Row” oder „Mix Column”, verhält es sich analog. Zu Beginn der Berechnung wird die Operation (Rechenvorschrift) mit der Basismaskierung maskiert und zumindest eine komplementärmaskierte Operation gebildet. Bei den Teilberechnungen innerhalb der Berechnung wird mit den vorab berechneten maskierten und komplementärmaskierten Operationen gerechnet. Somit ist die erweiterte Maskierung sicher und zugleich effizient.In contrast to the conceivable method of calculating a new XOR table with a new XOR mask for each table call in the case of XOR masking, in the case of the extended masking according to the invention only at the beginning of the calculation the table for table access must be extended by one or more complementary XOR tables. Tables are extended (hence the term extended masking). For subsequent table calls, the pre-calculated extended table can be used without recalculation for each table access. For other partial calculations (calculation steps) as table accesses, eg. B. calculations according to a calculation rule (operation), in AES z. As the shift operations "Shift Row" or "Mix Column", it behaves analogously. At the beginning of the calculation, the operation (calculation rule) is masked with the base masking and at least one complementary masked operation is formed. The partial calculations within the calculation are calculated using the previously calculated masked and complementary masked operations. Thus, the extended masking is safe and at the same time efficient.
Daher ist gemäß 10 2012 018 924.9 ein Verfahren zum Durchführen einer kryptographischen Berechnung unter Verwendung eines kryptographischen Schlüssels geschaffen, das gegen Ausspähen des Schlüssels über Seitenkanalangriffe, insbesondere DPA Angriffe höherer Ordnung, geschützt ist, so dass die Schlüsselausspähung verhindert ist oder zumindest stark erschwert ist, und das zugleich effizient ist.Therefore, according to 10 2012 018 924.9 a method is provided for performing a cryptographic computation using a cryptographic key that is protected against spying on the key via side channel attacks, in particular higher order DPA attacks, such that key spying is prevented or at least severely hampered, and at the same time efficient.
Nachteilig an dem Verfahren gemäß. 10 2012 018 924.9 ist, dass der Speicherbedarf gegenüber einen nur einfachen Maskierung erhöht ist. Vor allem bei einem Tabellenzugriff, der in der Praxis regelmäßig im (flüchtigen) Arbeitsspeicher z. B. RAM erfolgt, ist der Speicherbedarf im (flüchtigen) Arbeitsspeicher z. B. RAM erhöht. Der vorliegenden Erfindung liegt die Aufgabe zu Grunde, das Verfahren aus 10 2012 018 924.9 speichereffizienter zu gestalten, bevorzugt mit Ersparnis beim (flüchtigen) Arbeitsspeicher z. B. RAM.A disadvantage of the method according to. 10 2012 018 924.9 is that the memory requirement is increased compared to a simple masking. Especially in a table access, which in practice regularly in the (volatile) memory z. B. RAM, the memory requirement in the (volatile) memory z. B. RAM increases. The present invention is based on the object of the method 10 2012 018 924.9 memory-efficient, preferably with savings in (volatile) memory z. B. RAM.
Das Dokument DE 10 2004 032 893 A1 beschreibt ein Verfahren zum ausspähungsgeschützten Berechnen eines maskierten Ergebniswertes aus einem maskierten Eingangswert gemäß einer vorgegebenen Abbildung, die in Form einer Tabelle vorgesehen ist. Bei dem Verfahren wird zuerst in einem ersten Schritt eine maskierte Tabelle mit einer Mehrzahl von Einträgen berechnet, wobei zur Berechnung zumindest mancher Einträge der maskierten Tabelle die vorgegebene Abbildung an mindestens zwei Stellen ausgewertet wird und die dabei ermittelten Ergebniswerte, z. B. T(q1) und T(q2), in die Berechnung des Eintrags der maskierten Tabelle eingehen. Anschließend wird in einem zweiten Schritt der maskierte Ergebniswert unter Verwendung der maskierten Tabelle und der vorgegebenen Abbildung berechnet. Indem im ersten Schritt die Abbildung an mindestens zwei Stellen ausgewertet wird, um einen einzigen Tabelleneintrag zu berechnen, wird die Tabelle gefaltet (hiermit ist nicht die auch „Faltung” genannte mathematische Operation gemeint) und lässt sich hierdurch speichersparend speichern.The document DE 10 2004 032 893 A1 describes a method for spy-protected calculation of a masked result value from a masked input value according to a predetermined mapping, which is provided in the form of a table. In the method, a masked table with a plurality of entries is first calculated in a first step, wherein for calculating at least some entries of the masked table, the predetermined mapping is evaluated in at least two places and the resulting result values, eg. For example, T (q1) and T (q2) will be used to calculate the entry of the masked table. Subsequently, in a second step, the masked result value is calculated using the masked table and the predetermined mapping. In the first step, the image is evaluated in at least two places to calculate a single table entry, the table is folded (this does not mean the mathematical operation also called "convolution") and can thereby save memory.
Der Erfindung in der vorliegenden Anmeldung liegt die Aufgabe zu Grunde, das in 10 2012 018 924.9 angegebene Verfahren dahingehend zu modifizieren, dass der Speicherbedarf gegenüber der Lösung in 102012018924.9 verringert ist. Vorzugsweise soll die Lösung so modifiziert werden, dass bei der verbesserten Maskierung gemäß 102012018924.9 der Speicherbedarf gegenüber einer herkömmlichen Maskierung wie z. B. XOR-Maskierung nicht erhöht ist.The invention in the present application is based on the object, which in 10 2012 018 924.9 to modify the specified method so that the storage requirements compared to the solution in 102012018924.9 is reduced. Preferably, the solution should be modified so that in the improved masking according to 102012018924.9 the memory requirement compared to a conventional masking such. B. XOR masking is not increased.
Das erfindungsgemäße Verfahren gemäß Anspruch 1 geht im Oberbegriff von einer sogenannten „erweiterten Maskierung” gemäß 10 2012 018 924.9 A1 aus. Gemäß der erweiterten Maskierung wird zum einen eine Basismaskierung, z. B. XOR, angewandt, und zum anderen zusätzlich eine Sekundärmaskierung angewandt. Durch die Sekundärmaskierung wird bewirkt, dass für jeden mittels der Basismaskierung (z. B. XOR) maskierten Zwischenwert zufallsgesteuert (z. B. durch Zufallsbit b) die Berechnung (z. B. AES) entweder mit dem maskierten Zwischenwert oder mit dem Einerkomplement des maskierten Zwischenwerts durchgeführt wird. Das erfindungsgemäße Verfahren zeichnet sich dadurch aus, dass an der Berechnung weiter ein Schritt des Faltens durchgeführt wird, durch welchen bewirkt wird, dass zumindest manche mit der Basismaskierung maskierte Zwischenwerte als gefaltet maskierte Zwischenwerte vorgesehen sind, wobei der gefaltet maskierte Zwischenwert unter Verwendung des basismaskierten Zwischenwerts und mindestens eines weiteren Zweit-Zwischenwerts berechnet wird, wobei der Zweit-Zwischenwert aus dem basismaskierten Zwischenwert unter Verwendung einer Faltungsdistanz abgeleitet wird. Auf den gefaltet maskierten Zwischenwert wird die Sekundärmaskierung angewandt, sodass zufallsgesteuert die Berechnung entweder mit dem gefaltet maskierten Zwischenwert oder mit dem zum gefaltet maskierten Zwischenwert gehörigen Einerkomplement durchgeführt wird. Ein Wert wird also zuerst basismaskiert, dass durch Falten bearbeitet und schließlich sekundärmaskiert. Der maskierte Zwischenwert oder das zum maskierten Zwischenwert gehörige Einerkomplement wird weiter, falls erforderlich unter Verwendung eines Korrekturelements berechnet, in das die Faltungsdistanz eingeht. Das zufallsgesteuerte Zugreifen auf entweder den Zwischenwert oder das Einerkomplement des Zwischenwerts wird dann an Zwischenwerten durchgeführt, die mit Basismaskierung und dem zusätzlichen Schritt des Faltens erzeugt worden sind.The inventive method according to claim 1 is in the preamble of a so-called "extended masking" according to 10 2012 018 924.9 A1 out. According to the extended masking, on the one hand, a base masking, for. B. XOR applied, and on the other hand additionally applied a secondary masking. Secondary masking causes each to be masked by basic masking (eg XOR) masked intermediate value (for example by random bit b) the calculation (eg AES) is carried out either with the masked intermediate value or with the one's complement of the masked intermediate value. The method according to the invention is characterized in that a further step of folding is performed on the calculation, which causes at least some intermediate values masked with the base masking to be provided as folded masked intermediate values, the folded masked intermediate value using the base-masked intermediate value and at least one further second intermediate value, wherein the second intermediate value is derived from the base-masked intermediate value using a convolution distance. The secondary masking is applied to the folded masked intermediate value, so that the calculation is carried out either randomly with the folded masked intermediate value or with the one-complement associated with the folded masked intermediate value. Thus, a value is first basismasked, processed by folding, and finally secondary masked. The masked intermediate value or the one's complement associated with the masked intermediate value is further computed, if necessary, using a correction element that is entered by the convolution distance. Random access to either the intermediate value or the one's complement of the intermediate value is then performed on intermediate values generated with base masking and the additional step of folding.
Mit anderen Worten, werden, um einen einzigen mit Falten und mit der Basismaskierung maskierten Zwischenwert zu erzeugen, basismaskierte Zwischenwerte an zwei oder mehr Stellen ausgewertet. Dies entspricht einem Falten der durchgeführten Berechnung, so dass mindestens zwei Zwischenwerte an derselben Stelle zu liegen kommen. Dadurch lassen sich an einem einzigen Speicherplatz zwei (bei einfachem Falten) oder mehr (bei mehrfachem Falten) Zwischenwerte speichern. Der erforderliche Speicherplatz ist daher verringert. Die aufeinandergefalteten und basismaskierten Zwischenwerte werden zudem analog wie in 10 2012 018 924.9 angegeben erweitert maskiert. Das Korrekturelement ist gegebenenfalls erforderlich, z. B. nur falls mit dem Einerkomplement gerechnet wird, um den Einfluss des Faltens auf das Rechenergebnis zu kompensieren.In other words, to generate a single intermediate value masked with wrinkles and the base mask, base-masked intermediate values at two or more locations are evaluated. This corresponds to a folding of the calculation carried out so that at least two intermediate values come to lie in the same place. This allows you to store two (single folding) or more (multiple folding) intermediate values in a single memory location. The required storage space is therefore reduced. The interfolded and base masked intermediate values are also analogous as in 10 2012 018 924.9 indicated extended masked. The correction element may be required, for. B. only if the one-complement is calculated in order to compensate for the influence of folding on the calculation result.
Somit ist gemäß Anspruch 1 eine speichersparende Modifizierung des in 10 2012 018 924.9 angegebenen Verfahren geschaffen.Thus, according to claim 1, a memory-saving modification of the in 10 2012 018 924.9 specified method created.
Wahlweise wird nur entweder der gefaltet maskierte Zwischenwert oder das Einerkomplement des gefaltet maskierten Zwischenwerts unter Verwendung eines Korrekturterms berechnet, da nur entweder beim Zwischenwert oder beim Einerkomplement ein Korrekturterm erforderlich ist, z. B. nur beim Einerkomplement.Optionally, only one of the folded masked intermediate value and the one's complement of the convolved masked intermediate value is computed using a correction term, since only at either the intermediate value or the one's complement is a correction term required, e.g. B. only in the one's complement.
Als Berechnung ist wahlweise eine Verschlüsselung, Entschlüsselung, Signaturerzeugung oder Signaturprüfung vorgesehen, wahlweise gemäß einem vorbestimmten Algorithmus wie z. B. AES.As a calculation either encryption, decryption, signature generation or signature verification is provided, optionally according to a predetermined algorithm such. Eg AES.
Wahlweise ist als Basismaskierung eine einfache oder mehrfache XOR-Maskierung, oder eine Zerlegungsmaskierung, oder eine Hintereinanderschaltung zweier oder mehrerer der vorgenannten Basismaskierungen vorgesehen.Optionally, a simple or multiple XOR masking, or a disassembly masking, or a series connection of two or more of the aforementioned base masks is provided as basic masking.
Wahlweise, gemäß Anspruch 3, umfasst die Berechnung eine Teilberechnung, durch die aus einem Eingangswert unter Durchführung eines Tabellenzugriffs auf eine Tabelle, die eine Mehrzahl von Tabelleneinträgen aufweist, ein Zwischenwert erzeugbar ist. Gemäß Anspruch 3 wird zur Durchführung der Berechnung oder zumindest der Teilberechnung die Tabelle mit der Basismaskierung maskiert wird zu einer maskierten Tabelle. Die Teilberechnung wird durchgeführt, indem ein Tabellenzugriff durchgeführt wird. Bei dem Tabellenzugriff wird, wie in DE 10 2012 018 924.9 , eine Sekundärmaskierung angewandt, wobei durch die Sekundärmaskierung einer Tabelle bewirkt wird, dass ein Tabellenzugriff auf die Tabelle zufallsgesteuert auf entweder die Tabelle selbst oder die bzw. eine Komplementär-Tabelle zur Tabelle durchgeführt wird. Bis hierhin entspricht der Tabellenzugriff dem auf eine erweitert maskierte Tabelle. Das Verfahren nach Anspruch 3 ist weiter dadurch gekennzeichnet, dass ein Schritt des Faltens durchgeführt wird, wobei die bereits mit der Basisimaskierung maskierte Tabelle gefaltet wird zu einer gefalteten maskierten Tabelle, wobei, für zumindest manche Tabelleneinträge der gefalteten maskierten Tabelle, der Tabelleneintrag unter Verwendung eines basismaskierten Eingangswerts der Tabelle und mindesten eines weiteren basismaskierten Zweit-Eingangswerts der Tabelle berechnet wird, wobei der Zweit-Eingangswert aus dem unmaskierten Eingangswert unter Verwendung einer Faltungsdistanz abgeleitet wird. Die gefaltete maskierte Tabelle wird schließlich mit der (ohne Falten in DE 10 2012 018 924.9 beschriebenen) Sekundärmaskierung maskiert, so dass der Tabellenzugriff zufallsgesteuert entweder auf die gefaltete maskierte Tabelle selbst oder auf die bzw. eine Komplementär-Tabelle zur gefalteten maskierten Tabelle durchgeführt wird. Bedarfsweise wird der gefaltet maskierte Tabelleneintrag oder das zum gefaltet maskierten Tabelleneintrag gehörige Einerkomplement weiter unter Verwendung eines Korrekturterms und/oder einer Korrekturtabelle berechnet, wobei in den Korrekturterm und in die Korrekturtabelle die Faltungsdistanz eingeht.Optionally, according to claim 3, the computation comprises a partial computation, by which an intermediate value can be generated from an input value by performing a table access to a table which has a plurality of table entries. In accordance with claim 3, in order to carry out the calculation or at least the partial calculation, the table with the basic masking is masked to form a masked table. The sub-calculation is performed by performing a table access. In table access, as in DE 10 2012 018 924.9 , a secondary masking is applied, wherein the secondary masking of a table causes a table access to the table to be performed randomly on either the table itself or the or a complementary table to the table. So far, the table access corresponds to an expanded masked table. The method of claim 3 further characterized in that a step of folding is performed, wherein the table already masked with the base mask is convoluted into a folded masked table, wherein, for at least some table entries of the folded masked table, the table entry using a basestocked input value of the table and at least one further base masked second input value of the table, the second input value being derived from the unmasked input value using a convolution distance. The folded masked table is finally filled with the (without folding in DE 10 2012 018 924.9 described), so that the table access is performed randomly on either the folded masked table itself or on the or a complementary table to the folded masked table. If desired, the one-folded masked entry or the one-complement mask associated with the folded-masked table entry is further subordinated Using a correction term and / or a correction table calculated, wherein the folding date in the correction term and in the correction table.
Somit werden in der gefaltet basismaskierten Tabelle zumindest manche Tabelleneinträge, vorzugsweise und sofern nichts dagegenspricht, alle Tabelleneinträge mit einem Schritt des Faltens erzeugt, wobei die Tabelle ein- oder mehrfach gefaltet wird, so dass zwei oder mehr Eingangswerte aufeinander gespeichert werden. Sind beispielsweise alle Tabelleneinträge durch Aufeinander-Falten zweier Eingangswerte erzeugt, benötigt die Tabelle nur halb so viel Speicherplatz wie ohne Faltung. Andererseits benötigt eine erweitert maskierte Tabelle, die eine einzige Originaltabelle und eine einzige dazu komplementäre Komplementärtabelle umfasst doppelt so viel Speicherplatz wie eine nur basismaskierte entsprechende Tabelle. In dieser Kontellation – einfaches Falten der Tabelle, so dass immer zwei Eingangswerte in jeden Tabelleneintrag einfließen, und erweiterte Maskierung mit einer einzigen Komplementärtabelle – wird somit durch die Faltung die durch die erweiterte Maskierung erzeugte Erhöhung des Speicherbedarfs exakt wieder kompensiert. Der Speicherbedarf ist somit genau derjenige einer lediglich basismaskierten Tabelle (z. B. maskiert mit einer XOR-Maske).Thus, in the folded base-masked table, at least some of the table entries, preferably and unless contradicted, generate all the table entries with a folding step, folding the table one or more times such that two or more input values are stored one upon the other. For example, if all the table entries are created by stacking two input values, the table takes up only half as much space as it does without folding. On the other hand, an extended masked table, which includes a single original table and a single complementary table, requires twice as much space as a base-masked corresponding table. In this contouring-simple folding of the table, so that always two input values are included in each table entry, and extended masking with a single complementary table-the folding thus compensates exactly for the increase in memory demand generated by the extended masking. The memory requirement is thus exactly that of a basic-masked table only (eg masked with an XOR mask).
Die erfindungsgemäße gefaltete und erweiterte Maskierung ist besonders für Teilberechnungen vorteilhaft, die durch Tabellenaufrufe gebildet werden. Gerade bei einem Tabellenaufruf würde eine Neuberechnung der Tabelle für jeden Tabellenaufruf einen erheblichen zusätzlichen Rechenaufwand bedeuten. Im AES ist die relativ aufwändige nichtlineare S-Box-Operation als Tabellenaufruf verwirklicht. Auf Grund der erweiterten Maskierung ist, je nach Ausführungsform, doppelt bis viermal so viel Tabellen-Speicher erforderlich wie bei einer lediglich basismaskierten – z. B. XOR-maskierten – Tabelle. Durch die Faltung der Tabelle wird der Mehrbedarf an Speicher im vorteilhaften Fall ganz oder zumindest teilweise wieder aufgehoben (vgl. vorstehender Absatz). Andere, vergleichsweise einfache Teilberechnungen wie z. B. Shift Row oder Mix Column sind durch direkt implementierte Operationen gebildet. Für diese direkt implementierten einfachen Operationen kann es vom Rechenaufwand her vertretbar sein, jede Teilberechnung neu zu maskieren. Folglich ist die Erfindung wahlweise derart umgesetzt, dass Tabellenaufrufe mit der erfindungsgemäßen gefaltete erweiterten Maskierung maskiert sind und direkt implementierte Operationen mit einer anderen, z. B. stärkeren aber aufwändigeren, Maskierung maskiert sind. Wahlweise sind aufwändige Teilberechnungen – wie z. B. S-Box-Operationen beim AES – mit der gefalteten erweiterten Maskierung maskiert, und sind vergleichsweise einfache Teilberechnungen – z. B. Shift Row oder Mix Column – durch eine andere, z. B. stärkere aber dafür aufwändigere Maskierung maskiert, z. B. Neumaskierung bei jeder Teilberechnung (Rechenschritt). Alternativ kann auch die gesamte Berechnung gefaltet und erweitert maskiert sein. Teilberechnungen zwischen Tabellenaufrufen sollten zumindest nicht schwächer maskiert sein als Tabellenaufrufe.The folded and extended masking according to the invention is particularly advantageous for sub-calculations formed by table calls. Especially with a table call, a recalculation of the table would mean a considerable additional computation effort for each table call. In AES, the relatively complex non-linear S-box operation is realized as a table call. Due to the extended masking, depending on the embodiment, twice to four times as much table memory is required as with a base masked only - eg. B. XOR masked table. By folding the table, the additional requirement for storage in the advantageous case is completely or at least partially canceled (see above paragraph). Other, comparatively simple partial calculations such. Shift Row or Mix Column are formed by directly implemented operations. For these directly implemented simple operations, it can be justifiable from the computational effort to newly mask each sub-computation. Thus, the invention is optionally implemented such that table calls are masked with the folded expanded mask of the invention and directly implemented operations with another, e.g. B. stronger but more elaborate masking are masked. Optionally, complex partial calculations - such. B. S-box operations at the AES - masked with the folded extended masking, and are relatively simple sub-calculations - z. B. Shift Row or Mix Column - by another, z. B. stronger but more complex masking masked, z. B. Remapping at each sub-calculation (calculation step). Alternatively, the entire calculation can also be folded and expanded masked. Partial calculations between table calls should at least not be less masked than table calls.
Wahlweise ist die Korrekturtabelle mit einer Sekundärmaskierung maskiert, d. h. um (eine) Komplementärtabelle/(n) erweitert.Optionally, the correction table is masked with a secondary mask, i. H. expanded by (a) complementary table / (n).
Das zufallsgesteuerte Zugreifen auf entweder die gefaltet maskierte Tabelle oder die bzw. eine gefaltet maskierte Komplementär-Tabelle wird wahlweise dadurch durchgeführt, dass der Eingangswert zur Erzeugung des Zwischenwerts um einen Tabellenauswahl-Abschnitt erweitert wird, durch den die Tabelle festgelegt ist, auf die zugegriffen wird. Die Länge des Tabellenauswahl-Abschnitts ist passend zur Festlegung der ein oder mehreren Komplementär-Tabellen gewählt. Wird eine einzige Komplementär-Tabelle berechnet, ist der Tabellenauswahl-Abschnitt vorzugsweise ein Bit („Auswahlbit”) lang. Werden drei Komplementär-Tabellen berechnet, ist der Tabellenauswahl-Abschnitt vorzugsweise zwei Bit lang. Die Bits können wahlweise entweder aufeinanderfolgend sein (z. B. aa) oder zwischen die Bits des Tabelleneingangs eingestreut sein (z. B. xax; axax; etc.; vgl. Figuren).The random accessing of either the folded masked table or the folded masked complementary table is optionally performed by expanding the input value to produce the intermediate value by a table selection section which defines the table being accessed , The length of the table selection section is chosen to match the one or more complementary tables. If a single complementary table is calculated, the table selection section is preferably one bit ("selection bit") long. If three complementary tables are calculated, the table selection section is preferably two bits long. Optionally, the bits may either be consecutive (eg aa) or interspersed between the bits of the table input (eg xax; axax ;, etc, see figures).
Wahlweise weist (auch) die Korrekturtabelle einen Tabellenauswahlabschnitt auf, durch den die Korrekturtabelle festgelegt ist, auf die zugegriffen wird. Der Tabellenauswahlabschnitt der eigentlichen Tabelle und der Tabellenauswahlabschnitt der Korrekturtabelle sind ggf. vorzugsweise unabhängig voneinander. Beispielsweise wird also für Tabelle und Korrekturtabelle je ein Zufallsbit festgelegt.Optionally, the correction table also has a table selection section that defines the correction table that is being accessed. The table selection section of the actual table and the table selection section of the correction table may be preferably independent of one another. For example, a random bit is thus defined for the table and the correction table.
Die Tabelle weist wahlweise einen Tabelleneingang und einen Tabellenausgang auf, und wobei genau eine maskierte Komplementär-Tabelle berechnet wird, bei welcher sowohl der Tabelleneingang als auch der Tabellenausgang komplementiert sind, indem die Positionen der Tabelleneinträge in der Tabelle komplementiert sind (Komplementierung des Eingangs) und die Werte der Tabelleneinträge in der Tabelle komplementiert sind (Komplementierung des Ausgangs).The table optionally has a table input and a table output, and exactly computes a masked complementary table in which both the table input and the table output are complemented by complementing the positions of the table entries in the table (complementing the input) and the values of the table entries in the table are complemented (complementation of the output).
Wahlweise, alternativ, weist die Tabelle einen Tabelleneingang und einen Tabellenausgang auf, und wobei drei maskierte Komplementär-Tabellen berechnet werden, wobei
- – bei einer ersten gefaltet maskierten Komplementär-Tabelle nur der Tabelleneingang komplementiert ist, indem die Positionen der Tabelleneinträge in der gefaltet maskierten Tabelle komplementiert sind,
- – bei einer zweiten gefaltet maskierten Komplementär-Tabelle nur der Tabellenausgang komplementiert ist, indem die Werte der Tabelleneinträge in der gefaltet maskierten Tabelle komplementiert sind, und
- – bei einer dritten gefaltet maskierten Komplementär-Tabelle sowohl der Tabelleneingang als auch der Tabellenausgang komplementiert sind, indem sowohl die Positionen als auch die Werte der Tabelleneinträge in der gefaltet basismaskierten Tabelle komplementiert sind.
Alternatively, alternatively, the table has a table input and a table output, and where three masked complementary tables are calculated, where - In a first folded masked complementary table, only the table input is complemented by the positions of the table entries in the folded masked table being complemented,
- In a second folded masked complementary table, only the table output is complemented by the values of the table entries in the folded masked table being complemented, and
- In the case of a third folded masked complementary table, both the table input and the table output are complemented by complementing both the positions and the values of the table entries in the folded base-masked table.
Wahlweise werden die gefaltet maskierte Tabelle und die mindestens eine (z. B. eine oder alternativ drei) Komplementär-Tabelle(n) in eine einzige erweiterte Tabelle eingetragen, die die Tabelleneinträge der gefaltet maskierten Tabelle und der mindestens einen Komplementär-Tabelle in einer vorbestimmten Anordnung enthält. Die Anordnung der Tabelleneinträge kann z. B. hintereinander sein (vgl. z. B. 11), oder alternativ schachbrettartig abwechselnd (ausgehend von den Tabellen aus 11 schachbrettartige Verwürfelung der Tabelleneinträge, ggf. mit entsprechender Gestaltung der Tabellen-Auswahl-Abschnitte).Optionally, the folded masked table and the at least one (eg, one or alternatively three) complementary table (s) are entered into a single extended table containing the table entries of the folded masked table and the at least one complementary table in a predetermined one Arrangement contains. The arrangement of the table entries can z. B. in a row (see, for. 11 ), or alternatively checkered alternating (starting from the tables 11 checkerboard-like scrambling of the table entries, possibly with appropriate design of the table selection sections).
Wahlweise sind dem Prozessor ein Permanentspeicher (z. B. ROM, EEPROM, ...) und ein flüchtiger Arbeitsspeicher (z. B. RAM) zugeordnet, wobei die Tabelle im Permanentspeicher abgespeichert ist, und wobei die gefaltet maskierte Tabelle und die mindestens eine gefaltet maskierte Komplementär-Tabelle im flüchtigen Arbeitsspeicher berechnet werden. Beispielsweise sind bei AES die originären, unmaskierten S-Boxen im nichtflüchtigen Speicher abgespeichert. Die gefaltet maskierte Tabelle und ihre Komplementär-Tabelle(n) werden im flüchtigen Speicher berechnet und abgelegt. Insbesondere werden vorzugsweise zu Beginn der Berechnung (z. B. AES) die Tabellen (z. B. S-Boxen) aus dem nichtflüchtigen Speicher in den flüchtigen Speicher geladen, im flüchtigen Speicher die gefaltet maskierte Tabelle (z. B. 12) und ihre Komplementär-Tabellen) berechnet (dies führt z. B. zu 13, 14 oder 15) und im weiteren Verlauf der Berechnung (z. B. AES) stets ein und dieselben zu Beginn der Berechnung (AES) berechneten RAM-Tabellen (maskierte Tabelle und ihre Komplementär-Tabelle(n)) verwendet. Für einen neuen Durchlauf der Berechnung (z. B. AES), z. B. eine neue Verschlüsselung, Entschlüsselung, Signaturberechnung, Signaturverifizierung, werden neue RAM-Tabellen (die gefaltet maskierte Tabelle und ihre Komplementär-Tabelle(n)) berechnet.Optionally, the processor is assigned a non-volatile memory (eg, ROM, EEPROM, ...) and a volatile random access memory (eg RAM), the table being stored in non-volatile memory, and the folded masked table and the at least one folded masked complementary table to be calculated in volatile memory. For example, at AES, the original, unmasked S-boxes are stored in non-volatile memory. The folded masked table and its complementary table (s) are calculated and stored in volatile memory. In particular, preferably at the beginning of the calculation (eg AES) the tables (eg S-boxes) are loaded from the non-volatile memory into the volatile memory, in the volatile memory the folded-masked table is loaded (eg. 12 and their complementary tables) (this leads, for example, to 13 . 14 or 15 ) and in the further course of the calculation (eg AES) one and the same RAM tables calculated at the beginning of the calculation (AES) (masked table and its complementary table (s)) are always used. For a new pass of the calculation (eg AES), e.g. As new encryption, decryption, signature calculation, signature verification, new RAM tables (the folded masked table and its complementary table (s)) are calculated.
Das Falten wird hierbei an Tabellen durchgeführt, die im meist eher knapp bemessenen (flüchtigen) Arbeitsspeicher (z. B. RAM) erzeugt werden. Somit wird der knappe Arbeitsspeicher (z. B. RAM) sparsam verwendet. Dass zusätzlich eine Korrekturtabelle vorgehalten werden muss, beeinträchtigt die Ersparnis beim Arbeitsspeicher bevorzugt nicht, da die Korrekturtabelle bevorzugt im Permanentspeicher (z. B. ROM) gespeichert ist.The folding is done here on tables, which are usually produced in the rather scarce (volatile) memory (eg RAM). Thus, the scarce main memory (eg RAM) is used sparingly. The fact that a correction table must additionally be maintained does not affect the saving in the working memory, since the correction table is preferably stored in non-volatile memory (eg ROM).
Gemäß einer Ausführungsform wird ein Verfahren angegeben, wobei
- – die gefaltet maskierte Tabelle und mindestens eine Komplementär-Tabelle für eine Mehrzahl von Tabellenzugriffen auf die Tabelle verwendet werden, wahlweise für zumindest eine gesamte Durchführung der kryptographischen Berechnung (z. B. ein Durchlauf des AES), und
- – innerhalb der Mehrzahl von Tabellenzugriffen zumindest einmal, vorzugsweise für jeden Tabellenzugriff, neu zufallsgesteuert festgelegt wird, dass die Berechnung bzw. Teilberechnung entweder mit dem gefaltet maskierten Zwischenwert oder mit dem Einerkomplement des gefaltet maskierten Zwischenwerts durchgeführt wird, und die Berechnung bzw. Teilberechnung entsprechend dem Festlegen durchgeführt wird.
According to one embodiment, a method is given, wherein - The folded masked table and at least one complementary table are used for a plurality of table accesses to the table, optionally for at least one entire execution of the cryptographic calculation (eg a pass of the AES), and
- Within the plurality of table accesses, at least once, preferably for each table access, it is newly randomly determined that the calculation or partial calculation is performed either with the folded masked intermediate value or with the one's complement of the folded masked intermediate value, and the calculation or partial calculation according to FIG Set is performed.
Insbesondere wird wahlweise zu Beginn der Berechnung (z. B. AES) eine gefaltet maskierte Tabelle (z. B. S-Box) und ausgehend von der gefaltet maskierten Tabelle mindestens eine (z. B. genau eine oder genau drei) Komplementär-Tabelle(n) berechnet, z. B. im RAM. Im restlichen Verlauf der Berechnung (z. B. AES) werden die vorausberechneten Tabellen und Komplementär-Tabelle(n) verwendet (z. B. aus dem RAM). Zuvor wird ggf. die unmaskierte Tabelle aus dem nichtflüchtigen Speicher (z. B. ROM) geladen. Evtl., abhängig vom Einzelfall, wird eine so erzeugte RAM-Tabelle auch für mehrere AES-Durchläufe verwendet. Ansonsten wird vor jedem AES-Durchlauf die RAM-Tabelle neu berechnet wird.In particular, optionally at the beginning of the calculation (eg AES) a folded masked table (eg S-box) and starting from the folded masked table at least one (eg exactly one or exactly three) complementary table (n) calculated, z. In RAM. The rest of the calculation (eg, AES) uses the precalculated and complementary tables (eg, RAM). Previously, if necessary, the unmasked table is loaded from the non-volatile memory (eg ROM). Depending on the individual case, a RAM table generated in this way may also be used for several AES passes. Otherwise, the RAM table is recalculated before each AES pass.
Wahlweise weist die Tabelle einen Tabelleneingang und einen Tabellenausgang auf, und wobei die maskierte Tabelle
- – entweder einen maskierten Tabelleneingang hat,
- – oder einen maskierten Tabellenausgang hat,
- – oder einen maskierten Tabelleneingang und einen maskierten Tabellenausgang hat, wobei weiter der Tabelleneingang und der Tabellenausgang entweder mit der gleichen Basismaskierung maskiert sind oder mit unterschiedlichen Basismaskierungen maskiert sind.
Optionally, the table has a table input and a table output, and where the masked table - - either has a masked table input,
- - or has a masked table output,
- - or has a masked table input and a masked table output, further wherein the table input and the table output are either masked with the same base masking or are masked with different base masks.
Die hier angegebene getrennte Maskierung von Tabelleneingang und Tabellenausgang stellt eine Hintereinanderschaltung der zwei Maskierungen von Tabelleneingang und Tabellenausgang dar. The separate masking of table input and table output specified here represents a series connection of the two mappings of table input and table output.
Im Folgenden wird die Erfindung an Hand von Ausführungsbeispielen und unter Bezugnahme auf die Zeichnung näher erläutert, in der zeigen:In the following the invention will be explained in more detail with reference to exemplary embodiments and with reference to the drawing, in which:
1 Korrelationskurven für DPA 2. Ordnung a) bei XOR-Maskierung b) bei erweiterter Maskierung gemäß der Erfindung; 1 Correlation curves for DPA 2nd order a) with XOR masking b) with extended masking according to the invention;
2 eine Teilberechnung bei AES, umfassend einen Tabellenzugriff, der für die erfindungsgemäße erweiterte und gefaltete Maskierung geeignet ist; 2 a partial calculation in AES comprising a table access suitable for the extended and folded masking according to the invention;
3 Rechenvorschriften zur Basis-Maskierung eines Zwischenwerts zu einem maskierten Zwischenwert gemäß XOR-Maskierung und additiver Maskierung; 3 Calculation rules for base masking of an intermediate value to a masked intermediate value according to XOR masking and additive masking;
4 eine Tabelle in unmaskierter Form (Original-Tabelle); 4 a table in unmasked form (original table);
5 eine komplementierte Tabelle zur Tabelle aus 4, wobei nur der Tabelleneingang komplementiert (invertiert) ist; 5 a complemented table to the table 4 where only the table input is complemented (inverted);
6 eine komplementierte Tabelle zur Tabelle aus 4, wobei nur der Tabellenausgang komplementiert ist; 6 a complemented table to the table 4 where only the table output is complemented;
7 eine komplementierte Tabelle zur Tabelle aus 4, wobei der Tabelleneingang und der Tabellenausgang komplementiert sind; 7 a complemented table to the table 4 wherein the table input and the table output are complemented;
8 eine, ausgehend von der Tabelle aus 4, XOR-randomisierte Tabelle, mit Eingangsmaske 31 und Ausgangsmaske 00; 8th one, starting from the table 4 , XOR-randomized table, with input mask 31 and output mask 00;
9 eine, ausgehend von der Tabelle aus 4, XOR-randomisierte Tabelle, mit Eingangsmaske 00 und Ausgangsmaske 02; 9 one, starting from the table 4 , XOR-randomized table, with input mask 00 and output mask 02;
10 eine, ausgehend von der Tabelle aus 4, XOR-randomisierte Tabelle, mit Eingangsmaske 31 und Ausgangsmaske 02; 10 one, starting from the table 4 , XOR randomized table, with input mask 31 and output mask 02;
11 eine, ausgehend von der XOR-randomisierten Tabelle aus 10, einfach erweiterte Tabelle, mit einer einzelnen Komplementär-Tabelle; 11 one, starting from the XOR randomized table 10 , simply extended table, with a single complementary table;
12 eine, ausgehend von der Tabelle aus 10, gefaltete Tabelle mit Faltungsdistanz 12; 12 one, starting from the table 10 folded table with folding distance 12;
13 eine, ausgehend von der gefalteten Tabelle aus 12, einfach erweiterte Tabelle, mit Auswahlbit an der obersten binären Bitstelle, gemäß einer Ausführungsform der Erfindung; 13 one, starting from the folded table 12 , simply extended table, with selection bit at the top binary bit position, according to an embodiment of the invention;
14 eine, ausgehend von der gefalteten Tabelle aus 12, einfach erweiterte Tabelle, mit Auswahlbit an der untersten binären Bitstelle, gemäß einer weiteren Ausführungsform der Erfindung; 14 one, starting from the folded table 12 , simply extended table, with selection bit at the lowest binary bit position, according to another embodiment of the invention;
15 eine, ausgehend von der gefalteten Tabelle aus 12, zweifach erweiterte Tabelle, mit Auswahlbit an den beiden obersten binären Bitstellen, gemäß einer weiteren Ausführungsform der Erfindung. 15 one, starting from the folded table 12 , two-times extended table, with selection bit at the two uppermost binary bit positions, according to another embodiment of the invention.
1 zeigt Korrelationskurven für einen DPA-Angriff zweiter Ordnung auf einen Tabellenzugriff beim AES a) bei XOR-Maskierung und b) bei erweiterter Maskierung gemäß Ausführungsformen der Erfindung. Als Tabelle ist eine AES S-Box vorgesehen. Die Korrelationskurve aus 1a wurde mit einem DPA-Angriff zweiter Ordnung auf einen Tabellenzugriff im AES bei Durchführung des Tabellenzugriffs mit dem richtigen Schlüssel ermittelt. Die Tabelle ist XOR-maskiert. Der signifikante Peak zeigt an, dass der richtige Schlüssel k verwendet wurde. Wurde der Tabellenzugriff mit einem falschen Schlüssel k durchgeführt, fehlt der Peak, ähnlich wie in 1b. 1b zeigt eine Korrelationskurve, die aus einem DPA-Angriff zweiter Ordnung auf denselben Tabellenzugriff im Ablauf des AES gewonnen wurde wie die Kurve aus 1a. Im Unterschied zu 1a ist bei 1b die Tabelle, zusätzlich zur Basis-XOR-Maskierung, mit der erfindungsgemäßen Sekundärmaskierung maskiert. Die speichereffiziente Sekundärmaskierung ist verwirklicht, indem die XOR-maskierte Tabelle, die 1a zu Grunde liegt, zunächst gefaltet wird und zu einer einfach erweiterten Tabelle erweitert ist, welche die gefaltete XOR-maskierte Tabelle (erst wurde die Tabelle XOR-maskiert, dann wurde sie gefaltet) und die Komplementär-Tabelle zur gefalteten XOR-maskierten Tabelle umfasst. Der Tabellenzugriff wird auf die erweiterte gefaltete XOR-maskierte Tabelle durchgeführt. Dabei wird innerhalb der erweiterten gefalteten XOR-maskierten Tabelle zufallsgesteuert entweder auf die gefaltete XOR-maskierte Tabelle oder auf die Komplementär-Tabelle zugegriffen. Bei Durchführung des Tabellenzugriffs auf die erweiterte Tabelle mit dem richtigen Schlüssel fehlt in der Korrelation aus 1b im Vergleich zur Korrelation der nur basismaskierten Tabelle nach 1a der prominente Peak, der das Vorliegen des richtigen Schlüssels anzeigt. Somit sind mit der einfach erweiterten Tabelle statt einer lediglich XOR-maskierten Tabelle Tabellenzugriffe mit dem richtigen Schlüssel ununterscheidbar von Tabellenzugriffen mit falschen Schlüsseln. 1 Figure 9 shows correlation curves for a second order DPA attack on a table access in AES a) in XOR masking and b) in extended masking according to embodiments of the invention. The table is an AES S-Box. The correlation curve off 1a was determined with a second-order DPA attack on a table access in the AES when performing table access with the correct key. The table is XOR masked. The significant peak indicates that the correct key k was used. If the table access was performed with an incorrect key k, the peak is missing, similar to 1b , 1b shows a correlation curve obtained from a second-order DPA attack on the same table access in the AES's history as the curve 1a , In contrast to 1a is at 1b the table, in addition to the base XOR masking masked with the secondary masking of the invention. Memory-efficient secondary masking is accomplished by using the XOR-masked table, the 1a is initially folded, and expanded to a simply extended table that is, the folded XOR-masked table (first the table was XOR masked, then it was folded) and the complement table to the folded XOR-masked table. The table access is performed on the extended folded XOR-masked table. In this case, either the folded XOR-masked table or the complementary table is randomly accessed within the extended folded XOR-masked table. When performing table access to the extended table with the correct key, the correlation is missing 1b compared to the correlation of the base-masked table only 1a the prominent peak indicating the presence of the correct key. Thus, with the simple expanded table instead of a merely XOR-masked table, table accesses with the correct key are indistinguishable from table accesses with wrong keys.
Tabellenzugriffe auf eine zweifach erweiterte Tabelle, welche die Basismaskierte Tabelle und drei Komplementär-Tabellen umfasst, liefern ähnliche Korrelationskurven wie die in 1b gezeigte. Auch bei zweifach erweiterter Tabelle sind also Tabellenzugriffe mit dem richtigen Schlüssel k ununterscheidbar von Tabellenzugriffen mit einem falschen Schlüssel. Bei den drei Komplementärtabellen sind ausgehend von der gefalteten basismaskierten Tabelle nur der Tabelleneingang komplementiert, nur der Tabellenausgang komplementiert, bzw. der Tabelleneingang und der Tabellenausgang komplementiert.Table accesses to a two-extended table, which includes the base masked table and three complementary tables, provide similar correlation curves to those in FIG 1b shown. Even if the table is extended twice, table accesses with the correct key k are indistinguishable from table accesses with a wrong key. In the case of the three complementary tables, only the table input is complemented from the folded base-masked table; only the table output is complemented, or the table input and the table output are complemented.
2 zeigt eine Teilberechnung aus einer AES-Verschlüsselung, bei der ein Tabellenzugriff auf eine Tabelle S (S-Box, AES Substitutionstabelle) durchgeführt wird. Der Tabellenzugriff aus 2 ist dafür geeignet, mit dem erfindungsgemäßen Verfahren maskiert zu werden. In 2 sind zwei Tabellen S im AES dargestellt, die an unterschiedlichen Stellen im Algorithmus AES, hier genauer in unterschiedlichen Runden des AES, angewendet werden. Die beiden Tabellen S sind in 2 mit denselben Symbolen p, k, x, y für Klartext p, Schlüssel k, Eingangswert x der Tabelle S und Ausgangswert y der Tabelle S dargestellt, um anzudeuten, dass der Rechenvorgang auf Grund der Tabelle S für die beiden Tabellen S der gleiche ist. Die Werte von Klartext p, Schlüssel k, Eingangswert x und Ausgangswert y sind in der Regel für jede Tabelle S unterschiedlich. 2 shows a partial calculation from an AES encryption, in which a table access to a table S (S-box, AES substitution table) is performed. The table access 2 is suitable for being masked by the method according to the invention. In 2 Two tables S in the AES are shown, which are applied at different places in the algorithm AES, here in more detail in different rounds of the AES. The two tables S are in 2 with the same symbols p, k, x, y for plaintext p, key k, input value x of the table S and output value y of the table S, to indicate that the arithmetic operation due to the table S is the same for the two tables S. The values of plaintext p, key k, input value x and output value y are usually different for each table S.
3 zeigt Rechenvorschriften zur Basis-Maskierung eines Zwischenwerts zu einem maskierten Zwischenwert mit XOR-Maskierung und additiver Maskierung. Die Rechenvorschrift, um x mit einer XOR-Basismaskierung zu xXOR zu maskieren, lautet x → xXOR = x ⊕ r. Die Rechenvorschrift, um x mit einer additiven Basismaskierung zu xadd zu maskieren, lautet x → xadd = x + r mod 2n. Die Rechenvorschrift, um x mit einer affinen Basismaskierung zu xα zu maskieren, lautet x → xα = α·x ⊕ r, wird hier nicht weiter betrachtet. Im Zusammenhang mit dem erfindungsgemäßen Maskieren mit Falten und Erweitern ist die affine Maskierung von untergeordneter Bedeutung, da Faltung bei affin maskierten Tabellen sehr ineffizient ist. 3 shows calculation rules for base masking of an intermediate value to a masked intermediate value with XOR masking and additive masking. The calculation rule for masking x with an XOR base masking to x XOR is x → x XOR = x ⊕ r. The calculation rule for masking x with an additive base masking to x add is x → x add = x + r mod 2 n . The calculation rule for masking x with an affine base masking at x α is x → x α = α · x ⊕ r, will not be considered further here. In the context of the masking according to the invention with folding and widening, the affine masking is of subordinate importance, since folding is very inefficient in affine masked tables.
Die Beispielrechnungen aus 4–11 zeigen Tabellen S, deren Tabelleneinträge ohne Faltung von Eingangswerten erzeugt sind, und falls dabei erweitert maskiert ist (11), also gemäß der Lösung aus 10 2012 018 924.9 . 12 und 13 zeigen gefaltete Tabellen. Die nur mit Falten – und ohne Erweiterungsmaskierung (Sekundärmaskierung) – erzeugte Tabelle aus 12 entspricht vom Grundsatz her der Lösung aus DE 10 2004 032 893 A1 . Tabellen ohne Faltung sind vom Grundsatz her mit dem Symbol S bezeichnet, ggf. mit Zusätzen wie „'” oder „-” etc. um den Grad der Maskierung anzugeben. Eine gefaltete und erweitert maskierte Tabelle wird im Allgemeinen mit T bezeichnet. Dabei wird vom Grundsatz her zwar von einer Tabelle S = T ausgegangen wie in 2 angegeben. Insbesondere ist durch die Tabelle T dieselbe Funktion implementiert wir durch die Tabelle S, beispielsweise eine S-Box gemäß 2. Um Verwechslungen mit zwischen Tabellen S ohne Faltung und Tabellen T mit Faltung zu vermeiden, werden Tabellen, bei denen Eingangswerte gefaltet sind, um einen Tabelleneintrag zu erzeugen, im Allgemeinen mit T bezeichnet, Tabellen ohne Faltung oder Tabellen im Allgemeinen hingegen mit S.The example calculations 4 - 11 show tables S, whose table entries are generated without convolution of input values, and if it is expanded masked ( 11 ), so according to the solution 10 2012 018 924.9 , 12 and 13 show folded tables. The table generated only with pleats - and without extension masking (secondary masking) 12 is in principle the solution DE 10 2004 032 893 A1 , Tables without convolution are basically designated by the symbol S, if necessary with additions such as "'" or "-" etc. to indicate the degree of masking. A folded and expanded masked table is generally designated T. In principle, a table S = T is used as in 2 specified. In particular, the same function is implemented by the table T through the table S, for example an S-box according to FIG 2 , To avoid confusion with between non-convolved tables S and convolved tables T, tables with input values convolved to produce a table entry are generally denoted by T, tables without convolution, or tables in general, by S.
4 zeigt eine Tabelle S in unmaskierter Form (Original-Tabelle), z. B. eine AES-S-Box. Die Tabelle ist im Vierersystem mit Basis 4 dargestellt. Folglich kann jedes Bit die vier Werte 0, 1, 2, 3 annehmen. Bei einem Tabellenzugriff beim AES gemäß 2, mit einer Tabelle gemäß 4, wird durch die Konkatenation von Spaltenindex und Zeilenindex der Tabelleneingang x = xx gebildet. Der an der durch Spaltenindex und Zeilenindex festgelegten Stelle in der Tabelle stehende Wert ist der Tabellenausgang y = yy. In 4 ist ein Beispiel eines Tabellenzugriffs mit Tabelleneingang xx = 12 und Tabellenausgang yy = 11 eingezeichnet (Schnittbereich der beiden Ellipsen). 4 shows a table S in unmasked form (original table), z. For example, an AES-S box. The table is shown in the quad system with base 4. Thus, each bit can take the four values 0, 1, 2, 3. For a table access at the AES according to 2 , with a table according to 4 , is formed by the concatenation of column index and row index of the table input x = xx. The value in the table at the location specified by column index and row index is the table output y = yy. In 4 is an example of a table access with table input xx = 12 and table output yy = 11 drawn in (intersection of the two ellipses).
5 zeigt eine komplementierte Tabelle S zur Tabelle S aus 4, wobei nur der Tabelleneingang x komplementiert ist. Der Tabelleneingang x ist dadurch komplementiert, dass die Positionen der Tabelleneinträge komplementiert sind. Beispielsweise ist der Eintrag zum Index x = xx = 00 aus 4 in 5 an den Index x = 33 verschoben, der Eintrag zum Index x = 12 an den Index x = 21, etc.. Das Beispiel aus 4 wird mit der Maskierung aus 5 zu einem Tabellenzugriff mit Tabelleneingang xx = 21 und Tabellenausgang yy = 11 (Schnittbereich der beiden Ellipsen). 5 shows a complemented table S to the table S from 4 , where only the table input x is complemented. The table input x is complemented by the fact that the positions of the table entries are complemented. For example, the entry to the index is x = xx = 00 4 in 5 to the index x = 33 moved the entry to the index x = 12 at the index x = 21, etc .. The example 4 becomes with the masking off 5 to a table access with table input xx = 21 and table output yy = 11 (intersection of the two ellipses).
6 zeigt eine komplementierte Tabelle S zur Tabelle S aus 4, wobei nur der Tabellenausgang y = yy komplementiert ist zu y. Der Tabellenausgang y ist dadurch komplementiert, dass der Wert des Tabelleneintrags komplementiert ist. Beispielsweise ist der Tabellen-Ausgangs-Wert y = 11 am Index x = 12 aus 4 in 6 zu einem Tabellen-Ausgangs-Wert y = 22 komplementiert, und verbleibt dabei an der gleichen Stelle. Der beispielhafte Tabellenzugriff ergibt mit der Maskierung aus 6 Tabelleneingang x = 12 und Tabellenausgang y = 22 (Kreis). 6 shows a complemented table S to the table S from 4 , where only the table output y = yy is complemented to y , The table output y is complemented by the fact that the value of the table entry is complemented. For example, the table output value y = 11 at index x = 12 is off 4 in 6 to a table output value y = 22 complements, and remains in the same place. The example table access results with the masking 6 Table input x = 12 and table output y = 22 (Circle).
7 zeigt eine komplementierte Tabelle S zur Tabelle S aus 4, wobei der Tabelleneingang x und der Tabellenausgang y komplementiert sind. Ausgehend von 5 ist z. B. der Tabelleneintrag, der in 5 vom Eingangswert x = 21 zum Ausgangswert y = 11 führt, zu einem Ausgangswert y = 22 komplementiert. Ausgehend von 6 ist der Ausgangswert y = 22 von 6 vom Index x = 12 zum Index x = 21 verschoben, d. h. zusätzlich ist der Eingangswert x komplementiert zu x. Der Tabellenzugriff aus 4 wird in der Maskierung von 7 somit zum Tabellenzugriff mit Tabelleneingang x = 21 und Tabellenausgang y = 22 (Kreis). 7 shows a complemented table S to the table S from 4 , where the table input x and the table output y are complemented. Starting from 5 is z. For example, the table entry that is in 5 from the input value x = 21 to the output value y = 11 leads to an output value y = 22 complemented. Starting from 6 is the initial value y = 22 from 6 from the index x = 12 to the index x = 21 shifted, ie in addition, the input value x is complemented to x , The table access 4 is in the masking of 7 thus for table access with table input x = 21 and table output y = 22 (Circle).
8–12 zeigen ausgehend von der Tabelle aus 4 randomisierte (= maskierte) Tabellen S', S'', mit einer XOR-Maskierung als Basismaskierung. Jeder Eingangswert x der Tabellen in 8–12 ist somit gemäß der Rechenvorschrift x → XXOR = x ⊕ r maskiert zu XXOR. 8th - 12 show starting from the table 4 randomized (= masked) tables S ', S ", with XOR masking as base masking. Each input value x of the tables in 8th - 12 is thus masked according to the calculation rule x → X XOR = x ⊕ r to X XOR .
8 zeigt eine XOR-randomisierte Tabelle S', mit Eingangsmaske 31 und Ausgangsmaske 00, d. h. nur der Tabelleneingang x ist maskiert, nämlich mit XOR-Maske 31, und der Tabellenausgang y ist unmaskiert (XOR-Maske 00, was äquivalent ist zu keiner Maskierung). Ausgehend von der Tabelle S aus 4 ergibt dies Eingang 23 und Ausgang 11 (Kreis). 8th shows an XOR randomized table S ', with input mask 31 and output mask 00, ie only the table input x is masked, namely with XOR mask 31, and the table output y is unmasked (XOR mask 00, which is equivalent to no masking) , Starting from the table S from 4 this gives input 23 and output 11 (circle).
9 zeigt eine XOR-randomisierte Tabelle S', mit Eingangsmaske 00 und Ausgangsmaske 02, d. h. nur der Tabellenausgang ist maskiert, nämlich mit XOR-Maske 02, und der Tabelleneingang ist unmaskiert (XOR-Maske 00). Ausgehend von der Tabelle aus 4 gibt dies Eingang 12 und Ausgang 13. 9 shows an XOR randomized table S ', with input mask 00 and output mask 02, ie only the table output is masked, namely with XOR mask 02, and the table input is unmasked (XOR mask 00). Starting from the table 4 this gives input 12 and output 13.
10 zeigt eine XOR-randomisierte Tabelle S', mit Eingangsmaske 31 und Ausgangsmaske 02. 10 zeigt eine mit XOR-Maskierung als Basismaskierung maskierte Tabelle, die als Grundlage zur Erzeugung einfach und zweifach (doppelt) erweitert maskierter Tabellen (11, 12) dient. Ausgehend von der Tabelle aus 4 ergibt dies einen Tabellenzugriff mit Eingangswert xXOR = 23 und Ausgangswert yXOR = 13. 10 shows an XOR randomized table S ', with input mask 31 and output mask 02. 10 shows a mask masked with XOR masking as base masking, which is used as the basis for generating single and double (twice) extended masked tables ( 11 . 12 ) serves. Starting from the table 4 this results in a table access with input value x XOR = 23 and output value y XOR = 13.
11 zeigt eine einfach erweiterte XOR-randomisierte (= XOR-maskierte) Tabelle S'' (einfach: Erweiterung nur in eine Richtung der Tabelle, hier nach rechts), mit Eingangsmaske 31 und Ausgangsmaske 02. In der erweiterten Tabelle sind die unkomplementierte XOR-Basis-maskierte Tabelle S' (= Tabelle aus 10) und eine Komplementär-Tabelle S' zur XOR-Basis-maskierten Tabelle enthalten. Die Komplementär-Tabelle S' ist dadurch gebildet, dass bei der Basis-maskierten Tabelle S' aus 10 der Tabelleneingang x und der Tabellenausgang y komplementiert sind. Das zweite Bit (Spaltenindex) des Tabelleneingangs x ist um ein vorangestelltes Auswahlbit a (= Tabellen-Auswahlabschnitt) erweitert. Tabelleneingänge x haben somit in der Tabelle aus 11 die Form axx, Tabellenausgänge y unverändert die Form yy. Die Form axx ist beispielhaft angeführt und kann alternativ ebensogut xax oder xxa sein. Die Einträge zu den Zeilenindizes 00, 01, 02, 03 (oben), bei denen das Auswahlbit a im Tabelleneingangswert axx den Wert Null (0) hat, gehören zur unkomplementierten, nur mit der Basismaskierung maskierten Tabelle (Tabelle aus 10). Die Einträge zu den Zeilenindizes 10, 11, 12, 13 (oben,), bei denen das Auswahlbit a im Tabelleneingangswert axx den Wert Eins (1) hat, gehören zur Komplementär-Tabelle. Der beispielhafte Tabellenzugriff aus 4 wird in der erweiterten Maskierung S'' aus 11 zu einem Tabellenzugriff mit Tabelleneingang axx = 023 und Tabellenausgang yy = 13 oder Tabelleneingang axx = 123 und Tabellenausgang yy = 31. Ob der Tabellenzugriff mit entweder Tabelleneingang xXOR = axx = 023 und Tabellenausgang yy = 13 (obere Tabellenhälfte, Auswahlbit im Tabelleneingang 023 hat den Wert 0) oder Tabelleneingang = axx = 123 und Tabellenausgang yy = 31 (untere Tabellenhälfte, Auswahlbit im Tabelleneingang 123 hat den Wert 1) durchgeführt wird, ist dabei zufallsgesteuert. 11 shows a simply extended XOR-randomized (= XOR-masked) table S '' (simple: extension only in one direction of the table, here to the right), with input mask 31 and output mask 02. In the extended table are the uncomplemented XOR basis -masked table S '(= table off 10 ) and a complementary table S 'to the XOR base masked table. The complementary table S ' is formed by that in the base-masked table S ' out 10 the table input x and the table output y are complemented. The second bit (column index) of the table input x is extended by a preceding selection bit a (= table selection section). Table inputs x are thus in the table 11 the form axx, table outputs y unchanged the form yy. The form axx is given as an example and may alternatively also be xax or xxa. The entries for the row indexes 00, 01, 02, 03 (top), in which the selection bit a in the table input value axx has the value zero (0), belong to the uncomplemented table masked only with the basic masking 10 ). The entries for the row indexes 10, 11, 12, 13 (above), in which the selection bit a in the table input value axx has the value one (1) belong to the complementary table. The sample table access 4 will be off in the extended mask S " 11 to a table access with table input axx = 023 and table exit yy = 13 or table input axx = 123 and table exit yy = 31. Whether the table access has either table entry x XOR = axx = 023 and table exit yy = 13 (upper table half, selection bit in table entry 023) the value 0) or table input = axx = 123 and table output yy = 31 (lower half of the table, selection bit in table input 123 has the value 1) is random.
Der Einsatz einer einfach erweiterten Tabelle wird nachfolgend anhand von 2 und 11 erläutert. In einem AES-Krypto-Coprozssor wird eine AES-Berechnung (wahlweise Verschlüsselung, Entschlüsselung, Signaturerzeugung oder Signaturprüfung) gestartet, in 2 beispielhaft eine Verschlüsselung. AES umfasst mehrere Runden R = 1, 2, ... . In jeder Runde R wird eine Teilberechnung durchgeführt, in der ein Klartextbyte p mit einem Schlüsselbyte k verxort (p ⊕ k) wird, das Ergebnis der Verxorung in eine (Substitutions-)Tabelle S (S-Box) eingesetzt wird und hierdurch durch einen Tabellenzugriff auf die Tabelle S ein Zwischenwert x = S[p ⊕ k] berechnet wird.The use of a simply extended table is explained below by means of 2 and 11 explained. In an AES crypto coprocessor, an AES calculation (optionally encryption, decryption, signature generation or signature verification) is started, in 2 an example of encryption. AES comprises several rounds R = 1, 2, .... In each round R, a partial computation is performed in which a plaintext byte p with a key byte k becomes corrupted (p ⊕ k), the result of the corruption into a (substitution) table S (S-box) is used and this is calculated by a table access to the table S an intermediate value x = S [p ⊕ k] is calculated.
Gemäß einer Ausführungsform der erweiterten Maskierung wird als Tabelle S in 2 eine gemäß 11 einfach erweiterte Tabelle S'' verwendet. Der Eingangswert x wird um ein Bit als Tabellenauswahl-Abschnitt a erweitert. Der Eingangswert x lautet somit x = αx1x0, in 11 beispielsweise x = 023, falls auf die nicht-komplementierte Tabelle S' zugegriffen wird, mit Ausgangswert y = 13 (wie in 10), und x = 110, falls auf die komplementierte Tabelle S' in S'' zugegriffen wird, mit Ausgangswert y = 22.According to one embodiment of the extended masking, the table S in FIG 2 one according to 11 simply extended table S '' used. The input value x is extended by one bit as a table selection section a. The input value x is thus x = αx 1 x 0 , in 11 For example, x = 023 if the non-complemented table S 'is accessed, with output value y = 13 (as in FIG 10 ), and x = 110 if on the complemented table S ' is accessed in S '', with output value y = 22.
12 zeigt eine, ausgehend von der Tabelle S' aus 10, gefaltete XOR-randomisierte Tabelle T, mit Eingangsmaske i = 31, Ausgangsmaske o = 02 und Faltungsdistanz d = 12. Eingekreist ist derjenige Tabelleneintrag dargestellt, auf den der Tabellenzugriff erfolgt. Basis ist 4. Ausgehend von der Tabelle aus 10 wird der Tabelleneintrag an der Stelle (= am Eingangswert) 23 mit dem Tabelleneintrag an der Stelle 23 xor 12 = 31 zusammengelegt. D. h. die Tabelle S' wird so zur Tabelle T gefaltet, dass die Tabelleneinträge an den Stellen 23 und 31 aufeinander zu liegen kommen. Die Faltungsdistanz (bei Basis 4) d = 12 (dezimal 6) hat die Binärdarstellung 0110. Isolieren wir in der (binär dargestellten) Faltungsdistanz d das unterste Bit, das gleich 1 ist, erhalten wir 0010. Wie gesagt werden die Einträge an den Stellen 23 (= binär 0111) und 31 (= binär 1101) zusammengelegt. Dabei müssen wir für die gefaltete Tabelle T denjenigen Eingangswert auswählen, der an der Stelle 0010 gleich 0 ist, also den Eingangswert 31 (= binär 1101). Für die gefaltete Tabelle T müssen wir die 0 an der Stelle 0010 streichen, haben also als Eingangswert binär 111 (= 13 im Vierersystem). Deshalb erfolgt der Tabellenzugriff in der Tabelle T aus 12 auf den Tabellen-Ausgangswert 11 zum Tabellen-Eingangswert 13 (eingekreist). 12 shows one, starting from the table S 'from 10 , folded XOR-randomized table T, with input mask i = 31, output mask o = 02 and convolution distance d = 12. Circled is the table entry on which the table access takes place. Base is 4. Starting from the table 10 the table entry at the position (= at the input value) 23 is merged with the table entry at the position 23 xor 12 = 31. Ie. the table S 'is folded to the table T so that the table entries at the points 23 and 31 come to lie on each other. The convolution distance (at base 4) d = 12 (decimal 6) has the binary representation 0110. If we isolate in the (binary) convolution distance d the lowest bit, which is equal to 1, we get 0010. As said, the entries are at the positions 23 (= binary 0111) and 31 (= binary 1101) combined. For the folded table T we have to select the input value which is 0 at the position 0010, ie the input value 31 (= binary 1101). For the folded table T we have to delete the 0 at the position 0010, so we have as input value binary 111 (= 13 in the quad system). Therefore, the table access takes place in the table T 12 to the table output value 11 to the table input value 13 (circled).
Nun können wir noch den dort stehenden Wert 11 überprüfen. Die lediglich randomisierte Tabelle S' aus 10 hat an den Stellen 23 und 31 die Werte 13 und 00 stehen, was verxort 13 xor 00 = 13 ergibt. Da sich durch das Verxoren die Ausgangsmaske o = 02 wieder heraushebt, müssen wir sie noch einmal draufverxoren und erhalten somit 13 xor 02 = 11.Now we can check the value 11 there. The only randomized table S 'off 10 has at positions 23 and 31 the values 13 and 00, which gives xx = 13 13 xx. Since the original mask o = 02 is lifted out again by the Verxoren, we have to rewrite it once again and thus get 13 xor 02 = 11.
13 zeigt eine, ausgehend von der gefalteten Tabelle T aus 12, einfach erweiterte Tabelle T', mit Auswahlbit an der obersten binären Bitstelle, gemäß einer Ausführungsform der Erfindung. Insgesamt ist die Tabelle T' aus 13 somit XOR-randomisiert, mit Eingangsmaske i = 31 und Ausgangsmaske o = 02, gefaltet mit Faltungsdistanz d = 12 und einfach erweitert, mit Auswahlbit an der obersten binären Bitstelle (erste Spalte, erste Stelle). Die untere Hälfte der Tabelle T' aus 13 hat invertierte Ausgangswerte in umgekehrter Reihenfolge. Der markierte Eingangswert 13 aus Tabelle T 12 wird zur Erzeugung der Tabelle T' aus 13 invertiert zum Eingangswert 20. An der Stelle 20 der Tabelle T' 13 steht gerade der im Vergleich zur Stelle 13 von 12 invertierte Wert 22. 13 shows a, starting from the folded table T from 12 , simply extended table T ', with select bit at the top binary bit location, according to an embodiment of the invention. Overall, the table T 'is off 13 thus XOR-randomized, with input mask i = 31 and output mask o = 02, folded with convolution distance d = 12 and simply extended, with selection bit at the uppermost binary bit position (first column, first digit). The lower half of the table T 'off 13 has inverted output values in reverse order. The marked input value 13 from table T 12 is used to generate the table T ' 13 inverted to the input value 20. At the position 20 of the table T ' 13 is just the compared to the 13th place 12 inverted value 22.
14 zeigt eine, ausgehend von der gefalteten Tabelle aus 12, einfach erweiterte Tabelle T', mit Auswahlbit an der untersten binären Bitstelle, gemäß einer bevorzugten Ausführungsform der Erfindung. Die Tabelle 14 erhält man aus Tabelle 13, indem man abwechselnd einen Eintrag von der oberen und von der unteren Hälfte der Tabelle 13 wählt (Zeile für Zeile). Daher taucht der erste, eingekreiste, Wert 22 der zweiten Hälfte von Tabelle 13 gleich als zweiter Wert in der Tabelle 14 auf, und entsprechend der letzte, eingekreiste, Wert 11 der oberen Hälfte von Tabelle 13 als vorletzter Wert der Tabelle 14. 14 shows one starting from the folded table 12 , simply extended table T ', with selection bit at the lowest binary bit position, according to a preferred embodiment of the invention. The table 14 obtained from table 13 by alternating an entry from the top and from the bottom half of the table 13 selects (line by line). Therefore, the first, circled, value 22 appears in the second half of the table 13 the second value in the table 14 on, and according to the last, circled, value 11 of the upper half of table 13 as penultimate value of the table 14 ,
15 zeigt eine, ausgehend von der gefalteten Tabelle aus 12, zweifach erweiterte Tabelle, mit zwei Auswahlbits, nämlich einem an der obersten binären Bitstelle (wie in 13), sowie einem an der zweitobersten Bitstelle. Das Auswahlbit an der obersten Binärstelle (wie in 13) entscheidet, ob der Tabellen-Ausgang invertiert ist oder nicht. Das Auswahlbit an der zweitobersten Binärstelle entscheidet, ob der Tabellen-Eingang invertiert ist oder nicht. 15 shows one starting from the folded table 12 , two times extended table, with two select bits, one at the top binary bit position (as in 13 ), as well as one at the second uppermost bit position. The selection bit at the top bin (as in 13 ) decides whether the table output is inverted or not. The selection bit at the second highest binary location decides whether the table input is inverted or not.
Im Folgenden wird eine bevorzugte Ausführungsform dargelegt, um eine gefaltete und erweitert maskierte Tabelle T' und eine Korrekturtabelle T ^ zu erzeugen und einen Tabellenzugriff auf einen Tabelleneintrag in der Tabelle T' durchzuführen, umfassend Korrektur des Tabelleneintrags mittels der Korrekturtabelle T ^. Als T' kann z. B. die eine Tabelle wie die aus 13 oder 14 vorgesehen sein. Dabei wird vom Grundsatz her von einer Tabelle S ausgegangen wie in 2 und 4–12 angegeben. Insbesondere ist durch die unmaskierte Tabelle S wahlweise dieselbe Funktion implementiert wie durch die Tabelle S. Beispielsweise ist S eine S-Box im AES gemäß 2. Jede der Tabellen T' und T ^ hat die Struktur einer erweiterten Tabelle, d. h. es gilt In the following, a preferred embodiment is set forth to generate a folded and expanded masked table T 'and a correction table T ^ and perform a table access to a table entry in the table T' comprising correction of the table entry by means of the correction table T ^. As T 'z. For example, the one table like the one out 13 or 14 be provided. This is based on the principle of a table S as in 2 and 4 - 12 specified. In particular, the same function is implemented by the unmasked table S as by the table S. For example, S is an S-box in the AES according to 2 , Each of the tables T 'and T ^ has the structure of an extended table, that is to say
Im Permanentspeicher (vorzugsweise) ROM wird die folgende Korrekturtabelle T ^ abgelegt, wobei x >> i für ein Rechtsschieben von x um i Stellen in Binärdarstellung steht, und ein Überstrich für Einerkomplement-Bildung.In the non-volatile memory (preferably) ROM, the following correction table T ^ is stored, where x >> i is for a right shift of x by i digits in binary representation, and an override for one's complement formation.
Im Arbeitsspeicher RAM wird eine gefaltete und erweitert maskierte Tabelle T' erzeugt. Als Basismaskierung wird eine XOR-Maskierung verwendet, mit einer Tabelleneingangsmaske i und einer Tabellenausgangsmaske o. Anlässlich jeder Berechnung einer Tabelle T' im Arbeitsspeicher RAM wird zufällig eine Faltungsdistanz d ≠ 0 festgesetzt. Als unmaskierter Eingangswert für einen Tabellenaufruf auf Tabelle T' wird x verwendet, z. B. x = p ⊕ k gemäß 2. Für die Maskierung des Tabelleneingangs mit der Maske i wird ein erstes Zufallsbit b festgelegt, das, ebenso wie die Zufallsdistanz d, für jede Berechnung einer Tabelle T' im Arbeitsspeicher RAM neu zufällig festgesetzt wird. Der erweitert XOR-maskierte Tabellen-Eingangswert x' ist gleich A folded and expanded masked table T 'is generated in the main memory RAM. XOR masking is used as base masking, with a table input mask i and a table output mask o. On the occasion of each calculation of a table T 'in the main memory RAM, a folding distance d ≠ 0 is set at random. As an unmasked input for a table call on table T ', x is used, e.g. B. x = p ⊕ k according to 2 , For the masking of the table input with the mask i, a first random bit b is set, which, just like the random distance d, is again randomly set for each calculation of a table T 'in the main memory RAM. The extended XOR-masked table input value x 'is the same
Die ausgehend vom maskierten Tabelleneingangswert x' gebildete RAM-Tabelle T' ist definiert als, mit der Faltungsfunktion fd, The RAM table T 'formed from the masked table input value x' is defined as, with the convolution function f d ,
Die Faltungsfunktion fd (nicht gemeint ist hiermit die mathematische Operation der Faltung) wird in den folgenden zwei Schritten gebildet. Dabei ist mit „&” das bitweise UND bezeichnet. Die Zufallsdistanz d in Binärdarstellung ist dargestellt durch eine Folge von 1-Bits und 0-Bits. Die Bitlänge der Faltungsdistanz d ist in der Regel gleich der Bitlänge des Eingangswerts x. Für einen konkreten Wert der Zufallsdistanz d taucht an irgend einer bestimmten Bit-Stelle in d das niedrigste 1-Bit z von d auf, d. h. das niedrigste Bit, das Eins ist, und alle noch niedrigeren Bits sind Null. Das niedrigste 1-Bit ist gleich z = d&(–d). An der Bitstelle des niedrigsten 1-Bits der Zufallsdistanz d hat nur entweder der basismaskierte Eingangswert x' oder der Faltungs-Partner zum basismaskierte Eingangswert x' ⊕ d ein 1-Bit, d. h. nur entweder in x' oder in x' ⊕ d ist das niedrigste 1-Bit z von d (auf den Wert 1) gesetzt.The convolution function f d (not meant hereby the mathematical operation of convolution) is formed in the following two steps. Where "&" denotes the bitwise AND. The random distance d in binary representation is represented by a sequence of 1-bits and 0-bits. The bit length of the convolution distance d is generally equal to the bit length of the input value x. For a particular value of the random distance d, at any given bit position in d, the lowest 1-bit z of d appears, ie the lowest bit which is one, and all even lower bits are zero. The lowest 1-bit is equal to z = d & (- d). At the bit position of the lowest 1-bit of the random distance d, only either the base-masked input value x 'or the convolutional partner to the base-masked input value x' ⊕ d has a 1-bit, ie only in either x 'or x' ⊕ d lowest 1-bit z of d (set to the value 1).
Im ersten Schritt des Bildens der Faltungsfunktion fd wird derjenige Wert aus x' und x' ⊕ d ausgewählt, der an der Bitstelle des niedrigsten 1-Bits der Zufallsdistanz d eine Null stehen hat und als x'' definiert.In the first step of forming the convolution function f d , the value of x 'and x' ⊕ d is selected which has a zero at the bit position of the lowest 1-bit of the random distance d and defined as x ''.
Im zweiten Schritt wird die Null, die an der Bitstelle des niedrigsten 1-Bits der Zufallsdistanz d steht, aus dem basismaskierten Eingangswert x' gestrichen (der Eingangswert x' ist nach wie vor in Binärdarstellung). Durch die Streichung der Null wird x'' übergeführt in den Wert der Faltungsfunktion fd(x') an der Stelle x': fd(x') := (x'' + (x''&m)) >> 1, wobei m = –(x'&z) In the second step, the zero, which is at the bit position of the lowest 1-bit of the random distance d, is deleted from the base-masked input value x '(the input value x' is still in binary representation). By deleting the zero, x '' is converted into the value of the convolution function f d (x ') at the position x': f d (x '): = (x''+(x''& m)) >> 1, where m = - (x'& z)
Für alle d ≠ 0 verkürzt die Faltungsfunktion fd(x') ihr Argument x' um ein Bit und ist surjektiv. Daher ist die Tabelle T' wohldefiniert.For all d ≠ 0, the convolution function f d (x ') shortens its argument x' by one bit and is surjective. Therefore, the table T 'is well defined.
Da stattgilt, muss im Fall b = 1 der Term fd(z) zur Korrektur des Eingangswerts x' der RAM Tabelle verwendet werden.There instead is true, in case b = 1, the term f d (z) must be used to correct the input value x 'of the RAM table.
Insgesamt besteht beim vorliegenden Ausführungsbeispiel ein erweitert maskierter Tabellenaufruf mit gefalteter Tabelle aus folgenden Schritten.
- 1. Berechne den Index u = x' ⊕ d für die ROM Korrekturtabelle T ^
- 2. Für ein Zufallsbit b' (b', b unabhängig) maskiere den Index u um zu
- 3. Berechne den Index ν = fd(x') für die RAM Tabelle T'
- 4. Berechne die Korrektur
- 5. Korrigiere den Index ν zu ν' = ν ⊕ c
- 6. Werte die ROM Korrekturtabelle T aus mittels y0 = T ^[(u' << 1) + (b ⊕ b')]
- 7. Werte die RAM Tabelle T' (d. h. z. B. die AES S-Box) aus mittels y1 = T'[(ν' << 1) + b]
- 8. Kombiniere die ausgelesenen Tabellenwerte y0 der Korrekturtabelle und y1 der Tabelle (z. B. AES S-Box) zum Ergebnis des Tabellenzugriffs (= Tabellen-Ausgangswert) y' = y0 ⊕ y1
Overall, in the present embodiment, an expanded masked table call with folded table consists of the following steps. - 1. Compute the index u = x '⊕ d for the ROM correction table T ^
- 2. For a random bit b '(b', b independent) mask the index u to
- 3. Compute the index ν = f d (x ') for the RAM table T'
- 4. Calculate the correction
- 5. Correct the index ν to ν '= ν ⊕ c
- 6. Read out the ROM correction table T using y 0 = T ^ [(u '<< 1) + (b ⊕ b')]
- 7. Evaluate the RAM table T '(ie eg the AES S-Box) by means of y 1 = T '[(ν'<< 1) + b]
- 8. Combine the read table values y 0 of the correction table and y 1 of the table (eg AES S-Box) to the result of the table access (= table output value) y '= y 0 ⊕ y 1
Per Konstruktion ist das Ergebnis y' des Tabellenzugriffs auf die Tabelle T' der mit der XOR-Maske o und erweitertem Maskenbit b' erweitert maskierte Wert zum unmaskierten Wert y = T[x]: By construction, the result y 'of the table access to the table T' is the value masked with the XOR mask o and extended mask bit b 'to the unmasked value y = T [x]:
Die Rechnung zeigt, dass der angegebene Algorithmus funktional korrekt ist. Die Sicherheit gegen DPA 2. Ordnung kann durch sorgfältige Analyse der einzelnen Schritte verifiziert werden und wurde durch eine Implementierung auf einer Chipkarte praktisch überprüft.The calculation shows that the specified algorithm is functionally correct. The security against DPA 2nd order can be verified by careful analysis of the individual steps and has been practically verified by an implementation on a smart card.
Beim obigen Ausführungsbeispiel wurde durch einen Tabellenauswahlabschnitt, konkret mittels eines zusätzlich an der untersten Stelle ergänzten Bits, signalisiert, ob eine zusätzliche Komplementierung des (basis-)maskierten Werts gegeben ist (Bit = 1) oder nicht (Bit = 0). Dieses Bit muss nicht an unterster Stelle stehen, sondern kann auch an anderer Stelle stehen. Wird das Bit des Tabellenauswahlabschnitts an einer anderen Stelle eingefügt, ändern sich die Formeln für die Tabellen und die Berechnung der Indices (u, v) entsprechend. Zudem kann die Kodierung auch umgekehrt erfolgen, d. h. Bit = 1 ist ohne zusätzliche Komplementierung und Bit = 0 ist mit zusätzlicher Komplementierung. In der Regel wird die Information für den Tabellenauswahlabschnitt getrennt von den maskierten Daten gehalten und nur die die Durchführung eines Tabellenaufrufs eingefügt. Wahlweise wird statt der im Ausführungsbeispiel vorgesehenen einfachen Erweiterung (entsprechend 13, 14) eine doppelte Erweiterung vorgesehen (entsprechend 15).In the above embodiment, it was signaled by a table selection section, specifically by means of an additionally supplemented at the lowest point bits, whether an additional complementation of the (base) masked value is given (bit = 1) or not (bit = 0). This bit does not have to be at the bottom, but can also be somewhere else. If the bit of the table selection section is inserted elsewhere, the formulas for the tables and the calculation of the indices (u, v) change accordingly. In addition, the coding can also be reversed, ie bit = 1 is without additional complementation and bit = 0 is with additional complementation. In general, the information for the table selection section is kept separate from the masked data and only the implementation of a table call is inserted. Optionally, instead of the simple extension provided in the exemplary embodiment (corresponding to FIG 13 . 14 ) provided a double extension (corresponding to 15 ).
Zitierter Stand der Technik:Cited prior art:
-
1) DE 198 22217 A1 ;1) DE 198 22217 A1 ;
-
2) EP 2 302 552 A1 ;2) EP 2 302 552 A1 ;
-
3) DE 10 2012 018 924.9 3) DE 10 2012 018 924.9
-
4) DE 10 2004 032 893 A1 4) DE 10 2004 032 893 A1
-
5) [PRB10] E. Prouff, M. Rivain, R. Bévan: Statistical Analysis of Second Order Differential Power Analysis, http://eprint.iacr.org/2010/646.pdf, IEEE Transactions on Computers 58, S. 799.811, 2009 ;5) [PRB10] E. Prouff, M. Rivain, R. Bévan: Statistical Analysis of Second Order Differential Power Analysis, http://eprint.iacr.org/2010/646.pdf, IEEE Transactions on Computers 58, p. 799,811, 2009 ;
ZITATE ENTHALTEN IN DER BESCHREIBUNG QUOTES INCLUDE IN THE DESCRIPTION
Diese Liste der vom Anmelder aufgeführten Dokumente wurde automatisiert erzeugt und ist ausschließlich zur besseren Information des Lesers aufgenommen. Die Liste ist nicht Bestandteil der deutschen Patent- bzw. Gebrauchsmusteranmeldung. Das DPMA übernimmt keinerlei Haftung für etwaige Fehler oder Auslassungen.This list of the documents listed by the applicant has been generated automatically and is included solely for the better information of the reader. The list is not part of the German patent or utility model application. The DPMA assumes no liability for any errors or omissions.
Zitierte PatentliteraturCited patent literature
-
DE 19822217 A1 [0013, 0096] DE 19822217 A1 [0013, 0096]
-
DE 102012018924 [0016, 0017, 0018, 0021, 0022, 0022, 0024, 0026, 0027, 0031, 0031, 0066, 0096] DE 102012018924 [0016, 0017, 0018, 0021, 0022, 0022, 0024, 0026, 0027, 0031, 0031, 0066, 0096]
-
DE 102004032893 A1 [0023, 0066, 0096] DE 102004032893 A1 [0023, 0066, 0096]
-
DE 102012018924 A1 [0025] DE 102012018924 A1 [0025]
-
EP 2302552 A1 [0096] EP 2302552 A1 [0096]
Zitierte Nicht-PatentliteraturCited non-patent literature
-
E. Prouff, M. Rivain, R. Bévan: Statistical Analysis of Second Order Differential Power Analysis, http://eprint.iacr.org/2010/646.pdf, IEEE Transactions on Computers 58, S. 799.811, 2009 [0096] E. Prouff, M. Rivain, R. Bévan: Statistical Analysis of Second Order Differential Power Analysis, http://eprint.iacr.org/2010/646.pdf, IEEE Transactions on Computers 58, p. 799,811, 2009 [0096 ]