Wie lässt sich AES beschleunigen?

AES (Advanced Encryption Standard) ist ein symmetrischer Blockcode, der sich mit unterschiedlicher Schlüssellänge von 128, 192 und 256 Bit realisieren lässt. Aus der Schlüssellänge ergibt sich die Zahl der Verarbeitungsschritte für die Ver- und Entschlüsselung der betreffenden Daten. Algorithmen zur Blockchiffrierung arbeiten, wie der Name bereits sagt, mit Datenblöcken. Der AES-Algorithmus hat einen festen Blockumfang von jeweils 16 Bit. Bei einer Verschlüsselung von weniger als 16 Byte sind die ungenutzten Bytes entsprechend aufzufüllen. Da es sich bei AES um einen symmetrischen Code handelt, nutzt man zum Ver- und Entschlüsseln von Informationen dieselben Aktionen sowie denselben Schüssel. Asymmetrische Verschlüsselungsverfahren wie RSA nutzen im Gegensatz zu AES unterschiedliche Schlüssel für beide Operationen.

Jeder der vier Schritte des AES-Algorithmus findet auf einen State (Zustand) Anwendung. Die Kombination der vier AES-Schritte nennt man Runde. Wie viele Runden erforderlich sind, ergibt sich aus der Schlüssellänge. Der AES-State beginnt mit den 16 Bytes, die zu verschlüsseln sind. Jeder weitere Schritt aktualisiert den Zustand. Vor der Verarbeitung des States ist der Eingangs-Bytestring korrekt in den Anfangszustand zu einer 4×4-Matrix zu formatieren (Bild 1). Nach der Umformung der anfänglichen 16 Byte in den Anfangs-State als 4×4-Array lässt sich untersuchen, wie jeder Schritt auf ihren Eingangs-State wirkt.

Bild 1. Initial-State-Umsetzung der 16 Byte in ein 4×4-Array. Xilinx

Der Add-Round-Key ist der einzige Schritt, der den Schlüssel verwendet. Wie bereits erwähnt, hängt die Zahl der Runden im Verschlüsselungsalgorithmus von der Schlüssellänge (128, 192 oder 256 Bit) ab. Der Kodierschlüssel untergeht dabei eine Expansion. Dies stellt sicher, dass seine Bytes vor ihrem Einsatz in jeder Runde nicht mehrmals verwendet werden. Somit ist die expandierte Schlüssellänge (Expanded Key Size) jedes Mal anders. Die erweiterte Schüssellänge ist

 Expanded Key Size (Byte) = 16 * (Rounds + 1)

 Bei der Operation dieses Schrittes erfolgt eine Verknüpfung der Bytes des Eingangs-States per Exclusive-OR mit den 16 Byte des erweiterten Schlüssels. Jede Runde nutzt dabei eine andere Sektion des erweiterten Schlüssels. Runde 0 verwendet die Bytes 0 bis 15, Runde 1 die Bytes 16 bis 31, und so fort. In jeder Runde erfolgt eine Verknüpfung des Byte 1 des State per Exclusive-OR mit dem niedrigsten Byte des expandierten Schlüssels.

Der Schritt Sub-Bytes nutzt eine Byte-Substitution, um die State-Werte mit einem anderen Wert zu tauschen. Die Werte in der Substitutionsbox sind vordefiniert und so ausgelegt, dass sie eine niedrige Korrelation zwischen den Eingangs- und Ausgangsbits aufweisen. Die Substitutionsbox (S-Box) ist eine 16×16-Matrix. Als Index in der Substitutionstabelle erscheinen die oberen und unteren Nibbles des substituierten Bytes . Wenn also in der S-Box-Verschlüsselung nach Bild 2 das erste Anfangs-State-Byte 0 × 69 ist, wird es durch den Substitutionswert 0 × F9 ersetzt. Das obere Nibble des State-Byte bestimmt die Zeile der Substitutionsbox, das untere Nibble die Spalte. In Bild 2 zu beachten ist, dass es getrennte Substitutionsboxen für die Ver- und Entschlüsselung gibt, und dass ihre Inhalte verschieden sind.

