Génération de tokens

Je suis en train de travailler sur une application qui nécessite l’utilisation de tokens. Certains doivent avoir une durée de vie assez courte, d’autres n’ont pas de péremption. Tout l’enjeu autour de ces tokens est de s’assurer qu’ils ne soient pas devinables facilement, ni qu’ils soient attaquable par force brute. Mais en même temps, certains tokens sont destinés à être copier-coller, et il est alors préférable qu’ils puissent être saisis à la main par un être humain ; il faut donc qu’ils ne soient pas trop longs et qu’ils soient intelligibles.

À une époque, on aurait généré un hash MD5 à partir d’un nombre aléatoire, éventuellement en utilisant la date courante comme sel. En PHP ça donnait ça :

$token = md5(time() . mt_rand());

Simple et plutôt efficace. Sauf qu’il y a plusieurs soucis avec cette solution :

• Le résultat est une chaîne de 32 caractères hexadécimaux, ce qui correspond à un message de 128 bits. C’est bien d’un point de vue cryptographique (plus le message est long, plus il est difficile à craquer par force brute), mais c’est un peu long à taper à la main.
• MD5 est un algorithme aujourd’hui considéré comme insuffisamment sécurisé.

Pour le premier point, on peut changer la base du message ; en passant d’une base 16 (caractères hexadécimaux) à une base 36 (tous les caractères alphanumériques, aussi appelée base hexatridécimale, hexatrigésimale ou sexatrigésimale), on diminue la taille du token à 25 caractères.
Pour le second point, il est recommandé de passer à l’algorithme SHA256.

En PHP, cela donne ceci :

$token = base_convert(hash('sha256', time() . mt_rand()), 16, 36);

Cette fois-ci, on a un message de 256 bits, ce qui est encore mieux d’un point de vue cryptographique, généré par un algorithme bien plus robuste. Et grâce à la base 36, on a un message de 50 caractères au lieu de 64.
Il y a toutefois deux choses qui pourraient être améliorées. Le message est encore trop long à mon goût ; personne n’a envie de taper à la main un hash de 50 caractères, donc il faut trouver un moyen pour le raccourcir. Et il y a des caractères trop similaires (les lettres i et l, et le chiffre 1 ; le chiffre 0 et la lettre o) pour qu’un être humain normal puisse les recopier sans se poser la moindre question.

Un bon moyen de raccourcir le message est d’utiliser une base encore plus longue. Le plus simple est de passer sur un encodage en base 62 (les chiffres + les lettres minuscules + les lettres majuscules). Et pour enlever toute ambiguïté, on peut retirer les caractères “0oO1iIlL”. Appelons cet encodage «Base 54».

Il n’y a pas de fonction native en PHP pour gérer cela, alors j’ai fait un objet pour cela, (directement dérivé de celui trouvé sur un site allemand) :

class BaseConvert {
   /** Base 16. */
   const BASE16 = '0123456789abcdef';
  /** Base 54, same as base 62 (0-9a-zA-Z) without characters '0oO1iIlL'. */
  const BASE54 = '23456789abcdefghjkmnpqrstuvwxyzABCDEFGHJKMNPQRSTUVWXYZ';
    /**
     * Convert a number from any base to any other base.
     * @param int|string $value The number to convert.
     * @param string $inDigits The input base's digits.
     * @param string $outDigits The output base's digits.
     * @return string The converted number.
     * @throws Exception If a digit is outside the base.
     * @see http://www.technischedaten.de/pmwiki2/pmwiki.php?n=Php.BaseConvert
     */
    static public function convertBase($value, $inDigits, $outDigits) {
        $inBase = strlen($inDigits);
        $outBase = strlen($outDigits);
        $decimal = '0';
        $level = 0;
        $result = '';
        $value = trim((string)$value, "\r\n\t +");
        $signe = ($value{0} === '-') ? '-' : '';
        $value = ltrim($value, '-0');
        $len = strlen($value);
        for ($i = 0; $i < $len; $i++) {
            $newValue = strpos($inDigits, $value{$len - 1 - $i});
            if ($newValue === false)
                throw new \Exception('Bad Char in input 1', E_USER_ERROR);
            if ($newValue >= $inBase)
                throw new \Exception('Bad Char in input 2', E_USER_ERROR);
            $decimal = bcadd($decimal, bcmul(bcpow($inBase, $i), $newValue));
        }
        if ($outBase == 10)
            return ($signe.$decimal); // shortcut
        while (bccomp(bcpow($outBase, $level++), $decimal) !== 1)
            ;
        for ($i = ($level - 2); $i >= 0; $i--) {
            $factor = bcpow($outBase, $i);
            $number = bcdiv($decimal, $factor, 0);
            $decimal = bcmod($decimal, $factor);
            $result .= $outDigits{$number};
        }
        $result = empty($result) ? '0' : $result;
        return ($signe.$result);
    }
}

