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 copiés-collés, 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écautions 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…

4 réponses sur “Génération de tokens”

  1. Peux tu mapper ton hash vers quelque chose de plus facile à mémoriser pour l’humain, quitte à ce que ça soit plus long ? Dans l’esprit de xkcd password (sur l’url pershing, et/ou xkpasswd.net qui l’applique).

    Combien de mots a-t-on dans un dictionnaire ? Et qu’est ce que ça donne si on de permet toutes les permutations d’un mot avec chaque caractère en majuscule ou minuscule p.ex ?

  2. @Marcel : Question intéressante. Je pense qu’en introduisant des mots du dictionnaire dans un token, on en augmente le risque d’être cracké (il devient alors facilement sujet à une attaque au dictionnaire). Ou alors il faut générer un token beaucoup plus long, pour ajouter de l’entropie (avec plusieurs mots du dictionnaire et/ou des caractères spéciaux entre les mots) ; mais au final vaut-il mieux avoir un long token contenant des mots faciles à retenir et quelques caractères impossibles à mémoriser, ou un token court avec que des caractères impossibles à mémoriser ?

  3. Je ne vois pas en quoi le MD5 pose un soucis de sécurité dans le cas présent. C’est vrai, il n’est pas aussi fort que le SHA256, mais le but ici est de générer une chaîne aléatoire, on se moque de la chaîne de base qui a été hashée et qui n’est d’ailleurs rien de plus qu’un nombre aléatoire. Dans la génération de token tout ce qui compte est de pouvoir générer le plus de combinaisons possibles sur une chaîne de longueur raisonnable, un pirate ne gagnera rien à « casser » le hashage .

    Bonne continuation en tout cas

  4. @Stephane Non, la distribution du SHA256 est plus aléatoire que celle du MD5,. Dans le cas où un hacker peut faire générer à ton système des suites de tokens, il peut finir par deviner le prochain token d’un autre utilisateur s’ils ne sont pas distribués correctement. La sécurité n’est pas liée uniquement à ton générateur de nombre aléatoire ; la fonction de hashage participe encore plus à la distribution de l’aléa.
    Je suis d’accord que ce problème est grandement nuancé par l’utilisation d’une période de validité du token. Il y a peu de chances qu’un hacker trouve le prochain hash MD5, même réduit à 50 bits, si on invalide les tokens au bout de 15 minutes 😉

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Notifiez-moi des commentaires à venir via email. Vous pouvez aussi vous abonner sans commenter.