CoursTLS-SEC/Crypto/cours.md
2021-10-20 11:16:06 +02:00

23 KiB
Raw Permalink Blame History

Introduction à la Cryptographie

Responsable : vincent.migliore@insa-toulouse.fr

Definitions

La cryptographie est la science qui vise à écrire les secrets.

Il faut distinguer la Cryptographie de la cryptologie ainsi que de la crpytanalyse.

  • La Cryptologie est la science du secret en général et ne concerne pas nécessairement un savoir
  • La ccryptanalyse concerne elle la science qui vise à briser les secrets.

Principes de Kerkhoffs

1- Théoriquement un secret parfaitement gardé repose sur un algorithme inviolable. En revanche, on peut se contenter en pratique d'utiliser des algorithmes qui nécessiteraient un temps et des ressources déraisonnés pour être cassés.

2- La construction ainsi que la conception ne doivent pas nécessiter de secret. Le secret de chiffrement est externe à la conception du système. Ainsi, en récupérant un système, on ne peut pas en connaitre le secret et accéder à la donnée.

Cryptographie moderne

  • Sécurité basée sur des proobl_èmes mathématiques calculatoirement complexes.
  • La domaine est hautement standardisée et les algorithmes de chiffrement sont majoritairement publics
  • Il est fortement recommandé d'utiliser des librairies publiques et ne pas s'aventurer à reconstituer un algorithme de chiffrement fait maison, cela pourrait mettre en danger le secret associé.

En revanche, certaines brèches restent encore ouvertes.

  • Il existe toujours des failles liées aux attaques physiques
    • Injection de fautes
    • Side channels | Cannaux de fuites
  • Les ordinateurs quantiques sont aujourd'hui une source d'inquiétude puisqu'ils sont capables de résoudre les problèmes mathématiques bien plus rapidement que des ordinateurs quantiques.
    • Se pose alors la question de la mise en oeuvre d'algorithmes de protection post-quantiques

Un Algorithme Post quantique est un algorithme capable de tourner dans un temps et avec des ressources raisonnables sur un ordinateur standard, mais qui pour autant n'a pas encore été cassé par un ordinateur quantique.

Les acteurs de la standardisation

Nation Institute of Standards Technology - NIST

Prend en charge la régulation des algorithmes de cryptographie. Les enjeux actuels reposent sur la mise en place d'algorithmes post-quantiques stables.

Internet Engineering Task Force - IETF

Prend en charge la régulation de la sécurité dans les protocoles de l'internet et notamment TCP/IP

ISO

Prend en charge tous les autres domaines spécifiques.

Vocabulaire important

Anglais Français Explication
Plain Text Message clair Message non protégé
Cipher text Message chiffré Message protégé
Keygen Keygen Générateur de clés de chiffrement
Encryption Chiffrement Mécanisme qui chiffre un message clair
Decryption Déchiffrement Mécanisme qui extrait un message à partir d'un chiffré
Symetric Key Clé symétrique Même clé utilisée pour chiffrer et déchiffrer un message
Asymetriic key Clé asymétrique Clé différente est utilisée pour chiffrer et déchiffrer

Dans le cas de mécanismes asymétriques, on considère en général que la clé de chiffrement est une clé publique et à contrario, qu'une clé de déchiffrement est une clé privée.

On considèrera toujours que c'est Alice qui souhaite communiquer avec Bob

En général, dans un chiffrement symétrique, on parle de many to one encryption - serveur à plusieurs PC.

Propriétés essentielles d'un algorithme de chiffrement

  • Confidentialité : Une écoute ne permet pas de comprendre le message
  • Intégrité : Le récepteur peut détecter si le message reçu est différent du message émis | i.e. checksum etc
  • Authentification : Capacité à reconnaître ses destinataires et éviter les usurpations
  • Non répudiation : Avec des clés différentes on peut distinguer qui a émis quelle donnée et ainsi il n'y a pas de doute sur qui a émis telle ou telle donnée

Les différents types de canaux

  • Non-Sécurisé : Ecoute possible et modification possible des paquets
  • Sécurisé : Ni écoute ni modification possible
  • Confidentiel : Pas d'écoute possible
  • Authentique : Pas de modification par un tiers grâce par exemple à un contrôle d'intégrité

Notation fonctionnelle

f(message,key) = chiffré

Algorithmes déterministes

Deux entrées identiques mèneront à une clé identique. Dans le cas de la cryptographie, il y a absolue nécessité que Encrypt et Decrypt soient des algorithmes déterministes. Ainsi on peut attester la non déformation des messages lors de leur transport.

