Explication des algorithmes de chiffrement avec des exemples

La cryptographie, dans sa forme la plus élémentaire, est la science de l'utilisation de codes et de chiffrements pour protéger les messages.

Le chiffrement consiste à coder des messages dans le seul but de permettre au destinataire prévu de comprendre la signification du message. C'est une fonction bidirectionnelle (vous devez être capable d'annuler tout brouillage que vous avez fait au message). Ceci est conçu pour protéger les données en transit.

Si vous recherchez un contexte général sur la différence entre les algorithmes symétriques et asymétriques et un aperçu général de ce qu'est le cryptage, commencez ici. Cet article couvrira principalement deux des algorithmes de chiffrement les plus couramment utilisés.

D'une manière générale, il y avait un problème majeur avec les algorithmes symétriques lors de leur création - ils ne fonctionnaient efficacement que si les deux parties connaissaient déjà le secret partagé. Si ce n'était pas le cas, il était extrêmement difficile d'échanger une clé en toute sécurité sans un tiers.

Et si un tiers obtenait la clé, il était très facile pour lui de briser le cryptage, ce qui allait à l'encontre de l'objectif de communication sécurisée.

Diffie-Hellman a résolu ce problème en permettant à des étrangers d'échanger des informations sur des canaux publics qui peuvent être utilisés pour former une clé partagée. Une clé partagée est difficile à déchiffrer, même si toutes les communications sont surveillées.

Comment fonctionne Diffie-Hellman?

Diffie-Hellman est ce qu'on appelle un protocole d'échange de clés. Il s'agit de l'utilisation principale de Diffie-Hellman, bien qu'il puisse également être utilisé pour le cryptage (ce n'est généralement pas le cas, car il est plus efficace d'utiliser DH pour échanger des clés, puis de passer à un cryptage symétrique (beaucoup plus rapide) pour la transmission de données. ).

La façon dont cela fonctionne est la suivante:

En gros, il y a deux parties, Alice et Bob, qui s'accordent sur une couleur de départ (arbitraire mais doit être différente à chaque fois). Ils ont aussi une couleur secrète qu'ils gardent pour eux. Ils mélangent ensuite cette couleur avec la couleur partagée, ce qui donne deux couleurs différentes. Ils passent ensuite cette couleur à l'autre partie, qui la mélange avec leur couleur secrète, ce qui donne la même couleur secrète de fin.

Cela repose sur l'idée qu'il est relativement facile de mélanger deux couleurs ensemble, mais il est très difficile de les séparer afin de trouver la couleur secrète. En pratique, cela se fait avec les mathématiques.

Par exemple:

  1. Bob et Alice sont d'accord sur deux nombres, un grand premier, p = 29, et une base g = 5
  2. Maintenant, Bob choisit un nombre secret, x (x = 4) et fait ce qui suit: X = g ^ x% p (dans ce cas,% indique le reste. Par exemple, 3% 2 est 3/2, où le reste est 1) . X = 5 ^ 4% 29 = 625% 29 = 16
  3. Alice choisit également un nombre secret, y (y = 8) et fait ce qui suit: Y = g ^ y% p. Y = 5 ^ 8% 29 = 390,625% 29 = 24
  4. Bob envoie X à Alice et Alice envoie Y à Bob.
  5. Puis Bob fait ce qui suit: K = Y ^ x% p, K = 24 ^ 4% 29 = 331,776% 29 = 16
  6. Alice fait alors ce qui suit: K = X ^ y% p, K = 16 ^ 8% 29 = 4,294,967,296% 29 = 16

La grande chose (* peut-être magique *) à ce sujet, c'est que Bob et Alice ont le même numéro, K, et peuvent maintenant l'utiliser pour parler en secret, car personne d'autre ne connaît K.

La sécurité de ce protocole repose sur plusieurs éléments:

  1. (Fait) Il est relativement facile de générer des nombres premiers, même de grands nombres premiers (comme p).
  2. (Fait) L'exponentiation modulaire est facile. En d'autres termes, il est relativement facile de calculer X = g ^ x% p.
  3. (Hypothèse basée sur la puissance de calcul actuelle et les mathématiques) L'extraction de racine modulaire sans les facteurs premiers est très difficile. Essentiellement, il est très difficile de trouver K sans connaître x et y, même si vous avez espionné le trafic et pouvez voir p, g, X et Y.

Ainsi, en supposant que cela a été mis en œuvre correctement, il est relativement facile de faire les calculs nécessaires pour créer la clé, mais il est extrêmement difficile et prend du temps de faire les calculs nécessaires pour essayer de casser la clé en la forçant brutalement.

Même si un attaquant pouvait compromettre cette clé, Diffie-Hellman permet un secret de transmission parfait.

Qu'est-ce que le secret de transmission parfait?

C'est l'idée que si vous déchiffrez le cryptage que le serveur utilise pour communiquer maintenant, cela ne signifie pas que toutes les communications que le serveur a jamais effectuées peuvent être lues.

En d'autres termes, il vous permet uniquement de voir les communications qui sont actuellement utilisées (c'est-à-dire avec cette clé secrète). Étant donné que chaque ensemble de communications a une clé secrète différente, vous devrez les déchiffrer toutes séparément.

