Algorithme pour déchiffrer les données en traits dessinés

Question

Supposons que j’ai un fichier crypté sur un iPhone et chaque fois que je souhaite le déchiffrer, je souhaite "dessiner". un symbole de déchiffrement au lieu de devoir utiliser un clavier pour le saisir.

Si vous demandez à l'utilisateur de dessiner un symbole pour déchiffrer un fichier à chaque fois que vous en avez besoin (par exemple, chaque fois qu'il lance votre application), il préférerait probablement qu'il soit obligé de saisir un mot de passe de 20 caractères environ sur le petit clavier. , et ils obtiendraient toujours la sécurité qu’un mot de passe de 20 caractères leur donnerait (en fonction de la complexité de la forme / du symbole qu’ils dessinent).

Le symbole qu'ils dessineraient serait probablement un trait (par exemple, il est terminé une fois que vous avez levé votre doigt), mais peut être très complexe, de sorte qu'il est difficile pour quelqu'un d'autre de le répéter, même s'il vous voit le dessiner. En quelque sorte, la signature de chaque personne est unique et difficile à reproduire. En fait, cela risque de compliquer excessivement les choses s'il devait empêcher la duplication. Donc, pour l'instant, cela peut être ignoré et nous pouvons supposer que le symbole ne sera pas vu par quelqu'un d'autre et qu'il importe donc peu de savoir s'il peut être répété. par eux ou pas.

Je suppose que la vraie question est de savoir comment convertir le même trait (de manière raisonnable) en une même clé (par exemple, la valeur de hachage). Il devrait évidemment y avoir un seuil de tolérance dans l’algorithme, car on ne peut pas s’attendre à ce que l’utilisateur répète le trait exactement à 100%.

L'utilisation du symbole comme méthode de décryptage ajoute une autre dimension à ce problème. Vous ne voudrez jamais stocker la valeur de hachage générée sous une forme non chiffrée, car quelqu'un pourrait alors accéder à cette partie du disque dur et obtenir la clé de déchiffrement sans avoir à passer par le processus de dessin complet et à déchiffrer manuellement le fichier. De plus, vous ne voudrez probablement rien stocker sur la façon dont la forme est dessinée.

Les "& amp; & amp; "" sont un bon exemple d'accident vasculaire cérébral qu'un utilisateur peut utiliser comme symbole de déchiffrement. symbole. Imaginez un utilisateur qui dessine ce symbole sur son iPhone chaque fois qu'il doit déchiffrer un fichier. La taille du symbole peut ne pas être la même à chaque fois qu'il est dessiné. De plus, la rotation du symbole peut être différente en fonction de la manière dont l’utilisateur tient son appareil. Idéalement, dans les deux cas, étant donné que le symbole a été dessiné, il devrait pouvoir générer la même valeur de hachage et ainsi déchiffrer le fichier, par rapport aux traits de l'utilisateur.

Je pensais que quelque chose comme la reconnaissance de forme ou de caractère est un algorithme similaire. Où l'utilisateur dessine quelque chose (représentant raisonnablement une forme) et le fixe ensuite à la forme correcte qui aurait la même valeur de hachage à chaque fois qu'il est dessiné. Cependant, pour quelque chose comme cela, vous aurez probablement besoin d'une base de données de formes pouvant être dessinées, et si vous choisissez quelque chose comme toutes les lettres de l'alphabet, vous n'avez que 26 lettres. Et en supposant que l'utilisateur n'ait besoin que d'un seul symbole pour déchiffrer le fichier, vous disposez d'un mot de passe extrêmement peu sécurisé avec seulement 26 possibilités.

Une autre chose à laquelle j'ai pensé est que vous pouvez diviser le symbole dessiné en minuscules segments, puis exécuter la reconnaissance de symbole sur ceux-ci. Imaginez donc que vous ayez 4 symboles dans une base de données: ligne verticale, ligne horizontale et diagonale dans les deux sens. Au fur et à mesure que l'utilisateur dessine, chaque segment est reconnu comme l'un d'entre eux, puis tous sont combinés pour former une valeur de hachage. Imaginez donc que l’utilisateur ait choisi comme symbole de déchiffrement la lettre minuscule "r". Ils commenceraient donc par tracer une ligne verticale vers le bas, suivie d'une ligne verticale vers le haut, suivie d'une ligne diagonale vers le haut et à droite. Un problème avec cette méthode est comment sauriez-vous quand diviser le trait en segments individuels? Vous voudrez probablement aussi prendre en compte la longueur approximative de chaque segment individuel (par exemple, par incréments de 40 pixels). De cette façon, si quelqu'un dessine un " déformé "r" lorsque la bosse sort vers le bas, elle n'est pas reconnue comme le même symbole et ne décrypte donc pas le fichier.

Une troisième méthode peut être de diviser l’écran en une grille (vous ne savez pas encore quelle taille), de voir dans quelles cellules le trait est tracé et d’utiliser ces données pour générer une chaîne.

