Passa al contenuto principale

2.5 The Poly1305 Algorithm (L'algoritmo Poly1305)

2.5 The Poly1305 Algorithm (L'algoritmo Poly1305)​

Poly1305 è un autenticatore monouso (one-time authenticator) progettato da D. J. Bernstein. Poly1305 accetta una chiave monouso di 32 byte e un messaggio, e produce un tag di 16 byte. Questo tag serve ad autenticare il messaggio.

L'articolo originale ([Poly1305]) si intitola "The Poly1305-AES message-authentication code", e la funzione MAC ivi descritta richiede una chiave AES a 128 bit, una "chiave aggiuntiva" a 128 bit e un nonce a 128 bit (non segreto). Lì AES serve a cifrare il nonce per ottenere una stringa di 128 bit unica (e segreta), ma come afferma il documento, "Non c'è nulla di speciale in AES. Si può sostituire AES con una funzione arbitraria con chiave da un insieme arbitrario di nonce a stringhe di 16 byte."

Indipendentemente da come viene generata la chiave, questa è partizionata in due parti, chiamate "r" e "s". La coppia (r,s) DEVE essere unica e DEVE essere imprevedibile per ogni invocazione (ecco perché in origine si otteneva cifrando un nonce), mentre "r" PUÒ essere costante, ma va modificato come segue prima dell'uso: ("r" è trattato come un numero little-endian su 16 ottetti):

  • r[3], r[7], r[11] e r[15] DEVONO avere azzerati i quattro bit più significativi (essere minori di 16)

  • r[4], r[8] e r[12] DEVONO avere azzerati i due bit meno significativi (essere divisibili per 4)

Il seguente codice di esempio applica il clamp a "r" per ottenere valori conformi:

/*
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;
}

Qui "&=" è l'operatore di assegnazione AND bit a bit del linguaggio C.

"s" dovrebbe essere imprevedibile, ma è perfettamente accettabile generare in modo univoco sia "r" sia "s" ogni volta. Poiché ciascuno è di 128 bit, è accettabile anche generarli in modo pseudo-casuale (vedere la sezione 2.6).

Gli ingressi di Poly1305 sono:

  • Una chiave monouso a 256 bit

  • Un messaggio di lunghezza arbitraria

L'uscita è un tag a 128 bit.

Per prima cosa si applica il clamp al valore "r".

Poi si imposta la costante primo "P" a 2^130-5: 3fffffffffffffffffffffffffffffffb. Si imposta anche una variabile "accumulator" (accumulatore) a zero.

Quindi si divide il messaggio in blocchi di 16 byte. L'ultimo può essere più corto:

  • Leggere il blocco come numero in little-endian.

  • Aggiungere un bit oltre il numero di ottetti. Per un blocco di 16 byte equivale ad aggiungere 2^128 al numero. Per un blocco più corto può essere 2^120, 2^112, o una qualsiasi potenza di due divisibile per 8, fino a 2^8.

  • Se il blocco non è lungo 17 byte (l'ultimo blocco), riempirlo con zeri. Ciò non ha significato se si trattano i blocchi come numeri.

  • Aggiungere questo numero all'accumulatore.

  • Moltiplicare per "r".

  • Impostare l'accumulatore sul risultato modulo p. In sintesi: Acc = ((Acc+block)*r) % p.

Infine si aggiunge all'accumulatore il valore della chiave segreta "s", e i 128 bit meno significativi vengono serializzati in ordine little-endian per formare il tag.

2.5.1 The Poly1305 Algorithms in Pseudocode (Gli algoritmi Poly1305 in pseudocodice)​

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 (Esempio Poly1305 e vettore di test)​

Nel nostro esempio omettiamo la generazione della chiave monouso con AES e supponiamo di aver ottenuto il seguente materiale di chiave:

  • Materiale di chiave: 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 come stringa di ottetti: 01:03:80:8a:fb:0d:b2:fd:4a:bf:f6:af:41:49:f5:1b

  • s come numero a 128 bit: 1bf54941aff6bf4afdb20dfb8a800301

  • r prima del clamp: 85:d6:be:78:57:55:6d:33:7f:44:52:fe:42:d5:06:a8

  • r dopo il clamp come numero: 806d5400e52447c036d555408bed685

Per il messaggio usiamo un breve testo:

Messaggio da autenticare:

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

Poiché Poly1305 lavora a blocchi di 16 byte, il messaggio di 34 byte si divide in tre blocchi. Nel calcolo seguente "Acc" indica l'accumulatore e "Block" il blocco corrente:

Blocco n. 1

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

Blocco n. 2

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

Ultimo blocco

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

Sommando s si ottiene questo numero, che si serializza per produrre il tag:

Acc + s = 2a927010caf8b2bc2c6365130c11d06a8

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

Ultimo aggiornamento il