icon Polymorphisme

Bordeaux 2013

Polymorphisme

Introduction à la cryptographie

La stéganographie

Jeu de cache-cache

« Pour vivre heureux, vivons cachés »

La stéganographie est l'art de la dissimulation.

Les méthodes :

  • l'encre sympathique;
  • le micropoint (E. Goldberg, 1920);
  • l'anonymat.

Point fort : applicable à de nombreuses situations.

Point faible : réside dans la transmission et la diffusion de l'information.








Source : Stéganographie http://fr.wikipedia.org/wiki/St%C3%A9ganographie.

OutGuess

OutGuess est un outil de stéganographie qui permet de cacher l'insertion d'une information.

Installation d'OutGuess :

$ sudo apt-get install outguess

Insérer un message secret dans une image :

$ echo 'Message secret.' > secret.txt
$ outguess -d secret.txt imgOutguess.jpg imgOutguess-out.jpg
Reading imgOutguess.jpg....
JPEG compression quality set to 75
Extracting usable bits:   28973 bits
Correctable message size: 15370 bits, 53.05%
Encoded 'secret.txt': 128 bits, 16 bytes
Finding best embedding...
    ...
    201:    66(41.5%)[51.6%], bias    40(0.61), saved:     0, total:  0.23%
201, 106: Embedding data: 128 in 28973
Bits embedded: 159, changed: 66(41.5%)[51.6%], bias: 40, tot: 29101, skip: 28942
Foiling statistics: corrections: 24, failed: 0, offset: 131.500000 +- 113.844192
Total bits changed: 106 (change 66 + bias 40)
Storing bitmap into data...
Writing imgOutguess-out.jpg....

OutGuess, suite

Comparaison visuelle entre l'image originale et de l'image stéganographiée :

Image originale Image stéganographié

Récupérer le message secret inséré dans l'image :

$ outguess -r imgOutguess-out.jpg secret.txt
Reading imgOutguess-out.jpg....
Extracting usable bits:   28973 bits
Steg retrieve: seed: 201, len: 16
$ cat secret.txt 
Message secret.

Comparaison de la taille des images :

$ ls -lh imgOutguess* | awk '{ print $5,$9 }'
57K imgOutguess.jpg
29K imgOutguess-out.jpg

Source : OutGuess http://www.outguess.org/.

La cryptologie

La cryptologie est la science du secret.

Un petit lexique de la cryptologie

Alice et Bob (R. Rivest, 1978) cherchent à communiquer de manière sûre en utilisant un cryptosystème 𝒞, composé de :

Ève joue le rôle d'attaquant :

Rappel :

La cryptographie

La cryptographie est la science du chiffrement des messages.

Le chiffrement des messages a pour but d'assurer :

Les champs de la cryptographie :





Source : Cryptographie http://fr.wikipedia.org/wiki/Cryptographie.

La cryptanalyse

La cryptanalyse est la science du décryptage d'un cryptogramme.

Les champs :

La cryptographie symétrique

Le chiffrement symétrique (aussi appelé chiffrement à clé privée ou chiffrement à clé secrète) consiste à utiliser la même clé pour le chiffrement et le déchiffrement.

Point fort : rapidité du chiffrement et du déchiffrement.

Point faible : l'échange des clés et le nombre de clés.

Pour un groupe de N personnes utilisant un cryptosystème à clés secrètes, il est nécessaire de distribuer n(n1)2 clés.

Pour un groupe de 10 personnes, on obtient 45 clés.

Le chiffrement par transposition

Chiffrement de transposition, chiffrement par permutation ou anagramme.

Un alphabet 𝒜={a,,z} de taille 26.

Un message T=t0tn de taille n.

Une clé K=σ=(abcxyzbacxyz).

Un cryptogramme C=c0cn de taille n.

Un chiffrement par transposition de longueur de bloc n induit n! permutations.

20!1019 permutations. 36!4.1041 permutations.

Cryptanalyse : attaque à texte clair connu (KPA, Known-Plaintext Attack).

Constantes du chiffrement par transposition :

La scytale (Vème s. av. J.-C.)

Au Vème s. av. J.-C., les Spartiates utilisent la scytale.