Bild 2. Inhalte der AES-Substutionsbox. Xilinx

Der Schritt Shift-Rows dient zur Umordnung der Eingangs-State-Matrix über eine zirkuläre Byte-Verschiebung jeder Zeile. Dabei findet eine Rotation jeder Zeile um einen anderen Faktor nach rechts statt (Bild 3). Zeile 1 bleibt unverändert. Zeile 2 wird um ein Byte, Zeile 3 um zwei Byte und Zeile 4 um drei Byte verschoben. Beim Entschlüsseln werden dieselben Operationen ausgeführt, jedoch mit einer Rotation nach links statt nach rechts.

Bild 3. Operation der Zeilenverschiebung. Xilinx

Mix-Columns ist der komplizierteste Schritt einer Runde. Er erfordert 16 Multiplikationen und zwölf Exclusive-OR-Operationen. Diese Operationen erfolgen Spalte für Spalte an der Eingangs-State-Matrix, die man mit einer festen Matrix multipliziert, um eine neue State-Spalte zu erzeugen (Bild 4). Jede Eingabe in die Spalte multipliziert man mit einer Zeile der Matrix. Die Ergebnisse aller Multiplikationen werden XOR-verknüpft, um den neuen State-Wert zu bilden. In Bild 4 sind die erste zu multiplizierende Spalte und Zeile gelb hervorgehoben.

Bild 4. Mix-Columns-Funktion für die Ver- und Entschlüsselung. Xilinx

Die Mix-Columns-Gleichungen der ersten Spalte lauten wie folgt:

B1’ = (B1 * 2) XOR (B2 * 3) XOR (B3 * 1) XOR (B4 * 1)

B2’ = (B1 * 1) XOR (B2 * 2) XOR (B3 * 3) XOR (B4 * 1)

B3’ = (B1 * 1) XOR (B2 * 1) XOR (B3 * 2) XOR (B4 * 3)

B4’ = (B1 * 3) XOR (B2 * 1) XOR (B3 * 1) XOR (B4 * 2)

Dieser Prozess wiederholt sich mit derselben Multiplikationsmatrix für die nächste Spalte des Eingangs-State, bis alle Spalten des Eingangs-State adressiert worden sind.

Jede AES-Verschlüsselungsrunde umfasst alle vier Schritte in dieser Reihenfolge: Sub-Bytes, Shift-Rows, Mix-Columns (für die Runden 1 bis N – 1) sowie Add-Round-Key (mit expandiertem Schlüssel). Es ist unbedingt sicherzustellen, dass dieser Prozess umkehrbar ist, und sich der nicht lesbare Blocktext in Klartext zurück verwandeln lässt, sodass die verschlüsselte Information nutzbar ist. Dazu dienen die folgenden Schritte: Invert Shift-Rows, Invert Sub-Bytes, Add-Round-Key (mit expandiertem Schlüssel) sowie Invert Mix-Columns (für die Runden 1 bis N – 1). Vor der ersten Verschlüsselungsrunde muss noch eine Anfangs-Add-Round-Key-Operation für die Ver- und Entschlüsselung erfolgen.

Dazu ein Blick auf den Algorithmus, der zur Expansion des Schlüssels zu nutzen ist, damit im Schüssel genügend Bits für die Zahl der auszuführenden Add-Round-Key-Schritte zur Verfügung stehen (Bild 5). Schlüssellängen von 16, 24 oder 32 Byte erfordern dabei entsprechend 44, 52, oder 60 Runden zur Expansion. Die ersten Bytes des expandierten Schlüssels sind dem anfänglichen Schlüssel gleich. Dies bedeutet, dass im hier erläuterten AES256-Beispiel die ersten 32 Byte des expandierten Schlüssels der Schlüssel selbst sind. Die Schlüsselexpansion generiert in jeder Iteration die 32 zusätzlichen Bit für den expandierten Schlüssel.

Bild 5. Algorithmus zur Schlüsselexpansion. Xilinx

