Cryptography Engineering, Teil 2: AES auf PCs und Servern
Die theoretischen Grundlagen zu AES sind bekannt und lassen sich nun in einer ersten praktischen Implementierung anwenden. Dabei soll auch die Zielplattform berücksichtigt werden, denn es gilt, AES in C++ umzusetzen und zu zeigen, wie man eine mathematische Theorie in eine effiziente Computeranwendung wandelt.
- Oliver Müller
Die theoretischen Grundlagen zu AES sind bekannt und lassen sich nun in einer ersten praktischen Implementierung anwenden. Dabei soll auch die Zielplattform berücksichtigt werden, denn es gilt, AES in C++ umzusetzen und zu zeigen, wie man eine mathematische Theorie in eine effiziente Computeranwendung wandelt.
Cryptography Engineering setzt theoretische Vorarbeiten voraus, wohingegen in anderen Anwendungsdomänen durchaus in Trial-und-Error-Manier "drauflos" programmiert werden kann (aber auch nicht sollte). Bei kryptographischen Systemen ist das schlicht unmöglich. Man muss kein mathematisches Genie oder der ultimative Code-Brecher unter den Kryptanalytikern sein, um kryptographische Algorithmen zu implementieren. Die mathematischen Grundlagen und das Algorithmieren gilt es jedoch zu beherrschen und die Zielplattform im Auge zu behalten. Aber das macht das Cryptography Engineering schließlich so spannend. Nach all der theoretischen Vorarbeit im ersten Teil dieser Artikelreihe soll AES nun praktisch in C++ implementiert werden.
Cryptography Engineering
Die Artikel zur Reihe:
- Zur Theorie des AES
- AES-Implementierung für PC- und Serversysteme
- AES-Implementierung für 8-Bit-Microcontroller
- AES-Implementierung auf AVR ATmega
- AES-Implementierung für mobile Endgeräte (Android)
Die AES-Funktionen SubBytes(), InvSubBytes(), ShiftRows(), InvShiftRows(), MixColumns() und InvMixColums() operieren alle über der state-Matrix. Es fällt jedoch auf, dass diese Funktionen state wechselnd mit unterschiedlichen Datenbreiten ansprechen. Mal als Byte-Array, mal als Words. Zudem gehen Klartext und Chiffretext in das AES-System als Byte-Stream ein. Das System interpretiert diese Daten je nach Kontext jedoch auch als 32-Bit-Words. Bei der nicht näher bestimmten Zielplattform "32-Bit-Server- und -PC-Systeme" ruft das sofort das alte Problem von Big und Little Endian auf den Plan. Diesem muss eine AES-Implementierung begegnen.
Eine Möglichkeit wäre es, die Implementierung auf Operationen über Bytes herunterzubrechen. Das hätte jedoch den Nachteil, dass der generierte Code aus den 32-Bit-Integer-Rechenwerken der CPUs der Zielplattformen keinen Nutzen ziehen kann. Er würde schlicht Taktzyklen verschwenden. Schließlich wären im Extremfall für Operationen, beispielsweise Shifts, vier einzelne Byte-Operationen statt einer 32-Bit-Word-Operation notwendig.
Quellcode
Hinweis: Die Sourcen zu diesem Artikel finden Sie im Tarball auf dem heise Developer FTP zum Download.
Besser ist es, die Reihenfolge der Bytes in einem Word, abhängig von der Endianness des Systems, zu berücksichtigen. Das klingt zunächst nach viel if-else-Blöcken oder umständlichem Umordnen und viel Shifting und Masking zum Zugriff auf die einzelnen Bytes. Da die Beispielimplementierung für diesen Artikel jedoch in C++ erfolgt, lässt sich eine spracheigene komfortable Lösung nutzen. C++ bietet mit dem Datentyp union die Möglichkeit, Daten dem Kontext entsprechend anzusprechen. Ein 32-Bit-Word und seine einzelnen Teilbytes lassen sich elegant wie folgt darstellen (vergleiche Klasse AesEncryption in aes.h):
union word32_t
{
uint32_t w;
struct
{
#ifdef ARCH_BIG_ENDIAN
uint8_t b3;
uint8_t b2;
uint8_t b1;
uint8_t b0;
#else
uint8_t b0;
uint8_t b1;
uint8_t b2;
uint8_t b3;
#endif
};
};
Über die Elementvariable w lässt sich der Wert als 32-Bit-Word auslesen. Über b0 bis b3 lassen sich die einzelnen Bytes ansprechen. Das Präprozessor-Makro ARCH_BIG_ENDIAN bestimmt die Reihenfolge der Bytes – Big oder Little Endian. (Dieses Makro setzt im Übrigen der configure-Prozess unter Unix/Linux. Die Build-Skripte unter Windows, OpenVMS und OS/2 beziehungsweise eComStation setzen das Makro nicht, da sie grundsätzlich Little Endian verwenden.)
Nach dem selben Prinzip deklariert aes.h auch den Datentyp AesEncryption::state_t als union. Damit bildet der Beispielcode den 128-Bit-Block und die State-Matrix ab; letztere dem unteren, in Abbildung 1 gezeigten Teil folgend. Zusätzlich zu den Word-Werten und den geordneten Byte-Werten von b0 bis b15 unterstützt state_t noch das Byte-Array b, um Byte-basierte Operationen in Schleifen zu vereinfachen, bei denen die Reihenfolge der Bytes keine Rolle spielt (siehe AesEncryption::subBytes()).
Wichtig ist, dass die Elementvariablen einer union keinen zusätzlichen Speicher benötigen. Sie repräsentieren lediglich verschiedene Sichtweisen auf ein- und dieselben Daten.
Das Ganze hat auch einen Nachteil. Statt die eingehenden Klartext- oder Chiffredaten direkt zu verwenden, sind die Daten geordnet in state zu kopieren. "Geordnet" heißt, einzelne Operationen zu erzeugen: state.b0 = data[0], state.b1 = date[1] und so weiter. Eine Schleife lässt sich zum Kopieren nicht nutzen. Zudem sind 16 Einzeloperationen notwendig und das kostet Programmspeicher. Immerhin lassen sich diese 16 Einzeloperationen aber auch als entrollte Schleife auffassen, die in der Regel sogar schneller ist.