Un exemple d'utilisation de la scytale :

Le cryptogramme :

MSETSEUEARR_SISG_EMQN

Cryptanalyse :

  • taille du message : 21 caractères;
  • création de tableaux : 2×11,3×7,4×6,5×5,6×4,7×3.
Tableau de dimensions 7×3
M S E T S E U
E A R R _ S I
S G _ E M Q N

Finalement, on obtient le texte clair :

MESSAGER_TRES_MESQUIN




Source : Scytale http://fr.wikipedia.org/wiki/Scytale.

Le chiffrement par substitution

Les types de chiffrement par substitution :

Le chiffrement mono-alphabétique

Le chiffrement mono-alphabétique remplace chaque lettre du texte clair par une autre lettre de l'alphabet.

Une clé K est un entier n non nul.

En arithmétique modulaire, pour tout i𝒜, on a :

{Cn=En(i)i+n[26]Tn=Dn(i)in[26]

Cryptanalyse du chiffrement mono-alphabétique :

Pour un alphabet de n lettres, on dispose de n1 translations.

(abcxyzdefabc)

Le chiffre de César (Ier s. av. J.-C.)

À l'origine, le chiffre de César utilise un alphabet 𝒜 de 31 caractères (l'alphabet latin, l'espace, la virgule, le point et le point d'interogation) et la clé secrète K=3.

Un exemple de chiffre de César :

La clé secrète K=3.

Chiffrement d'un texte clair en cryptogramme :

$ echo 'Je suis très émue de vous dire que j'ai
bien compris l'autre soir que vous aviez
toujours une envie folle de me faire
danser. ... ' > secret.txt
$ tr [a-z] [d-za-c] < secret.txt > cryptogramme.txt
$ cat cryptogramme.txt
Jh vxlv wuèv épxh gh yrxv gluh txh m'dl 
elhq frpsulv o'dxwuh vrlu txh yrxv dylhc
wrxmrxuv xqh hqylh irooh gh ph idluh gdqvhu.  ... 

Déchiffrement du cryptogramme :

$ tr [d-za-c] [a-z] < cryptogramme.txt
Je suis très émue de vous dire que j'ai
bien compris l'autre soir que vous aviez
toujours une envie folle de me faire
danser. ... 

Cryptanalyse par analyse de fréquence

Graphe d'analyse de fréquence

La clé secrète : K=3.




Source : Fréquence des lettres http://www.lexique.org/listes/liste_lettres.php

Le chiffrement poly-alphabétique

Le chiffrement poly-alphabétique remplace chaque lettre du message par une autre lettre d'un alphabet indiqué par une lettre de la clé.

Point fort : l'analyse de fréquence est inefficace.

Point faible : difficulté de son utilisation manuelle.

Un alphabet 𝒜={a,,z} de taille 26.

Un message T=t0tn de taille n.

Une clé K=k0km de taille m.

Un cryptogramme C=c0cn de taille n.

La suite (ni)i𝒜 des occurrences des lettres i de 𝒜.

Pour tout i𝒜, on a :

{Ci=EK(ti)=(ti+ki)[26]Ti=DK(ci)=(ciki)[26]

Le chiffre de Vigenère (XVIème s.)

En 1586, le chiffre de Vigenère est découvert; et sera cassé par C. Babbage en 1854.

Un exemple du chiffre de Vigenère :

La clé secrète : clesecrete

Chiffrement d'un texte clair en cryptogramme :

Hannibal Lecter donne le nom de Faust Federel.
clesecre tecles ecret ec les ec retec lesecre
JLRFMDRP EIEEIJ HQERX PG YSE HG WENWV QIVITVP.

Déchiffrement du cryptogramme :

clesecre tecles ecret ec les ec retec lesecre
JLRFMDRP EIEEIJ HQERX PG YSE HG WENWV QIVITVP.
Hannibal Lecter donne le nom de Faust Federel.




Note : l'agent Clarisse Starling devine l'anagramme « sulfate de fer » :)

Cryptanalyse du chiffre de Vigenère

Méthode Test de Kasiski Test de Friedman
1 déterminer le type de chiffrement ok
2 déterminer la taille m de la clé K ok ok
3 déterminer la clé K=k0km ok
4 vérification du résultat du déchiffrement