Il devient alors assez facile de générer un token :

$hash = hash('sha256', time() . mt_rand());
$token = BaseConvert($hash, BaseConvert::BASE16, BaseConvert::BASE54);

On obtient alors une chaîne de 45 caractères de long. C’est bien, mais ça reste long. D’ailleurs, avons-nous réellement besoin d’un hash de 256 bits ? C’est assez énorme… c’est de l’ordre d’idée du nombre d’atomes dans l’univers (10 puissance 80, soit 266 bits).

Jetons un œil à l’image suivante :

http://i.imgur.com/gfYw57t.png

Regardons bien ce graphique. Il nous permet de calculer le temps moyen pour craquer un clé, en fonction de la taille de celle-ci et du nombre d’essais par seconde. J’aurais tendance à penser que si votre serveur web se prend un million de requêtes par seconde en continu, vous devriez vous en apercevoir ; mais soyons précautionneux et regardons la colonne correspondant à un milliard d’essais par seconde.

On peut voir qu’avec 256 bits, le temps moyen pour trouver un hash en force brute est de… ah ben le graphique ne va que jusqu’à 120 bits ! Ahahah 

Maintenant, prenons un peu de temps pour réfléchir à notre application. Suivant le nombre de tokens susceptibles d’exister en même temps et leur durée de vie, les choses peuvent être très différentes.

Imaginons qu’il s’agisse de tokens d’authentification. On peut se dire qu’on en aura un millier en même temps maximum, avec une durée de vie de 15 minutes. Les chances de tomber sur un token existant sont donc multipliées par 1000. Décalons-nous de deux colonnes dans le tableau. Puisque les tokens disparaissent au bout de 15 minutes, on peut considérer qu’on prend énormément de précaution en utilisant des messages nécessitant plus d’un mois pour être cassés. D’après le tableau, cela nous amène à un minimum de 62 bits.
Et 62 bits encodés en base 54, ça ne prend que 11 caractères. C’est beaucoup mieux !
Si on s’autorise à utiliser 12 caractères (c’est la limite que je m’autorise lorsque je demande à quelqu’un de recopier un code à la main), on monte à 70 bits, ce qui prendrait 37 ans à deviner. On est large !

Imaginons maintenant qu’il s’agisse d’une application de raccourcissement d’URL, mais dont les URLs doivent rester « privées » et donc difficiles à trouver (oui c’est un peu bizarre, mais c’est pour trouver un exemple).
On peut se dire que cette application devra être capable de stocker un million d’URL, sans limite de durée. Aouch, ça se complique. On peut voir que la colonne la plus à droite du tableau n’est plus suffisante, il faudra encore diviser les valeurs de temps par mille.
On peut voir qu’avec une clé de 82 bits, il suffira de un an et demi en moyenne pour tomber sur un token existant. Donc il suffira de 3 ans pour être certain de tomber sur un token alloué à une URL. Ce n’est pas satisfaisant. Si on passe à 92 bits, il faut alors 1600 ans en moyenne pour tomber sur une clé. Ce n’est pas mal. Il faut alors 16 caractères en base 54 pour encoder ça.
Si on s’autorise à monter jusqu’à 18 caractères en base 54, cela nous donne 104 bits, soit un délai moyen de plus de 6 millions d’années…

Continuons à réfléchir un peu. Comment faire pour raccourcir les messages ? On peut utiliser une base plus grande. Le projet libre ZeroMQ utilise en interne un encodage en base 85. Il s’agit de la base 62 (caractères alphanumériques minuscules et majuscules), à laquelle ils ont ajouté des caractères spéciaux («.-:+=^!/*?&<>()[]{}@%$#»). Ils ont bien fait attention à ne pas utiliser d’espace, d’apostrophe ou de guillemets, afin que les chaînes générées puissent être copiées-collées facilement et être utilisées en paramètre sur la ligne de commande, par exemple, sans que cela ne pose de problème.

Par curiosité, si on se dit que pour nos URLs on veut avoir un temps moyen supérieur à mille ans, ce qui correspond à 92 bits, quelle taille de message obtient-on en base 85 ? Eh bien seulement 15 caractères. Le gain n’est pas énorme… Mais là encore, si on s’autorise 18 caractères en base 85, on monte à 116 bits ; soit 26 milliards d’années en moyenne pour tomber sur un token existant. Ça devrait aller…