Bibm@th

Forum de mathématiques - Bibm@th.net

Bienvenue dans les forums du site BibM@th, des forums où on dit Bonjour (Bonsoir), Merci, S'il vous plaît...

Vous n'êtes pas identifié(e).

#1 12-04-2019 15:38:47

jeepy2
Membre
Inscription : 12-04-2019
Messages : 2

générateur pseudo-aléatoire de python, One-time-pad, seed and Co.

Bonjour,

C'est une question plus orientée protocole cryptographique que purement mathématique, mais je pense que cela puisse intéresser certains contributeurs.
Si c'est hors sujet, désolé pour le dérangement.

contexte :

Dans le cadre d'un petit prgm perso de One-Time-Pad j'explore le monde des générateurs pseudo-aléatoires (PRNG).
Les PRNG build-in dans python et/ou numpy ne sont pas "trop" solides dans la mesure où la taille du seed qui peut leur être appliquée est limitée. Si le nombre de seed possible est limité (ex : 2*32-1, pour 32 bits, pour Numpy soit environ 4,3 milliards, je n'ai pas trouvé l'info pour python 2.7), les attaques en force brute sur une clé deviennent "crédibles" en durée avec les puissances de calculs disponibles aujourd'hui (au pif je pense que ça se compterait en jours).
Il existe des algorithmes alternatifs tout prêts qui tiennent compte de ce problème : par exemple Tyche (évolution de Fortuna) écrit par Bruce Schneier et coll. et disponible pour python sur Github. J'ai bien essayé de l'installer avec PIP, mais j'ai reçu un tas de warnings aussi abscons les uns que les autres, j'ai donc abandonné cette voie pour l'instant (problèmes de cohérence de versions entre les différent éléments sans doute).

Hormis les calculs sophistiqués hors de ma portée dans Tyche, j'ai retenu que son principe est de changer de seed en cours de traitement de façon aléatoire.
Je pense donc essayer d'appliquer ce principe à mon One-Time-Pad perso, mais avant de me lancer je voudrais quelques avis éclairés sur mes hypothèses.

ma question :

Changer aléatoirement de seed avec plusieurs random.SystemRandom() (lui même aléatoire) au cours de la génération de ma clé complique-t-il significativement la difficulté d'une attaque en force brute en terme de temps de traitement ?

exemple :

Sur un ficher de 4 Mo je change aléatoirement 20 fois de seed avec le PRNG de Numpy soit 2**32-1 = 4 294 967 295 (env 4,3 milliards) de seeds possibles.
Après attaque en force brute, je me retrouve alors avec 4,3 milliards de fichiers candidats dont 20 contiennent chacun un bloc de données en clair, de tailles variées, mais "aisément" repérables en fonction du type de fichier chiffré (image ou texte intelligible). Non seulement l'un de ces 20 candidats contiendra en clair l'en-tête standard des types de fichier usuels (jpg, pdf, doc, etc...) mais sera aussi au début du fichier, donc facile à repérer. Ensuite il suffit d'ordonner les blocs clairs en fonction de leur offset depuis le début du fichier pour reconstituer le clair intégralement.
Plus généralement si j'applique un nombre aléatoire n de changements de seed, à la fin j'ai n fichiers sur 4,3 milliards contenant chacun un bloc de déchiffré. Plus n est grand plus les blocs clairs seront petits, donc plus difficiles à repérer et à réarranger. A la limite, si je change de seed à chaque octet au chiffrage, j'aurais 4 000 000 de candidats contenant chacun 1 octet en clair, donc quasi impossibles à repérer, il faudra alors tester tous les classements possibles sur 4,3 milliards ce devrait rallonger sérieusement le temps de traitement.
Ce serait donc le nombre de combinaisons de n parmi 4.3 Milliards ?

Tout le "jeu" consisterait alors à trouver un n qui va bien : suffisant pour augmenter la durée/coût de l'attaque (durée la plus proche possible de la date de péremption des datas à protéger) sans pour autant trop pénaliser le temps de chiffrage.

j'ai bon ? beaucoup de boulot pour pas grand chose ?

merci d'avance.

