Cryptography Engineering, Teil 5: AES-Implementierung für mobile Endgeräte

Inhaltsverzeichnis

Die AES-Implementierungen der vorigen Teile waren für große Serversysteme und für kleine Microcontroller ausgelegt. Beiden war gemeinsam, dass sie mit C++ und C noch nah an der Hardware operierten. Die Standardsprache für mobile Endgeräte unter Android ist hingegen Java. Bei dieser hardwarefernen Programmiersprache warten neue Herausforderungen im Cryptography Engineering.

Das Funktionsprinzip des Advanced Encryption Standard (AES) ist seit dem ersten Beitrag dieser Reihe bekannt. Die praktischen Implementierungen in C++ für Server- und PC-Systeme sowie in C für den Mikrocontroller ATmega von AVR verdeutlichten das Funktionsprinzip in der Praxis. Beide Systeme hatten mit C/C++ den Vorteil, dass sich die AES-Operationen gezielt und effizient hardwarenah umsetzen ließen. Neue Herausforderungen bringt nun die Implementierung für die nächste Plattform – Android – mit sich.

Mehr Infos

Cryptography Engineering – die Artikelserie

• Teil 1: Zur Theorie des AES
• Teil 2: AES-Implementierung für PC- und Serversysteme
• Teil 3: AES-Implementierung für 8-Bit-Microcontroller
• Teil 4: AES-Implementierung auf Atmel AVR ATmega
• Teil 5: AES-Implementierung für mobile Endgeräte (Android)

Problempunkt Java

Smartphones und Tablets unter Android setzen auf die Programmiersprache Java und die damit einhergehende virtuelle Maschine. Das Problem für das Cryptography Engineering und die effiziente Programmierung kryptographischer Algorithmen gliedert sich an der Stelle in zwei Teile.

Einerseits gibt es keine physische Prozessorarchitektur, für die sich eine Implementierung optimieren ließe. An ihre Stelle tritt eine virtuelle Maschine, also eine virtuelle Prozessorarchitektur. Diese ist infolge der Emulation im Laufzeitverhalten relativ unscharf. Beispielsweise müssen Registerbreiten des virtuellen nicht zwingend mit denen des physischen Prozessors übereinstimmen. Wie lange dauert beispielsweise eine spezifische 32-Bit-Integer-Operation? Wie viele Taktzyklen benötigt sie? Das ist für die breite Palette virtueller Maschinen nicht ohne weiteres beantwortbar. Selbst wenn im Falle von Android nur die Dalvik Virtual Machine als Java Virtual Machine (JVM) zum Einsatz kommt, ist die physische Prozessorarchitektur, auf der Dalvik operiert, doch wieder recht variabel (ARM, x86/AMD64).

Andererseits ist Java keine systemnahe Programmiersprache. In Java sind vorzeichenlose Datentypen (unsigned) ebenso unbekannt wie der (einfache) Zugriff auf einzelne Bytes eines Integer-Werts analog zum Datentyp union bei C/C++. Aufwendige Typumwandlungen und Operationen stehen hier ins Haus, um eine ähnliche Implementierung analog dem Ansatz der C++-Variante aus dem zweiten Teil zu erreichen.

Eine Variante wäre das Wiederverwenden der C++-Implementierung. Mit dem Native Development Kit (NDK) ermöglicht es Google für Android, auch Programmteile in C und C++ zu programmieren und in nativen Code zu übersetzen. Die so entstehenden Bibliotheken (shared objects) lassen sich dann in die Java-Anwendungen einbinden. Auf die Weise ließe sich effizienter Code für die jeweilige physische Prozessorarchitektur erarbeiten. Die Java-Anwendung bräuchte die native Bibliothek nur noch zu nutzen.

Das Ganze hat aber seine Nachteile. Für jede Prozessorarchitektur wäre eine eigene Bibliothek zu erstellen und mit der Anwendung auszuliefern. Derzeit wären das mindestens zwei: eine für ARM und eine für x86/AMD64. Kommen weitere Architekturen hinzu, wären weitere fällig. Der Entwicklungs- und Testaufwand würde durch die nativen Bibliotheken und jede neue Prozessorarchitektur ansteigen – infolge Auf- und Abwärtskompatibilität. Was technisch verführerisch ist, wäre wirtschaftlich nicht unbedingt die beste Alternative.

Die Leistung der Prozessoren in modernen Smartphones und Tablets ist inzwischen hoch. Sie übertrifft zumeist die Leistung der Systeme, die sich noch vor zwölf Jahren auf den Schreibtischen fanden, als AES verabschiedet wurde. Selbst wenn man noch die JVM ins Kalkül mit einbezieht, sollte auf einem Smartphone oder Tablet AES effizient auch in Java implementierbar sein. Die NDK-Variante spart dieser Beitrag daher aus.

