Introduction à la cryptographie

@secucrypt     |     cryptosec.org

sommaire

> où est la cryptographie?

> aperçu historique

> cryptographie symétrique

> cryptographie asymétrique

> fonctions de hachage

> utilisations combinées

> conclusion

où est la cryptographie?

dans les navigateurs

sur votre banque

dans votre téléphone

dans les distributeurs de billets

les cryptomonnaies - le bitcoin

la diplomatie, l'Etat

les militaires et services secrets

les délinquants

les entreprises

la presse

les ONG qui défendent les droits humains ou la nature

vous, qui croyez - ou pas - n'avoir rien à cacher

aperçu historique

> 1500 av. J.-C, sur les bords du Tigre, en Irak: une tablette d'argile contenant la recette d’un vernis codée

> 500 av. J.-C: la première utilisation militaire connue, la scytale spartiate, chiffrement par transposition (permutation de lettres)

> 5ème siècle av. J.-C : chiffrement de textes religieux par les hébreux : ex. le code Atbash, inversion de l’alphabet

- alphabet hébreux : aleph -> tau, beth -> shin

- Occidental alphabet: A -> Z , B -> Y

> 50 av. J.-C : début des codes mathématiques, le code César: utilise un décalage de 3 lettres dans l’alphabet

ce sont des exemples de chiffrement par substitution

> environ 5ème siècle : le kamasoutra recommande, entre autres arts, l’apprentissage du mlecchita-vikalpa, l’art de l’écriture secrète

> au 9ème siècle le savant arabe Al Kindi écrit le premier traité de cryptanalyse en utilisant l’analyse des fréquences
la lettre « e » étant la plus utilisée, la substitution de « e » aussi (une contre-mesure a consisté à utiliser des lipogrammes)

fréquence des lettres en français

fréquence des bigrammes en français

> 1379 : Gabriel de Lavinde publie « le nomenclateur », recueil de codes utilisés par les diplomates

> 1467 : Leon Battista Alberti propose d’utiliser plusieurs alphabets mélangés introduisant le code polyalphabétique ceci afin de contrer l’analyse des fréquences; il conçoit un cadran chiffrant aidant à utiliser ce chiffre

> 1553 : Giovanni Batista Bellaso propose pour le chiffrement polyalphabétique l’utilisation de clés littérales qu’il appelle « mots de passe »

1586, le chiffre de Vigenère

> en 1864 Charles Babbage casse le chiffre de Vigenère, une substitution polyalphabétique, inventée en 1586, grâce à une recherche de la longueur de la clé puis à des analyses de fréquences

Principes de Kerckhoffs [1/2]

> énoncés dans le « journal des sciences militaires » en 1883, ils fixent des critères pour un bon cryptosystème :

1. le système doit être matériellement, sinon mathématiquement, indéchiffrable (robustesse de l’algorithme)

2. il faut qu’il n’exige pas le secret, et qu’il puisse sans inconvénient tomber entre les mains de l’ennemi

3. la clef doit pouvoir en être communiquée et retenue sans le secours de notes écrites, et être changée ou modifiée au gré des correspondants

Principes de Kerckhoffs [2/2]

4. il faut qu’il soit applicable à la correspondance télégraphique

5. il faut qu’il soit portatif, et que son maniement ou son fonctionnement n’exige pas le concours de plusieurs personnes

6. enfin, il est nécessaire, vu les circonstances qui en commandent l’application, que le système soit d’un usage facile, ne demandant ni tension d’esprit, ni la connaissance d’une longue série de règles à observer

> A l'opposé de la "securité par l'obscurité"
> devise de Claude E. Shannon's: “The enemy knows the system”