Une autre propriété d'Encrypt et Decrypt est appelée la consistance : \forall m \in M, \forall S_k \in K, Decrypt(Encrypt(m,S_k),S_k)=m

Algorithmes aléatoires

Keygen est un algorithme non déterministe, Il peut attribuer une clé avec certaines probabilités en fonction des entrées. On utilise en général deux types de lois : Uniforme pour des algorithmes classiques, et plutôt Gaussienne pour des algorithmes post-quantiques.

Sécurité d'un algorithme de chiffrement/déchiffrement

Il est essentiel que le chiffré ne donne aucune information sur la clé de chiffrement, ainsi personne ne peut, en interceptant le message, avoir des pistes qui pourraient orienter les recherche pour briser le secret.

Est il possible d'avoir un secret parfait ?

Cas du XOR | Ou Exclusif | Addition modulo 2

Cette équation est toujours vraie : x \oplus y \oplus x = y et XOR est commutatif. Cela permettrait donc de chiffrer de façon symétrique un message très facilement : message \oplus clé = chiffré et à partir du chiffré, on pourrait facilement faire chiffré \oplus clé = message \oplus clé \oplus clé = message.

Ce type de chiffrement instaure deux sécurités immédiates :

  • Sans connaissance de la clé, un chiffré peut donner n'importe quel autre message en fonction de la pseudo clé qui serait utilisée pour déchiffrer
  • La sortie d'un tel chiffrement est totalement uniforme (car la création de la clé serait issue d'un keygen uniforme : message indépendant de la clé \oplus clé uniforme = une sortie totalement uniforme).
    • Cela permet d'empêcher les tentatives d'attaques fréquentielles

Problèmes

On a besoin d'une clé au moins aussi longue que la longueur du message. D'autant que d'après Shanon, on a beosin que la taille de la clé soit à minima supérieure ou égale à celle du message, autrement, il existe un algorithme capable de casser le secret.

En revanche, on peut se servir de ce type de protection dans le cas d'algorithmes one to many, qui correspondent en général à des algorithmes de signatures.

Chiffrements symétrique

Pour optimiser le chiffrement on souhaiterait

  • de petites clés
    • on accepte de réduire la sécurité sur le secret parfait pour parvenir à avoir de petites clés ET que les ressources nécessaires pour briser le secret sont démesurées
  • un temps de chiffrement/déchiffrement raisonnable sur des machines standards.

Chiffrement à flots | basé sur le chiffrement XOR

Chiffrement à blocs

  • Messages découpés en blocs de taille fixe n
  • La clé est choisie comme une chaine aléatoire de caractères de taille k
  • Chaque bloc est chiffré par le même mécanisme de chiffrement avec la clé et produit ainsi des blocs chiffrés de taille n
  • Déchiffrement basé sur la même clé et la même taille de blocs

On considère un chiffrement à bloc réussi si

  • Les blocs sont assimilables à des permutations
  • Un n-bit block chiffré est indistinguable d'un random n-bit block

En pratique, pour valider ce type de chiffrement, on se base sur les propriétés de Shannon :

  • Diffusion : Si 1 bit change dans le bloc d'origine, il faut que statistiquement, plus de la moitié du bloc chiffré soit impactée
  • Confusion : 1 bit du bloc chiffré doit être lié à plusieurs bits de la clé

Réseau de Substitutions/Permutations

Une autre techinque de chiffrement consiste à faier passer le message dans une chaine de bloc de substitutions permutations :

  • Chacune des fonctions de S/P est réversible
  • Chaque itération de S/P est appelée un Round
  • Plus il y a de round, plus le chiffré en sortie sera uniforme
  • Ici, on considère que le niveau de sécurité est proche de celui d'une attaque par force brute qui est une recherche à tatons de la clé de chiffrement

En pratique, on va avoir un algorithme qui délivre une clé maitre qui sera dérivée pour chaque étage. autrement dit, les clés de chaque étagesont conditionnées par une seule clé maître, et ne sont pas toutes indépendantes.

on a donc ici nb_{itération de recherches} = 2^{security level} = 2^{taille de la clé}

On parle de S-Box pour les substitions et P-Box ou D-Box pour Permutation ( Ou diffusion).

S-Box

Substitue un symbole pour un autre. Cela contribue à la confusion puisque ça rend la sortie inintelligible. D'une pière deux coups, cela accentue également la non linéarité de la sortie.

P-Box ou D-Box

Echange deux symboles les uns par rapport aux autres. Cela contribue à la diffusion puisque cela déplace les symboles d'un endroit à l'autre. Par contre cela n'a aucun effet sur la linéarité de la sortie.

AES