Jedoch ist eines im Hinterkopf zu behalten. Für andere kryptographische Verfahren sieht die Situation womöglich nicht so positiv aus. Beispielsweise sind im Fall der Kryptographie über elliptischen Kurven (Elliptic Curve Cryptography, ECC) rechenintensive Operationen notwendig. Hier mag eine Implementierung über nativen Code auf mobilen Endgeräten durchaus sinnvoll sein.

Skizze einer Java-Implementierung

Die Entscheidung "pro Java" heißt nun jedoch, Antworten auf die folgenden Herausforderung zu finden. Das Datentypsystem von Java hält einige "Schmankerl" bereit. Mit den primitiven Datentypen byte und int mit einer Breite von 8 beziehungsweise 32 Bit stehen grundsätzlich die in einer AES-Implementierung erforderlichen Datenbreiten zur Verfügung. Die Herausforderung ist an der Stelle jedoch, dass die Datentypen grundsätzlich vorzeichenbehaftet sind. Vorzeichenlose Datentypen wie uint8_t und uint32_t, wie sie der Header cstdint von C++ liefert, kennt Java per se nicht.

Das mag zunächst wie ein marginales Problem erscheinen, hat jedoch – gerade im Hinblick auf die Implementierung kryptographischer Algorithmen – einen wesentlichen Einfluss. Das Vorzeichen ist zunächst eine reine Interpretation von Java. Das Speichern des Werts als eine Folge von Bits im Hauptspeicher bleibt davon unberührt. Im Speicher liegt beispielsweise das Byte 0xFF. Erst durch die Interpretation durch Java wird daraus -1.

Die bitweisen Operationen wie XOR, AND und OR bleiben davon unberührt. Sie kümmert das Vorzeichen selbst in Java nicht. Ein wenig differenzierter sind hingegen die Schiebeoperatoren zu sehen. Ein Left-Shift mit << ist in jedem Fall unproblematisch. Sein Ergebnis ist arithmetisch und logisch identisch. Alle Bitwerte wandern eine Position nach oben. Das höchstwertige Bit fällt heraus. In das niederwertigste Bit wandert eine Null. Für einen Shift um mehr als eine Bit-Position erfolgt der Vorgang mehrfach.

Beim Right-Shift ist das ein wenig problematischer. Hier ist klar zwischen einer arithmetischen und einer logischen Operation zu unterscheiden. Für die mittleren und das niederwertigste Bit sind die Operationen noch identisch. Alle Bitwerte wandern hier eine Position nach unten. Das niederwertigste Bit fällt heraus. Der Unterschied offenbart sich im höchstwertigen Bit. Der arithmetische Right-Shift erhält an der Stelle das Vorzeichen; der logische nicht. Der arithmetische Right-Shift kopiert den Wert des ursprünglich höchstwertigen Bit in das neue höchstwertige Bit. Die Bitfolge 10000000 – interpretiert als vorzeichenbehaftetes Byte – um eine Position arithmetisch nach rechts geschoben ergibt somit 11000000.

Diese Art des Schiebens wäre beispielsweise ungeeignet zum Implementieren des Algorithmus für die Multiplikation in GF(2^8), wie ihn Abbildung 1 nochmals zeigt. Die Operation q = q >> 1 ließe sich hiermit nicht implementieren.

Zum Glück kennt auch Java den logischen Right-Shift, bei dem in das höchstwertige Bit beim Schieben der Wert null wandert. Beim logischen Right-Shift der Bitfolge 10000000 um eine Bit-Position ergibt sich somit das gewünschte Ergebnis 01000000.

Java unterscheidet daher explizit zwischen dem arithmetischen und dem logischen Right-Shift. Das Unterscheiden erfolgt über den Operator >> für arithmetisch und >>> für logisch. Damit lässt sich der Algorithmus aus Abbildung 1 in der Methode gmul() der AES-Implementierung des Beispielcodes wie folgt in Java umsetzen:

// Multiplication in GF(256)
private byte gmul(byte p, byte q) {
    byte r = 0;
    for (int i = 0; i < 8; i++) {
        if ((q & (byte) 0x01) != 0)
            r ^= p;
        if ((p & (byte) 0x80) != 0) {
            p <<= 1;
                p ^= 0x1b;
        } else
            p <<= 1;
        q >>>= 1;
    }
    return r;
}

Ein weitere Herausforderung stellt sich bei der Semantik von Java. Ganzzahlkonstanten sind grundsätzlich vom Typ Integer. Sie haben damit eine Länge von 32 Bit und sind naturgemäß vorzeichenbehaftet. Wer beispielsweise versucht, einer Variable vom Typ byte den Wert 0xFF zuzuweisen, scheitert bereits beim Kompilieren. Obwohl die Konstante 0xFF bereits suggeriert, ein 8-Bit-Wert zu sein, sehen das Syntax und Semantik von Java anders. Die erfordern eine explizite Typumwandlung mit (byte). Wer nun die Byte-Werte der S-Boxen von AES im Hinterkopf hat, ahnt bereits, welche Typumwandlungsorgie das nach sich ziehen wird.