Aller au contenu principal

2.5 The Poly1305 Algorithm

2.5 The Poly1305 Algorithm​

Poly1305 est un authentificateur à usage unique conçu par D. J. Bernstein. Poly1305 prend une clé à usage unique de 32 octets et un message, et produit une étiquette (tag) de 16 octets. Cette étiquette sert à authentifier le message.

L'article d'origine ([Poly1305]) est intitulé "The Poly1305-AES message-authentication code", et la fonction MAC qui y est décrite exige une clé AES de 128 bits, une "clé supplémentaire" de 128 bits et un nonce de 128 bits (non secret). AES y sert à chiffrer le nonce afin d'obtenir une chaîne de 128 bits unique (et secrète), mais comme l'indique l'article, "Il n'y a rien de particulier à AES ici. On peut remplacer AES par une fonction arbitraire à clé, d'un ensemble arbitraire de nonces vers des chaînes de 16 octets."

Quelle que soit la manière dont la clé est générée, celle-ci est partitionnée en deux parties, appelées "r" et "s". La paire (r,s) DOIT être unique et DOIT être imprévisible à chaque invocation (c'est pourquoi elle était à l'origine obtenue en chiffrant un nonce), tandis que "r" PEUT être constant, mais doit être modifié comme suit avant utilisation : ("r" est traité comme un nombre little-endian sur 16 octets) :

  • r[3], r[7], r[11] et r[15] DOIVENT avoir leurs quatre bits de poids fort à zéro (être inférieurs à 16)

  • r[4], r[8] et r[12] DOIVENT avoir leurs deux bits de poids faible à zéro (être divisibles par 4)

L'exemple de code suivant impose à "r" les contraintes appropriées (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;
}

Ici, "&=" est l'opérateur d'affectation ET bit à bit du langage C.

"s" devrait être imprévisible, mais il est tout à fait acceptable de générer de façon unique à la fois "r" et "s" à chaque fois. Comme chacun fait 128 bits, leur génération pseudo-aléatoire (voir la section 2.6) est également acceptable.

Les entrées de Poly1305 sont :

  • Une clé à usage unique de 256 bits

  • Un message de longueur arbitraire

La sortie est une étiquette de 128 bits.

D'abord, la valeur "r" est contrainte (clamp).

Ensuite, on fixe la constante première "P" à 2^130-5 : 3fffffffffffffffffffffffffffffffb. On initialise aussi une variable "accumulator" à zéro.

Ensuite, on divise le message en blocs de 16 octets. Le dernier peut être plus court :

  • Lire le bloc comme un nombre en little-endian.

  • Ajouter un bit au-delà du nombre d'octets. Pour un bloc de 16 octets, cela équivaut à ajouter 2^128 au nombre. Pour un bloc plus court, cela peut être 2^120, 2^112, ou toute puissance de deux divisible par 8, jusqu'à 2^8.

  • Si le bloc ne fait pas 17 octets (le dernier bloc), le compléter par des zéros. Cela n'a pas de signification si l'on traite les blocs comme des nombres.

  • Ajouter ce nombre à l'accumulateur.

  • Multiplier par "r".

  • Remplacer l'accumulateur par le résultat modulo p. En résumé : Acc = ((Acc+block)*r) % p.

Enfin, on ajoute à l'accumulateur la valeur de la clé secrète "s", et on sérialise les 128 bits les moins significatifs en little-endian pour former l'étiquette.

2.5.1 The Poly1305 Algorithms 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​

Pour notre exemple, nous ne générons pas la clé à usage unique avec AES, et nous supposons que nous disposons du matériel de clé suivant :

  • Matériel de clé : 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 comme chaîne d'octets : 01:03:80:8a:fb:0d:b2:fd:4a:bf:f6:af:41:49:f5:1b

  • s comme nombre sur 128 bits : 1bf54941aff6bf4afdb20dfb8a800301

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

  • r contraint comme nombre : 806d5400e52447c036d555408bed685

Pour le message, nous utilisons un court texte :

Message à authentifier :

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

Comme Poly1305 traite des tranches de 16 octets, le message de 34 octets se divise en trois blocs. Dans le calcul ci-dessous, "Acc" désigne l'accumulateur et "Block" le bloc courant :

Bloc no 1

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

Bloc no 2

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

Dernier bloc

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

En ajoutant s, on obtient ce nombre, qu'on sérialise pour produire l'étiquette :

Acc + s = 2a927010caf8b2bc2c6365130c11d06a8

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

Dernière mise à jour le