Il s'agit d'un mécanisme basé sur un réseau de S/P. Sa conception est très intéressante puisque la sécurité et l'implémentation ont été étudié lors du design de la solution.

Nous sommes ici avec un chiffrement symétrique.

On est sur des blocs de 128 bits en général.

L'état interne est composé d'une matrice d'octets de 4x4. 4 operations sont exécutées sur l'état interne à chacun des rounds.

1 - AddRoundKey

  • xor between state and round-key.
  • if message independant from key, and key uniform, then the new state
  • looks uniform.

2 - SubBytes

  • Non-linearity: Minimization of input-output correlation.
  • Complexity: Complex expression in GF(28).
  • Simple implementation: Look-up table (and must be since litteral expression complex).

3 - ShiftRows

  • Variable byte rotation of each line depending on line index.
  • First line: no rotation.
  • Second row: 1 byte rotation.
  • Third row: 2 bytes rotation.
  • Fourth row: 3 bytes rotation.

4 - MixColumns

  • Column per column scrambling of coefficients. Equivalent to multiplying each column by following matrix:

$\begin{pmatrix} 2 & 3 & 1 & 1\ 1 & 2 & 3 & 1\ 1 & 1 & 2 & 3\ 3 & 1 & 1 & 2 \end{pmatrix}$

Chiffrement de grands messages

Electronic Code Block

The message is split into blocks matching the size of Block-Ciphers block length. Each block is encrypted with the same key. Pros:

  • Simplest construction.
  • Destination can decrypt a specific block without extra computations.
  • Vulnerabilities?

Comment évaluer la sécurité ?

Propriétés de Sécurité :

Sans information sur la clé, aucune info du chiffré n'informe d'aucune info du clair. : Sécurité Sémantique

Adversary capabilities are defined as indistinguishability games:

  • IND-KPA (known plaintext-attack): adversary sees pairs $(m_i , Enc(m_i))$.

  • IND-CPA (chosen plaintext-attack): adversary SELECTS messages mi and ASKS an entity to encrypt m_i

  • IND-CCA: More information during asymmetric encryption lesson.

IND-CPA

