Diffie-Hellman avec des couleurs

tbowan

06/08/2017

Pour expliquer le protocole d'échange de clés Diffie-Hellman, beaucoup d'articles et de vidéos utilisent une métaphore avec des couleurs qu'il faut mélanger.

Je vous propose ici de pousser cette comparaison au bout, de voir sa spécificité et en quoi cette version colorée est en réalité bien moins sûre que ce qu'il n'y paraît.

L'échange de clé Diffie Hellman

Lorsque vous cherchez à établir un secret partagé entre deux correspondants, le protocole d'échange de clés Diffie-Hellman est un peu un incontournable. Il est plutôt simple à mettre en oeuvre et permet de sécuriser des sessions de communications en garantissant la confidentialité persistante.

Comme toute la cryptographie moderne, la définition de ce protocole utilise des théories mathématiques. Dans notre cas, les groupes, la notion de générateur, d'exponentiation et de calcul de logarithme discret. Lorsque vous comprenez ces notions, le protocole est relativement facile à comprendre.

Pour faciliter sa compréhension, la plupart des auteurs utilisent une métaphore où les participants s'échangent de la peinture. Sans la couche de mathématiques, le protocole est encore plus facile à comprendre. D'où le piège.

Je vous propose donc de pousser cette métaphore à fond pour voir jusqu'où elle fonctionne, quelle est la différence avec la version officielle et en quoi cette version est en fait moins sûre que ce qu'il n'y paraît.

La métaphore des couleurs

Pour communiquer, Alice et Bob vont donc devoir établir un secret partagé et, comme vous vous en doutez, ce sera une couleur. Cette nuance particulière, appelons-là pour l'instant taupe1, ne sera connue que d'eux seuls.

Alice et Bob commencent par utiliser une première peinture commune. Comme tout se fait publiquement, n'importe qui peut voir cette couleur, i.e. Eve qui aimerait bien pouvoir connaître leur secrets. Prenons du glauque2.

Avec le protocole officiel, cette couleur servirait de générateur d'une suite, Alice et Bob choisiraient des entiers aléatoires et se communiqueraient les couleurs correspondantes dans la suite.

Ici, Alice et Bob vont choisir chacun une couleur secrète. Après maintes hésitations, Alice s'arrête sur de l'amarante3. Bob à choisi du bleu4 depuis bien longtemps.

Chacun de leur côté, ils vont mélanger, à volumes égaux, un peu de leur couleur avec la couleur commune et s'envoyer leurs résultats. Cette couleur, envoyée publiquement est leur clé publique. Alice envoie une sorte de russett et Bob lui retourne une nuance de bleu de Boston.

Ils vont alors mélanger la couleur reçue avec leur couleur secrète pour obtenir le même mélange des trois couleurs à proportions égales. Ici, on obtient un bleu kashmir5.

La sécurité repose sur le fait qu'il est difficile pour Eve de trouver quelle est la nuance de gris taupe exacte en n'ayant observé que la couleur commune et les deux mélanges intermédiaires. Pour y arriver, il faudrait qu'elle puisse enlever la couleur commune à l'un des mélanges et tout le monde sait qu'une fois qu'on a commencé à mélanger les pinceaux, on ne retrouve jamais les couleurs d'origine.

Modélisation

Parmis les modélisation des couleurs possibles6, nous avons choisi le triplet de couleurs primaires (r, g, b) auxquel nous ajoutons un quatrième membre pour la quantité. Le code suivant est une implémentation en C++ d'exemple.

class Color
{
public:
    float r ;
    float g ;
    float b ;
    float w ;

public:

    Color(float r, float g, float b, float w = 1.0)
    : r(r), g(g), b(b), w(w)
    { }

    Color(std::string const & hex)
    {
        unsigned int r, g, b ;
        sscanf(hex.c_str(), "#%02x%02x%02x", &r, &g, &b) ;

        this->r = r / 256.0 ;
        this->g = g / 256.0 ;
        this->b = b / 256.0 ;
        this->w = 1.0 ;
    }
} ;

Le triplet (r, g, b) peut s'assimiler à une quantité de pigments dans l'échantillon, pour connaître la nuance, il faut donc canoniser ces valeurs en divisant par la quantité7. On peut utiliser cette opération pour écrire la couleur sur un flux de sortie :

template <typename Stream>
Stream & operator<<(Stream & stream, Color const & c)
{
    char buf[8] ;
    snprintf(buf, sizeof(buf), "#%02x%02x%02x",
        (unsigned int) (256.0 * c.r / c.w),
        (unsigned int) (256.0 * c.g / c.w),
        (unsigned int) (256.0 * c.b / c.w)
    ) ;
        
    stream << buf;
    return stream ;
}

Avec cette convention, les calculs de mélanges sont beaucoup plus simples, ajouter deux couleurs consiste simplement à ajouter les pigments et les quantités. On peut également définir un opérateur pour multiplier une couleur par un coefficient.

Color operator+(Color const & lhs, Color const & rhs)
{
    return Color(
        lhs.r + rhs.r,
        lhs.g + rhs.g,
        lhs.b + rhs.b,
        lhs.w + rhs.w
    ) ;
}