remarque : reste aussi à vérifier le comportement de python avec un nombre de changements de seed aussi élevé. SystemRandom() utilise un paramètre Date/Time system, entre autres, pour fabriquer le seed, donc les seeds utilisés seront quelque part ordonnés dans le temps, est-ce un point faible ?


(remarque pour le modérateur : je suis le même inscrit que jeepy dont j'ai perdu le login et le pwd, merci de bien vouloir fermer le compte jeepy).

Hors ligne

#2 12-04-2019 16:45:31

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 13 502

Re : générateur pseudo-aléatoire de python, One-time-pad, seed and Co.

Re,

Je n'ai pas lez pouvoir de supprimer le compte, juste de le signaler à Fred, l'Admin.
Pour réponse aux questions que tu poses attends que passent Rossignol ou LeSingeMalicieux.
La dernière fois, je t'avais recommandé de lire cette page http://python.jpvweb.com/python/mesrece … enalea_bbsde Tyrtamos.
A propos du générateur Blum Blum Shub :

Wikipedia a écrit :

Le générateur n'est pas approprié aux simulations, mais plutôt à la cryptographie, car il est assez lent.

Cependant, il possède une sécurité inhabituelle, puisqu'il a été démontré, tout d'abord, qu'il était cryptographiquement sûr sous l'hypothèse qu'il soit difficile de déterminer si, modulo un entier composé, un nombre est un carré ou non (problème de la résiduosité quadratique). Par la suite, il a été prouvé qu'il était cryptographiquement sûr, sous l'hypothèse que le problème de la factorisation soit difficile, et qu'au plus $\ln(( \ln( M ) ) $ bits de poids faible de chaque $x_ n$ soient sortis à chaque itération. Dans ce cas, il n'est pas possible de différencier la suite produite d'une suite réellement aléatoire.

Le générateur BBS de Tyrtamos est écrit en Python 2.x, c'est dire que ses estimations de temps en tenant compte de l'évolution des machines actuelles  par rapport aux machines de l'époque, doivent être sensiblement moins élevées

Pour que le générateur fonctionne en 3.x :
Remplacer print truc par print(truc)
Remplacer xrange() par range()
N-B : A partir de la version 2.6 le def pgcd() de Tyrtamos est inutile, importer gcd :

 from fractions import gcd

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#3 13-04-2019 10:02:45

jeepy2
Membre
Inscription : 12-04-2019
Messages : 2

Re : générateur pseudo-aléatoire de python, One-time-pad, seed and Co.

J'ai bien regardé BBS et il répond bien à la résolution du problème, à l'instar de Tyche, avec en plus une accessibilité toute faite puisque le code python est fourni.
Je pourrais bien sûr utiliser cette solution toute prête, mais je suis plus dans une intention ludique et étudiante : le peaufinage de ce petit projet purement artificiel et théorique me permet de découvrir et comprendre plus finement les aspects techniques et théoriques de la cryptographie. En échafaudant mes propres hypothèses/solutions et en les confrontant aux autres j'élargi ma vision et compense mes lacunes. Bref j'avance d'un petit pas en plus à chaque fois et c'est là mon véritable intérêt de la chose.
De plus chercher à consolider une réalisation "amateur" de ONE-TIME-PAD n'a qu'un intérêt limité puisqu'il existe beaucoup d'autres solutions toutes prêtes ça et là sur la toile qui permettent des échanges sûrs et pratiques (PGP, etc...), donc c'est et ça reste un loisir/jeu..

Il reste que ton partage au sujet de BBS m'a permis de voir des lignes de code python que je n'aurais jamais eu l'idée d'écrire de cette façon, c'est déjà ça de gagné...

Bon WE.

Hors ligne

Réponse rapide

Veuillez composer votre message et l'envoyer
Nom (obligatoire)

E-mail (obligatoire)

Message (obligatoire)

Programme anti-spam : Afin de lutter contre le spam, nous vous demandons de bien vouloir répondre à la question suivante. Après inscription sur le site, vous n'aurez plus à répondre à ces questions.

Quel est le résultat de l'opération suivante (donner le résultat en chiffres)?
vingt trois moins cinq
Système anti-bot

Faites glisser le curseur de gauche à droite pour activer le bouton de confirmation.

Attention : Vous devez activer Javascript dans votre navigateur pour utiliser le système anti-bot.

Pied de page des forums