Journal Existe-t-il un bon algorithme qui permet de compresser et de chiffrer en meme temps

Posté par (page perso) . Licence CC by-sa
Tags :
2
13
mai
2015

Chers lecteurs de linuxfr,

Mon poste initial sur une mailing liste:
"Is there a good algorithm providing both compression and encryption at the same time?"
http://www.metzdowd.com/pipermail/cryptography/2015-May/025479.html

En francais, je cherche un algorithme de compression qui permet de faire:

compression(texte_en_clair) = (dictionnaire_pour_la_decompression, texte_compresse)

Apres, pour avoir une bonne performance, au lieu d'encrypter
toute la paire il serait suffisant de faire:

(encryption_symmetrique(dictionnaire, cle_secrete), texte_compresse)

J'ai fais un deuxieme poste sur la ML ou je donne plus de details sur mon systeme:

http://www.metzdowd.com/pipermail/cryptography/2015-May/025522.html

Je suis assez decu par cette mailing liste: c'est soi-disant une liste moderee mais on ne dirait pas et je trouve le rapport signal sur bruit extremement faible.

Je prefererai un algo qui existe depuis pas mal de temps et qui a resiste
a la cryptanalyse. Pas un truc encore tout chaud qui sort du four et que
personne n'a jamais tente de craquer.
La haute performance est desiree: l'algorithme doit etre rapide, genre comme
LZ4 qui lui ne fait que de la compression legere.

