Cryptographie

Quelques éléments regroupés pour faciliter la navigation parmi tous ces algorithmes, mode opératoires et calculs.

Tous les schémas présentés viennent des pages respectives sur Wikipedia et sont publiées sous CC0. Voir par exemple Block cipher mode of operation.

Symétrique

Types de chiffrement symétrique

• Chiffrement par bloc
• Chiffrement par flot: super important d'avoir un nonce qui n'est pas fixé, sinon le keystream est fixe, donc c'est comme un one time pad avec une réutilisation de la même clé à chaque fois...

Modes opératoires

EBC très mauvaise idée, fuite d'info, si 2 blocs égaux on aura le même résultat. image très visible.

Counter mode, genère un algo de flot avec un keystream

CBC

CTR

ECB

Authentification

HMAC

CBC-MAC

seulement sûr pour messages de taille fixe.

Vulnérable à des changements de taille de messages. Par exemple, avec un un message de 1 bloc et son tag, on peut forger un nouveau message de 2 blocs:

• ( signifie la concaténation de 2 blocs de messages)
• Explication: En ajoutant le même bloc avant, on arrive à connaitre l'entrée à gauche du XOR deux sur le 2ème bloc (il vaut ).
• On peut donc définir le message du bloc 2 à pour que résulte en simplement , ce qui va nous donner à nouveau le même tag en final.

Chiffrement authentifié

CCM

Schéma inspiré et démêlé de la slide 40 du PDF 03 de M. Duc.

GCM - Galois Counter Mode

Inclut du CTR pour le chiffrement au milieu du schéma.

Approche pour casser des constructions symétriques

De manière générale sur les constructions:

• Dessiner ou regarder le schéma des constructions
• Mettre en évidence tout ce que l'on connaît
• Définir ce qu'on cherche à faire

Quelques stratégies acquises sur les exercices, pour casser des constructions de mode opératoires.

• Le XOR () est très intéressant à manipuler comme peut être remanié en et
• Penser de mettre à zéro devant un XOR pour annuler son effet.
• Si on a un XOR qui contient 3 branches, une branche connue, une autre non connue mais constante entre les messages et la 3ème qu'on cherche. Exemple sur le one time pad avec réutlista: le texte chiffré connu, le pad inconnu
• Comprendre les parties des constructions qui sont déterministes
  • Soit par l'algorithme: par exemple AES est déterministe
  • Soit parce qu'une variable est constante pour un sous problème:
    • Exemple 1: une clé de chiffrement qui varie mais qui reste la même entre les plusieurs messages de même la communication
    • Exemple 2: un IV qui change à chaque message mais qui reste le même pour tous les blocs du message
• Qu'est-ce qu'on peut en déduire si on a messages chiffrés à disposition ?
  • Est-ce que des blocs égaux sur les 2 messages ( message 1 = message 2) donneront aussi des blocs chiffrés égaux ? Si oui, est-ce qu'on arrive à avoir des indices sur le contenu des deux messages ?

Asymétrique

Source: slides de M. Duc sur la cryptographie asymétrique (04_slides_asym.pdf).

Toute la crypto asymétrique déterministe est cassée pour le chiffrement de petits messages. Le fait d'avoir accès à la clé publique, on a accès à un oracle de chiffrement (un moyen de chiffrer des textes arbitraires), donc il suffit de tester toutes les valeurs possibles. Exemple des salaires ou des coordonnées GPS.

Diffie-Hellman

Le logarithme discret est une fonction à sens unique. Il est facile de l'utiliser mais très difficile de l'inverser.

• est un nombre premier de taille suffisante, où q est également un nombre premier plus petit
• pour être capable de multiplier et d'inverser, on a besoin du groupe multiplicatif .
• g est un élément d’ordre q du .

Etapes de Diffie-Hellman, sur un canal authentique

• Définir sur , d'ordre premier.
• Alice génère un nombre aléatoire et calcule et l'envoit à Bob.
• Bob fait pareil et calcule et l'envoit à Alice.
• Alice peut maintenant calculer la clé symétrique
• Bob fait de même . Les deux ont donc utilisé et ont bien le même secret partagé.