Avez-vous d'autres idées sur la façon dont cela pourrait être mis en œuvre? Avez-vous déjà entendu parler de quelque chose comme ça? Existe-t-il des défauts fondamentaux qui empêcheraient un système de ce type de fonctionner?

Merci

Answer 1

Le problème du cryptage des données avec du matériel clé pouvant comporter de petites erreurs a été étudié de manière approfondie. En particulier, il existe un certain nombre de propositions pour protéger des données en utilisant des données biométriques (par exemple des empreintes digitales ou un scan de la rétine) en tant que clé. Une approche typique consiste à utiliser un code de correction d'erreur approprié, à prendre votre clé K d'origine, à en calculer le syndrome et à ne stocker que le syndrome. Une fois que vous obtenez une seconde lecture de votre clé K ', le syndrome peut être utilisé pour restaurer K à partir de K' si K et K 'sont suffisamment proches (où «suffisamment proches» dépend bien sûr du schéma de correction d'erreur.)

Pour vous aider à démarrer, voici un document proposant un schéma de vault fuzzy . Ceci est une proposition générale pour un schéma de chiffrement utilisant un "fuzzy" clé. Bien entendu, vous devez encore examiner comment extraire des caractéristiques des dessins suffisamment stables pour utiliser un tel schéma de correction d'erreur. Vous devrez également examiner combien d'entropie vous pouvez extraire de tels dessins. Aussi mauvais que soient les mots de passe en ce qui concerne l'entropie, ils peuvent être difficiles à battre.

Answer 2

Je voudrais essayer une variante de la variante de segmentation: Reconnaître des motifs simples - je m'en tiendrai aux lignes droites et diagonales, mais en théorie, vous pouvez également ajouter des cercles, des arcs et peut-être d'autres choses.

Vous pouvez être tout à fait sûr quand une ligne se termine et une autre commence car il y a 8 directions et vous pouvez détecter un changement de direction (ou pour une approche plus simple, il suffit de détecter stylo en haut et en bas et de les utiliser comme délimiteurs de ligne). La première ligne donne un facteur d'échelle, de sorte que la longueur d'une ligne sur deux puisse être représentée sous forme de facteur (par exemple, sous une forme en L habituelle, la première ligne verticale donne la "longueur de base" b et l'autre ligne avoir la longueur d'environ 0,5 * b). Une fois que l'utilisateur a terminé, vous pouvez utiliser le plus petit facteur s pour "arrondir". les longueurs, de sorte que vous aurez un tableau de longueurs entières comme [1 * s, 2 * s, 4 * s, 5 * s]. Cela empêchera le système d’être trop précis et l’utilisation de la longueur de base rend le système résistant à la mise à l’échelle.

Maintenant, convertissez d’une manière ou d’une autre ces informations (longueurs et directions) en une chaîne (ou une valeur de hachage, comme vous voudrez) et ce sera la même chose pour les mêmes traits, même si le symbole est traduit ou mis à l'échelle.

De plus, vous pouvez stocker une valeur de décalage 2D (bien entendu "arrondie") pour chaque ligne après la deuxième ligne, de sorte que les lignes doivent également se trouver à la même position, si vous ne le faites pas. , L et T obtiendront probablement la même chaîne (1 ligne haut-bas, 1 ligne gauche-droite longueur 0.5). Donc, stocker des positions renforce un peu le tout mais est facultatif.

EDIT:

Si vous prenez l'angle de la première ligne comme angle de base, vous pouvez même le rendre robuste en rotation.

Veuillez noter que cet algorithme ne donne que 3 bits par trait si toutes les lignes ont la même longueur et un maximum de peut-être 6-8 bits par trait, certaines plus si vous enregistrez des positions également. Cela signifie que vous aurez besoin d’un symbole assez complexe d’environ 20 à 40 traits pour obtenir une sécurité de 128 bits.

Un moyen simple d’ajouter plus de variation / sécurité serait de laisser l’utilisateur utiliser différentes couleurs d’une palette donnée.

Pour réduire le risque que quelqu'un vous surveille, vous pouvez supprimer chaque ligne après son tracé ou modifier la couleur en une couleur présentant un très faible contraste par rapport à l'arrière-plan.

Answer 3

La reconnaissance de l'écriture prend souvent la durée du trait plus en compte que la durée réelle, etc.

Bien que cela concerne la sensibilité à la pression, je pense que vous pourrez peut-être voir des éléments conceptuels similaires à ce que vous pensez ici .... jdadesign.net/safelock/

Ce n'est pas exactement le même sujet, mais c'est la chose la plus proche qui me vienne à l'esprit pour le moment.

Answer 4

Je ne pense pas que vous puissiez obtenir suffisamment de & bits; bits " à partir d'un symbole dessiné à la main pour effectuer un cryptage sécurisé. Comme vous le constatez, vous devez prévoir suffisamment de temps pour reconnaître que les variations naturelles du dessin seront tolérées. En d'autres termes, vous devez éliminer le bruit dans les traits en les lissant pour obtenir un signal reproductible. Mais le bruit (entropie élevée) permet de meilleures clés cryptographiques.

