23 KiB
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-Cipher’s 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)
, trouverm_2
est difficile tel queH(m_2)=h_{m1}
- Pour un message
m_1
, trouverm_2
tel queH(m_1) = H(m_2)
est difficile - Trouver
m_1
etm_2
tel queH(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!}{(365−n)!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}{1−p}}
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