Cryptography Engineering, Teil 3: AES auf 8-Bit-Mikrocontrollern

Problem S-Boxen

Die S-Boxen verursachen ein erhebliches Ressourcenproblem. Wie lässt sich eine Tabelle anders als durch eine Tabelle darstellen? Für den veralteten Kryptostandard DES (Data Encryption Standard) hieß die Antwort noch: Es muss eine Tabelle sein. AES ist an der Stelle intelligenter. Die S-Boxen sind hier nicht willkürlich durch "Würfeln" entstanden. Vielmehr sind die Substitutionen in AES Abbildungen eines Bytes auf sein multiplikatives Inverses im endlichen Körper GF(2^8), auf das noch eine affine Transformation in GF(2) (also bitweise) erfolgt. Die "affine Transformation" klingt komplizierter als sie ist. Sie besteht aus bitweisen XOR-Verknüpfungen und lässt sich der AES-Spezifikation (PDF) aus Abschnitt 5.1.1 auf Seite 15 direkt entnehmen.

Diese Eigenschaft der S-Boxen von AES ermöglicht es, die entsprechenden Werte dynamisch zur Laufzeit zu berechnen und nicht starr in einer Tabelle vorhalten zu müssen. Grundsätzlich stellt sich dabei die Frage, wie das effizient erfolgen kann, ohne die kryptografischen Funktionen zu sehr zu verlangsamen. Schließlich muss die Berechnung mit einem einfachen Table-Lookup (siehe 32-Bit-Implementierung) konkurrieren.

In GF(2^8) gibt es prinzipiell drei Ansätze, um das multiplikative Inverse p^-1 zu einem gegebenen Wert p zu berechnen. Ein Ansatz wäre, den Wert p sukzessive mit jedem Wert von 0 bis 255 in GF(2^8) zu multiplizieren, bis sich 1 ergibt. Dieser Brute-force-Ansatz hat jedoch seine Schwächen. Im schlimmsten Fall benötigt er zur Berechnung des multiplikativen Inversen 256 Multiplikationen. Eine Multiplikation in GF(2^8) ist – wie der erste Beitrag dieser Reihe zeigt – nicht gerade eine schnelle Operation. Einen Rausch der Geschwindigkeit darf man vom Brute-force-Ansatz daher nicht erwarten. Er ist ungeeignet; gerade, aber nicht nur für Mikrocontroller.

Die zweite Möglichkeit ist es, eine Logarithmustabelle in GF(2^8) aufzubauen und die Multiplikation nach dem Rechenschieberprinzip auf Subtraktionen zurückzuführen. Das multiplikative Inverse p^-1 von p ließe sich dann wie folgt errechnen:

p^-1 = alog(0xFF XOR log(p))

log ist hierbei der Logarithmus in GF(2^8), und alog ist der zugehörige Antilogarithmus.

Das Problem ist bei dem Ansatz wieder das Stichwort "Tabelle". In den Tabellen für Logarithmus und Antilogarithmus ist für jedes Byte der zugehörige Wert zu halten. Beide Tabellen sind wiederum je 256 Bytes groß. Das komplizierte und zusätzliche Taktzyklen verbrauchende Logarithmieren kann man sich demnach von vornherein sparen. Die S-Boxen würden als Tabellen realisiert auch nicht mehr Speicherplatz belegen, und gesonderte Rechenoperationen wären dann ebenfalls unnötig.

Alternativ lassen sich Logarithmus und Antilogarithmus dynamisch berechnen. Das läuft aber im Wesentlichen auf eine Schleife ähnlich dem Brute-force-Ansatz hinaus. Auch wenn diese Schleife zur Laufzeit im Mittel effizienter als der Brute-force-Ansatz ist, gibt es eine bessere Alternative: das Berechnen des multiplikativen Inversen mit dem erweiterten euklidischen Algorithmus. Das zeigen Menezes, Oorschot und Vanstone in ihrem "Handbook of Applied Cryptography" [2] ab Seite 71 sowie Hankerson, Menezes und Vanstone im "Guide to Elliptic Curve Cryptography" [3] ab Seite 39.

Die Grundvariante zum Berechnen des multiplikativen Inversen in GF(2^8) mit dem irreduziblen Polynom 0x011B zeigt Abbildung 1. Der Algorithmus setzt auf den erweiterten euklidischen Algorithmus. Der Parameter u ist hierbei der Wert, für den es das Inverse zu berechnen gilt. Der Parameter v erhält das Polynom 0x011B. Die Funktion deg(p) berechnet den Grad des Polynoms p. Vereinfacht gesagt, liefert deg(p) nichts anderes als die Position des höchsten gesetzten Bits in p zurück. Je nachdem, ob nun zuerst u oder v den Wert 1 annimmt, liegt das Inverse in g1 oder g2. Dieser Algorithmus lässt sich so oder ähnlich der mathematischen Fachliteratur entnehmen. Er enthält für die Implementierung auf einem 8-Bit Mikrocontroller jedoch einige Schwächen.

Erweiterter euklidischer Algorithmus zur Berechnung des multiplikativen Inversen in GF(2^8) (Abb. 1)

