dimanche 27 février 2011

Détection de LSB

Comme vu dans un de mes précédents articles, une technique largement utilisée en stéganographie consiste à cacher des informations dans les bits de poids faible (LSB) d'une image. Je vais décrire ici une méthode qui permet dans de nombreux cas de savoir si oui ou non une information est cachée dans ces bits.
Attention, il n'est pas question ici d'extraire cette information, car il existe une infinité de façon de cacher les données dans le LSB :
  • Un bit sur deux, un bit sur trois...
  • Choix des bits de certaines composantes de l'image uniquement (que dans la composante verte, rouge, bleue, ou toutes les combinaisons possibles)
  • Ordre des bits en lisant l'image ligne par ligne, colonne par colonne, une ligne sur 2....
  • Lecture des bits à l'envers ou non
  • Utilisation des bits de poids le plus faible, ou de poids un peu plus important (avec comme conséquence une altération de l'image plus importante)
  • ...
Toutes les techniques ou combinaisons de techniques sont possibles tant qu'elles sont partagées par l'émetteur du message stéganographié et son récepteur.

Le point important est que toutes les méthodes stéganographiques à base de LSB altèrent le contenu de l'image et que même si cette légère modification n'est pas visible à l'œil nu, elle peut quand même être décelée si on utilise les bonnes techniques.

L'idée est la suivante, même si les bits de poids faibles sont porteurs de très peu d'information (comme vu dans mon article sur le LSB), ils ne sont tout de même pas distribués aléatoirement dans l'image. Porteur de très peu d'information, ne veut pas dire porteur d'aucune information. Dans une zone ou il n'y a qu'une couleur présente par exemple, il y a peu de chance qu'en plein milieu il y ait un pixel différent de tous ses voisins... possible, mais peu probable. Les bits de poids faibles respectent en règle générale l'apparence de l'image et les pixels sont cohérents entre eux.

Le but va donc être de visualiser cette cohérence entre les bits de poids faibles. Pour cela on va recréer l'image en "vidant" chaque bit des informations inutiles (c'est à dire les bits de poids fort). Seuls les bits susceptibles de cacher de l'information vont donc être gardés. Comme ce sont des bits de poids faibles, ils ont un impact faible sur le rendu de l'image et il sera donc très difficile de distinguer quoique soit. Il suffit pour cela d'augmenter le poids du bit en faisant un simple décalage binaire vers la gauche.
// On enlève les informations inutiles
composante = composante & 1;

// On augmente le poids du bit
composante = composante << 7;

Exemple :
Composante (décimale) 255 0 111 56
Composante (binaire) 11111111 00000000 01101111 00111000
Devient (binaire) 10000000 00000000 10000000 00000000
Devient (décimale) 128 0 128 0
Pour effectuer cette petite transformation sur les images j'utilise un petit outil que j'ai écrit :

# ./lsb.rb -h
lsb.rb [options] -i input_image -o output_image
Version 1.1
--colors|-c r|g|b: couleur que l'on veut garder
--bit|-b bit: bit que l'on va utiliser (par defaut 0)
--help|-h : affiche cette aide
--version|-v : affiche le numero de version

Utilisons ce petit programme sur cette image qui ne cache aucune information à l'intérieur.

# ./lsb.rb tux.png -o tux_lsb.png

Comme on peut le voir très clairement ici, la structure de l'image est ici conservée, et cela même dans les bits de poids faibles.

Cachons maintenant des informations dans notre image de départ et regardons le résultat :

# ./lsb_hide.rb -f hide.txt tux.png -o tux_hidden.png
# ./lsb.rb tux_hidden.png -o tux_hidden_lsb.png
On voit très clairement ici que quelque chose s'est passé sur le haut de l'image, puisque cette partie n'est plus du tout cohérente. La raison est qu'un message a été caché, et celui-ci étant court, toute l'image n'a pas été nécessaire pour le cacher.

Cette technique ne fonctionnera pas dans tous les cas, à plus forte raison si l'image est bruitée ou par exemple si elle avait été préalablement compressée en jpg. Cependant, je la trouve suffisamment intéressante pour être citée. De plus elle m'a rendu de précieux services lors de certains challenges.

samedi 26 février 2011

NDH Cryptographie Epreuve 3

