TP6_C Hash_simple

🕒 : 3 h maximum

Prérequis:

Cours sur les chaines de caractères (string)
Les TP de C précédents
utilisation de gdb permet de comprendre l’intérieur du code !
cours sur hash en C

But:

Compréhension d’un hash
Manipulation de chaîne sans utiliser la notion de tableau avec des []
Collision sur les hashs, utilisation d’un nombre premier élevé !

Code de hash simple

le hash permet de sécuriser un mot de passe par exemple ! dans la conclusion vous expliquerez cela à la fin du TP

Compiler ce code et avec le GDB comprendre l’algorithme de ce HASH

#include<stdlib.h>
#include<stdio.h>

/* Fonction du hash_simple       */
/* Entrée: chaine de caractères  */
/* Sortie: un long int (64 bits) */

unsigned long int hash_simple(const char *str)
{
    unsigned long int hash = 0;
    const unsigned long int prime = 1; /* 31 ou un nombre premier plus élevé est préférable */
    const char *p;
    
    if (str == NULL)   /* cas ou pas de chaine */
    {
        return 0;
    }
    
    p = str;
    while (*p != '\0')
    {
        hash = (hash * prime) + (unsigned long int)(*p);
        p++;
    }
    return hash;
}
/**************************************************************************************************/
int main (int argc, char **argv)
{
if (argc!=2) 
	{
		fprintf(stderr, "Aucune chaine fournie.\n");
		fprintf(stderr, "syntaxe: ./hash_simple \"chaine de caractère\"\n");
		return EXIT_FAILURE;
	}
/* ici argv[1] contient une chaine a hacher */
printf ("Le hash simple de %s en décimal   est %ld \n",argv[1],hash_simple(argv[1])); 
printf ("Le hash simple de %s en héxadémal est %lx \n",argv[1],hash_simple(argv[1])); 

return EXIT_SUCCESS;
}

bruno@elliott:~/Works/langage_C/hash$/hash "Bonjour"
Le hash simple de Bonjour en décimal   est 735 
Le hash simple de Bonjour en héxadémal est 2df

On va étudier la fonction main(int argc, char **argv)

Si argc est diffèrent de 2

expliquer pourquoi argc peut être diffèrent de 2 et comment ?

fprintf et stderr

bruno@elliott:/dev$ ls /dev/std*
stderr  stdin  stdout
bruno@elliott:/dev$ ls -l /dev/std*
lrwxrwxrwx 1 root root 15  9 févr. 10:39 stderr -> /proc/self/fd/2
lrwxrwxrwx 1 root root 15  9 févr. 10:39 stdin -> /proc/self/fd/0
lrwxrwxrwx 1 root root 15  9 févr. 10:39 stdout -> /proc/self/fd/1
bruno@elliott:/dev$

A l’aide du man fprintf et du man stderr déterminer ce que représente stderr

bruno@elliott:~$ echo "Erreur !" > /dev/stderr 
Erreur !
bruno@elliott:~$

l’idée de diriger les erreurs sur stderr est d’éviter de mélanger les stdout et les erreurs

                  +----------------+
                  |    Programme   |
                  |                |
     stdin  <-----| 0              |-----> 1  stdout
   (entrée)       |                |     (sortie)
                  |                |-----> 2  stderr
                  +----------------+     (erreurs)

La fonction unsigned long int hash_simple(const char *str)

le mot clé const va imposer de ne pas modifier ici str (constante)

on utilise ici un format d’entier particulier , unsigned long int

Linux 64-bit

8 octets (64 bits)

18 446 744 073 709 551 615

0xFFFFFFFFFFFFFFFF

unsigned , donc que positif et énorme !! sur 64 bits !

Pourquoi avoir choisi ce type pour faire un hash ?

Donner le role de %ld et %lx dans notre code

le code du hash est essentiellement ici !

    p = str;
    while (*p != '\0')
    {
        hash = (hash * prime) + (unsigned long int)(*p);
        p++;
    }

(*p != ‘\0’) , sert à déterminer quoi ? (aidez vous de gdb)

L’algorithme du hash = (hash * prime) + (unsigned long int)(*p);

ici on découvre peut être le cast (un moule en francais) qui force un char ici *p en format unsigned long int

comment évolue le hash ?

la constante prime ici va nous servir à faire « un mélange » on y mettra un nombre premier pour augmenter le mélange …ici on a mis 1 vous pouvez utiliser d’autres prime et constater.

si prime vaut 1

si prime vaut 31

On va utiliser des nombres premiers pour prime , pour éviter les collisions

// Avec un nombre NON premier (ex: 4)
hash = (hash * 4) + char
// 4 = 2 × 2 → beaucoup de motifs répétitifs

// Avec un nombre premier (ex: 5)
hash = (hash * 5) + char
// 5 est premier → mélange meilleur

Mot_de_passe

On va réaliser un code qui va comparer un mot de passe

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MOT_DE_PASSE "secret123"

int main(int argc, char *argv[]) 
{
    /* Vérifier qu'un argument a été passé */
    if (argc != 2) 
    {
        printf("Usage: %s <mot_de_passe>\n", argv[0]);
        return EXIT_FAILURE;
    }


    /* Comparer la chaîne passée avec la constante */
    if (strcmp(argv[1], MOT_DE_PASSE) == 0) 
    {
        printf("Accès autorisé\n");
        return EXIT_SUCCESS;
    } 
    else 
    {
        printf("Accès interdit\n");
        return EXIT_FAILURE;
    }
}

on teste le code !

bruno@elliott:~/Works/langage_C/passwd$ ./mot_de_passe dorian
Accès interdit
bruno@elliott:~/Works/langage_C/passwd$ echo $?
1
bruno@elliott:~/Works/langage_C/passwd$ ./mot_de_passe secret123
Accès autorisé
bruno@elliott:~/Works/langage_C/passwd$ echo $?
0
bruno@elliott:~/Works/langage_C/passwd$

Le hacker !

le hacker avec la commande hexdump va regarder dans le code! et découvrir en clair le mot de passe !

hexdump -C mot_de_passe


....
000011f0  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
*
00002000  01 00 02 00 55 73 61 67  65 3a 20 25 73 20 3c 6d  |....Usage: %s <m|
00002010  6f 74 5f 64 65 5f 70 61  73 73 65 3e 0a 00 73 65  |ot_de_passe>..se|
00002020  63 72 65 74 31 32 33 00  41 63 63 c3 a8 73 20 61  |cret123.Acc..s a|
00002030  75 74 6f 72 69 73 c3 a9  00 41 63 63 c3 a8 73 20  |utoris...Acc..s |
00002040  69 6e 74 65 72 64 69 74  00 00 00 00 01 1b 03 3b  |interdit.......;|
00002050  28 00 00 00 04 00 00 00  d4 ef ff ff 74 00 00 00  |(...........t...|
00002060  14 f0 ff ff 9c 00 00 00  24 f0 ff ff 44 00 00 00  |........$...D...|
00002070  0d f1 ff ff b4 00 00 00  14 00 00 00 00 00 00 00  |................|
.....

Pour sécuriser utilisons le hash simple !

Proposer un code utilisant le hash simple permettant de ne pas connaitre le mot de passe en regardant dans le code