Attaque par force brute : on a 26m possibilités.

Le test de Kasiski (1863)

Le test de Kasiski permet de déterminer la taille m de la clé K.

Le test de Kasiski suppose que deux n-grammes identiques du texte clair seront chiffrés avec la même partie de la clé, lorsque la distance entre ces n-grammes est δ0[m].

La taille m de la clé est un diviseur du pgcd des distances entre deux n-grammes identiques, avec n2.

Méthode :

  • trouver les suites de n-grammes identiques dans le cryptogramme;
  • calculer les distances entre les n-grammes de chaque suite : δ1, δ2, …;
  • conjoncture : mδ1, mδ2, … donc mpgcd(δ1,δ2,).

Exemple d'un calcul de distance :

i 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
ti J A I C R E E D E S P A L A I S
clé P A S S W D P A S S W D P A S S
ci V A A U N H T D W K L D A A A K

δ(ci,cj)=ij δ(c1,c13)=131=120[6]

Exemple d'un test de Kasiski

KQOWE FVJPU JUUNU KGLME KJINM WUXFQ MKJBG WRLFN FGHUD WUU MB SVLPS NCMUE KQC TE SWR EE K OYSS IWCTU AXYOT APXPL WPNTC GOJBG FQHTD WXIZA YG FFN SXCSE YNCTS SPNTU JNYTG GWZGR WUU NE JUUQE APYME KQHUI DUXFP GUYTS MTFFS H NUOC ZGM RU WEYTR GKMEE DCTVR ECFBD JQCUS WVBPN LGOYL SKMTE FVJJT WWMFM WPNME MTMHR SPXFS SKFFS T NUOC ZGMDO EOY EE K CPJR GPMUR SKHFR SEIUE VGOYC WXIZA YG OSA ANYDO EOYJL WUNHA MEBFE LXYVL WNOJN SIOFR WUCCE SWKVI D GMU C GOCRU WGNMA AFFVN SIUDE KQHCE UCPFC MPVSU DGAVE MNYMA MVLFM AOYFN TQCUA FVFJN XKLNE IWCWO DCCUL WRIFT W GMU S WOVMA TNYBU HTCOC WFYTN MGYTQ MKBBN LGFBT WOJFT WGNTE JKNEE DCLDH WTVBU VGFBI JG
n-grammes δi m
2 3 5 19
WUU 95 0 0 1 1
EE K 200 3 0 2 0
WXIZA YG 190 1 0 1 1
NUOC ZGM 80 4 0 1 0
DO EOY 45 0 2 1 0
GMU 90 1 2 1 0

Toutes les distances δi sont divibles par m=5.

Le test de Friedman (1925)

Le test de Friedman repose sur la fréquence des lettres.

Il donne des informations sur :

L'indice de coïncidence

L'indice de coïncidence est la probabilité d'obtenir deux lettres identiques.

L'indice de coïncidence d'un message :

IC=i𝒜Cni2Cn2=i𝒜ni(ni1)n(n1)

Approche probabiliste : pour chacune des lettres i de l'alphabet 𝒜, la probabilité d'obtenir deux lettres identiques est la probabilité d'obtenir l'une d'entre elle est ni/n, puis la probabilité d'obtenir de nouveau cette lettre (ni1)/(n1).

Approche combinatoire : pour chacune des lettres i de l'alphabet 𝒜, il existe Cni2 façons de choisir 2 lettres identiques parmi ni, et il existe Cn2 façons de choisir 2 lettres parmi n. Finalement, la probabilité d'obtenir deux lettres identiques Cni2/Cn2.

L'indice de coïncidence d'une langue :

IC=i𝒜ni(ni1)n(n1)i𝒜pi2

où la probabilité d'occurrence pi de la lettre i doit être connue. La probabilité d'obtenir deux fois une même lettre est pipi.

Ia=0,0385; Ifr=0,0746; Ien=0,0667; Ide=0,07187

IC des chiffrements poly-alphabétiques

Le nombre de paires de lettres chiffrées avec la même lettre de la clé : Nid=n(n/m1)2=n(nm)2m