L'épreuve 3 de cryptographie de la nuit du hack 2010 se présente de cette façon :

Ws szdv od gowhooehzb od nsesp saqpigd pge kp ao5 cp qp spled doyr pgazns
Pour commencer et pour tous les messages chiffrés, il est important de faire une bonne première analyse pour écarter les mauvaises pistes. Ici plusieurs éléments sont marquants :

  • Le message chiffré contient une majuscule en début de phrase
  • Le message chiffré contient des espaces, et la proportion des "mots" semble respectée
  • Le chiffre 5 apparaît dans le message chiffré, avec deux caractères avant ce qui nous fait penser à md5
Ici on écarte rapidement le chiffrement de transposition, car la majuscule en début de phrase et la proportion des mots qui semble respectée ne collent pas.

Le calcul de l'indice de coïncidence donne le résultat suivant (après retrait des espaces, du 5 et transformation du W en w) :

# ./indice_coincidence.rb "wsszdvodgowhooehzbodnsespsaqpigdpgekpao cpqpspleddoyrpgazns"
0.0647307924984876
L'indice de coïncidence est proche de celui de l'anglais et un peu bas pour du français. Cependant le texte est très court, et se fier aveuglément sur l'indice de coïncidence sur un texte de cette longueur est risqué.
Même si la substitution mono-alphabétique a déjà été utilisée lors de la ndh, c'était une mono-substitution particulière puisqu'un chiffrement de césar, donc on se lance dans cette voie, peut être sans issue.

Des outils existent pour casser une mono-substitution comme SCBSolvr. Cependant je trouve que dans ce genre de challenge, le cheminement vers la solution est plus important que la solution en elle même, du coup on n'utilisera pas cet outil.

J'ai écrit un petit outil sans prétention, permettant de faire une recherche de motif dans une liste de mot. Par exemple si on lui passe 123123 ou abcabc en paramètre il sortira tous les mots comme coucou, tintin ou encore bonbon. Le 4° mot du message chiffré gowhooehzb paraît suffisamment long avec plusieurs lettres répétées, un candidat parfait comme pattern.
# pattern -f dict_fr.txt -p gowhooehzb

# pattern -f dict_en.txt -p gowhooehzb
Ca s'annonce mal... un mot de ce type n'existe ni en français, ni en anglais. Donc soit ce mot est un mot inventé, soit ce n'est pas une mono-substitution. On tente d'autres combinaisons pour confirmer ou infirmer nos hypothèses.
# pattern -f dict_fr.txt -p nsesp,spled,pgazns
...
balai aigle intuba
...
maias asdic stroma
...
Bon hormis le fait que mon dictionnaire est à retravailler... aucun groupe de mots ne semble réellement correspondre à ce que nous recherchons. La voie de la mono-substitution est donc sans issue.

On va tenter l'algorithme Vigenère qui est un algorithme très connu et largement utilisé dans les challenges. Plusieurs techniques existent pour casser l'algorithme Vigenère, mais ici une technique est à privilégier. L'analyse préalable du cipher a laissé supposer que le mot md5 était présent dans le texte en clair, une attaque par mot connue ou KPTA pour known Plain Text Attack sera donc utilisée.

Pour que md5 devienne ao5, il faut qu'il y ait un décalage de 14 (soit la lettre "O" dans l'alphabet) sur la première lettre et de 11 (soit la lettre "L" dans l'alphabet) sur la deuxième. On connait donc deux lettres de notre clé, on va tester ces deux lettres comme clé (et donc supposer que la clé fait deux caractères).
Cipher : WSSZDVODGOWHOOEHZBODNSESPSAQPIGDPGEKPAOCPQPSPLEDDOYRPGAZNS
Clé :    LOLOLOLOLOLOLOLOLOLOLOLOLOLOLOLOLOLOLOLOLOLOLOLOLOLOLOLOLO
Plain :  LEHLSHDPVALTDATTONDPCETEEEPCEUVPESTWEMDOECEEEXTPSANDESPLCE
Intéressant... on devine le mot validation. L'algorithme de chiffrement est donc le bon mais la clé est encore mauvaise.

Le chiffré GOWHOOEHZB doit donc devenir VALIDATION. Pour cela, la clé doit être LOLZLOLZLO. On voit bien la répétition, on teste donc la clé LOLZ.

# vigenere.rb -d WSSZDVODGOWHOOEHZBODNSESPSAQPIGDPGEKPAOCPQPSPLEDDOYRPGAZNS -k LOLZ
LEHASHDEVALIDATIONDECETTEEPREUVEESTLEMDDECETEXTESANSESPACE
Voilà épreuve terminée :)