Ceci est possible si chaque session a une clé éphémère différente pour chaque session. Parce que Diffie-Hellman utilise toujours de nouvelles valeurs aléatoires pour chaque session (générant donc de nouvelles clés pour chaque session), il est appelé Diffie Hellman éphémère (EDH ou DHE). De nombreuses suites de chiffrement l'utilisent pour obtenir un secret de transmission parfait.

Comme Diffie-Hellman vous permet d'échanger des éléments clés en texte clair sans vous soucier de compromettre le secret partagé, et que le calcul est trop compliqué pour qu'un attaquant puisse utiliser la force brute, l'attaquant ne peut pas dériver la clé de session (et même s'il le pouvait, en utilisant des clés différentes, éphémères, pour chaque session signifie qu'ils ne pouvaient espionner que cette session - pas aucune dans le passé ou le futur).

Le transfert de secret est activé avec n'importe quel échange de clé Diffie-Hellman, mais seul l'échange de clé éphémère (une clé différente pour chaque session) fournit un secret de transfert parfait.

Voici un article de Scott Helme qui en parle plus en détail et explique comment l'activer sur vos serveurs.

Quelles sont les limites de Diffie-Hellman?

La plus grande limitation de DH est qu'elle ne vérifie pas l'identité. En d'autres termes, n'importe qui peut prétendre être Alice ou Bob et il n'y a pas de mécanisme intégré pour vérifier que sa déclaration est vraie.

De plus, si la mise en œuvre n'est pas effectuée de manière sécurisée, l'algorithme pourrait être craqué avec suffisamment de ressources dédiées (peu probable, mais possible pour les équipes académiques ou les acteurs des États-nations).

Par exemple, cela peut se produire si le générateur de nombres aléatoires n'est pas fourni avec une entropie adéquate pour supporter la force souhaitée - en d'autres termes, parce que les nombres générés par ordinateur ne sont jamais vraiment aléatoires, le degré auquel vous avez injecté artificiellement l'incertitude compte pour la force. de votre mise en œuvre.

De plus, une attaque a été démontrée en 2015 qui a montré que lorsque les mêmes nombres premiers étaient utilisés par de nombreux serveurs au début de l'échange de clés, la sécurité globale de Diffie-Hellman était plus faible que prévu.

Essentiellement, un attaquant pourrait simplement précalculer l'attaque contre ce nombre premier, ce qui facilite la compromission des sessions pour tout serveur qui a utilisé ce nombre premier.

Cela s'est produit parce que des millions de serveurs utilisaient les mêmes nombres premiers pour les échanges de clés. Le précalcul de ce type d'attaque nécessite toujours des ressources universitaires ou nationales et il est peu probable qu'il ait un impact sur la grande majorité des gens.

Cependant, heureusement pour ceux qui doivent s'inquiéter des attaquants des États-nations, il existe une manière différente de réaliser l'échange de clés DH en utilisant la cryptographie à courbe elliptique (ECDHE). Cela sort du cadre de cet article, mais si vous souhaitez en savoir plus sur les mathématiques derrière cet échange, consultez cet article.

Pour un aperçu plus détaillé des faiblesses de DH, consultez ce livre blanc et ce site Web.

RSA

RSA porte le nom des créateurs - Rivest, Shamir, Adleman - et c'est une manière de générer des clés publiques et privées.

Techniquement, il existe deux algorithmes RSA (l'un utilisé pour les signatures numériques et l'autre utilisé pour le cryptage asymétrique.) - cet article couvre l'algorithme de cryptage asymétrique.

Cela permet l'échange de clés - vous affectez d'abord chaque partie aux clés publiques / privées de la transaction, puis vous générez une clé symétrique, et enfin, vous utilisez les paires de clés publiques / privées pour communiquer en toute sécurité la clé symétrique partagée.

Étant donné que le cryptage asymétrique est généralement plus lent que le cryptage symétrique et ne s'adapte pas également, l'utilisation du cryptage asymétrique pour échanger en toute sécurité des clés symétriques est très courante.