El Gamal

Application de Diffie-Hellman pour du chiffrement, via la partie réceptrice de la communication qui tire ses nombres aléatoires en avance, génère une paire de clé et publie la clé publique.

• Même début que Diffie-Hellman pour les paramètres publiques et la génération de .
• Clef privée
• Clef publique
• Chiffrement: un message , on tire un aléatoire -> calcul de la paire . La première partie est l'équivalent de dans Diffie-Hellman qu'on doit bien envoyer, sinon il sera impossible de déchiffer. La deuxième partie est le message multipliée par la clé publique puissance .
• Déchiffrement: avec la pair ->
• Comme g est d’ordre q, on peut travailler dans l’exposant !

Attention: Chiffrement non déterministe...

RSA

• Générer 2 grands nombres aléatoires premiers et privés
• devient publique
• Calculer , possible uniquement parce qu'on connait et en privé
• Prendre une valeur (souvent 65537)
• Calculer
• La paire = la clef publique
• La paire = la clef privée
• Chiffrement:
• Déchiffrement:

Il est possible d'accélérer ce chiffrement en passant par CRT.

Cette version RSA textbook est complètement cassée comme elle est déterministe !

RSA-OAEP

Il corrige le problème de RSA textbook en introduisant une seed aléatoire, différente à chaque message, qui sera cachée dans le message chiffré. Il utilise textbook RSA dessous.

Schéma de préparation de RSA-OAEP, le message encodé en bas est passé dans textbook RSA. signifie Mask Generating Function.

les autres sujets

TODO plus tard

ECDH

TODO plus tard

ECDSA

TODO plus tard

Signature RSA

• on créée la signature sur un message avec
• on vérifie la signature , en s'assurant que

CRT

TODO, probablement pas le temps de faire...

Quelques notes de patterns: si on connait une valeur qui est multiple de mais pas de alors on peut récupérer , car est premier le PGDC est forcément égal à .

Courbes elliptiques - ECC

Source des formules et recettes: slides de M. Duc sur les ECC (06_slides_ecc.pdf). Quelques modifications des formats des gros calculs ont été appliqués pour améliorer la vitesse de lecture.

Une courbe est un ensemble de points décrits par des tuples , avec , avec un point spécial appelé point à l'infini. Ces points sont basés sur une équation du style . Les coefficients et sont utiles dans les calculs.

Voici tous les calculs possibles, présenté sur une courbe sur . Les coordonnées sont dans et doivent respecter cette équation en modulo 5. Chaque résultat doit rester un point de la courbe, si on a la liste des points, il est facile de le vérifier.

• Génération des points parmi tous les tuples possibles
  1. Calculer tous les carrés possibles de en modulo . Ici avec à en modulo 5.
  2. Passer toutes les valeurs possibles en tant que pour trouver les valeurs qui sont des . Par exemple en modulo toujours.
  3. Reprendre les résultats qui ont donné pour générer les points associés
     • -> et
     • -> et
     • ->
  4. Résultat: tous les points trouvés sont , , , , et ne pas oublier le !!
• Inverse d'un point: il suffit de prendre l'opposé de la coordonnée Y, modulo p. Ainsi l'inverse de avec est
• Additions de points
  • si P est l'inverse de
  • si
  • si
  • Si alors on a -> formule dédiée de doublement de points
    • On cherche
    • Premier bloc: attention n'est pas la clé privée mais vient de l'équation de départ.
  • Sinon -> formule dédiée d'addition de points
    • On cherche
    • Premier bloc:
• Additions plus avancés
  • Par exemple -> doublement de points puis addition de points.

Astuces

• Pour éviter de faire de nombreux calculs, il est parfois possible de partir depuis la fin.
  • Sur une courbe à 9 points, avec un point donné, on a
  • Si on cherche , on peut partir de
  • , le calcul devient trivial à faire
  • Autre exemple:

TLS & x509.v3

TODO