jeudi 17 février 2011

Indice de coïncidence

Quand on analyse un message chiffré, découvrir le type de chiffrement utilisé est primordial. Cette tâche n'est pas toujours évidente mais certains outils peuvent aider. Parmi ces outils l'indice de coïncidence ou IC est un passage obligé... autant que l'analyse de fréquence voire plus.

Présentation de l'Indice de Coïncidence

L'IC est une valeur décimale inventée par Wilfried Friedman et publiée en 1920 qui mesure la probabilité que deux lettres choisies aléatoirement dans un texte soient identiques.

La formule de l'IC est la suivante :
IC = SUM(1,N) Ni(Ni-1) / N(N-1

N : Nombre de lettre dans l'alphabet
Ni : Nombre d'occurrence de la lettre i
Chaque langue ayant ses propres caractéristiques, chaque langue a aussi un IC qui lui est propre (tableau original ici) :

LangueIndice
Russe0,0529
Serbe0,0643
Suédois0,0644
Anglais0,0667
Esperanto0,0690
Grec0,0691
Norvégien0,0694
Danois0,0707
Finnois0,0737
Italien0,0738
Portugais0,0745
Arabe0,0758
Allemand0,0762
Hébreu0,0768
Espagnol0,0770
Japonais0,0772
Français0,0778
Néerlandais0,0798
Malaysien0,0852


On peut trouver des IC différents selon les sources, tout dépend bien entendu du texte d'origine sur lequel il a été calculé. Par exemple un texte issu du livre La disparition de Georges Perec aura peu de chance d'être représentatif de la langue française et aura donc un IC bien différent.

Utilisation de l'Indice de Coïncidence


Bon c'est bien beau tout ça, mais ça n'explique pas en quoi l'IC peut aider au décryptage d'un texte. Pour commencer, la valeur de l'indice est indépendante des lettres utilisées, il mesure la probabilité de tomber deux fois sur la même lettre quelle que soit cette lettre.

Ce qui veut dire que dans le cas d'une substitution mono-alphabétique (césar, carré de polybe...), le texte chiffré et le texte en clair auront exactement le même IC. De la même façon les chiffres de transposition comme celui utilisé à la NDH par exemple, ne font que modifier l'ordre d'apparition des lettres dans le texte, sans en modifier la quantité, l'IC reste donc inchangé.

Quand on travaille sur un texte chiffré suffisamment long (pour être le plus représentatif possible), on peut donc facilement écarter certaines hypothèses grâce à cet outil. Si ce dernier a une valeur de 0.03 il y a peu de chance que ce soit une substitution mono-alphabétique ou une transposition, il faudra donc plus regarder en direction de chiffres polyalphabétiques par exemple de type Vigenère, Porta ou Gronsfeld qui eux modifient la quantité de chaque lettre.

L'utilisation de l'IC va bien au delà de la simple caractérisation du type de chiffrement utilisé. Prenons par exemple un texte en clair que l'on chiffre avec un algorithme qui va modifier la fréquence d'apparition de chaque lettre (Hill, ADFGVX, Playfair...), et on applique un surchiffrement dessus avec une substition mono-alphabétique. A priori l'exercice paraît compliqué pour passer du texte chiffré au texte en clair. Pourtant l'IC apporte ici une aide non négligeable.
Si on décide de faire une recherche exhaustive des clés du premier algo, il ne sera pas possible de savoir si on a trouvé la bonne clé, car le deuxième chiffrement nous masquera la réponse. Cependant on sait que le deuxième algo ne modifie pas l'IC. Il sera donc possible de réduire énormément l'espace de recherche, en ne sélectionnant que les textes qui ont un IC convenable. L'algorithme suivant permet d'expliquer cette démarche.
ecart_accepte = 0.01   // A adapter selon les besoins
Pour toutes les clés K faire
   plain = déchiffrer(cipher,K);
   Si abs(0.0778 - IC(plain)) < ecart_accepte Alors
      plain_possibles.add(plain);
   FinSi
FinPour
L'espace de recherche qui était constitué d'un ensemble aussi important que le nombre de clé est grandement réduit grâce à l'IC.

L'IC peut aussi être utilisé dans la recherche de la taille de la clé pour un message chiffré avec Vigenère. Cet algorithme modifie le rapport de fréquence d'apparition des lettres, et donc l'IC. Cependant il n'est ni plus ni moins qu'un ensemble de N décalages (N césar) où N est la taille de clé.

Prenons ce texte suivant : "CET ARTICLE PARLE DE L INDICE DE COINCIDENCE QUI EST UN OUTIL TRES UTILE EN CRYPTANALYSE" et chiffrons le avec la clé "CLE".

CETARTICLEPARLEDELINDICEDECOINCIDENCEQUIESTUNOUTILTRESUTILEENCRYPTANALYSE
CLECLECLECLECLECLECLECLECLECLECLECLECLECLECLECLECLECLECLECLECLECLECLECLEC
EPXCCXKNPGAETWIFPPKYHKNIFPGQTRETHGYGGBYKPWVFRQFXKWXTPWWEMNPIPNVAAXCYENJWG

Les 1°, 4°, 7°... caractères sont chiffrés avec le caractère C et sont donc décalés de 2 caractères (3° lettre de l'alphabet).
Les 2°, 5°, 8°... caractères sont chiffrés avec le caractère L et sont donc décalés de 11 caractères (12° lettre de l'alphabet).
Les 3°, 6°, 9°... caractères sont chiffrés avec le caractère E et sont donc décalés de 4 caractères (5° lettre de l'alphabet).

Il y a donc 3 groupes de lettres dans le texte en clair qui subissent chacun un décalage différent et chaque groupe de lettre a un IC proche de celui de sa langue d'origine. Etant donné qu'un décalage n'est qu'une substitution mono-alphabétique, l'IC de chaque groupe de lettres chiffrées doit être proche de celui de la langue d'origine, si c'est pas le cas c'est que le groupe n'est pas bon et que donc la taille de la clé est fausse.
# ./friedman_test.rb 1 4 EPXCCXKNPGAETWIFPPKYHKNIFPGQTRETHGYGGBYKP
WVFRQFXKWXTPWWEMNPIPNVAAXCYENJWG
Taille Clé:1 => 0.05213089802130898
Taille Clé:2 => 0.04804804804804805 0.050793650793650794
Taille Clé:3 => 0.07333333333333333 0.09057971014492754 0.07608695652173914
Taille Clé:4 => 0.08187134502923976 0.0915032679738562 0.026143790849673203 0.032679738562091505
Comme on peut le voir ici, une taille de clé égale à 3 donne les IC les plus proches du français. La taille de la clé sera probablement de 3 caractères. Bien entendu, une clé de longueur multiple de 3 doit donner aussi de bons résultats. Ce test est appelé le test de Friedman.

Voilà pourquoi l'indice de coïncidence est un outil indispensable en cryptanalyse qui peut nous aider dans bien des cas.

mercredi 2 février 2011

Débuter avec les buffer overflows...

Je suis complètement débutant dans tout ce qui est exploitation, reverse et autres joyeusetés du même genre... alors je travaille pour m'améliorer en lisant beaucoup de documentation (notamment Hacking The Art of Exploitation)
Le problème c'est qu'aujourd'hui de nombreuses protections sont mises en places par défaut sur les différents systèmes, ce qui rend l'apprentissage bien plus compliqué. La moindre petite exploitation devient donc pour les débutants comme moi, infaisable...
Voilà donc quelques éléments qui peuvent faciliter la tâche à des fins d'apprentissages.

Pour commencer lors de la création du binaire vulnérable, il faut préciser au compilateur l'option -fno-stack-protector à gcc qui va empêcher la mise en place de code supplémentaire permettant de détecter les débordements de buffer.

# gcc vuln.c -o vuln -fno-stack-protector -ggdb3

Ensuite on va autoriser la création des fichiers core (on va leur donner un nom sexy et surtout s'assurer qu'il n'y a pas /dev/null dans /proc/sys/kernel/core_pattern) :

# sudo sysctl -w kernel.core_pattern=%e-%p-%t.core
kernel.core_pattern = %e-%p-%t.core
# ulimit -c 100000

Ensuite on va utiliser le programme execstack, pour rendre la pile de notre programme exécutable (désactivation du NX bit):

# readelf -l vuln
Elf file type is EXEC (Executable file)
Entry point 0x8048310
There are 8 program headers, starting at offset 52

Program Headers:
Type Offset VirtAddr PhysAddr FileSiz MemSiz Flg Align
PHDR 0x000034 0x08048034 0x08048034 0x00100 0x00100 R E 0x4
INTERP 0x000134 0x08048134 0x08048134 0x00013 0x00013 R 0x1
[Requesting program interpreter: /lib/ld-linux.so.2]
LOAD 0x000000 0x08048000 0x08048000 0x004b4 0x004b4 R E 0x1000
LOAD 0x000f14 0x08049f14 0x08049f14 0x00100 0x00108 RW 0x1000
DYNAMIC 0x000f28 0x08049f28 0x08049f28 0x000c8 0x000c8 RW 0x4
NOTE 0x000148 0x08048148 0x08048148 0x00044 0x00044 R 0x4
GNU_STACK 0x000000 0x00000000 0x00000000 0x00000 0x00000 RW 0x4
GNU_RELRO 0x000f14 0x08049f14 0x08049f14 0x000ec 0x000ec R 0x1

Section to Segment mapping:
Segment Sections...
00
01 .interp
02 .interp .note.ABI-tag .note.gnu.build-id .gnu.hash .dynsym .dynstr .gnu.version .gnu.version_r .rel.dyn .rel.plt .init .plt .text .fini .rodata .eh_frame
03 .ctors .dtors .jcr .dynamic .got .got.plt .data .bss
04 .dynamic
05 .note.ABI-tag .note.gnu.build-id
06
07 .ctors .dtors .jcr .dynamic .got
# execstack -s vuln
# readelf -l vuln
Elf file type is EXEC (Executable file)
Entry point 0x8048310
There are 8 program headers, starting at offset 52

Program Headers:
Type Offset VirtAddr PhysAddr FileSiz MemSiz Flg Align
PHDR 0x000034 0x08048034 0x08048034 0x00100 0x00100 R E 0x4
INTERP 0x000134 0x08048134 0x08048134 0x00013 0x00013 R 0x1
[Requesting program interpreter: /lib/ld-linux.so.2]
LOAD 0x000000 0x08048000 0x08048000 0x004b4 0x004b4 R E 0x1000
LOAD 0x000f14 0x08049f14 0x08049f14 0x00100 0x00108 RW 0x1000
DYNAMIC 0x000f28 0x08049f28 0x08049f28 0x000c8 0x000c8 RW 0x4
NOTE 0x000148 0x08048148 0x08048148 0x00044 0x00044 R 0x4
GNU_STACK 0x000000 0x00000000 0x00000000 0x00000 0x00000 RWE 0x4
GNU_RELRO 0x000f14 0x08049f14 0x08049f14 0x000ec 0x000ec R 0x1

Section to Segment mapping:
Segment Sections...
00
01 .interp
02 .interp .note.ABI-tag .note.gnu.build-id .gnu.hash .dynsym .dynstr .gnu.version .gnu.version_r .rel.dyn .rel.plt .init .plt .text .fini .rodata .eh_frame
03 .ctors .dtors .jcr .dynamic .got .got.plt .data .bss
04 .dynamic
05 .note.ABI-tag .note.gnu.build-id
06
07 .ctors .dtors .jcr .dynamic .got

Enfin on va désactiver l'ASLR:

# sudo sysctl -w kernel.randomize_va_space=0
kernel.randomize_va_space = 0

Ces petites modifications m'ont permis de tester quelques exploitations très simples. En espérant que ca en aidera certains :)

Update: Certaines options peuvent être ajoutées à gcc pour désactiver encore plus de sécurité et qui peut être utile lors de l'exploitation de format string (et qui permet aussi de se passer de execstack) :

# gcc vuln.c -w -O0 -ggdb -std=c99 -static -D_FORTIFY_SOURCE=0 -fno-pie -Wno-format -Wno-format-security -fno-stack-protector -z norelro -z execstack -o vuln