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.

Byte-Reihenfolge

Byte-Reihenfolge und einzelne Bytes

Java wartet in seinem Werkzeugkasten mit Klassen auf, die einem auf den ersten Blick vom Problem der Byte-Reihenfolge befreien. Zudem erleichtern sie den Zugriff auf Teil-Bytes eines 32- oder 64-Bit-Words. Die Rede ist von der Klasse ByteBuffer. Sie kapselt ein übergebenes byte[]-Array und gestattet mit den Methoden getInteger() und setInteger() den Zugriff auf 32-Bit-Integers. Die einzelnen Bytes lassen sich mit get() und set() erreichen. Grundsätzlich kann die Klasse ByteBuffer das Fehlen des von C++ bekannten Datentyps union kompensieren.

Der Fallstrick lauert jedoch in der Performance. Instanzen von ByteBuffer sind Objekte und keine Basistypen mehr. Eine mit ByteBuffer realisierte AES-Implementierung war in Tests des Autors gegenüber einer äquivalenten, reinen Byte-Implementierung auf der Basis von byte[]-Arrays auf Androids Dalvik um bis zu 11 Prozent langsamer. ByteBuffer beziehungsweise byte[] kamen bei den jeweiligen Implementierungen jeweils für den expandierten Schlüssel und die State Arrays zum Einsatz. Die Performance-Messungen erfolgten im Emulator mit Android 2.3.x, einem HTC Desire HD mit Android 2.3.5 und einem Acer Iconia Tab A510 mit Android 4.0.3.

Grundsätzlich gilt daher: Bei der Implementierung kryptographischer Algorithmen sind Basistypen Objekten vorzuziehen. Die häufigen Operationen über den mathematischen Körpern ziehen in der Implementierung auf Computern schlicht häufige Speicherzugriffe nach sich. Arrays mit Basistypen sind für derartige Speicherzugriffe einfach effizienter als der "Umweg" über Objektmethoden. Die Beispielimplementierung des Artikels wählt daher auf Android ähnlich wie auf AVR einen Byte-Ansatz – wie im Übrigen die meisten Java-Implementierungen von AES. In puncto Byte-Reihenfolge setzt die Implementierung auf Big Endian. Eine Entscheidung, die beispielsweise auch für Standardklassen von Java wie ByteBuffer gilt, wenn nicht explizit etwas anderes festgesetzt wird.

Fehlende Subarrays

byte[]-Arrays unter Java haben allerdings einen eklatanten Nachteil gegenüber denen von C++. Durch das Fehlen von Zeigern ist Java nicht in der Lage, Teil-Arrays an eine Methode zu übergeben. Das ruft sofort die nächste Herausforderung auf den Plan. Die Eingaben für Ver- und Entschlüsselung bei AES gehen bekanntlich in Blöcken à 128 Bits in das System ein. Eine Nachricht ist daher – sofern sie länger als ein 128-Bit-Block ist – in Blöcke zu zerlegen. In C und C++ lässt sich die Aufgabe einfach dadurch lösen, dass die Teil-Arrays schlicht als Zeiger übergeben werden: &state[0], &state[16], &state[32] und so weiter. In Java funktioniert das aufgrund der fehlenden Zeiger nicht.

Leider kennt Java keinen Mechanismus, um aus einem Array ein Subarray zu referenzieren. Es gäbe zwar als Ansatz, ein byte[]-Array als Referenz in einer Liste zu kapseln. In Code gebannt würde das so aussehen:

byte[] array = new byte[some-size];
...
ArrayList<byte> arrayList = new ArrayList<byte>(Arrays.asList(myarray));

Die Liste operiert dann auf dem array. Es kommt also nicht zu einer Kopie. Außerdem existiert die vielversprechende Methode subList(). Über sie lassen sich Sublisten referenzieren. Auch hier kommt es nicht zum Kopieren von Daten. Ein einfaches Ansprechen des Arrays ist ohne Methoden dann allerdings nicht mehr möglich. Die Methode toArray() ist Tabu. Sie würde schlicht eine Kopie der Listenelemente in ein natives Array bannen. Wer den Ansatz wählt, kann gleich auf die Methode System.arraycopy() setzen. Das Bannen in ein Objekt der Klasse ArrayList<byte> würde nur unnötigen Overhead bringen.