Il existe n choix pour la première lettre, il reste n/m1 choix pour la seconde lettre; aussi chaque paire de lettre a été comptée 2 fois. Sinon, on peut partir de mCn/m2.

Le nombre de paires de lettres chiffrées avec une lettre différente de la clé : Ndiff=n(nn/m)2=n2(m1)2m

Il existe n choix pour la première lettre, il reste nn/m choix pour la seconde lettre; aussi chaque paire de lettre a été comptée 2 fois. Sinon, on peut partir de Nid : on a Ndiff=Cn2Nid.

Le nombre de paires de lettres dans un texte : Np=Cn2=n(n1)2

Le nombre de paires de lettres identiques dans un texte : Npi=NidIl+NdiffIa

Finalement, on obtient l'indice de coïncidence poly-alphabétique :

IC=NpiNp=nmm(n1)Il+n(m1)m(n1)Ia

IC et type de chiffrement

IC=nmm(n1)Il+n(m1)m(n1)Ia

IlIc>Ia

Si l'IC du cryptogramme est peu différent de l'IC du texte clair, alors le chiffrement est une transposition ou est mono-alphabétique; car la fréquence des caractères est conservée : IcIl.

Si l'IC du cryptogramme est très différent de celui du texte clair, alors il est vraisemblable que le chiffrement soit poly-alphabétique : IcIl.

A.N. : Ia=0,0385 et If=0,0776.

La taille de la clé

m=(IlIa)n(n1)IcnIa+Il

1mn

Ic=Ilm=1 et Ic=Iam=n

A.N. : Ia=0,0385 et If=0,0776

Méthode

Création d'une matrice M de dimension m×n/m :

Mm,n/m=(c0cmc2mc1cm+1c2m+1cm1c2m1c3m1)

δ Sous-chaînes Ic
1 KQOWE FVJPU JUUNU KGLME KJINM WUXFQ MKJBG WRLFN FGHUD… 0,04350
2 KOE VP JUU GM KIM UF MJG WLN GU… 0,04473
QW FJU UN KLE JN WXQ KB RF FHD… 0,04344
3 KWVUUKMJMXMBRNH… 0,04272
QEJJNGEIWFKGLFU… 0,04362
OFPUULKNUQJWFGD… 0,04267

Pour δ=5, on a IcIf donc m=5 très probablement.

Seconde étape : déterminer la clé

Supposons que nous connaissons la taille m de la clé K

Pour trouver la clé K=k0km :

Troisième étape : vérification

Enigma (Seconde Guerre mondiale)

La machine Enigma est inventée en 1918 par A. Scherbius. Les cryptologues britanniques, dont Alan Turing, construisent la Bombe dont l'objectif est de casser les chiffres d'Enigma.

Points forts : nombre de clés presque infini, et la réversibilité.

Points faibles : recherche de bigrammes, de mots probables, bulletin météo, une unique clé pour un réseau.

Enigma et UNIX : la commande mcrypt.

$ echo 'Message secret' > secret.txt
$ mcrypt -a enigma --keymode scrypt --bare secret.txt
Enter the passphrase (maximum of 512 characters)
Please use a combination of upper and lower case letters and numbers.
Enter passphrase: 
Enter passphrase: 