Win condition

  • L'adversaire gagne si : Pr[b = b'] > 1/2.
  • Si Pr[b = b'] = 1/2, alors l'adversaire peut seulement deviner au hasard quel message a été chiffré.
  • Advantage: ACPA = |Pr[b = b'] 1/2| = \in

Intégrité et Authentification

Cahier des charges

  • On voudrait un petit bout de code comparé à la donnée à checker.

  • On souhaiterait une robustesse intrinseque aux bitflips.

  • On voudrait qu'il soit impossible de trouver un antécédant du code chiffré à partir de ce petit bout code.

On parle ici de codes de contrôles d'intégrité, ou fonction de Hash.

Propriétés usuelles :

  • En connaissant h_{m_1} = H(m_1), trouver m_2 est difficile tel que H(m_2)=h_{m1}
  • Pour un message m_1, trouver m_2 tel que H(m_1) = H(m_2) est difficile
  • Trouver m_1 et m_2 tel que H(m_1)=H(m_2) est difficile.

Etude de la sécurité des fonctions de hashage

Est ce que la pire des attaques concernant les fonctions de hashage est la recherche exhausitve

On parle d'attaque annivesaire en lien avec le paradoxe de l'anniversaire.

Notation

Soit \mathbb{Z}_M -> \mathbb{Z}_H une fonction de Hash avec H sorties possibles. On note

  • p(n;H) la probabilité de trouver au moins une collision après n essais
  • n(p,H) le nombre d'essais avant de trouver une collision avec une probabilité p.

Estimation of p(n; H)

  • p(n; H) = \frac{365!}{(365n)!365^n} \simeq 1 e^{n2 /(2H)}.
  • (Birthday attack exact formula + application of stirling formula
  • (n! \simeq \sqrt{2\pi n}(\frac{n}{e})^n)
  • application of taylor expansion at order 2). Estimation of n(p; H)
  • n(p; H) = \sqrt{2H\ln\frac{1}{1p}}

Au vu des chiffres induits par ces valeurs, on estime qu'un mécanisme sécurisé l'est à partir de 80 bits de niveau de sécurité, soit 2^{80}

Construction d'une fonction de Hash - Merkle-Dagmard (MD5, SHA-1, SHA-2...)

Ici, f est une fonction de compression, elle produit une sortie strictement plus petite que l'entrée. Le message d'entrée est masqué ce qui rend la longueur des messages masqués comme un multiple de l'entrée de f.

Merkle-Damgard ˚ strenghtening: Size of message is appended at the end of padded message. It makes collision security of hash function only relying on collision security of f

Configuration

Le message est splité en blocs de 64 octets. F produits 128 bits IV.

Limites

En attaque anniversaire, 2^{64} < 2^{80}, ce n'est donc pas considéré comme sécurisé en cryptographie.

On a également une vulnérabilité au attaques par collision à préfixes choisis : ∀(m1, m2), at most 239 calls are required to find (s1, s2) such as MD5(m1||s1) = MD5(m2||s2). Has been successfully used to forge a fake server certificate from legal authority.

Other limitation

  • MD5 computation is fast: A GPU can compute about 150 million hashes per second (Yanjun et al., 2014).
  • Chosen Prefix Attack: $150 millions \simeq 2^{27} =⇒ 2{39}/2^{27} = 2^{12} sec = 1h 8m

Secure Hash Algorithm (SHA) familly

  • SHA-1: Collision in 260 calls (slightly better than MD5), but not secure from modern cryptography point of view. (160 bit output)
  • SHA-2: Different output sizes (SHA-224, SHA-256, SHA-384, SHA-512,...). No known vulnerability, just avoid implementations with 31/64 rounds.
  • SHA-3: Alternative to SHA-2 (not a replacement). More flexibility (can be used to cover several cryptographic algorithms).

Sécurité des fonctions de Hash seules

Intégrité avec authentification - AEAD - Authenticated Encryption with Associated Data

Limite des fonctions de Hash en pratique

Si on considère qu'un utilisateur télécharge un programme depuis un serveur officiel, un attaquant pourrait intercepter la communication et remplacer le programme par un malveillant. En contre-mesure on pourrait imaginer que le serveur et l'utilisateur partagent un secret, inconnu par l'attaquant, et ils peuvent utiliser une construction appelée MACs, similaire aux fonctions de hash pour authentifier le message reçu.

Préfixe secret

Definition

Pour un message m et un secret s, MAC=H(s||m). Ce n'est pas une bonne solution puisque Merkle-Damgard est basée sur des fonctions qui sont vulnérables aux attaques par extension.

Principe On note p le block de padding d'un message s||m. Avec une paie (m,MAC=H(s||m)), un attaquant peut forger une paire (m',h') ou m'=M||p||K et h' obtenu en hashant K avec IV=h.

Suffixe secret

Définition

Pour un message m et un secret s, MAC = H(m||s).

Quelques faiblesses architecturelles demeurent

  • Vulnérabilité hors ligne d'une attaque par seconde-preimage: (i.e. For given m1, finding m2 such as H(m1) = H(m2)). An attacker can search second pre-image offline (i.e. without information on the secret s) and find m2. Then, attacker can substitute m1 by m2.

  • Vulnerability on offline collision attack (weak collision): (i.e. Find m1 and m2 such as H(m1) = H(m2)). If an attacker can ask an authority to compute a MAC, then he asks a MAC for m1 and an substitute this for m2.

Une construction robuste : HMAC

HMAC(S_k,m) = H((S_k)\oplus opad) || H((S_k\oplus ipad)||m))

Propriétés:

Une propriété de HMAC est que la fonction de compression n'est pas résistante aux collisions. (seulement PRF est requis) si elle est utilisée intentionnellement => MD5 et SHA-1 peuvent êtrer utilisée pour HMACs

Faiblesse en cas de serveur malicieux - cas de MD5

Un serveur a computé un prefix p tel que p||m2 entre en collision. (i.e. MD5(p||m1)=MD5(p||m2)). Que se passe-t-il si S_k = p\oplus ipad ?

HMAC(Sk , m1) = MD5((Sk ⊕ opad)||MD5(p||m1)) = MD5((Sk ⊕ opad)||h0) HMAC(Sk , m2) = MD5((Sk ⊕ opad)||MD5(p||m2)) = MD5((Sk ⊕ opad)||h0)

Donc HMAC(Sk , m1) = HMAC(Sk , m2)

Famille des Algorithmes MAC

Aglo MAC basé sur un chiffrement par blocs - CMAC

CMAC est construit à partir d'un chiffrement par bloc qui opère en mode CBC. NIST SP800-38B. C'est une amélioration de CBC-MAC qui avait des vulnérabilités lorsque les messages avaient des longueurs variables. La variante XCBC-MAC a été proposée en 2003.

Algo MAC basé sur un HASH - HMAC

HMAC est aussi appelée Keyed-Hash message authentification code est construit à partir d'un e fonction de hash.

Intégrité, Authentification, et Confidentialité

GMC et GMAC sont des modes d'opérations de chiffrement par bloc qui intègrent directement ces principes.

Exemple de MACs implémentés en OpenSSL

CMAC, GMAC, HMAC, KMAC, SiphHASH, Poly1305 (Bernstein, selectionné par google pour remplacer RC4 dans TLS/SSL).

MAC + Encryption : How to ?

Le process le plus rapide pour chiffrer et certifier est Encrypt and Mac puisqu'on parallélise les process Encrypt et Mac.

Le process qui mène à la vérification la plus rapide est Encrypt then Mac, ou on peut vérifier le MAC sans avoir à déchiffrer le plain.

Le plus vulnérable au chosen plain-text attack, est la construction Encrypt and MAC puisque le Hash est directement correlé au plain-text.

Les sécurité de ces trois construction ont été étudiées, le plus complet est le process ENCRYPT-THEN-MAC.

Constructions Hybrides

AES-GCM

Ici, le chiffrement est implémenté avec AES en mode compteur pour générer un flux de clés XOR du message clair. On reprend ainsi le principe du OneTimePad. Le MAC généré est basé sur un Hashage universel, utilisant un hash polynomial dans un champ Galois.

Ce process peut être parallélisé, mis en pipeline et supporte des messages de tailles variables.

GCM utilise donc le parallélisme encrypt then MAC, LA STAR.

Autre utilisation des fonctions de Hash, PasswordChecking

Use-Case : SHA-1

No storage

  • Number of combinations is $36^8 = 2^{40} $⇒ brute force requires 240 calls to SHA-1 before expecting finding a password.
  • Modern 4GHz CPU: 3.5 MHash/sec = 2^{21} Hash/sec =⇒ 2 19s = 40 days. Full storage Dictionnary of all possible hashes possible:
  • Number of combinations: 368 = 2^{40}
  • Time complexity: 240 dictionnary entry checking in the worst case, for 4 GHz processor = 2^{32} op/sec. ⇒ 2^{8} sec = 4 min.
  • Space complexity: 243 bytes of storage (without password storage) ⇒ 8 Terabytes of data

Table Arc-en-ciel

Ici, H est une fonction de Hash, R, une fonction de réduction qui transforme les hash en valeur alphanumérique. On stocke uniquement les left_most et right-most strings.

Attack We note h the hashes obtained by attacker after a successfull attack.

  • step 1: Check if h is in database. If it is, take the corresponding password p and compute R2(H(R1(H(p)))) ⇒ done.
  • step 2: Check if H(R2(h)) is in database. If it is, take the corresponding password p and computes H(R1(H(p))) ⇒ done.
  • step 3: Check if H(R1(H(R2(h)))) is in database. If it is, take the corresponding password p ⇒ done.
  • step 4: Fail

Renforcement des PasswordChecking

  • Strenghtening using random salt
    • Before storing hashed password p, generate a large random number r and store H(r||p) and r.
    • Rainbow tables are penalized since they are construct with usual characters. Moreover, even if attack succeeds, attack still needs to remove salt.
  • Strenghtening using slow hash functions
    • Since attacker must execute hash function many times and legitimate server only one, slowing hash function drastically penalize attacker.

Autre construction des PasswordCheck

Preuve de travail | Proof of work

Pour éviter le spam ou le déni de service, oh force les hashes des émetteuurs de message à avoir 20 bits de poids forts à zéro, en utilisant un custom header. C'est également utilisé pour le bitcoin.

Dérivation de clé

Des que les fonctions de hash ont des sorties uniformes, ont peut également les utiliser pour créer des secrets uniformes.

Definitions of Random Number Generators

True Random Number Generator (TRNG)

  • Généralement créé par hardware, avec une forte entroie puisqu'on n'a aucun moyen de remonter à la source.
  • Peut être biaisée par la loi utilisée (i.e. si ce n'est ni gaussien ni uniforme), mais chacun des biais peut être contré par des algorithmes que l'on appelle des extracteurs

Pseudo Random Number Generator

  • Entropie Finie, au bout d'un moment on peut prédire les sorties

Exemple de générateurs d'aléas purs :

  • Bruit thermique autour d'une résistance
  • Décomposition atomique

Partage de clés dans un monde symétrique

Cas de deux utilisateurs, si le secret est déjà partagé ok, sinon, il yè a échange de clé sur un canal sûr, ou trouver un moyen de le partager astucieusement.

Cas d'un groupe d'utilisateurs : Partager un secret peut être dangereux puisqu'il peut y avoir des usurpation d'identité, de l'interception de messages... On peut aussi envisager d'avoir un secret par paire d'uitlisateurs, mais cela nécessiterait énromément de clés.

En pratique on adopte un modèle serveur client avec une clé par client.

Comment échange-t-on le secret

cf . slides