Die wichtigsten Schritte der Schlüsselexpansion sind: Rotate-Word – Dieser Schritt ist ähnlich wie Shift-Rows. Er ordnet ein 32-Bit-Wort so um, dass aus dem höchst signifikanten Byte (MSB) das niedrigst signifikante Byte (LSB) wird. Der Schritt Subword verwendet dieselbe Substitutionsbox wie für die Byte-Substitutionen bei der Verschlüsselung, während der Schritt rcon die Zweierpotenz auf einen vom Anwender definierten Wert bildet. Wie bei Mix-Columns erfolgt die Ausführung von rcon im Galois-Körper. Deshalb setzt man hier meist eine vorberechnete Lookup-Tafel ein. EK liefert vier Byte aus dem expandieren Schlüssel, K wie EK, vier Byte.

Wie lässt sich die korrekte Implementierung der Algorithmen zur Verschlüsselung und zur Schlüsselerweiterung verifizieren? Die NIST-Spezifikation (National Institute of Standards and Technology) für AES bietet dazu eine Reihe erprobter Beispiele, die sich zur Überprüfung der eigenen Implementierung gut nutzen lassen.

Code-Erstellung

Um sicherzustellen, dass sich der Verschlüsselungsteil des AES-Code in der programmierbaren Logik (PL) des Zynq-SoC beschleunigen lässt, muss man den Code von Anfang an mit diesem Ziel vor Augen entwickeln. Die erste Betrachtung gilt dabei der Architektur des Algorithmus und seiner angemessenen Segmentierung. AES ist für dieses Vorgehen gut geeignet, denn man kann Funktionen für jeden Schritt schreiben und sie wie erforderlich aufrufen. Außerdem ist für die zu beschleunigende Funktion eine eigene Datei vorzusehen.

Die entsprechende Software-Architektur enthält also folgende Bestandteile: main.c, aes_enc.c, aes_enc.h und sbox.h. Die Datei main.c enthält den Algorithmus zur Schlüssel-Expansion, den Schlüssel selbst und die Klartexteingabe, sowie den Call für die AES-Verschlüsselungsfunktion. Die Datei aes_enc.c führt die Verschlüsselung aus. Jede Stufe codiert man jeweils als eigene Funktion, sodass sie wie gefordert für die AES-Runde aufrufbar ist. Damit diese Auslegung den üblichen Implementierungen auf den Prozessoren entspricht, verwendet man dazu die Lookup-Tabellen der Mixed-Step-Multiplikationen. Die Datei aes_enc.h enthält die Definition der aes_Funktion und die Parameter zur Bestimmung ihrer Größe (zum Beispiel mk, nb und nr). Die Datei sbox.h enthält die Substitutionsbox für die Substitutions-Bytes, die Lookup-Tabelle für die rcon-Funktion zur Schlüsselerweiterung und die Lookup-Tabellen für die Mix-Columns-Multiplikationen. Mit dieser Struktur lässt sich die zu beschleunigende AES-Verschlüsselungsfunktion durch Rechtsklick auf die Funktion und über den Umschalter HW/SW auswählen (Bild 6).

Bild 6. Die zu beschleunigende Funktion. Xilinx

Um die Realisierung der Mindest-Perfomance und der Einsparungen durch die Beschleunigung der Funktion sicherzustellen, muss es möglich sein, die Ausführung der Funktion zeitlich festzulegen. Dazu dient sds_clock_counter in sds_lib.h.

Nach dem Schreiben des Quellcodes ließ sich der AES-Algorithmus in 36.662 Prozessorzyklen in Software auf einem einzigen ARM-Cortex-A9-Prozessorkern im Zynq-SoC ausführen.

Die Beschleunigung optimieren

Die Beschleunigung des AES-Algorithmus ist etwas komplizierter als der Algorithmus zur Matrix-Multiplikation, weil die Hauptschleife des AES-Algorithmus aus voneinander abhängigen Stufen besteht.

In der Praxis lässt sich der AES-Algorithmus beschleunigen, indem man die Schleifen untersucht, um festzustellen, wo man sie zur Optimierung der Speicherbandbreite entrollen kann. Darüber hinaus wählt man an dieser Stelle die korrekte Taktfrequenz für den Datenfluss und die Frequenz der Hardware-Funktionen.

