Seite 2: Byte-Reihenfolge

Inhaltsverzeichnis

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.