Home
IPSec
SSL
AES-Kandidaten

e-Mail an mich

Der Algorithmus MARS

zurück     weiter

MARS

Auch IBM nahm mit seiner Chiffre MARS an der Ausschreibung zum AES teil. In der Runde der letzten Fünf belegte MARS den letzten Platz.

MARS bietet Schlüssellängen von 128 bis 448 Bit, wobei die Schlüssellänge ein Vielfaches von 32 Bit sein muss. Die Blocklänge beträgt 128 Bit und die Standardrundenzahl beträgt 32.

Der 128-Bit-Textblock wird in vier Worte – D[0], D[1], D[2] und D[3] – à 32 Bit aufgeteilt. Diese vier Worte durchlaufen drei Phasen des Algorithmus. In der ersten Phase werden die Worte D[0] bis D[3] zunächst mit je einem 32-Bit-Teilschlüssel K[i] modulo 232 addiert. Anschließend durchlaufen D[0] bis D[3] acht Runden einer schlüssellosen Vermischung der Daten. Diese Phase wird als „forward mixing“ bezeichnet. Danach beginnt die Phase 2 des Algorithmus. Die Worte D[0] bis D[3] werden acht Runden einer Transformation, die als „forward transformation“ bezeichnet ist, unter Einbeziehung der Teilschlüssel K[i] unterzogen. Anschließend durchlaufen die vier Worte acht Runden einer Transformation, die als „backwards transformation“ bezeichnet ist und ebenfalls unter Einbeziehung der Teilschlüssel K[i] durchgeführt wird. Diese 16 Runden der Transformation und Rückwärtstransformation werden als der kryptographische Kern der Chiffre bezeichnet. Danach beginnt die dritte Phase des Algorithmus, die als „backwards mixing“ bezeichnet ist. Die Worte D[0] bis D[3] werden in acht Runden einer schlüssellosen Rückwärtsvermischung bearbeitet. Abschließend wird von jedem der Worte je ein Teilschlüssel K[i] modulo 232 abgezogen. Die Struktur von MARS ist im folgenden Bild dargestellt.

Nun wird Phase 1 des Algorithmus genauer betrachtet. Nach der Addition der Teilschlüssel K[i] wird in jeder Runde ein Wort D[j] als Input für die S-Boxen S0 und S1 genutzt, die anderen drei Worte werden anschließend durch die Outputs der S-Boxen modifiziert. Die S-Boxen besitzen 256 Einträge der Größe 32 Bit, die durch einen 8-Bit-Input ausgewählt werden. Hierzu wird das jeweilige Wort D[j] in seine vier Bytes unterteilt, die mit b0, b1, b2 und b3 bezeichnet sind. Das niedrigstwertige Byte wird hierbei durch b0 repräsentiert. Die Bytes b0 und b2 dienen als Input für die S-Box S0 und die Bytes b1 und b3 dienen als Input für die S-Box S1. Die S-Boxen können frei definiert werden und werden durch einen pseudozufälligen Algorithmus generiert, bei dem der SHA-1, ein Hashalgorithmus, eingesetzt wird.

In der ersten Runde dient D[0] als Input für die S-Boxen. Zunächst wird D[1] mit S0[b0] XOR-verknüpft und dann wird S1[b1] zu diesem Ergebnis modulo 232 hinzu addiert. Zu D[2] wird S0[b2] modulo 232 addiert und D[3] wird mit S1[b3] XOR-verknüpft. Abschließend rotiert D[0] um 24 Positionen nach rechts.

Die nächste Runde wird nach dem gleichen Schema durchgeführt, nachdem die vier Worte um eine Position nach rechts rotiert sind (z.B. (D[3],D[2],D[1],D[0]) ® (D[0],D[3],D[2],D[1])). In den Runden, in denen D[0] oder D[1] als Input dienen, wird nach der Rotation D[3] bzw. D[2] zu D[0] bzw. D[1] modulo 232 addiert. Die im Bild dargestellte Struktur wird zweimal durchlaufen, so dass sich acht Runden ergeben.

Die Phase 2 des Algorithmus wird als der kryptographische Kern bezeichnet. Hauptbestandteil dieser Phase ist die Funktion E. Diese verarbeitet ein 32-Bit-Inputwort und produziert drei 32-Bit-Outputworte. Ein Datenwort D[j] dient in jeder Runde als Input für die Funktion E, die anderen drei Worte werden durch den Output entweder mittels Addition modulo 232 oder XOR-Verknüpfung modifiziert. Anschließend rotiert das Datenwort, das als Input diente, um 13 Positionen nach links. Der „forward mode“ und der „backwards mode“ unterscheiden sich nur durch die Zuordnung zu den einzelnen Datenworten, wie im folgenden Bild gezeigt.