Erster markanter Punkt ist bei der ersten Anweisung nach dem START in Abbildung 1 zu sehen. Die Variable v erhält den Wert 0x011B. Das ist offensichtlich ein 16-Bit-Wert. Auf 8-Bit-Architekturen heißt das, sämtliche Operationen gesplittet auf zwei Bytes durchzuführen. Das ist pures Verschwenden von Taktzyklen und das für ein einziges Bit. Mal von Zwischenergebnissen von xtime() abgesehen, verwendet lediglich das irreduzible Polynom 0x011B dieses Bit Nr. 8. Hierfür lohnt sich das Verschwenden von Taktzyklen wohl kaum.

Ein weiterer Schwachpunkt sind die Operationen rund um deg() und die Variable j. Die j. Potenz der Variablen z ist trügerisch. z ist die Indeterminante der Polynome. z^j steht somit für den Wert des j. Bit des Polynoms. Der Algorithmus aus Abbildung 1 errechnet somit zunächst das höchste gesetzte Bit per deg() und ermittelt später das j. Bit. Mathematisch formal ist das nachvollziehbar und elegant. Für eine technische Realisierung ist das jedoch alles andere als wegweisend.

Zunächst sind das zusätzliche Bit und damit die Notwendigkeit eines 16-Bit-Werts wegzubekommen. Hierbei hilft ein Trick, den der optimierte Algorithmus in Abbildung 2 verwendet. Der Trick beruht auf der Beobachtung, dass der Wert 0x00 per definitionem bezüglich der Multiplikation zu sich selbst invers ist. Des Weiteren ist auch der Wert 0x01 multiplikativ zu sich selbst invers. Die beiden Werte 0 und 1 sind jedoch die einzigen Werte, deren Grad vom ersten Bit abhängt. Alle anderen Werte haben ein höchstes gesetztes Bit größer als das Bit 0. Relevant für das Berechnen des Grads eines Polynoms ist dieses Bit also nur für 0 und 1, die selbst invers sind. Der Algorithmus aus Abbildung 2 sortiert die beiden Werte zu Anfang einfach aus. Das unterste Bit ist damit im Folgenden verzichtbar. Das "überzählige" achte Bit des Polynoms 0x011B wandert damit beim Bestimmen des Grads eine Position tiefer.

Optimierte Variante für 8-Bit-Mikrocontroller des Algorithmus zur Berechnung des Inversen in GF(2^8) (Abb. 2)

Statt nun die Polynome u und v durch einen 16-Bit-Wert zu repräsentieren, genügt es, die Polynome als 8-Bit-Wert aufzufassen. Das nullte Bit blendet die Darstellung einfach aus. Den zugehörigen Grad halten dann die Variablen zj1 für u und zj2 für v fest. Damit sind zwar immer noch 2 mal 8 Bit notwendig, aber nicht mehr 1 mal 16 Bit plus der Wert von deg().

Zudem kombiniert dieser optimierte Algorithmus die Funktion deg() mit dem Berechnen von z^j. Die Funktion gdeg() liefert von vornherein das höchste gesetzte Bit des Polynoms als seinen Wert, nicht als seine Position zurück. Das allerdings unter Einbeziehung des vorherigen Tricks, dass gdeg() lediglich die Bits 1 bis 8 betrachtet und Bit 0 streicht. Statt beispielsweise für 0x10 den deg()-Wert 4 zu liefern, gibt gdeg(0x10) das Ergebnis von 2^4 >> 1, also 0x08, zurück. Statt nun über den Wert j als Differenz der beiden deg()-Werte wie in ursprünglichen Algorithmus z^j zu ermitteln, verfügt der optimierte Algorithmus automatisch über den jeweiligen Wert von z^j. Die Differenz der Exponenten (deg(u) - deg(v)) weicht in dem Fall dem Quotienten (zj2 / zj1).

gdeg() errechnet über einfachste Schiebeoperationen das höchste gesetzte Bit. Es pflanzt das höchste gesetzte Bit dabei in alle niederen Bits. Eine Addition von 1 und das Rechtsschieben um zwei Positionen liefert das gewünschte – um Bit 0 – bereinigte Ergebnis. Dieser Algorithmus ist im Beispielprogramm in gmulinv() im Modul aes.c (Verzeichnis avr) implementiert (siehe hier). Um nun die S-Box-Werte zu berechnen, ist dem Ergebnis von gmulinv() nur noch stumpf die oben angesprochene affine Transformation aus AES (PDF) anzuhängen. Das geschieht in den Funktionen subByte() und invSubByte() aus aes.c. Damit ist das dynamische Berechnen der S-Box-Einträge 8-Bit-verträglich und effizient realisiert.

Mit dem Algorithmus aus Abbildung 2 beziehungsweise gmulinv() schließt der Artikel nun die Lücke aus dem ersten Beitrag. Exakt hiermit lässt sich das Inverse p^-1 eines beliebigen Werts p aus GF(2^8) berechnen. Multipliziert man dieses Inverse p^-1 mit einem anderen Wert q aus GF(2^8), kommt das einer Division durch p in GF(2^8) gleich. Es gilt also für alle p in GF(2^8) die folgende Aussage:

q / p = q * p^-1 = q * gmulinv(p)