Die Sache klingt soweit gut. Sie hat allerdings einen Haken, der sich als ausgewachsener Showstopper erweist. Java ist nicht in der Lage, als Typ T einer generischen Klasse wie ArrayList<T> einen Basistypen zu nutzen. Der Typ T muss in jedem Fall eine Klasse sein. byte wäre somit ungültig, was den obigen Code an der semantischen Prüfung des Java-Compilers scheitern ließe.

Damit bliebe nur die Klasse Byte statt byte übrig. Das ruft jedoch das nächste Problem auf den Plan: die Konvertierung eines Arrays vom Basistyp byte in ein korrespondierendes Array mit Objekten der Klasse Byte. Eine einfache Typumwandlung reicht leider nicht. Jede Konvertierung, die doch wieder in einer Schleife endet, ist kontraproduktiv. Hier ist System.arraycopy() über einem byte[]-Array wieder die einfachere und vermutlich schnellere Wahl. Man bedenke, dass Klartexte wohl als String in das System eingehen. Die Methode getBytes() der String-Objekte liefert jedoch ein byte[]-Array zurück.

Den einfachen arraycopy()-Ansatz wählt im Beispielcode die Implementierung in der Klasse AesEncryptionReference im Package org.cogito_ergo_sum.aes. Sie implementiert AES im Wesentlichen eins zu eins nach dem Vorbild der Implementierungen in C++ und C aus den vergangenen Teilen der Artikelreihe. Wie aber das wiederholte Kopieren von Arrays der Größe 16 Bytes zeigt, kann das nicht effizient sein.

Der andere Ansatz ist das "Mittragen" eines Offsets. Das Array bleibt immer das gleiche. Die jeweilige Methode, wie shiftRows() oder mixColumns(), erhält jedoch einen Offset, der das erste zu betrachtende Element im Array angibt. Mit dem "Trick" operieren einige Methoden in der Java-Welt. So nutzt die Implementierung in der Klasse AesEncryption, ebenfalls im Package org.cogito_ergo_sum.aes beheimatet, den Ansatz. Jede Methode ist um den Parameter int offset erweitert. Alternativ ließe sich das Offset in ein Objektattribut fassen. Das würde den Stack ein wenig entlasten, hätte jedoch Auswirkungen, sofern eine Instanz von AesEncrpytion in mehreren Threads parallel genutzt werden soll. Nachteil des Ansatzes liegt klar auf der Hand: Wo sich in AesEncryptionReference noch fixe Indizes im Array state fanden, sind in AesEncryption Rechenoperationen notwendig (vergleiche beispielsweise die Methode shiftRows()).

Unter Gesichtspunkten der Effizienz betrachtet sind beide Implementierungen aus der Not heraus geboren und haben beide ihre Nachteile. Im realen Laufzeitverhalten in Dalvik und der dort an den Tag gelegten Geschwindigkeit liegen sie recht nah beisammen. In den ausgeführten Tracing-Läufen hatte geringfügig die Implementierung mit Offsets, AesEncryption, die Nase vor.

Wie die exemplarische Diskussion rund um ByteBuffer und ArrayList zeigt, genügt es im Cryptography Engineering nicht, einfach vorhandene Klassen blind zu nutzen. Kapselung und Information Hiding sind sinnvolle Mittel, Komplexität beherrschen zu können. Im Fall effizienter Implementierungen von Kryptoalgorithmen lohnt sich ein genaues Studium der Dokumentation von Klassenbibliotheken und – soweit möglich – ein Blick in den Quelltext der verwendeten Bibliotheken.

Beispiel & Fazit

Beispiel: AESDroid

Die Beispiel-App AESDroid ist einfach aufgebaut und liegt im Eclipse-Projekt aesdroid bereit. Die App offeriert ein Eingabefeld, in dem sowohl der zu verschlüsselnde als auch der verschlüsselte Text Aufnahme finden. Neben Schaltflächen für "Über AESDroid", Verschlüsseln und Entschlüsseln bietet "Erzeuge Schlüssel" die Möglichkeit, einen AES-Schlüssel zu erzeugen. Die Schaltfläche erzeugt über einen einzugebenden String einen SHA-256-Hash. Der 256-Bit-Wert dient anschließend als AES-Schlüssel. Sobald ein Schlüssel erzeugt ist, sind die Schaltflächen zur Ver- und Entschlüsselung aktiv.

Zum Hin- und Herschalten zwischen den Implementierungen in AesEncryption und AesEncryptionReference dient die Checkbox "Verwende Referenzimplementierung". Das Programm nutzt das Interface AesInterface, das beide AES-Klassen erfüllen, um beide Implementierungen identisch ansprechen zu können.