Merci beaucoup,
Francois.

  • # En français ?

    Posté par (page perso) . Évalué à 4.

    En francais, je cherche un algorithme de compression qui permet de faire:
    […]
    Apres, pour avoir une bonne performance, au lieu d'encrypter[…]

    En français, tu cherches un algorithme qui permette de faire… Après, pour avoir une bonne performance, au lieu de chiffrer

  • # Quel est le problème avec une combinaison de l'existant ?

    Posté par (page perso) . Évalué à 10.

    Quel est le problème avec ce qui existe déjà, et qui peut être combiné ? Genre LZ4 puis AES ?

    • [^] # Re: Quel est le problème avec une combinaison de l'existant ?

      Posté par . Évalué à 5. Dernière modification le 13/05/15 à 12:21.

      Quel est le problème avec ce qui existe déjà, et qui peut être combiné ? Genre LZ4 puis AES ?

      +1
      Je ne pense pas que la vitesse de AES pose problème (la plupart des SoC possèdent des instructions pour l'accélérer matériellement).
      Et le codage de source (compression) et le chiffrement sont des opérations relativement orthogonales à mon sens, modulo le fait qu'il vaut mieux appliquer le codage de source avant le chiffrement pour maximiser l'entropie de la source (mais bon, après tout, on a bien vu des sujets initialement un peu distincts se regrouper: par exemple les treillis-coded modulations mélangent modulation et codage de canal, et on parle aussi pas mal de codage conjoint source-canal, donc même si je suis circonspect sur la combinaison compression+chiffrement "tout en un", qui sait s'il n'y a pas des choses à regarder… :)

    • [^] # Re: Quel est le problème avec une combinaison de l'existant ?

      Posté par (page perso) . Évalué à 9.

      Oula malheureux, surtout pas !
      Si tu fais ça, un attaquant peut faire le distingo entre 0000000000 et 6632056564 parce que le premier prendra moins de place que le second. Y a eu une attaque publiée récemment, pas mal de services sécurisés ont désactivé la compression suite à ça.

      Après, quelque soit l'algo de compression tu risques d'avoir le problème, mais un algo qui fait compression + chiffrement sans donner trop d'infos ça parait complexe

      • [^] # Re: Quel est le problème avec une combinaison de l'existant ?

        Posté par . Évalué à 2.

        En effet, la compression peut entraîner une fuite d'information que l'on pense être en sécurité. Voir l'attaque SSL CRIME.

      • [^] # Re: Quel est le problème avec une combinaison de l'existant ?

        Posté par (page perso) . Évalué à 7.

        Tu aurais pu donner quelques références.

        Je pense que tu fais référence à l'attaque CRIME qui s'est intéressé au fait que TLS utilise la compression de données pour deviner quelques choses à propos des cookies de l'utilisateur.

        L'idée générale étant que la compression réduit la taille en s'intéressant aux redondances. Si l'attaquant arrive à ajouter un mot au cookie qui n'est pas présent dans le cookie, alors la taille du cookie compressé puis chiffré va augmenter. Mais si la taille n'augmente pas notablement, cela veut dire que le texte ajouté était présent dans le cookie. Cela donne ainsi des informations sur le texte en clair, et ça casse le chiffrement.
        Au sein de l'attaque, le vecteur était que la page d'un site web https faisait référence à une autre page qui envoyait le texte à tester. Après plusieurs essais, l'attaquant à un avantage non négligeable, et c'est la merde.

        Dans l'absolue, cette attaque ne devrait pas avoir beaucoup d'impact sur le cas ici présent, à moins que tu ne t'amuses à compresser et chiffrer plusieurs fois le même fichier légèrement modifié par un tiers.

      • [^] # Commentaire supprimé

        Posté par . Évalué à 7. Dernière modification le 13/05/15 à 17:59.

        Ce commentaire a été supprimé par l'équipe de modération.

        • [^] # Re: Quel est le problème avec une combinaison de l'existant ?

          Posté par (page perso) . Évalué à 4.

          Je pense que tu exagères considérablement. Les attaques tels que CRIME doivent avoir un certain nombre d'autres pré-requis qui ne sont pas réunis dans toutes les situations.

          Certes. Après, le monsieur en haut demandé un algo prouvé qui fasse compression ET chiffrement, et je pensais qu'il voulait ça pour pouvoir augmenter la sécurité du système, en fait vu les autres messages, c'est plus une question de vitesse.
          Effectivement la seule attaque connue/vaguement exploitable est en attaque à clair choisi, et potentiellement l'auteur n'est pas dans ce cas. On parle typiquement de GPG plus bas, sauf si c'est script, il n'y a pas d'attaque à clair choisi possible.

          • [^] # Re: Quel est le problème avec une combinaison de l'existant ?

            Posté par . Évalué à 0.

            Si compresser d'abord et chiffrer ensuite est un problème pour les attaques dîtes à « clair choisi », je ne vois en revanche pas de problèmes quand à chiffrer d'abord, compresser ensuite.

            • [^] # Re: Quel est le problème avec une combinaison de l'existant ?

              Posté par (page perso) . Évalué à 7.

              je ne vois en revanche pas de problèmes quand à chiffrer d'abord, compresser ensuite.

              Le texte chiffré est censé être indistinguable d’un flux d’octets aléatoires, tu ne devrais pas pouvoir le compresser. Si tu y arrives (si la compression réduit effectivement la taille du fichier chiffré), c’est qu’il y a un problème avec l’algorithme de chiffrement.

              • [^] # Commentaire supprimé

                Posté par . Évalué à 1.

                Ce commentaire a été supprimé par l'équipe de modération.

              • [^] # Re: Quel est le problème avec une combinaison de l'existant ?

                Posté par . Évalué à 2. Dernière modification le 13/05/15 à 21:51.

                Le texte chiffré est censé être indistinguable d’un flux d’octets aléatoires,

                Si il est vrai que la définition d'une suite aléatoire est de ne pas pouvoir être compressée (complexité de Kolmogorov), il est en revanche faux de dire qu'un chiffrement doit nécessairement produire une suite aléatoire.

                Que le texte chiffré soit aléatoire n'est pas une propriété nécessaire d'un chiffrement. L'exemple le plus simple est le one-time-pad car tu peux très simplement choisir la clé pour que le texte chiffré ressemble à un autre texte ayant lui aussi du sens : clé = texte_cible xor texte_clair.

                En pratique cependant il y a en effet des chances pour que la compression soit inutile car il n'y a pas a ma connaissance dans les chiffrements les plus populaire des moyens pour contrôler la forme du texte chiffré.

                • [^] # Re: Quel est le problème avec une combinaison de l'existant ?

                  Posté par . Évalué à 4.

                  L'exemple le plus simple est le one-time-pad car tu peux très simplement choisir la clé pour que le texte chiffré ressemble à un autre texte ayant lui aussi du sens

                  La sécurité de l’OTP réside sur le fait que tu choisisses ton OTP de manière aléatoire sur l’ensemble des OTP possible, avec une distribution uniforme. En insistant sur la compressibilité, tu casses ce postulat. De fait, ton schéma (choisir un texte aléatoire dans l’ensemble des textes en langue naturelle, puis faire un xor avec ton plaintext pour obtenir l’OTP), ça revient du point de vue d’une attaque par analyse fréquentielle à chiffrer deux messages avec le même OTP, et ça c’est pas sécurisé du tout.

                  Si tu regardes les modes de chiffrements par bloc, tous demandent que l’algorithme de chiffrement soit à minima une fonction pseudo-aléatoire. De même dans le chiffrement par flux, la brique de base c’est un générateur pseudo-aléatoire.

                  • [^] # Re: Quel est le problème avec une combinaison de l'existant ?

                    Posté par . Évalué à 2.

                    La sécurité de l’OTP réside sur le fait que tu choisisses ton OTP de manière aléatoire

                    Même si l'attaquant sait que tu as choisi la clé pour faire en sorte que le texte chiffré ait une forme particulière, ça ne baisse pas la sécurité du one-time-pad. Tout les textes clairs restent possible avec la même probabilité.

                    Lors d'utilisations successives du OTP, la sécurité baisse si tu choisis le texte cible de manière non aléatoire (car la distance entre deux textes clairs devient mesurable grâce aux textes chiffrés), mais elle ne baisse pas quand les textes cibles sont aléatoirement choisis.

                    • [^] # Re: Quel est le problème avec une combinaison de l'existant ?

                      Posté par . Évalué à 2.

                      Même si l'attaquant sait que tu as choisi la clé pour faire en sorte que le texte chiffré ait une forme particulière, ça ne baisse pas la sécurité du one-time-pad. Tout les textes clairs restent possible avec la même probabilité.

                      Aussi contre-intuitif que ça me paraissee, tu sembles avoir raison, mea culpa.

                      • [^] # Re: Quel est le problème avec une combinaison de l'existant ?

                        Posté par . Évalué à 1.

                        Si tu considère le "one-time-pad" sur les entiers naturel avec +, un chiffré c est un texte t auquel on ajoute une clé k.
                        L'attaquant connait c et sait que c = t + k. Il y a c+1 solutions à cette équation, et il y a c+1 possibilités pour t, ça ne lui donne pas la moindre information.

                        Please do not feed the trolls

                    • [^] # Re: Quel est le problème avec une combinaison de l'existant ?

                      Posté par . Évalué à 6.

                      Sauf que pour choisir la clé de manière à ce que le texte chiffré ait une forme particulière, il faut connaitre le texte clair avant d'échanger la clé, du coup autant donner directement le texte que tu veux transmettre au lieu de la clé, vu qu'il faut de toute façon un moyen sécurisé pour transmettre la clé.

                      Tous les nombres premiers sont impairs, sauf un. Tous les nombres premiers sont impairs, sauf deux.

                      • [^] # Re: Quel est le problème avec une combinaison de l'existant ?

                        Posté par . Évalué à 1.

                        C'est exactement pour cela que le one-time-pad n'est pas très praticable. Même si on ne se donne pas la contrainte d'avoir un texte chiffré ayant une forme particulière le OTP n'est pas très pratique.

                        Toutefois qu'il éxiste quand même des cas où l'OTP avec texte chiffré choisi est praticable. Imaginons par exemple que tu peux transmettre des données de manière sécurisée uniquement aujourd'hui (disons qu'il y a un convoi sous très haute garde qui part et qui arrive dans la même journée), mais tu aimerais que le destinataire puisse en prendre connaissance qu'à partir de demain. Ce que tu peux faire est d'envoyer les clés aujourd'hui (dans le convoi sécurisé), et ensuite le texte chiffré le lendemain (sur un canal non sécurisé, par internet en clair par exemple).

                        Note que j'avais choisis l'exemple OTP pour montrer qu'en théorie (du moins), un texte chiffré aléatoire n'est pas nécéssaire pour avoir un chiffrement sûr.

                        • [^] # Re: Quel est le problème avec une combinaison de l'existant ?

                          Posté par . Évalué à 2.

                          Le problème, c'est que dans le cas que tu décris, tu veux cacher l'information à deux personnes. La première, c'est bien un observateur extérieur, et là dessus je suis d'accord (ou en tout cas je n'ai pas cherché assez ;-) ) ça m'a l'air sécurisé.

                          Mais la deuxième personne à qui tu veux cacher un message, c'est la personne à qui tu remets la clé. Bon, tu veux ne lui cacher le message que temporairement (jusque demain), mais si lui décide qu'il veut le lire tout de suite, il peut tenter de trouver, parmi tous les ensembles (message clair, "forme particulière") ceux qui s'obtiennent avec la clé qu'il a déjà.

                          Bon évidemment, il doit connaitre la forme particulière, mais l'ensemble des couples qu'il doit parcourir est bien limité, contrairement au bon one-time pad.

                          Évidemment, si tu fais confiance à ton correspondant pour ne pas attaquer ton message (enfin, ta clé, vu que c'est ce qu'il a), alors ce n'est pas un problème. Mais à moins d'avoir une bonne raison (et il peut y en avoir une, par exemple c'est probablement plus discrète de transmettre "forme particulière" qu'une chaine aléatoire si quelqu'un écoute pour trouver les messages chiffrés), je pense qu'il vaut mieux utiliser le "vrai" algo.

                          Je ne sais pas si je suis très clair, enfin, c'est pas très grave non plus ;-)

                          Tous les nombres premiers sont impairs, sauf un. Tous les nombres premiers sont impairs, sauf deux.

                          • [^] # Re: Quel est le problème avec une combinaison de l'existant ?

                            Posté par . Évalué à 2.

                            Mais la deuxième personne à qui tu veux cacher un message, c'est la personne à qui tu remets la clé. Bon, tu veux ne lui cacher le message que temporairement (jusque demain), mais si lui décide qu'il veut le lire tout de suite, il peut tenter de trouver, parmi tous les ensembles (message clair, "forme particulière") ceux qui s'obtiennent avec la clé qu'il a déjà.

                            La forme particulière peut être tout à fait aléatoire, c'est pas important. L'essentiel ici pour ce protocole est que la clé soit elle même chiffrée.

                            Au lieux d'avoir chiffré = clair ^ clef tu as:
                            chiffré = clair ^ clef_transmise_manière_securisée ^ clef_publique

                            Please do not feed the trolls

                          • [^] # Re: Quel est le problème avec une combinaison de l'existant ?

                            Posté par . Évalué à 1. Dernière modification le 20/05/15 à 14:48.

                            mais si lui décide qu'il veut le lire tout de suite, il peut tenter de trouver, parmi tous les ensembles (message clair, "forme particulière") ceux qui s'obtiennent avec la clé qu'il a déjà.

                            Dans l'exemple le destinataire n'est pas sensé savoir que le message clair à une forme particulière. Il sait juste que le message chiffré a l'apparence d'un texte non aléatoire (dit autrement : que le texte chiffré a une forme particulière). Et cela ne change pas la probabilité des textes clairs possible.

                            Dans l'hypothèse ou le destinataire sait que texte chiffré et le texte clair ont une forme particulière alors c'est une autre histoire. Et intuitivement je dirais qu'en effet, dans le cas ou l'attaquant (ou le destinataire) connait la clé (comme dans l'exemple plus haut) alors cela réduit la sécurité du OTP. Si l'on imagine qu'il y a que deux textes clair possible, alors il suffit de les xorer avec la clé que l'on a reçu (par convoi sécurisé) et il est alors possible d'éliminer les textes chiffrés qui ne respectent pas la forme que l'on attendait.

    • [^] # Re: Quel est le problème avec une combinaison de l'existant ?

      Posté par (page perso) . Évalué à 5.

      Chiffrer uniquement pourquoi pas, mais l'authenticité/intégrité de ton message/fichier n'est absolument pas garantie.

      Je te proposerais d'utiliser AES-GCM après l'étape de compression (ça utilise AES en mode CTR, et tu peux authentifier tes données).
      Bon, mais il semblerait que ça soit vraiment compliqué de chiffrer des fichiers, puisque j'ai pas vraiment trouvé d'outils le faisant.

      Bon, mais sinon, gpg te propose de chiffrer et de compresser via la même commande.

    • [^] # Re: Quel est le problème avec une combinaison de l'existant ?

      Posté par (page perso) . Évalué à 2.

      LZ4 puis AES est effectivement ce que je vais proposer par defaut.
      Je me demandais juste s'il n'existait pas deja des algo avec
      des meilleures performances qui font les deux a la fois.
      J'ai ete intrigue par cet article:
      https://people.csail.mit.edu/rivest/pubs/GMR96.pdf

  • # Ou est le problème?

    Posté par (page perso) . Évalué à 9. Dernière modification le 13/05/15 à 12:21.

    (encryption_symmetrique(dictionnaire, cle_secrete), texte_compresse)

    Ben… AES(LZ4(texte_en_clair)) est rapide, je ne vois pas ce que ça améliorerai de faire une seule fonction (dans les 2 cas il faut un bloc temporaire). En plus ça se parallélise (une fonction par CPU).

    • [^] # Re: Ou est le problème?

      Posté par . Évalué à 1.

      il est dit plus haut que ca ne serait pas la bonne méthode (passer le compression avant de crypter le texte).

      Triviallement (le dev, la compression et l'encryptage ne sont pas mon milieu) je dirai que l'inverse (compresser quelquechose de déjà crypter, soir LZ4(AES(texte_en_clair))) ne donnerai pas un bon ratio de compression (mais un peu qd même), du fait que le cryptage rend trés aléatoire les données; mais je me trompe peut être ?

      • [^] # Re: Ou est le problème?

        Posté par (page perso) . Évalué à 5.

        je dirai que l'inverse (compresser quelquechose de déjà crypter, soir LZ4(AES(texte_en_clair))) ne donnerai pas un bon ratio de compression (mais un peu qd même), du fait que le cryptage rend trés aléatoire les données; mais je me trompe peut être ?

        Tu peux t'amuser à essayer, mais ça ne servira à rien du tout (voire à augmenter sa taille). Dans le cas contraire, j'aurais pas trop confiance en l'algorithme de chiffrement utilisé.

    • [^] # Re: Ou est le problème?

      Posté par . Évalué à 3.

      À vue de pif, (encryption_symmetrique(dictionnaire, cle_secrete), texte_compresse) me semble aussi très vulnérable aux attaques statistiques.
      En effet, vu que le texte compressé est en clair, il ne me semble pas impossible (1) d'essayer de segmenter les différents codons(?) et (2) d'utiliser des techniques statistiques pour en déduire un dictionnaire plausible.

      La partie (1) me semble plus difficile et doit sans doute pas mal dépendre de l'algorithme de compression. À voir en pratique.

      • [^] # Re: Ou est le problème?

        Posté par . Évalué à 3.

        Ok tout ça me semble en rapport avec le sujet de discussion de l'article cité dans le 2e message de Zaurus sur la ML.
        Donc des gens intelligents ce sont sans doute déjà penchés plus sérieusement sur cet aspect du problème.

  • # Et c'est une très mauvaise idée...

    Posté par . Évalué à 6.

    Quand tu fais :

    (encryption_symmetrique(dictionnaire, cle_secrete), texte_compresse)

    Tu laisses le texte compressé disponible à l'attaquant.

    Pour tout ce qui est texte par exemple, il est probablement bcp moins couteux et long de faire un mix de brute force / analyse sémantique du texte compressé qu'un brute force du texte compressé encrypté avec AES….

    Bref, tu affaiblis la sécurité de la chose de manière substantielle.

    • [^] # Re: Et c'est une très mauvaise idée...

      Posté par . Évalué à 1.

      Désolé j'ai inutile trop vite parce que j'avais rien compris au post et à ton commentaire. J'ai pas d'excuse. D'autant plus que maintenant que je comprends, j'aurai pertinenté :/

  • # Quel est ton exact problème ?

    Posté par (page perso) . Évalué à 3.

    Pour donner une réponse pertinente, il est utile de connaître exactement ton problème. Actuellement ça ressemble à un problème XY? Que veut tu faire exactement ?

    Peut tu donner un maximum d'information sur ton problème initial ?

    Le plus détaillé est ceci mais si tu pouvais en dire encore plus ce serait plus facile de t'aider.

    Le plus d'info que tu as livré est dans: http://www.metzdowd.com/pipermail/cryptography/2015-May/025522.html, mais ça reste vague.

    • [^] # Re: Quel est ton exact problème ?

      Posté par (page perso) . Évalué à 1.

      Je cherche s'il existe un algorithme qui fait compression et chiffrement en meme temps.
      Dans l'ideal, comme c'est pour un systeme haute performance, il faudrait
      que ca soit plus rapide mais aussi sur que AES(LZ4(message)).

Suivre le flux des commentaires

Note : les commentaires appartiennent à ceux qui les ont postés. Nous n'en sommes pas responsables.