Pensez-y de cette façon. Si vous décomposiez le geste en segments haut, bas, gauche et droite, chaque segment représenterait 2 bits d'information. Pour une clé AES, le symbole aurait besoin de 64 segments de ce type. C'est un geste assez compliqué à retenir. Et si cela est simplifié en répétant de nombreux segments à la suite ("bon, bon, bon, ..."), cela crée une clé moche (prévisible, non aléatoire).

Answer 5

J'ai eu une autre réflexion à ce sujet. Je ne suis pas une comp-sci, mais je voudrais quelque chose comme ça.

Disons que, quel que soit le symbole ou le "motif" quelqu'un dessine. La seule chose viable à analyser reste tous les points du modèle générés dans les événements touchBegan, touchMoved et touchEnded.

Alors ... prenons tous les points générés, que ce soit 100 ou 1 000 000, cela n'a pas vraiment d'importance.

Divisez-les en groupes, autant de groupes que vous le souhaitez. Plus on suppose que plus on est de fous, mais pour cet exemple, classons-les en 4 groupes. Avec 100 points, le groupe 1 contiendrait les points 1 > 25, le groupe 2 contient 26 > 50 et ainsi de suite.

Pour chaque groupe, utilisez tous les points pour calculer une position moyenne.

Cela fonctionnera mieux si les espaces de travail sont divisés en une grille et que les "positions moyennes" sont tracées sur leur coordonnée la plus proche.

Vérifiez ensuite la distance relative entre tous les groupes. Ainsi, entre 1,2,3,4,3,4,4,4,4.

Vous avez maintenant autant de points distincts et d'informations sur ces points pour générer une clé. Les moyennes et la grille devraient aider à lisser une partie, sinon la totalité de l'entropie.

Vous devrez peut-être demander à l'utilisateur de tracer son motif plusieurs fois et comparer chaque groupe à des groupes de tentatives précédentes. De cette façon, vous pouvez identifier les groupes que les utilisateurs peuvent tracer de manière cohérente. Cela présente l'avantage supplémentaire de former les utilisateurs à dessiner leur modèle.

Je pense que plus vous aurez de points et de groupes, plus cela sera précis.

En fait, je vais essayer moi-même.

Answer 6

Les gestes.

http://depts.washington.edu/aimgroup/proj/dollar/

Vous pouvez définir vos propres algorithmes pour des gestes particuliers. Par exemple un cercle,

1. Trouver le point de départ 2. Trouvez le point le plus à gauche, le plus à droite et le plus éloigné et obtenez un rayon approximatif. 3. comparer tous les points au rayon avec une marge d'erreur (25%?) 4. Si le rayon vérifie, vous avez un cercle.

Ligne droite verticale: 1. Vérifiez le point de départ et les positions X et Y du point final. 2. Comparez les points intermédiaires entre les points x et y du début et de la fin. 3. Si elles sont à peu près sur la même coordonnée X, mais que les coordonnées sont ascendantes ou descendantes, vous avez une ligne verticale.

Et ainsi de suite, de plus en plus complexe pour des gestes plus compliqués.

Vous pouvez même combiner des gestes. Alors disons que vous avez un algorithme pour 6 gestes. Vous pouvez les combiner pour former différents symboles. L'ordre dans lequel les gestes sont créés peut être important car il ajoute une couche de sécurité supplémentaire.

Answer 7

Et si vous preniez toutes les coordonnées x, y du trait et préformiez une sorte d'opération linéaire à 2 sens sur eux? Vous pouvez ensuite calculer un hachage "approximatif", et si le nombre calculé lorsque le trait est dans ... disons 10% de votre approximation, vous accordez l'accès ..

Answer 8

Tout dépend du type d’attaque que vous essayez de prévenir. Si vous voulez un chiffrement complet, en supposant que l'attaquant dispose d'un accès complet au fichier chiffré, vous aurez besoin de beaucoup d'entropie pour atteindre un niveau de protection convenable. En supposant que les algorithmes soient corrects, vous pouvez alors prendre les deux à la puissance de l'entropie d'entrée en bits (la limite supérieure pour cela est le nombre d'entrées différentes possibles), multiplier par le temps que prend la procédure de configuration de clé, divisez par plus de puissance de calcul de l'attaquant et obtenez le temps qu'il faut pour percer votre cryptage par la force.

Par exemple, quelque chose comme la méthode de déverrouillage de la figure à 9 cellules d'Android pourrait vous procurer environ 16 bits d'entropie. Supposons que vous utilisiez 5 secondes de temps CPU pour calculer la clé de cryptage. Ensuite, avec un PC moyen, il faut 5 * 2 ** 16/20 secondes, ou environ 4,5 heures pour craquer. Toute perte d'entropie dans l'entrée ou tout manque d'efficacité dans la configuration de la clé et le cryptage le réduira rapidement à quelques minutes, sans parler de l'utilisation éventuelle de grappes d'ordinateurs.

Pour être franc, ce ne sera pas mieux que de stocker le fichier dans un format de fichier obscur et d’espérer que personne ne le découvre