Eine Besonderheit gilt noch für die Verschlüsselung: Sie erzeugt keinen direkten String im Eingabefeld. Vielmehr konvertiert die App das Kryptogramm in eine hexadezimale Zeichenkette und legt diese in das Eingabefeld (siehe Abb. 2). Entsprechend erwartet die Entschlüsselung einen hexadezimalen String im Eingabefeld.

Um die Implementierung zu verifizieren, liefert das Eclipse-Projekt aesdroid-test Android-JUnit-Tests. Neben einigen Tests der Einzelmethoden der AES-Implementierung führt es für beide Klassen AesEncryption und AesEncrpytionReference die bekannten AES Known Answer Tests (KAT) aus. Die Implementierung der Tests beschränkt sich rein auf den Electronic Code Book Mode (ECB), da er als Einziger in AESDroid genutzt wird.

Auch bei den KATs wartet Java mit einer kleinen Hürde auf. Wie anhand der Quelltexte der JUnit-Tests AesAtomicMethodTest und AesReferenceAtomicMethodTest zu sehen ist, implementieren diese die einzelnen KATs in separaten Methoden. Die Implementierung in C++ ließ an der Stelle noch ein großes Array als Steuertabelle für die KATs zu, was einen wesentlich einfacheren Ablauf innerhalb der CppUnit-Tests gestattete. Java wartet an der Stelle jedoch mit einer Besonderheit auf. Sowohl Methoden als auch Objekt- und Klassenattribute dürfen 64 KByte nicht überschreiten. Daher ist es in Java notwendig, die Tests in separate Methoden zu legen. Die KATs überschreiten sonst die magische 64-K-Grenze.

Problem Key-Management

Moderne Smartphones sind extrem leistungsfähig. Es sind vollwertige Computer, die auch Telefonieren können. Die meisten Vertreter dieser Kleincomputer – darunter auch die Android-Systeme – haben einen Nachteil. Sie sind nicht für höchste Sicherheit ausgelegt. Das Rooten bei Android oder der Jailbreak bei Apples iOS bedrohen sicher abgelegte Daten. Zudem vertraut Android bei der Installation neuer Apps zu sehr auf das Sicherheitsbewusstsein des Benutzers.

Das sichere Verwalten von Schlüsseln – das Key-Management – stellt daher auf mobilen Endgeräten eine große Herausforderung dar. Ein sicheres Speichermedium existiert hier zumeist nicht. Die Bestrebungen, im aktuellen Android einen sicheren Speicher für Schlüssel und Zertifikate zu schaffen, ist daher zu begrüßen. Doch auch dessen Sicherheitsbarrieren lassen sich mit genügend krimineller Energie überwinden.

Die Beispiel-App AESDroid mogelt sich am Thema vorbei. Sie erwartet ein Passwort und bildet einen kryptographischen Hash darüber. Doch auch das Ausspähen der Eingabe von Daten lässt sich auf kompromittierten Geräten nicht ausschließen. Eine tiefergehende Behandlung des so wichtigen Themas würde jedoch den Rahmen der Artikelreihe sprengen.

Fazit

Auch wenn die mathematische Theorie eines kryptographischen Verfahrens sich dem Cryptography Engineer gut erschließt, wartet noch ein gutes Stück Arbeit auf sie oder ihn, bis ein (effizient) lauffähiges Programm implementiert ist. Gerade die Herausforderung mit Java auf Android zeigt, welche Entscheidungen noch getroffen und welche Hürden genommen sein wollen, bis der aus vier Teilen zuvor so vertraute AES auch auf dieser Plattform implementiert ist.

Es gilt vieles zu beachten und abzuwägen – beispielsweise die Prozessor- und Systemarchitektur, Speichergrößen und CPU-Takt sowie die Möglichkeiten der Programmiersprache und die Optimierung von Algorithmen für mathematische Körper. Der Weg von der mathematischen Theorie zum lauffähigen Programm ist ein herausforderndes Arbeitsgebiet. Das hat diese Artikelreihe gezeigt, und sie regt hoffentlich ein wenig zum eigenen Experimentieren an.

Oliver Müller
ist freiberuflicher IT-Berater und -Trainer mit den Schwerpunkten Software Engineering, Kryptographie, Java EE, Linux, Unix, z/OS und OpenVMS. Derzeit forscht er zudem auf dem Gebiet des Key-Managements auf mobilen Endgeräten. (ane)