Die Hauptschleife der AES-Verschlüsselungsfunktion umfasst die Funktionen für jeden AES-Schritt. Jede Funktion des AES-Algorithmus muss komplett ausgeführt, und das Ergebnis berechnet sein, bevor die nächste Funktion laufen kann. Diese Abhängigkeit erfordert die volle Konzentration auf die als separate Funktionen erstellten AES-Schritte. Innerhalb dieser Schritte besteht ein reichliches Potenzial zur Optimierung.

Man kann die Schritte Add-Round-Key, Sub-Bytes und Mix-Columns als Pipeline anordnen, um die Leistungsfähigkeit zu steigern. Mit diesen Funktionen führt man den HLS-Pipeline-Befehl durch Einsetzen von Pragmas in die erste Schleife aus. Man sollte auch die innere Schleife entrollen. Einige dieser Funktionen stammen aus Lookup-Tabellen, die man normalerweise als Block-RAM realisiert. Um die Speicherbandbreite zu erhöhen, nutzt dieses Beispiel als Pragma-Parameter „complete“. Dies implementiert die Speicherinhalte als diskrete Register.

Die Fähigkeit zum Datentransfer zwischen dem PS- und dem PL-Teil des Zynq-SoC ist auch für die Steigerung der Performance von Bedeutung. Im ersten Schritt erfolgte die Einstellung des Taktes im Netzwerk für den Datenfluss auf den höchsten möglichen Wert: 200 MHz. Als nächstes erfolgte die Sicherstellung des direkten Speicherzugriffs beim Datentransfer zwischen PS und PL. Dies erforderte ein Umschreiben der Schnittstelle und die Nutzung der Funktion sds_alloc, damit die Daten zusammenhängend im Speicher stehen, wie es der DMA-Transfer fordert (Bild 7).

Bild 7. Netzwerk für den Datenfluss zwischen Prozessorsystem (PS) und programmierbarer Logik (PL). Xilinx

Als dritter und letzter Optimierungsschritt erfolgte die Einstellung der Taktrate für die Hardware-Funktion auf die höchste der von dieser Applikation unterstützten Frequenz: 166,67 MHz.

Ergebnisse mit den unterstützten Betriebssystemen

Nach dem Aufbau der Beispielschaltung lief der PL-beschleunigte AES-Code unter Linux in 16.544 Prozessor-Taktzyklen. Dies entspricht 45 % (16.544/36.662) der Zyklenzahl beim Betrieb des AES-Code nur in Software, was eine massive Reduktion von 55 % in der Ausführungszeit für einen recht komplexen und interdependenten Algorithmus bedeutet.

Für die Entwickungsumgebung SDSoC kann man auch die Betriebssysteme Baremetal oder Free-RTOS nutzen. Die Erstellung von Baremetal- und Free-RTOS-Projekten mit Code-Reuse erlaubt einen guten Vergleich der Performance aller drei unterstützten Betriebssysteme. Für ein bestimmtes Projekt hängt die Wahl des Betriebssystems von der Art der Applikation, der geforderten Leistungsfähigkeit und dem Zeitbudget der Entwicklung ab.

Bild 8 verdeutlicht die Performance der drei genannten Betriebssysteme mit dem Zynq-SoC. Dabei ist es nicht überraschend, dass sich mit Free-RTOS und Baremetal ähnliche Reduktionen ergeben, denn beide ermöglichen viel einfachere Implementierungen als Linux.

Bild 8. Leistungsfähigkeit von Free-RTOS und Baremetal für den Baustein aus der Familie Zynq (PS und PL) mit ähnlichen Reduktionsergebnissen. Xilinx

Wie die Ergebnisse belegen, bringt der Einsatz der Entwickungsumgebung SDSoC zur Beschleunigung der AES-Verschlüsselung eine reale Verbesserung der Performance bei einfacher Realisierung – auch ohne besondere Vorkenntnisse beim FPGA-Design.

(hb/ah)