Il y a un peu plus d'un an de ça, j'ai travaillé sur une application web de stockage de données sur qrcode utilisant un système proche du Raid des disques dur permettant de proposer à l'utilisateur de stocker des données sur une série de qrcode et de pouvoir n'utiliser qu'une fraction de ces qrcodes pour récupéré ses données.
À l'époque, il s'agissait d'une application web qu'il était compliqué de déployer car nécessitant quelques binaires et notamment une version patché de zbarimg, j'avais l'idée de porter l'application en nodejs et faire une interface avec nodewebkit, mais je n'ai pas trouvé le temps et la motivation.
Malgré ma fainéantise, docker me permet aujourd'hui de distribuer une version libre et fonctionnelle de l'application et de la proposer à tout un chacun pour jouer avec.
La genèse du projet était de trouver un moyen de stocker des données importante sur le long terme comme un portefeuille de cryptomonnaie, une clé privé, etc, de permettre de distribuer le stockage des données entre plusieurs lieux ou personnes et de pouvoir récupérer ces données après une longue période de temps alors même qu'une fraction des qrcodes aurait été perdue. Les données sont chiffrées sur les qrcodes et il n'est pas possible d'accéder partiellement aux données avec un seul qrcode.
D'un point de vu technique, il s'agit des mêmes algorithmes mis en œuvre dans le RAID 6, à savoir Reed-solomon, le développement de ce projet m'a été très formateur d'un point de vu mathématique, les corps de Galois utilisés pour calculer les données de parités ont des propriétés étonnantes.
L'implémentation d'origine en PHP est disponible sur github, le projet est lourd car il est livré avec des matrices pré-calculées afin d'accélérer le codage et le décodage des données. Le Dockerfile est également disponible sur github et un container précompilé de l'application sur le hub docker.
Il existe quelques limitations actuellement, il n'est pas possible de créer plus de 256 qrcodes (255 dans l'implémentation actuelle, un bug dont je n'ai pas identifié l'origine se produit lorsque l'on cherche à décoder 256 qrcodes), et la taille des données que l'on peut stocker au maximum n'est pas très importante (740 096 octets sans parités), une version permettant d'aller jusqu'à 65 536 qrcodes est définit mais pas encore implémentée (les matrices nécessaires au calcul prendrait plus de 4Go de ram et le temps de calcul pourrait être très important, limitant sont intérêt). Le format est spécifié sur le billet que j'avais publié l'année dernière.
Il existe une démo sur un serveur pas très costaux avec un certificat auto-signé (ne pas l'utiliser avec des données sensibles).
Si vous décidez d'héberger une instance derrière un proxy inverse, prenez garde au timeout qui peuvent se produire lors de la manipulation d'un nombre important de qrcodes.
La licence du projet est la MIT licence. Toutes les contributions et commentaires sont les bienvenues bien entendu :)
# Méthod de Shamir
Posté par ymorin . Évalué à 6.
Ça ressemble fortement à la méthode de Shamir pour partager un secret : https://en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing , et qui est prouvée mathématiquement.
En quoi ta solution est-elle différente ?
Hop,
Moi.
[^] # Re: Méthod de Shamir
Posté par Anonyme . Évalué à 3.
Je ne connaissais pas cet algorithme et cela donne envie d'explorer un peu le concept :)
L'approche est du coup différente mais similaire dans sa finalité. Ici on va découper les données en parts égales, les chiffrer avec une clé et on va distribuer la clé sur les différents supports avec les données.
J'ai l'impression que l'algorithme de Shamir serait plus efficace au final, et sans doute beaucoup moins gourmand que le calcul de reed-solomon. Il faudrait que je fasse des essaies, mais il n'est pas impossible du coups que je travaille sur une version utilisant cet algorithme.
[^] # Re: Méthod de Shamir
Posté par Anonyme . Évalué à 6.
Je me réponds à moi même car après un peu plus de réflexion, Shamir ne permet pas de fractionner la clé comme le permet reed-solomon, car chaque fragment est égale au message original. Dans le cas de qraidcode, le message est bien fragmenté en partie plus petites et il est donc possible de stocker plus de données que ne le permettrait le partage de Shamir.
[^] # Re: Méthod de Shamir
Posté par M . Évalué à 4.
Mais est ce ta méthode garanti vraiment que si tu n'atteins pas le seuil qu'il n'y a quand même pas assez d'info pour deviner le secret ?
Qu'elle est la différence de taille ?
[^] # Re: Méthod de Shamir
Posté par Anonyme . Évalué à 1.
Je viens de me replonger dans le code, et je constate qu'il y a clairement une faiblesse au niveau de la taille de la clé. Ça m'emmerde un peu de le constater moi-même, mais il est évidant qu'il serait possible de brute-forcer les données partielles en réunissant par exemple 30 qrcodes sur 32, puisque dans ce cas là chaque qrcode contiennent 1 octet de la clé de chiffrement…
Je ne comprends pas moi-même comment j'ai pu laisser passer une telle aberration sachant que 32 octets sont réservés sur chaques qrcodes, il serait tout à fait possible de généré une clé de chiffrement à 32 * n qrcodes sans revoir le format des données.
Je vais travailler à corriger ça, la prochaine version aura bien 32 octets de données de clé sur chaque qrcode, ce qui devrait rendre le format bien plus solide que ce qu'il est maintenant.
[^] # Re: Méthod de Shamir
Posté par Nicolas Boulay (site web personnel) . Évalué à 2.
32 c'est pas assez. Si tu veux aller dans le domaine du "totalement infaisable par brute force", il faut aller dans le 64 bits. 4G combinaisons à tester cela peut aller vite aujourd'hui.
Le protocole de ssss a été fait exactement pour ce cas-là : définir un nombre d’élément présent sur un nombre total pour pouvoir reconstruire une clef. C'est fait pour.
"La première sécurité est la liberté"
[^] # Re: Méthod de Shamir
Posté par Nicolas Boulay (site web personnel) . Évalué à 1. Dernière modification le 28 octobre 2014 à 16:37.
.
"La première sécurité est la liberté"
[^] # Re: Méthod de Shamir
Posté par oinkoink_daotter . Évalué à 2.
Non, par définition, "totalement infaisable par brute force", ça veut dire qu'il faut taper dans une longueur de clef classique sauf si les données ont une validité éphémère, ce qui n'est pas le cas ici, cf le §4 du journal. Donc d'après l'ANSSI (RGSv2) le strict minimum serait une clef de 100 bits pour du symétrique pour protéger jusque 2020 (128 au delà) et 128 bits recommandés.
[^] # Re: Méthod de Shamir
Posté par Nicolas Boulay (site web personnel) . Évalué à 2.
C'est toujours mieux de faire plus. Mais 264 combinaisons, c'est quelques années de calculs sur une machine très puissantes.
"La première sécurité est la liberté"
[^] # Re: Méthod de Shamir
Posté par Anonyme . Évalué à 1.
32 octets, pas 32 bits.
Donc à 32 octets on a une difficulté de 2256, le tout multiplié par le nombre de qrcodes.
[^] # Re: Méthod de Shamir
Posté par Anonyme . Évalué à 1. Dernière modification le 01 novembre 2014 à 23:17.
Le code à été mis à jour. Désormais chaques qrcodes embarque 256 bits de clé de chiffrement indépendament du nombre de qrcodes.
L'application reste compatible avec les qrcodes précédemment générées, la version inscrite dans les qrcodes est maintenant 3 (au lieux de 1 dans la première version). La version 2 corresponds aux qrcodes utilisant les corps de Galois GF(16) dont une partie du code existe mais actuellement non finalisé.
L'image docker est en construction.
# Bravo!!!
Posté par kaveck . Évalué à 3.
Un très beau projet. Intelligent. KISS!!! Cela donne envie de bidouiller un peu. Mais, le sens inverse, QRcode->données
- C'est déjà existant et je n'ai pas vu où.
- C'est en projet.
- C'est à moi de faire.
En tout cas un travail qui permet d'imaginer beaucoup de choses, que je te remercie de partager.
[^] # Re: Bravo!!!
Posté par Anonyme . Évalué à 2.
L'application est capable de lire et de décoder les données sur les qrcodes (sinon l'intérêt serait tout de même limité). Il suffit d'uploader soit le pdf ou des images contenants les qrcode dans la section décode de l'application.
[^] # Re: Bravo!!!
Posté par kaveck . Évalué à 3.
Merci. Je ne sais pas pourquoi l'interface ne m'a pas semblé évidente a priori. Elle l'est pourtant a posteriori .
# Transformée Mojette
Posté par edhelas (site web personnel) . Évalué à 4.
Pour faire un peu de pub tu devrais aussi être intéressé par la Transformée Mojette (http://fr.wikipedia.org/wiki/Transform%C3%A9e_Mojette). C'est super simple à comprendre ;)
[^] # Re: Transformée Mojette
Posté par Anonyme . Évalué à 1.
Oui, j'ai regardé un peu il y a quelque temps et le concept est intéressant car vraiment simple à mettre en œuvre d'un point de vu mathématique (pas de calcul polynomial contrairement a reed-solomon).
Seul la distribution des données de parité pose problème car leur taille n'est pas identique aux fragments.
[^] # Re: Transformée Mojette
Posté par Nicolas Boulay (site web personnel) . Évalué à 3.
Je suis étonné que ton reed solomon soit si lent. Il y a ~10 ans, j'utilisais une IP reed solomon dans un petit FPGA qui faisait son calcul en un seul cycle. De mémoire, c'était des paquets de 8 bits, et il n'y avait pas du tout de multiplieur.
"La première sécurité est la liberté"
[^] # Re: Transformée Mojette
Posté par Anonyme . Évalué à 1.
Ça s'explique sans doute par l'implémentation un peu sale que j'ai réalisé en php.
J'ai eu pas mal de difficulté pour y parvenir car je ne maîtrise pas nécessairement la complexité des mathématiques mises en œuvre dans ce projets (pour situer le niveau j'ai appris à faire des calculs sur des matrices en faisant ce projet). Pour les corps de Galois, j'ai lu quelques publications universitaire qui expliquaient comment calculer les matrices permettant d'avoir les propriétés recherchées pour calculer les données de parité, et j'ai du coup pas mal bricolé jusqu'à avoir un truc qui marche. Je sais qu'il y a des calculs redondant par endroit.
Après, faire une parité sur un octet et sur 500 000 n'implique pas la même masse de calcule. Le calcule de l'ensemble des matrices dans corps de Galois GF(8) afin de pouvoir gérer tout les cas de 1 à 255 éléments de parité à pris plusieurs jours (et plusieurs centaines de mégaoctets de données), je n'ai plus l’entièreté de l'algo en tête, mais il me semble que le nombre de parité augmente en puissance le nombre de calcul à réaliser sur les octets.
[^] # Re: Transformée Mojette
Posté par Zylabon . Évalué à 3.
je suis pas super fort en reed solomon, mais c'est pas "juste" une multiplication de polynômes sur le corps de galois ?
Please do not feed the trolls
[^] # Re: Transformée Mojette
Posté par Anonyme . Évalué à 1.
Oui, c'est juste ça. Je serais toutefois bien incapable de calculer la complexité de l’algorithme. D'ailleurs si des gens à l'aise avec ça se sentent d'aller jeter un œil au code pour me faire des remarques à ce sujet, j'en serais ravi :)
[^] # Re: Transformée Mojette
Posté par Michaël (site web personnel) . Évalué à 2.
Pourquoi pas, où est-ce qu'il faut regarder? Est-ce que tu as une référence qui décrit bien le calcul que tu veux implémenter?
[^] # Re: Transformée Mojette
Posté par Anonyme . Évalué à 1.
Les fonctions qui effectues tout les calculs sont dans ce fichier: https://github.com/cmehay/qraidcode_php/blob/master/qraidcode.php
Cela reste tout de fois complexe, ce n'est pas de l’objet mais les fonctions principales sont encode() et decode() où on retrouvera toute les étapes pour encoder et décoder les qrcodes.
Pour les références, je me suis énormément basé sur les travaux de ce monsieur notamment ce tutoriel sur l'implémentation de l’algorithme reed-solomon, sa révision ainsi que l'implémentation qu'il a réaliser en c/c++ depuis laquelle j'ai porté quelques morceaux de code.
[^] # Re: Transformée Mojette
Posté par Michaël (site web personnel) . Évalué à 2.
Ouh — la partie où je peux être utile c'est la multiplication de polynômes sur un corps de Galois, je n'ai pas réussi à identifier cette partie.
[^] # Re: Transformée Mojette
Posté par Anonyme . Évalué à 1. Dernière modification le 01 novembre 2014 à 21:41.
Oui, c'est beaucoup de choses à ingurgiter d'un coup :p
Les fonctions sont notamment reed_solomon_enc_8() et reed_solomon_dec_8(), je me souviens avoir eu du mal à appliquer les algo convenablement et il y a énormément de boucles for imbriqué, certaines redondantes car l'implémentation de référence s'appliquait sur un simple tableau et que je stockais mes matrices dans un tableau à deux dimensions, le code est peu commenté car je ne l'ai moi-même pas hyper bien compris (et quand je regarde certaines choses, j'y vois pas mal d'aberration). La fonction inverse() aussi est une horreur…
Bref, je vais travailler sur le nouveau chiffrement, j'en profiterai pour faire un coup de propre (comme dans la ligne 14 (les parisiens comprendront)) dans mon code maintenant que j'ai lvlé un peu depuis l'année dernière :)
Suivre le flux des commentaires
Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.