Cryptographie

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

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