{ "cells": [ { "cell_type": "markdown", "id": "6e067ec9-baba-4d8c-b1a2-c4e45b28ddfa", "metadata": {}, "source": [ "# Fonctions de hachage\n", "Une _fonction de hachage_ est une fonction qui permet de calculer, à partir de n'importe quel message, une chaîne de caractères de longueur limitée, appelée le **haché** du message.\n", "\n", "Une fonction de hachage est déterministe, c'est-à-dire que le résultat du calcul pour deux messages identiques est toujours le même. Cette propriété est utilisée pour l'authentification par mot de passe. En effet, au lieu de stocker les mots de passe en clair sur un serveur, il est souhaitable de stocker uniquement leurs hachés. Ainsi, l'utilisateur reste le seul à connaître son mot de passe. Pour l'authentification, le serveur calcule le haché du mot de passe entré par l'utilisateur, et vérifie qu'il est bien identique à celui qui est stocké dans sa base de données. \n", "\n", "Par ailleurs, une fonction de hachage doit posséder plusieurs\n", "propriétés de sécurité. Par exemple, une fonction de hachage doit être **résistante aux collisions** c'est-à-dire qu'il ne doit pas être facile de trouver deux messages distincts qui ont le même haché." ] }, { "cell_type": "markdown", "id": "ca3393b1-86fe-4731-9ca1-ea16bf2e1c37", "metadata": {}, "source": [ "## Fonctions de hachages naïves\n", "L'objectif des fonctions de hachages naïves dans cet exercice est de vous permettre de trouver des collisions facilement grâce à un petit programme et un peu de réflexion.\n", "\n", "1) Soient les hachés suivants par une certaine fonction de hachage H :\n", "```\n", "H(A) = 65\n", "H(B) = 66\n", "H(C) = 67\n", "H(Z) = 90\n", "H(a) = 97\n", "H(z) = 122\n", "H(AB) = 131\n", "H(ABC) = 198\n", "H(CB) = 133\n", "```\n", "Quel est le calcul effectué par cette fonction de hachage H ?\n", "Trouvez (au moins) une pré-image de 298 (qui a du sens ou pas).\n", "\n", "2) Pour éviter les soucis des anagrammes, on modifie un peu la fonction de hachage et on construit la fonction G suivante, qui produit les hachés suivants :\n", "```\n", "G(A) = 65\n", "G(B) = 66\n", "G(C) = 67\n", "G(D) = 68\n", "G(AB) = 197\n", "G(ABC) = 398\n", "G(ABCD) = 670\n", "G(BAC) = 397\n", "```\n", "Trouvez le fonctionnement de cette nouvelle fonction de hachage G et deux prénoms d'au plus six lettres qui forment une collision.\n", "Les personnages célèbres suivants peuvent vous aider : Federer, Hitchcock, Knuth, Obispo, Polo, Popeye, Murphy, Shannon, Smith, Turing, Turner, Tyson, Wilde." ] }, { "cell_type": "code", "execution_count": null, "id": "b3007a18-77f2-45eb-b4f3-34b5ede5645f", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "id": "0d722852-82cc-4f1e-8bc7-550a62f9aa5d", "metadata": {}, "source": [ "## Adobe\n", "Le hachage des mots de passe est une précaution élémentaire dans la gestion d’une base de données\n", "d’utilisateurs. Malheureusement, dans le cas de la fuite, en 2013, de la base de données de la société\n", "Adobe, pour chaque login était aussi stocké, en clair, dans la base de données, un indice. Cette\n", "information était destinée à permettre à l’utilisateur de retrouver son mot de passe en cas d’oubli,\n", "mais représentait potentiellement une faille de sécurité.\n", "\n", "Voici un extrait (fictif) de la base de données Adobe qui a (réellement) fuité il y a maintenant quelques années.\n", "| **Login** | **Hint** | **Hash SHA-256** |\n", "| --------- | ------------- | ---------------- |\n", "| Bart | element 74 | 068be8be83f9bfafd1545d357fd3cd132f8c659effd11e635a698811b796c880 |\n", "| Bob | numbers | 15e2b0d3c33891ebb0f1ef609ec419420c20e320ce94c65fbc8c3312448eb225 |\n", "| Carlton | 1 to 9 | 15e2b0d3c33891ebb0f1ef609ec419420c20e320ce94c65fbc8c3312448eb225 |\n", "| Homer | metal | 068be8be83f9bfafd1545d357fd3cd132f8c659effd11e635a698811b796c880 |\n", "| John | nine | 15e2b0d3c33891ebb0f1ef609ec419420c20e320ce94c65fbc8c3312448eb225 |\n", "| Lisa | mendeleiev 74 | 068be8be83f9bfafd1545d357fd3cd132f8c659effd11e635a698811b796c880 |\n", "| March | hard rock | 068be8be83f9bfafd1545d357fd3cd132f8c659effd11e635a698811b796c880 |\n", "| William | digits - 0 | 15e2b0d3c33891ebb0f1ef609ec419420c20e320ce94c65fbc8c3312448eb225 |\n", "\n", "Trouvez les 2 mots de passe qui sont utilisés par ces utilisateurs d'Adobe, prouver vos résulats.\n", "\n", "On donne ci-dessous un exemple d'utilisation de la fonction SHA256 :\n" ] }, { "cell_type": "code", "execution_count": 3, "id": "10edb2e4-324f-4d33-a636-ebd9c5af9dbc", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "'2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824'" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "import hashlib\n", "pswd=\"hello\".encode()\n", "hashlib.sha256(pswd).hexdigest()" ] }, { "cell_type": "markdown", "id": "b6745d26-98b4-4c57-9cf3-b0861070f43c", "metadata": {}, "source": [ "## Route 666\n", "Un célèbre chanteur de rock qui habite aux USA décide de publier son numéro de téléphone d'une façon cachée sur Internet. Comme tous les numéros aux USA, le sien commence par le code national 001, qui est suivi par un code de zone (_area code_) à 3 chiffres, un préfixe à 3 chiffres, puis un numéro unique à 4 chiffres. \n", "Il hache son numéro en utilisant la fonction de hachage SHA256 et obtient :\n", "`fbac829d8d0d299bead993cab8360e565c956fca1a647a93cc12a11840ac9702`\n", "\n", "Il publie le texte suivant sur les réseaux sociaux :\n", "\n", "---\n", "Find me if you can!#Rock#SHA256\n", "\n", "#fbac829d8d0d299bead993cab8360e565c956fca1a647a93cc12a11840ac9702\n", "\n", "#USA#ZONE555#PREFIX666\n", "\n", "---\n", "\n", "- Combien de valeurs faut-il essayer pour retrouver le numéro de téléphone par force brute ?\n", "- Retrouvez le numéro en utilisant `Sage`" ] }, { "cell_type": "code", "execution_count": null, "id": "b293027a-3122-4017-9dfc-48eb25019470", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "id": "09d1452b-16de-4b7e-82fd-acd97efa09e6", "metadata": {}, "source": [ "## Test du canard\n", "Dans cette question, la fonction de hachage $H_p^M$ est paramétrée par des entiers $p$ et $M$ et définie de la façon suivante :\n", "$$H_p^M(u)=u^p\\;\\texttt{ mod }M$$\n", "\n", "Trouvez des collisions sur cette fonction de hachage." ] }, { "cell_type": "markdown", "id": "979a2607-2c97-4eb4-8377-62e630d5d11e", "metadata": {}, "source": [ "## Forcer le hasard\n", "Madame et Monsieur Confusious détestent faire le ménage. Ils veulent trouver une façon équitable de partager cette tâche. Ils ont imaginé le système suivant :\n", "Ils utilisent une boîte postale dont chacun possède un exemplaire de clé. Monsieur Confusious commence toujours le protocole et choisit un nombre $N$ compris entre 1 et 50. Pour cacher la valeur choisie, il utilise une fonction de hachage $H$ et calcule $h=H(N)$, qu'il imprime et dépose dans la boîte postale. \n", "Madame Confusious passe ensuite par la boîte postale où elle peut voir le message haché par son mari. Elle choisit un nombre $M$ entre 1 et 50, calcule $H(M)$, l'imprime et le laisse à son tour dans la boîte aux lettres.\n", "Lorsqu'ils rentrent du travail, ils récupèrent les deux messages déposés dans la boîte postale. Ils révèlent les valeurs $N$ et $M$ qu'il avaient choisies. Afin, de prouver la véracité de ces valeurs, ils vérifient que les valeurs déposées correspondent respectivement à $H(N)$ et $H(M)$. Ensuite ils calculent la somme $N+M$ : si la valeur est impaire alors c'est Madame Confusious qui doit le faire. \n", "\n", "1) Expliquez le problème (algorithmique) que Monsieur et Madame Confusious essayent de résoudre.\n", "2) Après deux mois, Monsieur Confusious a fait le ménage tous les jours. Il soupçonne sa femme de tricher, expliquer comment elle pourrait faire ?\n", "3) Donner des contre-mesures pour améliorer le protocole." ] }, { "cell_type": "markdown", "id": "9b896847-ea24-4a6e-99c9-4e94d2f013ed", "metadata": {}, "source": [ "# OpenSSL\n", "## Chiffrement Symétrique\n", "\n", "1. Créez un fichier texte `message.txt` avec le message de votre choix. Utilisez la commande suivante pour chiffrer ce message avec `openssl` :\n", "\n", "```bash\n", "openssl enc -aes-256-cbc -pbkdf2 -in message.txt -out ciphersym.bin\n", "```\n", "\n", "2. Envoyez ce message chiffré à une autre personne avec le mot de passe. La personne peut alors déchiffrer le message avec la commande suivante :\n", "```bash\n", "openssl enc -d -aes-256-cbc -pbkdf2 -in ciphersym.bin -out plainsym.txt\n", "```\n", "\n", "## Génération de clefs RSA\n", "1. Générez une paire de clef RSA de longueur 4096 avec la commande suivante (la passphrase doit faire entre 4 et 1023 caractères):\n", "```bash\n", "openssl genrsa -aes256 -out rsakey.pem 4096\n", "``` \n", "\n", "2. Extrayez la clé publique de `rsakey.pem` avec la commande suivante :\n", "```bash\n", "openssl rsa -in rsakey.pem -pubout -out public.pem\n", "``` \n", "\n", "3. Les informations sur le module et les nombres premiers utilisés sont chiffrées avec AES-256 dans le fichier `rsakey.pem`. Utilisez la commande suivante pour trouver les éléments $N,p,q,e,d$ de la clé RSA générée :\n", "```bash\n", "openssl rsa -in rsakey.pem -noout -text\n", "``` \n", "\n", "4. Utilisez sagemath pour vérifier que les valeurs sont correctes.\n", "\n", "\n", "## Chiffrement à clé publique\n", "1. En utilisant la commande suivante, chiffrez le même message `message.txt` avec la clef RSA que vous avez générée précédemment :\n", "```bash\n", "openssl pkeyutl -encrypt -in message.txt -pubin -inkey public.pem -out cipherasym.bin\n", "``` \n", "2. Comparez les deux chiffrés obtenus (symétrique et asymétrique) et leurs tailles.\n", "3. Déchiffrez le chiffré `cipherasym.bin` avec la commande suivante :\n", "```bash\n", "openssl pkeyutl -decrypt -in cipherasym.bin -inkey rsakey.pem -out plainasym.txt\n", "``` \n", "4. Quelle est le nombre maximal de caractères que peut contenir le fichier `message.txt` ?\n", "Pour info, un fichier `.txt` commence par un header (invisible) de 12 octets. Vous voudrez peut-être vous aider d'une commande du type :\n", "```bash\n", "sage -c 'print(\"a\"*10)' > message2.txt\n", "```\n", "pour vérifier vos hypothèses.\n", "\n", "5. Envoyez votre clé publique à une autre personne et demandez-lui de vous envoyer un message chiffré, puis déchiffrez-le avec votre clé privée.\n", "\n", "## Signature\n", "1. Pour signer un message, on utilise le chiffrement RSA, avec la commande suivante :\n", "```bash\n", "openssl pkeyutl -sign -in messageasigner.txt -inkey rsakey.pem -out signedmessageasigner.bin\n", "```\n", "\n", "2. Quelle est le nombre maximal de caractères que peut contenir le fichier `messageasigner.txt` ?\n", "3. Comment signer des messages plus gros ? La commande suivante peut vous aider :\n", "```bash\n", "openssl dgst -sha256 -binary message.txt > hmessage.dgst\n", "``` \n", "\n", "4. Pour vérifier la validité d'une signature il faut utiliser la commande suivante :\n", "```bash\n", "openssl pkeyutl -verify -in messageasigner.txt -pubin -inkey public.pem -sigfile signedmessageasigner.bin\n", "``` " ] } ], "metadata": { "kernelspec": { "display_name": "SageMath 10.7", "language": "sage", "name": "sagemath-10.7" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.13.3" } }, "nbformat": 4, "nbformat_minor": 5 }