Zum Hauptinhalt springen

2.5 The Poly1305 Algorithm (Der Poly1305-Algorithmus)

2.5 The Poly1305 Algorithm (Der Poly1305-Algorithmus)​

Poly1305 ist ein Einmal-Authentifikator (one-time authenticator), der von D. J. Bernstein entworfen wurde. Poly1305 nimmt einen 32-Byte-Einmalschlüssel und eine Nachricht entgegen und erzeugt ein 16-Byte-Tag. Dieses Tag dient zur Authentifizierung der Nachricht.

Der Originalartikel ([Poly1305]) trägt den Titel "The Poly1305-AES message-authentication code", und die dort beschriebene MAC-Funktion erfordert einen 128-Bit-AES-Schlüssel, einen 128-Bit-"Zusatzschlüssel" und einen 128-Bit-(nicht geheimen) Nonce. Dort wird AES zum Verschlüsseln des Nonce verwendet, um eine eindeutige (und geheime) 128-Bit-Zeichenkette zu erhalten; wie das Papier jedoch ausführt, "gibt es an AES nichts Besonderes. Man kann AES durch eine beliebige schlüsselabhängige Funktion von einer beliebigen Nonce-Menge zu 16-Byte-Zeichenketten ersetzen."

Unabhängig davon, wie der Schlüssel erzeugt wird, wird er in zwei Teile aufgeteilt, die "r" und "s" heißen. Das Paar (r,s) MUSS eindeutig sein und MUSS bei jedem Aufruf nicht vorhersagbar sein (deshalb wurde es ursprünglich durch Verschlüsseln eines Nonce gewonnen), während "r" konstant sein KANN, aber vor der Verwendung wie folgt angepasst werden muss: ("r" wird als 16-Oktett-Zahl in Little-Endian-Byte-Reihenfolge behandelt):

  • r[3], r[7], r[11] und r[15] MÜSSEN ihre oberen vier Bits gelöscht haben (kleiner als 16 sein)

  • r[4], r[8] und r[12] MÜSSEN ihre unteren zwei Bits gelöscht haben (durch 4 teilbar sein)

Der folgende Beispielcode setzt "r" auf geeignete Werte fest (clamp):

/*
Adapted from poly1305aes_test_clamp.c version 20050207
D. J. Bernstein
Public domain.
*/

#include "poly1305aes_test.h"

void poly1305aes_test_clamp(unsigned char r[16])
{
  r[3] &= 15;
  r[7] &= 15;
  r[11] &= 15;
  r[15] &= 15;
  r[4] &= 252;
  r[8] &= 252;
  r[12] &= 252;
}

Dabei ist "&=" der bitweise UND-Zuweisungsoperator der Sprache C.

"s" sollte nicht vorhersagbar sein, aber es ist völlig in Ordnung, sowohl "r" als auch "s" jedes Mal neu und eindeutig zu erzeugen. Da jeder von ihnen 128 Bit hat, ist auch ihre pseudozufällige Erzeugung (siehe Abschnitt 2.6) akzeptabel.

Die Eingaben für Poly1305 sind:

  • Ein 256-Bit-Einmalschlüssel

  • Eine Nachricht beliebiger Länge

Die Ausgabe ist ein 128-Bit-Tag.

Zuerst wird der Wert "r" begrenzt (clamp).

Als Nächstes wird die Konstante Primzahl "P" auf 2^130-5 gesetzt: 3fffffffffffffffffffffffffffffffb. Außerdem wird eine Variable "accumulator" (Akkumulator) auf null gesetzt.

Dann wird die Nachricht in 16-Byte-Blöcke unterteilt. Der letzte kann kürzer sein:

  • Den Block als Little-Endian-Zahl lesen.

  • Ein Bit jenseits der Oktettanzahl hinzufügen. Bei einem 16-Byte-Block entspricht dies dem Addieren von 2^128 zur Zahl. Bei einem kürzeren Block kann es 2^120, 2^112 oder eine beliebige Zweierpotenz sein, die durch 8 teilbar ist, bis hinunter zu 2^8.

  • Wenn der Block nicht 17 Byte lang ist (der letzte Block), mit Nullen auffüllen. Dies ist bedeutungslos, wenn man die Blöcke als Zahlen behandelt.

  • Diese Zahl zum Akkumulator addieren.

  • Mit "r" multiplizieren.

  • Den Akkumulator auf das Ergebnis modulo p setzen. Zusammengefasst: Acc = ((Acc+block)*r) % p.