(Wikipedia's translation)

Enigma

> la seconde guerre mondiale: Enigma, une machine électromécanique de série, améliorée par l’armée allemande

> suites de substitutions polyalphabétiques

> plus complexe, mais du même type que Vigenère

Enigma

> le code Enigma a été cassé à l’aide des premiers ancêtres de nos ordinateurs, les « bombes cryptographiques », à Bletchley Park

Retour vers le passé - Linéaire A

Ecriture de Crète ancienne - Minoens - composée de 88 signes et idéogrammes. Non déchiffrée à ce jour.

Questions!

Questions

Quel mathématicien a eu un rôle clé dans les efforts britanniques pour casser Enigma à Bletchley Park?

Qu'est-ce que PGP (Pretty Good Privacy) ?

De quoi / qui est la devise « in cryptography we trust »?

Une arme de guerre (1/2)

> Utilisées par les militaires et les diplomates, les techniques cryptographiques ont longtemps été classifiées secret défense

En France:

- considérée comme arme de guerre jusqu’en 1990

- 1996 : la procédure d’autorisation pour les produits de chiffrement est assouplie

- 1998 : libéralisation sous contrôle avec régime des tiers de séquestre

Une arme de guerre (2/2)

- 1999 : échec des tiers de séquestre, « changement fondamental d’orientation »

- 2000 : libéralisation totale de la cryptographie à 128 bits

- 2001 : loi sur la sécurité quotidienne (les fournisseurs doivent prévoir des portes dérobées)

- 2004 : l’utilisation de la cryptographie est libre

Une révolution: 1976

> en 1976 avec la publication de « New directions in cryptography » la cryptographie devient une discipline publique, le 2e principe de Kerckhoff devient la norme en permettant à la communauté internationale d’évaluer la robustesse des algorithmes (!= sécurité par l’obscurité)

> a la fin de leur présentation Whitfield Diffie et Martin E. Hellman concluent : « L'habileté dans la cryptanalyse a toujours été lourdement du côté des professionnels, mais l'innovation, en particulier dans la conception des nouveaux types de systèmes cryptographiques, est venue principalement d'amateurs. »

Question!

from itertools import starmap, cycle

key = ceciestlaclesecretequisertachiffrer

def encrypt(message):

    # convert to uppercase.
    # strip out non-alpha characters.
    message = filter(str.isalpha, message.upper())

    # single letter encrpytion.
    def enc(c,k): return chr(((ord(k) + ord(c) - 2*ord('A')) % 26) + ord('A'))

    return "".join(starmap(enc, zip(message, cycle(key))))

def decrypt(message):

    # single letter decryption.
    def dec(c,k): return chr(((ord(c) - ord(k) - 2*ord('A')) % 26) + ord('A'))

    return "".join(starmap(dec, zip(message, cycle(key))))

vocabulaire [1/4]

> cryptographie: science visant à transformer, à l'aide de conventions secrètes, des informations en clair en informations inintelligibles par des tiers sans connaître la clé

> cryptanalyse: science visant à analyser un message chiffré pour le rendre intelligible sans connaître la clé

> chiffrer: convertir de l'information intelligible (appelée texte clair) en information inintelligible (texte chiffré)

> déchiffrer: opération inverse, permet de retrouver le texte clair à partir du texte chiffré

vocabulaire [2/4]

> cryptologie : science regroupant la cryptographie et la cryptanalyse

> stéganographie : discipline de la cryptographie visant à camoufler des informations sur un support (sans chiffrer)

> code : méthode de chiffrement visant à substituer des mots du message

vocabulaire [3/4]

> intégrité : garantie que des données n‘ont pas été modifiées ou altérées

> confidentialité : chiffrement de données qui assure que seules les entités autorisées y auront accès

> authentification : processus visant à établir de manière formelle et intangible l'identification d’entités ou de données

vocabulaire [4/4]

signature électronique : mécanisme permettant de garantir l'intégrité d'un document électronique et d'en authentifier l'auteur (2000 / 2001: définie dans le code civil)

> non-répudiation : caractéristique qui garantit qu’une action ou transaction ne puisse pas être mise en cause par son ou ses auteurs

synthèse

> nous avons vu que l’on retrouve depuis les origines de la cryptologie les mêmes méthodes :

- transposition

- substitution

> la robustesse du mécanisme était au départ basée sur le secret de la méthode pour arriver de nos jours à une robustesse basée sur l’étude publique de la méthode

> l’utilisation de la cryptographie s’est progressivement démocratisée et les lois s’adaptent

cryptographie symétrique

algorithmes symétriques

> réduction d’un secret « long » (le clair à chiffrer) en un secret « court », la clé.

> la clé qui sert à chiffrer est celle qui sert à déchiffrer.

cryptographie symétrique

> la plupart des algorithmes sont basés sur des combinaisons complexes de :
- substitutions : remplacement d’une lettre par une autre
- transpositions : permutation de lettres au sein d’un bloc

> les algorithmes symétriques sont en général conçus pour :
- être rapides
- pouvoir s’intégrer efficacement en matériel

> il en existe deux grandes familles : les algorithmes de chiffrement en continu (stream cipher) et par bloc (block cipher).

cryptographie symétrique: quelques exemples [1/2]

> début 1970 Lucifer

> 1977 : DES (Data Encryption Standard), 3-DES: clé de 112 à 168 bits

> IDEA : clés de 128 bits

> CAST: clés de 128 ou 256 bits

> 2000, AES (Rijndael): clés de 128, 192, 256, 512 bits

> 1987, RC4 : rapide, continu, clé de longueur variable. De multiples vulnérabilités

cryptographie symétrique: quelques exemples [2/2]

> RC5 : clé de longueur variable

> RC6 :clé de longueur variable

> Blowfish: clé de 448 bits

> Twofish: clés de 128, 292 ou 256 bits

> Masque jetable (One-time Pad, chiffre de Vernam): XOR, seul prouvé absolument sûr mais peu pratique (téléphone rouge…)

Masque jetable

Questions!

Questions

Quel sont les problèmes du masque jetable (One-time Pad ou chiffre de Vernam)?

Si l’on dispose d’un chiffré et d’aucune information sur le clair, en recherche exhaustive, combien d’essais (au maximum) pour trouver une clé de k bits ?

Et en moyenne?

Quelle est la taille de clé symétrique recommandée en 2018?

chiffrement par blocs - Modes

> ECB (Electronic CodeBook), CFB (K-bit Cipher FeedBack), CBC (Cipher Block Chaining)...

  

chiffrement par blocs - DES (1/2)

> héritier direct de LUCIFER : IBM (et NSA), premier algorithme de chiffrement par blocs
1977, DES pour Data Encryption Standard est standardisé par le NIST

> DES est conçu pour être implémenté en matériel

chiffrement par blocs - DES (2/2)

> la NSA a suggéré (fortement) des clés courtes au contraire de la proposition initiale d’IBM (112 bits) ouvrant la porte à de nombreuses conjonctures…

> DES avec clé de 56 est cassable aujourd’hui : démonstration pratique par EFF en 1998 (DES Cracker, $250 000) 3 jours et 1999 / EFF + distributed.net (100 000 PC’s) 22 heures et 15 minutes

chiffrement par blocs - DES

  

chiffrement par blocs - DES

> outre la force brute, pas de faille majeure

> variante du DES encore fiable : triple DES

  - chiffre-déchiffre-chiffre

  - trois clés différentes

  - clé résultante de 112 bits (à cause de l’attaque MiTM... meet-in-the-middle)

  - mais relativement lent

Algorithme symétrique - IDEA

> IDEA pour International Data Encryption Algorithm : origine suisse (1990-1992)

> libre d’utilisation pour des applications non commerciales chiffrement par blocs de 64 bits, clé de 128 bits

> presque aussi rapide que DES-56

> utilisé par exemple dans: PGP, SSH, OpenSSL

> au fil des années, des vulnérabilités sont apparues

> son successeur IDEA NXT est soumis à licence

Algorithme symétrique - AES (1/2)

> le DES vieillissant, le NIST a lancé en 1997 un appel à candidature internationale pour sa succession : AES pour Advanded Encryption Standard

> les 5 finalistes étaient :

  - MARS de IBM,

  - RC6 de RSADSI,

  - Rijndael de Joan Daemen et Vincent Rijmen,

  - Serpent de Anderson, Biham et Knudsen,

  - Twofish de Schneier

Algorithme symétrique - AES (2/2)

> le gagnant est Rijndael (2000) :

  - très rapide en soft et matériel (un des critères)

  - blocs de 128 bits, clés de 128, 192 ou 256 bits

  - s’impose comme le standard de remplacement à DES

> le triple DES est 3 fois plus lent que DES et l'AES est 2,7 fois plus rapide que 3DES

> il n’y a pas d’attaques connues efficaces sur AES complet

cryptographie symétrique: limites

    n*(n-1)/2 clés pour n utilisateurs

    10 utilisateurs: 45 clés

    100 utilisateurs: 4950 clés

    5 000 utilisateurs: 12 497 500 clés

cryptographie symétrique - synthèse

> limites du chiffrement symétrique

  - nombre de clés

  - le transport des clés, impossibilité d’établir un canal chiffré avec un tiers inconnu

> avantages du chiffrement symétrique
  - rapidité
  - robustesse
  - simplicité algorithmique

cryptographie asymétrique

cryptographie asymétrique

> née des problèmes de distribution des clés et de l’établissement de clés partagées

> repose sur des asymétries mathématiques : utilisation d’opérations mathématiques que l’on ne sait pas inverser efficacement d’un point de vue algorithmique

cryptographie asymétrique: Diffie-Hellman

en 1976 Whitfield Diffie et Martin Hellman proposent un concept novateur à clé publique, naissance du premier algorithme asymétrique:

> principalement utilisé pour établir des clés partagées sans communiquer de secrets, mais aussi pour la signature

> sa sécurité repose sur la difficulté (lenteur) de calculer des logarithmes discrets versus la facilité de calculer les exponentielles

> peut être étendu plus de 2 participants

> utilisé dans des protocoles comme TLS, IPSec…

> on sait maintenant que James H. Ellis, Clifford Cocks, et Malcolm Williamson (UK) avaient écrit des documents précurseurs , classifiés

cryptographie asymétrique: Diffie-Hellman

L'algorithme:

Antoine et Barbara veulent établir une clé symétrique sans échanger de secrets.

> Ils se mettent d'accord sur deux grands entiers premiers entre eux, n et g

> Barbara choisit un grand nombre entier aléatoire x, calcule : X = g^x (mod n) et l'envoie à Antoine.

> Antoine choisit un grand nombre entier aléatoire y, calcule : Y = g^y (mod n) et l'envoie à Barbara.

> Barbara calcule k = Y^x (mod n)

> Antoine calcule k’ = X^y (mod n)

> On a k = k‘ = g^yx (mod n)

Antoine et Barbara sont donc parvenus à établir une clé secrète commune, sans échanger de secret préalable

question!

Question!

calculez de tête:
23 x 31
(levez la main lorsque vous avez terminé)

factorisez:
481
(levez la main lorsque vous avez terminé)

Conclusion?

cryptographie asymétrique: RSA

> en 1977 par Ron Rivest, Adi Shamir et Leonard Adleman

> RSA, algorithme asymétrique le plus répandu et maintenant libre de droits :

  - relativement lent : de 100 à 1000 fois plus lent que DES (matériel ou logiciel)

  - sa sécurité repose sur la difficulté (lenteur) à factoriser de grands nombres en facteurs premiers

> utilisations:

  - signature

  - chiffrement

  - échange de clés

cryptographie asymétrique: RSA

> Une clé publique, une clé privée

> la clé privée signe et déchiffre

> la clé publique vérifie et chiffre

> la vérification de signature est beaucoup plus rapide que la génération de signature

cryptographie asymétrique: RSA

Alice veut communiquer secrètement avec Bob:

Alice choisit deux grands nombres premiers: p et q (à l’aide d’un test de primalité probabiliste)

elle calcule n = p*q

elle choisit un nombre e tel que e et (p-1)(q-1) soient premiers entre eux

le couple (e,n) est la clé publique (n donne la longueur de la clé RSA)

elle choisit d tel que e*d ≡ 1 (mod (p-1)(q-1)) (grâce à l’algorithme d’Euclide étendu)

le couple (d,n) est la clé privée

cryptographie asymétrique: RSA

Bob veut envoyer un message chiffré à Alice:

> envoi du message chiffré

- il le représente sous la forme d'un ou plusieurs entiers M compris entre 0 et n-1

- Bob possède la clé publique (n, e) d’Alice. Il calcule C = M^e (mod n)

- c'est ce dernier nombre qu‘il envoie à Alice

> réception du message chiffré

- Alice reçoit C, et elle calcule grâce à sa clé privée D = C^d (mod n)

- D = M^ed (mod n) = M^[k(p-1)(q-1)+1] (mod n) = M.M^[k(p-1)(q-1)] (mod n)

- D = M^ed (mod n) = M (mod n)... qui est le message original.

cryptographie asymétrique: RSA

> la sécurité repose sur la difficulté de résoudre un problème mathématique: dépend des progrès mathématiques et matériels

> 22 août 1999, factorisation d’un nombre de 512 bits par des méthodes de cribles - Durée 5,2 mois - 37,5 années CPU à 8 000 MIPS

> en 2009, RSA-768 factorisé (232 chiffres)

> taille de la clé recommandée en 2016 : pas moins de 2048 bits

cryptographie asymétrique: DSA

> conçu par le gouvernement étasunien et la NSA comme standard de signature (DSS) en 1994

- variante de Diffie-Hellman : logarithme discret

- optimisé pour la signature mais peut être modifié pour du chiffrement

- clés au delà de 1024 bits

- génération de signature plus rapide que vérification de signature

Cryptographie asymétrique: courbes elliptiques (ECC)

> proposées au milieu des années 80
- autre moyen d’implémenter la méthode des logarithmes discrets
- points des courbes elliptiques qui constituent un groupe et sur lequel on peut faire des opérations arithmétiques
- à sécurité égale, clés plus courtes
- ECDSA, standardisation ANSI / IEE / NIST
- commencent à être largement implémentées

> avantages: clés plus courtes, adapté aux applications à faible ressources (cartes à puces, tokens...)

> inconvénients: malgré tout, encore jeune - le développement a été freiné par les brevets

cryptographie asymétrique: synthèse

> un biclé
- une clé publique : clé à diffuser largement
- une clé privée : clé confidentielle personnelle

 
> tout ce qui est chiffré avec la clé publique ne peut être déchiffré qu’avec la clé privée

 
> tout ce qui est chiffré avec la clé privée ne peut être déchiffré qu’avec la clé publique (réciprocité)

 
> principe : Il est impossible de déduire une clé privée à partir de la clé publique

cryptographie asymétrique: avantages et limites

> limites du chiffrement asymétrique
- lenteur de calcul : ~1000 fois plus lent que du symétrique
- « robustesse » : beaucoup de conjonctures
- complexité algorithmique

 
> avantages du chiffrement asymétrique
- nombre de clés
- échange des clés publiques très aisé
- capacité de distinguer les actions de chacun (imputabilité)

Questions!

Questions!

Quels sont les usages de la cryptographie asymétrique?

> identification / authentification
- associer une personne, une ressource à une identité numérique
- certitude de l’identité des tiers

> confidentialité / chiffrement
- données maintenues privées
- lisibles uniquement par le destinataire du message

> Intégrité / signature électronique
- impossibilité d’altérer ou de modifier les données

> non-répudiation

fonctions de hachage

les fonctions de hachage: principes

> but: donner une « empreinte » (hash) caractéristique, unique et de longueur fixe d'une quantité de données:
- doit être irréversible
- il ne doit pas être possible de trouver un texte initial qui renvoie une empreinte donnée
- il doit être impossible de trouver deux textes initiaux différents qui aient la même empreinte

les fonctions de hachage: principes

> autres propriétés:
- le lien entre les données et l’empreinte doit paraître le plus aléatoire possible
- une infime modification des données doit radicalement modifier l’empreinte
- rapides

> utilisations:
- signatures: intégrité, réduction de la taille des données à signer

les fonctions de hachage: exemples

> les anciennes:
- MD2, MD4 : de RSA Data Security, anciennes elles ne sont plus utilisées: souffrent de faiblesses connues

> les courantes, mais à éviter:
- MD5 (Message Digest Algorithm 5) : de RSA Data Security. Renvoie une empreinte de 128 bits. Des faiblesses ont été trouvées
- SHA-1 (Secure Hash Algorithm) : A l’initiative du gouvernement US. Renvoie une empreinte de 160 bits. Des faiblesses identifiées

> les nouvelles:
- RIPEMD-160 : conçue pour remplacer MD4 et MD5. Renvoie une valeur de 160 bits
- SHA-256 : successeur de SHA-1. Renvoie une valeur de 256 bits

utilisations combinées

utilisations combinées

> chiffrement :

- utilisation de la cryptographie asymétrique pour échanger une clé de chiffrement

- utilisation de la cryptographie symétrique et de la clé précédemment négociée pour le chiffrement de la communication

> facilité d’échange de clés de l’asymétrique, rapidité du chiffrement symétrique

utilisations combinées: chiffrement

utilisations combinées: signature électronique

Conclusion

4 logiciels de cryptographie utiles

Avertissement: ne téléchargez pas n'importe quel outil!

Veracrypt, outil de chiffrement de disque:
https://www.veracrypt.fr

GnuPG, outil de chiffrement de courriels:
https://gnupg.org

7-Zip, outil de chiffrement de fichiers:
https://www.7-zip.org

KeePass, outil de gestion de mots de passe:
https://keepass.info

Bibliographie

  Secrets et mensonges, Sécurité numérique dans un monde en réseau, de Bruce Schneier, éditions Vuibert Informatique.
La signature électronique, Transactions et confiance sur Internet, de Arnaud-F. Fausse, éditions Dunod.
Sécuriser ses échanges électroniques avec une PKI, de Thierry Autret, Laurent Bellefin et Marie-Laure Oble-Laffaire, éditions Eyrolles.
Digital Certificates, de Jalal Feghhi, Jalil Feghhi et Peter Williams, éditions Addison Wesley.
Initiation à la Cryptographie, de Gilles Dubertet, éditions Vuibert.
Cryptographie, théorie et pratique, de Douglas Stinson, éditions Thomson Publishing.
Cryptographie Appliquée, de Bruce Schneier, éditions Thomson Publishing.
Algorithmique et cryptographie, de Guy Robin, éditions Ellipses.
Cours de cryptographie, de Gilles Zémor, éditions Cassini.
Cryptography and Network Security, de William Stallings, éditions Prentice Hall.
Internet, Sécurité et Firewalls, de Karanjit Siyan et Chris Hare, éditions Mc Millan.
L’Ethique Hacker et l’esprit de l’ère de l’information, de Pekka Himanen, édition Exils.
Histoire des codes secrets, Simon Singh, éditions JC Lattès.
Enigma, de Robert Harris, éditions Pocket.

vous, qui croyez - ou pas - n'avoir rien à cacher

¡ Merci !