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

Problem Schlüsselexpansion

Das zweite Problem ist die Schlüsselexpansion. Wie angesprochen kann der für die Runden expandierte Schlüssel zwischen 176 und 240 Bytes belegen. Die einzige Möglichkeit, das Belegen dieses Speichervolumens zu vermeiden, ist die Expansion des Schlüssels "on the fly" während der Ver- beziehungsweise Entschlüsselung. Statt die Rundenschlüssel in einem Array vorzuhalten, würde während der jeweiligen Runde der passende Schlüssel berechnet. Somit bräuchte man lediglich nur noch einen Speicherbereich von 16 (AES128), 24 (AES192) beziehungsweise 32 Bytes (AES256), der den jeweiligen Rundenschlüssel aufnimmt. Das Problem hierbei ist jedoch der Geschwindigkeitsverlust. Wo der Zeitaufwand bei der Expansion in ein Array nur einmal auftritt, tritt er bei der "On the fly"-Variante pro Block jeweils erneut auf. Gerade bei längeren – und daher aus mehreren Blöcken bestehenden – Nachrichten schlägt das negativ zu Buche. Bei niedrig getakteten Systemen oder Mikrocontrollern mit aktiviertem Prescaler führt das zu merklichen Verzögerungen bei Ver- und Entschlüsselung.

Die andere Variante ist, den expandierten Schlüssel in einen Festwertspeicher wie in das interne oder ein externes EEPROM auszulagern. Pro Runde ist dann der jeweilige Rundenschlüssel aus dem EEPROM in den Speicherbereich von 16 bis 32 Bytes im RAM zu laden. Das kann je nach EEPROM ebenfalls einiges an Taktzyklen kosten. In jedem Fall ist darauf zu warten, dass das EEPROM zum Lesen bereit ist (siehe Funktion eeprom_busy_wait() der AVR libc). Bei einem externen EEPROM kommt noch der zeitliche Aufwand für das Ansteuern und Synchronisieren eines externen Bus, wie I2C beziehungsweise TWI, hinzu.

Wer all das nicht will, sondern höchste Performance wünscht, kommt nicht umhin, die 176 bis 240 Bytes RAM für den expandierten Schlüssel zu opfern. Die Expansion des Schlüssels kann bei Systemstart erfolgen, oder der expandierte Schlüssel lässt sich auch komplett in einem Festwertspeicher halten und initial beim Booten beladen. In der Regel bietet sich jedoch die Expansion bei Systemstart an, da man hierdurch den nicht minder kostbaren Festwertspeicher entlasten kann. Die Schlüsselexpansion verlängert zwar die Boot-Phase des Systems, liegt aber in der Regel noch im vertretbaren Rahmen. Die Beispielimplementierung setzt daher auf diesen Ansatz. Diese Implementierung in C ist Thema des nächsten Teils. Die Simulation des AVR-Systems auf dem PC sowie eine Anregung zur Implementierung auf echter Hardware werden dort ebenfalls beleuchtet werden. (ane)

Oliver Müller
ist freiberuflicher IT-Berater und -Trainer mit den Schwerpunkten Software Engineering, Kryptografie, Java EE, Linux, Unix, z/OS und OpenVMS.

  1. National Institute of Standards (Hrsg.); Announcing the Advanced Encryption Standard (AES); Federal Information Processing Standards Publication 197: November 26, 2001
  2. Alfred J. Menezes, Paul van Oorschot, Scott Vanstone; Handbook of Applied Cryptography; CRC Press 1997
  3. Darrel Hankerson, Alfred J. Menezes, Scott Vanstone; Guide to Elliptic Curve Cryptography; Springer 2004
  4. Florian Schäffer; AVR: Hardware und C-Programmierung in der Praxis; Elektor 2. Aufl. 2008