Alors, comment ça marche?

  1. Choisissez 2 très grands nombres premiers (au moins 512 bits ou 155 chiffres décimaux chacun), x et y (ces nombres doivent être secrets et choisis au hasard)
  2. Trouvez le produit, c'est-à-dire z = x * y
  3. Sélectionnez un entier public impair, e, entre 3 et n - 1, et n'a pas de facteurs communs (autres que 1) avec (x-1) (y-1) (il est donc relativement premier à x - 1 et y - 1 ).
  4. Trouvez le plus petit commun multiple de x - 1 et y - 1, et appelez-le L.
  5. Calculez l'exposant privé, d, à partir de x, y et e. de = 1% L. d est l'inverse de e% L (vous savez qu'il existe un inverse car e est relativement premier à z - 1 et y - 1). Ce système fonctionne car p = (p ^ e) ^ d% z.
  6. Sortie (z, e) comme clé publique et (z, d) comme clé privée.

Maintenant, si Bob souhaite envoyer un message à Alice, il génère le texte chiffré (C) à partir du texte brut (P) en utilisant cette formule:

C = P ^ e% z

Afin de décrypter ce message, Alice calcule ce qui suit:

P = C ^ d% z

La relation entre d et e garantit que les fonctions de cryptage et de décryptage sont inverses. Cela signifie que la fonction de décryptage est capable de récupérer avec succès le message d'origine, et qu'il est assez difficile de récupérer le message d'origine sans la clé privée (z, d) (ou les facteurs premiers x et y).

Cela signifie également que vous pouvez rendre z et e publics sans compromettre la sécurité du système, ce qui facilite la communication avec d'autres personnes avec lesquelles vous n'avez pas déjà de clé secrète partagée.

Vous pouvez également utiliser les opérations inversées pour obtenir une signature numérique du message. Tout d'abord, vous utilisez l'opération de déchiffrement sur le texte brut. Par exemple, s = SIGNATURE (p) = p ^ d% z.

Ensuite, le destinataire peut vérifier la signature numérique en appliquant la fonction de cryptage et en comparant le résultat avec le message. Par exemple, m = VERIFY (s) = S ^ e% z.

Souvent, lorsque cela est fait, le texte brut est un hachage du message, ce qui signifie que vous pouvez signer le message (quelle que soit sa longueur) avec une seule exponentiation.

La sécurité du système repose sur plusieurs éléments:

  1. (Fait) Il est relativement facile de générer des nombres premiers, même de grands nombres premiers (comme x et y).
  2. (Fait) La multiplication est facile. Il est très facile de trouver z.
  3. (Hypothèse basée sur les mathématiques actuelles) La factorisation est difficile. Étant donné z, il est relativement difficile de récupérer x et y. C'est faisable, mais cela prend du temps et coûte cher.

    Selon une estimation, la récupération des facteurs premiers d'un nombre de 1024 bits prendrait un an sur une machine qui coûterait 10 millions de dollars. Doubler la taille augmenterait de façon exponentielle la quantité de travail nécessaire (plusieurs milliards de fois plus de travail).

    Au fur et à mesure que la technologie progresse, ces coûts (et le travail requis) diminueront, mais à ce stade, ce type de cryptage, correctement mis en œuvre, est une source peu probable de compromis.

    En général, les seuls hackers avec ce type d'argent et se consacrant à une seule cible sont les États-nations. De plus, s'il existe un moyen plus simple de compromettre un système (voir ci-dessous), c'est probablement une meilleure option.

4. (Fait) L'exponentiation modulaire est facile. En d'autres termes, il est relativement facile de calculer c = p ^ e% z.

5. (Fait) L'extraction de racine modulaire - inverser le processus ci-dessus - est facile si vous avez les facteurs premiers (si vous avez z, c, e et les facteurs premiers x et y, il est facile de trouver p tel que c = p ^ e% z).

6. (Hypothèse basée sur la puissance de calcul actuelle et les mathématiques) L'extraction de racine modulaire sans les facteurs premiers est très difficile (si vous avez z, c, e, mais pas x et y, il est relativement difficile de trouver p tel que c = p ^ e% z, en particulier si a est suffisamment grand).

Vous voulez en savoir plus sur les mathématiques auprès de personnes beaucoup plus intelligentes? Consultez cet article.

Génial, quel est le meilleur?

Cela dépend de votre cas d'utilisation. Il existe quelques différences entre les deux algorithmes - tout d'abord, le Perfect Forward Secrecy (PFS), dont nous avons parlé plus tôt dans le contexte de Diffie-Hellman. Bien que techniquement vous puissiez générer des paires de clés RSA éphémères et fournir un secret de transmission parfait avec RSA, le coût de calcul est beaucoup plus élevé que pour Diffie-Hellman - ce qui signifie que Diffie-Hellman est un meilleur choix pour les implémentations SSL / TLS où vous voulez un secret de transmission parfait. .  

Bien qu'il existe des différences de performances entre les deux algorithmes (en termes de travail requis du serveur), les différences de performances ne sont généralement pas assez importantes pour faire une différence lors du choix de l'un par rapport à l'autre.

Au lieu de cela, en général, la principale considération pour déterminer ce qui est le mieux dépend de celui qui est le plus pris en charge pour votre cas d'utilisation (par exemple, lors de la mise en œuvre de SSL, vous voudrez Diffie Hellman en raison du secret de transmission parfait) ou de celui qui est le plus populaire ou accepté comme la norme dans l'industrie.

Par exemple, alors que Diffie-Hellman était approuvé par le gouvernement américain et soutenu par un organisme institutionnel, la norme n'a pas été publiée - alors que RSA (normalisé par une organisation privée) fournissait une norme gratuite, ce qui signifie que RSA est devenu très populaire parmi les organisations privées.

Si vous souhaitez en savoir plus, voici un excellent fil de discussion sur les différences.

Vous souhaitez apprendre à utiliser les attaques cryptographiques par les pirates informatiques? Essayez cet ensemble de défis de Cryptopals.

Plus j'en apprends sur la cryptographie, plus je pense qu'Alice et Bob devraient probablement parler en personne.

- Paul Reinheimer (@preinheimer) 13 mars 2017