In der Funktion E werden drei temporäre Variablen benutzt, die als L, M und R bezeichnet sind und die Länge 32 Bit haben. Die Variable R wird gleich dem Ergebnis der Linksrotation um 13 Positionen des Inputs gesetzt und M wird gleich dem Ergebnis der Addition modulo 232 vom Input und einem Teilschlüssel K[i] gesetzt. Nun werden die neun niedrigstwertigen Bits von M als Input einer S-Box genutzt, die 512 Einträge besitzt und aus der Verkettung der S-Boxen S0 und S1 aus der „mixing“-Runde entsteht. Der Output dieser S-Box wird in L gespeichert. Des Weiteren wird R mit einem zweiten Teilschlüssel K’[i] modulo 232 multipliziert, wobei der Teilschlüssel eine ungerade ganze Zahl sein muss. Anschließend rotiert R um 5 Positionen nach links und wird mit L XOR-verknüpft. Nun rotiert M um den Inhalt der fünf niedrigstwertigen Bits von R. R rotiert anschließend nochmals um 5 Positionen nach links und wird wiederum mit L XOR-verknüpft. Abschließend rotiert L um den Inhalt der fünf niedrigstwertigen Bits von R nach links. Nun entspricht L dem Output 1, M dem Output 2 und R dem Output 3. Die beschriebenen Vorgänge zeigt das folgende Bild.

Phase 3, das sogenannte „backwards mixing“ läuft nach sehr ähnlichem Schema wie Phase 1 ab. Die Unterschiede bestehen in der Zuordnung der einzelnen Bytes zu den S-Boxen und die Addition modulo 232 wurde durch eine Subtraktion modulo 232 ersetzt. Zu Beginn wird D[1] mit S1[b0] XOR-verknüpft und S0[b3] von D[2] modulo 232 subtrahiert. Dann wird S1[b2] von D[3] modulo 232 subtrahiert und S0[b1] mit dem Ergebnis XOR-verknüpft. Abschließend werden die vier Worte D[j] einer Subtraktion von je einem Teilschlüssel unterzogen. Sind D[1] bzw. D[3] die Inputworte, so werden zu Beginn die Inhalte von D[1] bei D[2] bzw. D[0] bei D[3] subtrahiert.

Für den gesamten Algorithmus werden 40 Teilschlüssel benötig, die in einem Feld K[0] bis K[39] gespeichert werden. Die Länge des geheimen Schlüssels wird in Bit dividiert durch 32 angegeben. Demnach ist bei einem Schlüssel der Länge 128 Bit n = 4. Zur Generierung der Teilschlüssel K[0] bis K[39] wird zunächst ein temporäres Feld T mit 15 Einträgen der Größe 32 Bit gebildet. Diese Einträge werden von T[0] bis T[n – 1] gleich dem geheimen Schlüssel gesetzt. T[n] wird gleich n gesetzt und T[n + 1] bis T[14] wird mit Nullen gefüllt. Anschließend werden vier Runden , die aus XOR-Verknüpfungen und Rotationen bestehen. Die Teilschlüssel K[i] werden hierbei den Einträgen von T zugeordnet. Abschließend müssen die Teilschlüssel, die zur Multiplikation genutzt werden, folgende Anforderungen erfüllen:

  • Die zwei niedrigstwertigen Bits müssen zu 1 gesetzt sein.
  • Keiner der Teilschlüssel enthält 10 oder mehr aufeinander folgende Nullen oder Einsen.

Um die erste Voraussetzung zu erfüllen, werden einfach die zwei niedrigstwertigen Bits ausgelesen und anschließend per ODER-Verknüpfung zu ´1´ gesetzt. Hat das so entstandene Wort w 10 oder mehr aufeinander folgende Nullen oder Einsen, so wird eine Maske M erzeugt. In M werden zunächst alle Stellen zu ´1´ gesetzt, an denen in w ein „run“ – so nennt man eine Abfolge von gleichen Zeichen – von Nullen oder Einsen steht. Anschließend werden das höchstwertige Bit, die beiden niedrigstwertigen Bits und das erste und letzte Bit des jeweiligen „runs“ zu Null gesetzt. So entsteht z.B. aus einem Wort w = 031130121011 die Maske M = 041110011005, wobei die hochgestellten Zahlen die Wiederholungen des jeweiligen Zeichens angeben. Anschließend wird mit Hilfe der ausgelesenen zwei niedrigstwertigen Bits des ursprünglichen Wortes einer der Einträge 265 bis 268 der S-Box ausgewählt. Dieser Eintrag rotiert um den Inhalt der fünf niedrigstwertigen Bits des letzten Teilschlüssels K[i – 1] nach links und wird mit der Maske UND-verknüpft. Dieses Ergebnis wird mit dem Wort w XOR-verknüpft und man erhält den Teilschlüssel K[i].

Man glaubt, dass die Ver- und Entschlüsselung bei MARS gleichwertige Stärke besitzen, da beim Design der Chiffre auf größtmögliche Symmetrie geachtet wurde. Die Einschränkung der möglichen Teilschlüssel zur Multiplikation soll schwache Teilschlüssel verhindern und trotzdem möglichst zufällig ermittelte Teilschlüssel bieten.

zurück     weiter

[Home] [IPSec] [SSL] [AES-Kandidaten] [Über mich] [Links] [Gästebuch]