File secret.txt was encrypted.
$ vim secret.txt.nc
^S°ÙO´UÚ^_zRw<8c>1`d

Source : Cryptanalyse d'Enigma http://fr.wikipedia.org/wiki/Cryptanalyse_d%27Enigma.

Le mot de passe

Complexité théorique d'un mot de passe de longueur l avec un alphabet de taille n :

card((l,n))=n××nlfois=nl

La robustesse d'un mot de passe :

Comparatif entre la complexité d'un mot de passe et la taille d'une clé :

l N Clé Complexité Commentaire de l'ANSSI
8 70 49 très faible taille usuelle
12 90 78 faible taille minimale pour des mots de passe ergonomiques.
16 36 82 moyen taille pour des mots de passe plus sûrs.
20 90 130 fort force équivalente à la plus petite taille de clé de l’algorithme AES (128 bits).

Source : Calculer la ’force’ d’un mot de passe http://www.securite-informatique.gouv.fr/gp_article728.html.

La création et l'utilisation d'un mot de passe

1 Création : choisir une méthode et une phrase

Méthode Phrase Code
acrostiche « Un tiens vaut mieux que deux tu l’auras. » 1tvmq2tl’a
phonétique « J’ai acheté huit cd pour cent euros cet après-midi. » ght8CDp100E7am

2 Étendre l'alphabet puis associer le mot de passe à un accès

Code Alphabet étendu Accès (site Web)
1tvmq2tl’a 1tvmq2tl’@ 1tvmq2tl’@Gir
ght8CDp100E7am ght8CD%E7am ght8CD%E7amPol

3 Règles d'utilisation :

  • ne jamais communiquer son mot de passe;
  • ne jamais utiliser le même mot de passe pour différents accès;
  • sa durée de vie : de préférence courte, terminée au moindre soupçon de compromission.

Données aléatoires : nombre π, e; OEIS (On-Line Encyclopedia of Integer Sequences, http://oeis.org/), etc.

JTR

« Sésame, ouvre-toi ! »

JTR (John The Ripper) est un outil permettant aux administrateurs système de trouver les mots de passe faibles.

La commande john est capable de casser différents formats de chiffrement de mots de passe : les mots de passe crypt, MD5, etc.

Elle utilise 4 modes dont les principaux sont :

  • mode simple : john applique les règles de transformations définies dans le fichier /etc/john/john.conf sur les informations GECOS des utilisateurs;
  • attaque par dictionnaire : john essaye un à un tous les mots de dictionnaire donnés;
  • mode incrémental (attaque par force brute) : john va essayer toutes les combinaisons de caractères possibles, jusqu'à trouver le mot de passe.








Source : John the Ripper password cracker http://www.openwall.com/john/.

L'interface Johnny

Johnny est une interface graphique pour John The Ripper.

Installation de Johnny :

$ wget http://openwall.info/wiki/_media/john/johnny_1.1.3_i386.deb
$ sudo dpkg --install johnny_1.1.3_i386.deb

L'interface graphique Johnny :

Source : Johnny - GUI for John the Ripper http://openwall.info/wiki/john/johnny.

GPG

GnuPG (GNU Privacy Guard) est un outil permettant de sécuriser les communications et le stockage de données.

Installation du paquet gnupg :

$ sudo apt-get install gnupg

Pour chiffrer le fichier secret.txt :

$ gpg -c secret.txt
$ vim secret.txt.gpg
<8c>^M^D^C^C^Bo<9c>ó«^BD¥Ø`É+èu²ÅWì]ÉÕÉ(<94><84>ú¡
<9b><80>^Z<8d>n¹^YÝ;xAÍøz^?äÉ^W<8f>C¹®ìúy<8f>0!

Pour déchiffrer le fichier secret.txt.gpg :

$ gpg -o secret.out.txt -d secret.txt.gpg





Source : GPG http://www.gnupg.org/.

L'interface GPA

GPA (Gnu Privacy Assistant) est une interface graphique utilisateur pour GnuPG.

Installation de GPA :

$ sudo apt-get install gpa

L'interface graphique GPA :

Source : GPA http://www.gnupg.org/related_software/gpa/index.fr.html.

La cryptographie asymétrique (années 70)

La cryptographie asymétrique, ou cryptographie à clé publique, est fondée sur l'existence des fonctions à sens unique et à brèche secrète.

Les fonctions à sens unique ("clé publique") sont telles qu'une fois appliquées à un message, il est extrêmement difficile de retrouver le message original.

L'existence d'une brèche secrète ("clé privée") permet cependant à la personne qui a conçu la fonction à sens unique de déchiffrer facilement le cryptogramme grâce à un élément d'information qu'elle possède : la clé privé.

Point faible : l'échange de la clé publique sur un canal non sécurisé.

Pour se prémunir contre ce risque on fait généralement appel à une infrastructure à clés publiques.

L'algorithme RSA (1975) :

L'algorithme RSA repose sur une fonction a sens unique ou plutôt une fonction très difficilement réversible.

Facile : ×:×,(n,m)n×m

Difficile : f:np×qp,q𝒫.

La taille des clés RSA devraient aujourd'hui être au minimum de 1024 bits. En 2005, le nombre RSA-200, un nombre de 663 bits a été factorisé.

OpenSSL

OpenSSL est une boîte à outils qui implémente les protocoles Secure Sockets Layer (SSL v2/v3) et Transport Layer Security (TLS v1); c'est aussi une librairie dédiée à la cryptographie.

La bibliothèque permet de réaliser des applications client/serveur sécurisées s'appuyant sur SSL/TLS.

La commande en ligne (openssl) permet :

  • la création de clés RSA, DSA;
  • la création de certificats X.509;
  • le calcul d'empreintes (MD5, SHA, …);
  • le chiffrement et déchiffrement (DES, IDEA, RC2, RC4, …);
  • la réalisation de tests de clients et serveurs SSL/TLS;
  • la signature et le chiffrement de courriers (S/MIME).





Source : OpenSSL: The Open Source toolkit for SSL/TLS http://www.openssl.org/.

La création de certificats CACert

CACert

Créer un compte CACert (http://www.cacert.org). Enregistrer son nom de domaine.

La clé privée RSA et le certificat CSR

Créer une clé privée RSA (Rivest, Shamir et Adleman) domain.tld.key et un certificat CSR (Certificate Signing Request) domain.tld.csr pour un nom de domaine :

$ openssl req -config /etc/ssl/ca/ca.conf \
-newkey rsa:2048 -passout file:/etc/ssl/ca/private/passphrase.txt -keyout domain.tld.key \
-subj "/C=FR/ST=Gironde/L=Bordeaux/O=NomOrganisme/OU=NomOrganisme/CN=domain.tld/
emailAddress=webmaster@domain.tld" \
-out domain.tld.csr

Le certificat X.509

Rendez-vous ensuite sur votre compte CACert, et cliquez sur Certificat Serveur > Nouveau. Ensuite, copiez-collez le certificat CSR dans la zone de texte.

$ openssl req -in domain.tld.csr
-----BEGIN CERTIFICATE REQUEST-----
MIICfTCCAeYCAQAwgaoxCzAJBgNVBAYTAkZSMRAwDgYDVQQIEwdHaXJvbmRlMREw
...
IneHrYX1yhkUSrnqVACrf5g=
-----END CERTIFICATE REQUEST----- 

CACert demande alors de confirmer la demande de certificat pour le domaine.

Enfin, CACert envoie, sur la page Web et par email, le certificat X.509 :

Veuillez trouver ci-dessous votre Certificat de Serveur
-----BEGIN CERTIFICATE-----
MIIFwTCCA6mgAwIBAgIDDbyRMA0GCSqGSIb3DQEBBQUAMHkxEDAOBgNVBAoTB1Jv
...
RYr+VFb91OHTCAUV0vhKtCG+Vo8V4hTwvv5w1JoFa2hBMmhq6Q==
-----END CERTIFICATE-----

C’est le certificat domain.tld.crt.

Vérifier l’information du certificat X.509 :

$ openssl req -noout -text -in domain.tld.crt

Le certificat PEM (Privacy Enhanced Mail)

La dernière étape consiste à créer un fichier d'extension .pem. Le fichier au format pem est pris en charge par les serveurs Web ou mail.

On récupére la clé privée RSA non protégée :

$ openssl rsa -passin file:/etc/ssl/ca/private/passphrase.txt \
-in domain.tld.key -out domain.tld.pem
writing RSA key

On concatène la clé privée RSA non protégée et le certificat :

$ cat domain.tld.pem domain.tld.crt > domain.tld.pem

Source : The Open–source PKI Book http://sourceforge.net/projects/ospkibook/.

L'interface XCA

XCA (X509 Certification Authority) est une interface graphique utilisateur pour la création de clés RSA, DSA et ECC, les certificats, les signatures, les listes de révocations.

Installation de XCA :

$ sudo apt-get install xca

L'interface graphique XCA :

Source : XCA http://xca.hohnstaedt.de/.

Bordeaux 2013

Polymorphisme

Introduction à la cryptographie

gregory.at.polymorphisme.fr

Les trois petits singes