Color operator*(float f, Color const & rhs)
{
    return Color(
        f * rhs.r,
        f * rhs.g,
        f * rhs.b,
        f * rhs.w
    ) ;
}

L'ensemble de quadruplets possibles forme un groupe dans (R4, +). Notre modélisation à base de nombres à virgule flottante est un sous-ensemble qui, à quelques imprécisions de mesures près, formerait un groupe aussi.

Par contre, l'ensemble des couleurs qui ont un sens physique et réel forme un Quasigroupe8. Ces couleurs sont celles dont les nombres sont tous positifs et où le rapport entre une couleur et sa quantité est inférieur à 1.

Cette opération de mélange perd donc la notion d'inverse, aucune couleur ne peut en annuler une autre. Le protocole d'échange de clés est alors parfaitement sûr ; le calcul d'un inverse n'est pas seulement difficile, il est impossible.

Mais ce n'est pas parce que Alice et Bob ont une convention que Eve est tenue de la respecter. La notion d'inverse d'une couleur, impossible dans le monde physique, existe dans (R4, +), est plutôt simple à calculer et peut donc être utilisée par Eve.

Eve peut donc disposer d'un opérateur d'inversion d'une couleur comme celui-ci :

Color operator-(Color const & rhs)
{
    return -1.0 * rhs ;
}

Eve peut donc très facilement retrouver la couleur commune d'Alice et Bob. En mélangeant les couleurs publiques, elle obtient un mélange constitué d'une part de couleur secrète d'Alice, une part de celle de Bob et deux parts de la couleur initiale. En supprimant une part de couleur publique, elle obtiendra un mélange des trois couleurs à part égale.

Color getCommonSecret(
    Color const & base,
    Color const & pubA,
    Color const & pubB
    )
{
    return pubA + pubB - base ;
}

Il s'agit ici d'une attaque directe sur le problème de Diffie-Hellman. Eve calcule le secret partagé directement à partir des informations publiques, sans passer par les clés secrètes.

Le calcul de ces clés secrètes, c'est à dire de l'équivalent métaphorique du logarithme discret9 est également très facile à effectuer. En voici une implémentation :

Color log(
    Color const & base,
    Color const & pub,
    )
{
    return pub - base ;
}

On peut difficilement faire plus simple comme attaque.

Conclusion

Cette métaphore est adaptée pour illustrer l'idée que, si on dispose d'une opération difficilement inversible comme le mélange de pots de peinture, on peut définir un protocole pour établir un secret partagé. Notre expérience nous a appris qu'on ne peut pas physiquement annuler un mélange de couleur, nous comprenons et acceptons donc intuitivement la sécurité du protocole.

Mais ce n'est pas parce que quelque chose est physiquement impossible qu'on ne peut pas le modéliser, construire un modèle mathématique et, in fine, y faire des calculs utiles. Les nombres complexes en sont un exemple10, le mélange de couleurs en est un autre.

Avec cette version colorée, Alice et Bob croient leurs communications en sécurité alors que Eve les a déjà déchiffrées.

Et ceci nous amène à un principe philosophique plus profond, le doute. Ce n'est pas parce qu'on vous dit que c'est sécurisé que ça l'est forcément et votre intuition est rarement bonne conseillère en la matière. Que ce soit pour vos propres codes ou ceux des autres, vérifiez toujours tout avec rigueur si vous ne voulez pas laisser passer une vulnérabilité.


  1. Car comme tout le monde le sait, à force de mélanger des couleurs, on obtient toujours une sorte de brun très moche et indéfinissable que n'importe quel enfant appelle caca mais que les décorateurs d'intérieur ont décidé d'appeler taupe.

  2. Sorte de vert un peu grisâtre tirant vers le bleu canard. Personne n'est vraiment d'accord sur la nuance de couleur exacte. On peut partir du principe que, par sécurité, Alice a envoyé un échantillon à Bob.

  3. Nuance de pourpre plus claire que le bordeaux qui évoque la fleur d'amarante. Bob appelle ça du rose mais il fallait une couleur commençant par A.

  4. Alice aurait dit azur mais ça n'est pas exactement la même couleur et surtout, ça ne commence pas par B.

  5. Sorte de bleu acier. On sent bien la parenté avec du gris taupe mais comme dirait Bob, ça reste quand même bien Bleu tout ça.

  6. Codage informatique des couleurs, wikipedia.

  7. Le principe est similaire à celui des coordonnées homogènes, wikipedia

  8. Quasigroupe wikipedia.

  9. Vu que ce protocole n'utilise pas de générateur et d'exponentiation mais une simple opération, on ne devrait pas pouvoir parler de logarithme. Mais puisque cette métaphore est utilisée pour illustrer le problème du logarithme discret, nous l'utiliserons quand même.

  10. On sait tous qu'un carré ne peut pas avoir une aire négative ! Mais on peut définir une longueur de côté i dont l'aire du carré soit -1. On peut alors l'utiliser pour construire un ensemble cohérent et découvrir la plus belle formulle et tracer le plus bel ensemble.