Schließlich wird der Wert des Geheimschlüssels "s" zum Akkumulator addiert, und die 128 niedrigstwertigsten Bits werden in Little-Endian-Reihenfolge serialisiert, um das Tag zu bilden.

2.5.1 The Poly1305 Algorithms in Pseudocode (Der Poly1305-Algorithmus in Pseudocode)​

clamp(r): r &= 0x0ffffffc0ffffffc0ffffffc0fffffff
poly1305_mac(msg, key):
   r = le_bytes_to_num(key[0..15])
   clamp(r)
   s = le_bytes_to_num(key[16..31])
   a = 0  /* a is the accumulator */
   p = (1<<130)-5
   for i=1 upto ceil(msg length in bytes / 16)
      n = le_bytes_to_num(msg[((i-1)*16)..(i*16)] | [0x01])
      a += n
      a = (r * a) % p
      end
   a += s
   return num_to_16_le_bytes(a)
   end

2.5.2 Poly1305 Example and Test Vector (Poly1305-Beispiel und Testvektor)​

In unserem Beispiel verzichten wir darauf, den Einmalschlüssel mit AES zu erzeugen, und nehmen an, dass wir folgendes Schlüsselmaterial erhalten haben:

  • Schlüsselmaterial: 85:d6:be:78:57:55:6d:33:7f:44:52:fe:42:d5:06:a8:01:03:80:8a:fb:0d:b2:fd:4a:bf:f6:af:41:49:f5:1b

  • s als Oktettfolge: 01:03:80:8a:fb:0d:b2:fd:4a:bf:f6:af:41:49:f5:1b

  • s als 128-Bit-Zahl: 1bf54941aff6bf4afdb20dfb8a800301

  • r vor dem Clamp: 85:d6:be:78:57:55:6d:33:7f:44:52:fe:42:d5:06:a8

  • Geklemmtes r als Zahl: 806d5400e52447c036d555408bed685

Für unsere Nachricht verwenden wir einen kurzen Text:

Zu authentifizierende Nachricht:

000  43 72 79 70 74 6f 67 72 61 70 68 69 63 20 46 6f  Cryptographic Fo
016  72 75 6d 20 52 65 73 65 61 72 63 68 20 47 72 6f  rum Research Gro
032  75 70                                            up

Da Poly1305 in 16-Byte-Stücken arbeitet, zerlegt sich die 34-Byte-Nachricht in drei Blöcke. In der folgenden Rechnung bezeichnet "Acc" den Akkumulator und "Block" den aktuellen Block:

Block Nr. 1

Acc = 00
Block = 6f4620636968706172676f7470797243
Block with 0x01 byte = 016f4620636968706172676f7470797243
Acc + block = 016f4620636968706172676f7470797243
(Acc+Block) * r =
     b83fe991ca66800489155dcd69e8426ba2779453994ac90ed284034da565ecf
Acc = ((Acc+Block)*r) % P = 2c88c77849d64ae9147ddeb88e69c83fc

Block Nr. 2

Acc = 2c88c77849d64ae9147ddeb88e69c83fc
Block = 6f7247206863726165736552206d7572
Block with 0x01 byte = 016f7247206863726165736552206d7572
Acc + block = 437febea505c820f2ad5150db0709f96e
(Acc+Block) * r =
     21dcc992d0c659ba4036f65bb7f88562ae59b32c2b3b8f7efc8b00f78e548a26
Acc = ((Acc+Block)*r) % P = 2d8adaf23b0337fa7cccfb4ea344b30de

Letzter Block

Acc = 2d8adaf23b0337fa7cccfb4ea344b30de
Block = 7075
Block with 0x01 byte = 017075
Acc + block = 2d8adaf23b0337fa7cccfb4ea344ca153
(Acc + Block) * r =
     16d8e08a0f3fe1de4fe4a15486aca7a270a29f1e6c849221e4a6798b8e45321f
((Acc + Block) * r) % P = 28d31b7caff946c77c8844335369d03a7

Durch Addition von s erhalten wir diese Zahl und serialisieren sie, um das Tag zu erhalten:

Acc + s = 2a927010caf8b2bc2c6365130c11d06a8

Tag: a8:06:1d:c1:30:51:36:c6:c2:2b:8b:af:0c:01:27:a9

Letztes Update am