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

Verschlüsselung hat sich unbestritten einen festen Platz in der IT erobert. Nicht mehr nur leistungsstarken Rechenboliden in Rechenzentren und PC-Systemen ist sie vorbehalten, auch in der Welt der Winzlinge nimmt die Bedeutung von Kryptografie zu. Embedded-Systeme mit Mikrocontrollern sind ebenfalls eine Zielplattform für moderne Kryptografie.

Die Implementierung von Kryptografie auf leistungsstarken Systemen bereitet kaum mehr Probleme. Wie der zweite Beitrag der Artikelreihe zeigt, ist die Implementierung ohne kompliziertere mathematische Kunstgriffe auf 32-Bit-Systemen machbar. Bei eingebetteten Systemen ist die Ausgangslage wesentlich ungünstiger. Doch werden die begrenzten Ressourcen der kleinen Systeme gebührend beachtet, lässt sich der Advanced Encryption Standard (AES) auch auf 8-Bit-Mikrocontrollern implementieren. Atmels AVR ATmega ist ein geeignetes Demonstrationsobjekt für einen weiteren Ausflug in die Welt des Cryptography Engineering. Zumal sich die Umgebung ohne echte AVR-Hardware komplett auf Windows simulieren lässt.

Kryptografische Algorithmen wie AES sind zwar für die Implementierung in Hardware geeignet, um einen in Hardware "gegossenen" AES nutzen zu können, muss jedoch die entsprechende Hardware vorhanden sein. Das ist aber nur bei speziellen Mikrocontrollern der Fall, wie im Online-Banking oder Zahlungsverkehr eingesetzten Chipkarten (Smartcard, Integrated Circuit Card, kurz ICC). Einfache oder Allzweck-Mikrocontroller verfügen über derartige Kryptohardware nicht. Hier bleibt nur eine Implementierung in Software, die bei den erheblich eingeschränkten Ressourcen eines einfachen Mikrocontrollers eine Herausforderung darstellt.

Die Prozessorarchitektur mit dem schmalen 8-Bit-Integer-Rechenwerk ist dabei kein zentrales Problem. Die Operationen über den 128 Bit großen Blöcken (State-Matrix) in AES lassen sich leicht auf einzelne Bytes herunterbrechen. Zugegeben, eine 32- oder 64-Bit-Architektur kann die meisten Operationen parallel in weniger Takten abarbeiten. Ein 8-Bit-Rechenwerk benötigt hier mehrere Durchläufe, also auch mehr Taktzyklen. Zudem beschleunigen auf größeren Mikroprozessoren zusätzlich Barrel-Shifter Schiebe- und Rotationsoperationen. Für derartigen "Luxus" gibt es auf dem Chip des AVR-Zwergs keinen Platz. Der eigentliche Algorithmus aus der Ankündigung des AES-Standards (PDF) lässt sich aber auch auf einem 8-Bit-AVR problemlos implementieren. Die Hardware des ATmega mit schnellen Taktraten von bis zu 20 MHz ist für AES völlig geeignet. Die Herausforderungen liegen an anderer Stelle.

Naturgemäß sind die S-Boxen von AES, die für jedes Byte einen Ersetzungseintrag vorhalten, entsprechend ausladend. Für die Ver- und die Entschlüsselung ist jeweils eine eigene 256 Byte große Tabelle vorzuhalten. Insgesamt also 512 Bytes, die die begrenzten Ressourcen eines kleinen Mikrocontrollers erheblich belasten. Bei Mittelklasse-ATmegas wie dem ATmega88 belegen die S-Boxen entweder das gesamte EEPROM (Electrically Erasable Programmable Read-Only Memory) oder die Hälfte des RAM. Eine Alternative wären ein Ablegen im Programmspeicher, also im Flash, und der Zugriff über die speziellen pgmspace-Routinen der AVR libc – das allerdings unter der Voraussetzung, dass der Programmspeicher noch über genügend freien Speicher verfügt. Für eigene Rechenübungen gibt eine Atmel-Webseite einen Überblick über die Größen von RAM, EEPROM und Flash der einzelnen ATmega-Modelle.

Zusätzlich sind aus dem eigentlichen AES-Schlüssel, wie der erste Teil dieser Artikelreihe zeigte, für die einzelnen Runden separate Schlüssel zu erzeugen. Diese Schlüsselexpansion resultiert in einem Array von Rundenschlüsseln, das bei AES128 schon 176 Bytes, bei AES192 208 Bytes und bei AES256 stattliche 240 Bytes umfasst. Zumindest für die kleineren bis mittleren ATmega-Modelle ist das wiederum eine hohe Belastung der geringen Speicherressourcen. Ein Ablegen im Flash (PGMSPACE) scheidet hier zudem von vornherein aus. Es ist unklug, einen individuellen kryptografischen Schlüssel, der ein System identifiziert, in den Flash zu legen. Der Flash-Inhalt eines jeden einzelnen Systems wäre individuell zu erzeugen und zu programmieren. Ist später ein (kompromittierter) Schlüssel auszutauschen, wäre wieder der Flash neu zu programmieren.

Der "verschwenderische" Umgang mit dem Speicher wie bei Server- und PC-Systemen scheidet beim Mikrocontroller folglich aus. Die Hardware weist die bewährten Algorithmen aus den beiden vergangenen Artikeln in ihre Schranken. Obgleich der Algorithmus AES unverändert bleibt, heißt es, für die spezielle Hardwareplattform des ATmega-Mikrocontrollers neue Antworten zu finden.