Empêcher la compression LZMA2

11

Objectif

Créez un programme ou une paire de programmes qui perturbent et corrigent collectivement les fichiers dans le but d'empêcher LZMA2 de fonctionner efficacement. Les routines de perturbation et de correction doivent être réciproques, afin que vous puissiez récupérer le fichier d'origine exactement.

Cibles

Méthodes de compression

  • Ubuntu / liés: xz -kz5 <infile>
  • Les fenêtres: 7z.exe a -txz -mx5 <outfile> <infile>
  • Autre: Utilisez un compresseur LZMA2 avec un niveau de compression 5 qui comprime les œuvres de Shakespeare à 1570550 octets ± 100 octets.

Notation; somme de (tout est en octets, ls -lou dirça):

  • Taille du ou des programmes (tout ce qu'il faut collectivement pour "casser" / réparer le fichier de manière réversible)
  • Différence de taille (absolue) entre:
    • Oeuvres brutes collectées de Shakespeare et votre copie modifiée (non compressée).
    • Photo brute et votre copie modifiée (non compressée).
  • Différence de taille ou 0, la valeur la plus élevée étant retenue:
    • Œuvres brutes collectées de Shakespeare moins votre copie compressée LZMA2 modifiée.
    • Photo brute moins votre copie compressée LZMA2 modifiée.

Exemple

Exemple de Python 2.x mal marqué, paresseusement joué, mais conforme:

import sys
x = 7919 if sys.argv[1] == 'b' else -7919
i = bytearray(open(sys.argv[2], 'rb').read())
for n in range(len(i)):
    i[n] = (i[n] + x*n) % 256
o = open(sys.argv[2]+'~', 'wb').write(i)

Fonctionnement...

$ python break.py b pg100.txt 
$ python break.py f pg100.txt~ 
$ diff -s pg100.txt pg100.txt~~
Files pg100.txt and pg100.txt~~ are identical
$ python break.py b Glühwendel_brennt_durch.jpg 
$ python break.py f Glühwendel_brennt_durch.jpg~
$ diff -s Glühwendel_brennt_durch.jpg Glühwendel_brennt_durch.jpg~~
Files Glühwendel_brennt_durch.jpg and Glühwendel_brennt_durch.jpg~~ are identical
$ xz -kz5 pg100.txt~
$ xz -kz5 Glühwendel_brennt_durch.jpg~
$ ls -ln
-rw-rw-r-- 1 2092 2092     194 May 23 17:37 break.py
-rw-rw-r-- 1 2092 2092 1659874 May 23 16:20 Glühwendel_brennt_durch.jpg
-rw-rw-r-- 1 2092 2092 1659874 May 23 17:39 Glühwendel_brennt_durch.jpg~
-rw-rw-r-- 1 2092 2092 1659874 May 23 17:39 Glühwendel_brennt_durch.jpg~~
-rw-rw-r-- 1 2092 2092 1646556 May 23 17:39 Glühwendel_brennt_durch.jpg~.xz
-rw-rw-r-- 1 2092 2092 5589891 May 23 17:24 pg100.txt
-rw-rw-r-- 1 2092 2092 5589891 May 23 17:39 pg100.txt~
-rw-rw-r-- 1 2092 2092 5589891 May 23 17:39 pg100.txt~~
-rw-rw-r-- 1 2092 2092 3014136 May 23 17:39 pg100.txt~.xz

But

  • = 194 + abs (5589891 - 5589891) + max (5589891 - 3014136, 0) + abs (1659874 - 1659874) + max (1659874 - 1646556, 0)
  • = 194 + 0 + 2575755 + 0 + 13318
  • 2 589 267 octets. Mauvais, mais ne rien faire dans les fichiers donne un score de 4 635 153 octets.

Clarification

C'est le golf, donc vous essayez de minimiser votre score. Je ne sais pas si les commentaires indiquent un trou légitime dans mon score ou s'ils le sont parce que je l'ai rendu trop compliqué. Dans tous les cas, vous voulez le PLUS PETIT :

  • code source
  • différence entre le fichier modifié non compressé et le fichier d'origine (par exemple, si vous le modifiez en ajoutant un billion de 0 à la fin, votre score a augmenté d'un billion d'octets)
  • différence entre le fichier modifié compressé et le fichier d'origine (par exemple, plus les fichiers sont incompressibles, plus votre score est élevé). Un fichier parfaitement incompressible qui croît légèrement ou pas du tout donnera 0.
code-challenge compression Nick T
la source
2
La réponse à la traîne: Étape 1 - déterminez combien d'espace disque libre vous avez, puis divisez cela par la taille du fichier pour obtenir N. Étape 2 - ajoutez le fichier à lui-même N fois et ajoutez le nombre N. Étape 3 - réalisez qu'il y a il ne reste plus d'espace pour compresser le fichier mais vous obtenez une différence absolue de tailles de fichiers de plusieurs terrabytes (ou plus) .... [Pour inverser, lisez N à la fin du fichier et réduisez le fichier au 1 / Nème de la taille. ]
MT0
@ MT0: Ah je pense que la solution est que les différences ne doivent pas être absolues. Si votre fichier modifié est plus grand, cela devrait soustraire des points.
Claudiu
@ MT0 si vous modifiez le fichier pour en faire un téraoctet de grande taille, votre score sera de 1 téraoctet ... assez mauvais lorsque vous essayez de jouer au golf.
Nick T
@ MT0 J'ai ajouté une clarification au message, cela aide-t-il?
Nick T
2
Un chicanage. Le compresseur peut créer un fichier plus gros si t est particulièrement incompressible. Dans ce cas, vous devriez être récompensé, pas puni, non?
Claudiu

Réponses:

8

Python, score = 120

import sys,hashlib
i=0
for c in sys.stdin.read():sys.stdout.write(chr(ord(c)^ord(hashlib.md5(str(i)).digest()[0])));i+=1

Crée un pad unique en utilisant md5 en mode compteur . xors le fichier avec. Cela présente l'avantage que les fichiers d'origine et perturbés sont de la même taille et que le perturbateur et le fixateur sont le même programme.

Les fichiers perturbés compressés sont plus volumineux que les originaux.

Keith Randall
la source
J'ai ajusté le score, donc si les fichiers zippés sont plus grands que leurs homologues d'origine, vous n'êtes pas pénalisés et ils marquent simplement 0. Je ne sais pas de quel côté la différence était pour vos fichiers mais vous pouvez mettre à jour le score
Nick T
@NickT: mis à jour.
Keith Randall
8

C, 51 = 51 + 0 + 0 + 0 + 0

main(c){for(;c=~getchar();putchar(~c^rand()>>23));}

Sous les astuces de golf , ce programme boucle pour chaque octet en entrée standard, et fait exclusif ou avec un pad infini de rand (). J'ai testé cela avec rand () dans la libc d'OpenBSD 5.5.

Usage:

./scramble <orig >scrambled
./scramble <scrambled >orig.copy

Pour tester mon programme, j'ai écrit un script shell test.sh (57 lignes) pour compiler mon programme et calculer mon score.

$ sh test.sh
[1/4] Compiling scramble...
/tmp//ccbcB43x.o(.text+0x6): In function `main':
: warning: rand() isn't random; consider using arc4random()
[2/4] Scrambling files...
[3/4] Compressing scrambled files...
[4/4] Checking descrambler...
SCORE: 51=51+0+0+0+0
You may wish to rm -rf tmp.9Tjw89dgCs
$ ls -l tmp.9Tjw89dgCs/
total 43032
-rw-r--r--  1 kernigh  kernigh  1659874 May 28 17:23 filament.jpg.cp
-rw-r--r--  1 kernigh  kernigh  1659874 May 28 17:23 filament.jpg.sc
-rw-r--r--  1 kernigh  kernigh  1660016 May 28 17:23 filament.jpg.sc.xz
-rw-r--r--  1 kernigh  kernigh  5589891 May 28 17:23 pg100.txt.cp
-rw-r--r--  1 kernigh  kernigh  5589891 May 28 17:23 pg100.txt.sc
-rw-r--r--  1 kernigh  kernigh  5590232 May 28 17:23 pg100.txt.sc.xz
-rwxr-xr-x  1 kernigh  kernigh     8564 May 28 17:23 scramble

Notes sur rand () et le décalage à droite

Aucun algorithme de compression ne peut compresser des données aléatoires. Je peux déguiser pg100.txt et filament.jpg en données aléatoires si je les brouille avec un chiffrement de flux .

Ma première idée a été d' exclure du texte en clair ou en clair avec pad pour créer du texte chiffré , puis de stocker à la fois le texte chiffré et le pad dans le fichier brouillé. Cela augmenterait la taille du fichier et augmenterait mon score. Le choix évident est d'utiliser le même pad pour chaque fichier et de ne stocker que du texte chiffré dans le fichier brouillé. Si j'appelle simplement rand (), il utilise une valeur par défaut de 1 et crée le même pad à chaque fois.

OpenBSD 5.5 définit rand () dans stdlib.h et rand.c :

/* from stdlib.h */
#define RAND_MAX    0x7fffffff

/* from rand.c */
static u_int next = 1;

int
rand_r(u_int *seed)
{
    *seed = *seed * 1103515245 + 12345;
    return (*seed % ((u_int)RAND_MAX + 1));
}

int
rand(void)
{
    return (rand_r(&next));
}

Il s'agit d'un générateur congruentiel linéaire . Le gros défaut est que les bits bas ont de courtes périodes. Le 1er bit a une période de 2: si vous lancez une pièce avec rand()&1, elle irait des têtes, des queues, des têtes, des queues, etc. Le nième bit a une période de 2 n . Il y a 31 bits, donc toute la séquence a une période de 2 31 .

LZMA2 peut trouver des modèles sur de courtes périodes et les compresser. Le code le plus court ~c^rand()prend les 8 bits les plus faibles et n'empêche pas la compression. Le bon changement dans l' ~c^rand()>>9aide, mais pas assez. J'utilise ~c^rand()>>23.

  • ~c SCORE: 4227957 = 40 + 0 + 0 + 4019391 + 208526
  • ~c^rand() SCORE: 2474616 = 47 + 0 + 0 + 2463735 + 10834
  • ~c^rand()>>9 SCORE: 350717 = 50 + 0 + 0 + 350667 + 0
  • ~c^rand()>>23 SCORE: 51 = 51 + 0 + 0 + 0 + 0
kernigh
la source
5

BrainFuck : 129 (129 + 0 + 0 + 0 + 0) *

random.bf (sauts de ligne ajoutés pour plus de lisibilité)

,+[->>>>++[<++++++++[<[<++>-]>>[>>]+>>+[-[->>+<<<[<[<<]<
+>]>[>[>>]]]<[>>[-]]>[>[-<<]>[<+<]]+<<]<[>+<-]>>-]<[-<<+
>>]<<.,+[->]>>>]]

Pour créer, unrandom.bfvous devez changer le dernier + dans la deuxième ligne.

La plupart du code est basé sur le générateur de nombres aléatoires basé sur la règle 30 de Daniel B Cristofani, adapté pour ajouter le numéro à chaque entrée et pour se terminer lorsqu'il n'y a plus d'entrée.

* J'ai testé les octets qu'il a traités jusqu'à présent 212992 (traités après 12 heures) et les deux fichiers se transforment en un fichier compressé 213064. Je suppose que cela pourrait être fait d'ici la fin de la semaine pour être sûr, mais je ne veux pas attendre la publication. Je mettrai à jour le score si c'est faux, mais gardez la solution car Rule30 bascule!

Anecdote: la règle 30 a été découverte par Stephen Wolfram en 1983 et selon Wikipedia, elle est utilisée pour produire des nombres entiers aléatoires dans Mathematica.

Compilation et exécution:

Il utilise du temps et de l'espace exponentiels (itère plus de 32 cellules supplémentaires par caractère traité), il nécessite donc un runtime BrainFuck qui a au moins 178 876 517 cellules pour coder le fichier Shakespear, ne traite pas non ascii comme unicode, possède des cellules de plus de 8 bits et utilise -1 en eof (à différer entre 255 et -1). J'utilise généralement des interprètes d'autres personnes mais cette fois, je dois être un plugin et promouvoir le mien:

jitbf --eof -1 -b 16 -c 200000000 random.bf < pg100.txt > pg100.txt.ran
jitbf --eof -1 -b 16 -c 200000000 random.bf < Glühwendel_brennt_durch.jpg > Glühwendel_brennt_durch.jpg.ran

jitfb compile BrainFuck en C optimisé et abuse de perl Inline :: C pour l'exécuter. Ce sont des bundles avec mon compilateur Extended BrainFuck . Avec la taille et la largeur de la cellule dans l'argument, il allouera environ 400 Mo.

Sylwester
la source
3

CJam, 22 octets

G,~q{5$H$+255%_@^o}/];

Cela utilise un générateur de Fibonacci décalé avec une relation de récurrence s n = (s n-5 + s n-16 )% 255 (que j'ai sélectionné par erreur, mais cela fonctionne quand même) et une graine triviale pour générer un flux pseudo-aléatoire d'octets , qu'il XORs ensuite avec l'entrée.

J'ai testé mon code avec CJam 0.6 , qui a été publié le 1er mai 2014.

Comment ça fonctionne

G,~                    e# Dump 0, 1, ... and 15 on the stack.
   q                   e# Read from STDIN.
    {             }/   e# For each character in the input.
     5$H$              e# Copy the sixth and 19th element from the stack.
         +255%         e# Push their sum modulo 255.
              _@       e# Duplicate and rotate the character on top.
                ^o     e# XOR and print.
                    ]; e# Clear the stack.

But

$ LANG=en_US
$ alias cjam='java -jar /usr/local/share/cjam/cjam-0.6.jar'
$ cjam thwart.cjam < pg100.txt > pg100.txt~
$ cjam thwart.cjam < pg100.txt~ > pg100.txt~~
$ diff -s pg100.txt pg100.txt~~
Files pg100.txt and pg100.txt~~ are identical
$ cjam thwart.cjam < Gluehwendel_brennt_durch.jpg > Gluehwendel_brennt_durch.jpg~
$ cjam thwart.cjam < Gluehwendel_brennt_durch.jpg~ > Gluehwendel_brennt_durch.jpg~~
$ diff -s Gluehwendel_brennt_durch.jpg Gluehwendel_brennt_durch.jpg~~
Files Gluehwendel_brennt_durch.jpg and Gluehwendel_brennt_durch.jpg~~ are identical
$ xz -kz5 pg100.txt~ Gluehwendel_brennt_durch.jpg~
$ wc -c thwart.cjam pg100.txt* Gluehwendel_brennt_durch.jpg*
      22 thwart.cjam
 5589889 pg100.txt
 5589889 pg100.txt~
 5589889 pg100.txt~~
 5590232 pg100.txt~.xz
 1659874 Gluehwendel_brennt_durch.jpg
 1659874 Gluehwendel_brennt_durch.jpg~
 1659874 Gluehwendel_brennt_durch.jpg~~
 1660016 Gluehwendel_brennt_durch.jpg~.xz
28999559 total
Dennis
la source
3

PHP, 117 + 0 + 0 + 0 + 0 = 117

Parce que confieriez-vous vraiment la tâche de falsifier vos données au-delà de la reconnaissance à une autre langue?

<?=substr(gmp_export(gmp_invert(2*gmp_import($s=stream_get_contents(STDIN))+1,$m=2*gmp_pow(256,strlen($s)))/2+$m),1);

Alors que toutes les autres solutions sont basées sur des constructions «sécurisées» comme des «générateurs de nombres aléatoires» ou une «cryptographie de qualité militaire», celle-ci interprète simplement les chaînes comme représentant des nombres impairs de longueur modulo 2⋅256 ^ et calcule leur inverse modulaire .

Démo:

$ php thwart.php < 100.txt.utf-8 > 100.txt.utf-8~
$ php thwart.php < 100.txt.utf-8~ > 100.txt.utf-8~~
$ diff -s 100.txt.utf-8 100.txt.utf-8~~
Files 100.txt.utf-8 and 100.txt.utf-8~~ are identical
$ php thwart.php < Glühwendel_brennt_durch.jpg > Glühwendel_brennt_durch.jpg~
$ php thwart.php < Glühwendel_brennt_durch.jpg~ > Glühwendel_brennt_durch.jpg~~
$ diff -s Glühwendel_brennt_durch.jpg Glühwendel_brennt_durch.jpg~~
Files Glühwendel_brennt_durch.jpg and Glühwendel_brennt_durch.jpg~~ are identical
$ xz -kz5 100.txt.utf-8~ Glühwendel_brennt_durch.jpg~
$ wc -c *
 5589889 100.txt.utf-8
 5589889 100.txt.utf-8~
 5590232 100.txt.utf-8~.xz
 5589889 100.txt.utf-8~~
 1659874 Glühwendel_brennt_durch.jpg
 1659874 Glühwendel_brennt_durch.jpg~
 1660016 Glühwendel_brennt_durch.jpg~.xz
 1659874 Glühwendel_brennt_durch.jpg~~
     117 thwart.php
28999654 total
Anders Kaseorg
la source
2

script shell, 203

id|gpg --batch --passphrase-fd 0 --personal-compress-preferences Uncompressed $1 $2

L'exécuter:

% sh break.sh -c pg100.txt                       
% sh break.sh -d pg100.txt.gpg > pg100.txt-original
gpg: CAST5 encrypted data
gpg: encrypted with 1 passphrase
gpg: WARNING: message was not integrity protected
% diff -s pg100.txt pg100.txt-original
Files pg100.txt and pg100.txt-original are identical
% sh break.sh -c Glühwendel_brennt_durch.jpg
% sh break.sh -d Glühwendel_brennt_durch.jpg.gpg > Glühwendel_brennt_durch.jpg-original
gpg: CAST5 encrypted data
gpg: encrypted with 1 passphrase
gpg: WARNING: message was not integrity protected
% diff -s Glühwendel_brennt_durch.jpg Glühwendel_brennt_durch.jpg-original
Files Glühwendel_brennt_durch.jpg and Glühwendel_brennt_durch.jpg-original are identical
% xz -kz5 Glühwendel_brennt_durch.jpg.gpg 
% xz -kz5 pg100.txt.gpg 
% ls -ln
total 28340
-rw-r--r-- 1 1000 1000      84 May 24 04:33 break.sh
-rw-r--r-- 1 1000 1000 1659874 Jan 19 17:22 Glühwendel_brennt_durch.jpg
-rw-r--r-- 1 1000 1000 1659943 May 24 04:46 Glühwendel_brennt_durch.jpg.gpg
-rw-r--r-- 1 1000 1000 1660084 May 24 04:46 Glühwendel_brennt_durch.jpg.gpg.xz
-rw-r--r-- 1 1000 1000 1659874 May 24 04:46 Glühwendel_brennt_durch.jpg-original
-rw-r--r-- 1 1000 1000 5589891 May 24 03:55 pg100.txt
-rw-r--r-- 1 1000 1000 5589941 May 24 04:43 pg100.txt.gpg
-rw-r--r-- 1 1000 1000 5590284 May 24 04:43 pg100.txt.gpg.xz
-rw-r--r-- 1 1000 1000 5589891 May 24 04:43 pg100.txt-original

Pas très portable, mais pourrait être fait au prix de quelques octets. Nécessite PGP (une implémentation avec OpenSSL serait également possible). La différence de ~ 50 octets entre le fichier encodé et l'original peut probablement être enregistrée.

Notation:

84 + abs (1659874 - 1659943) + max (1659874 - 1660084, 0) + abs (5589891 - 5589941) + max (5589891 - 5590284, 0) = 203

copie
la source
1

Python, score = 183 + 7 + 6 + 0 + 0 = 196

La notation vous pénalise pour avoir rendu le fichier complètement incompressible, car le fichier compressé est plus volumineux par rapport à la surcharge de compression. Ainsi, mon programme les rend légèrement moins que totalement incompressibles:

import sys
from random import randint as J,seed
x=sys.stdin.read()
seed(ord(x[1]))
n=int(2362*J(1,2)**2.359)
sys.stdout.write(x[:n]+''.join(chr(ord(c)^J(0,255))for c in x[n:]))

Résultat:

Laxori@Laxori-PC /cygdrive/f/Programming/lzkill
$ cat photo.jpg | python break.py > photo.jpg~; cat photo.jpg~ | python break.py > photo.jpg~~; diff photo.jpg photo.jpg~~; xz -kz5 photo.jpg~

Laxori@Laxori-PC /cygdrive/f/Programming/lzkill
$ cat pg100.txt | python break.py > pg100.txt~; cat pg100.txt~ | python break.py > pg100.txt~~; diff pg100.txt pg100.txt~~; xz -kz5 pg100.txt~

Laxori@Laxori-PC /cygdrive/f/Programming/lzkill
$ ls -l
total 28337
----------+ 1 Laxori mkpasswd     183 2014-05-24 13:43 break.py
----------+ 1 Laxori mkpasswd 5589891 2014-05-23 19:19 pg100.txt
-rw-r--r--+ 1 Laxori mkpasswd 5589891 2014-05-24 13:45 pg100.txt~
-rw-r--r--+ 1 Laxori mkpasswd 5589884 2014-05-24 13:45 pg100.txt~.xz
-rw-r--r--+ 1 Laxori mkpasswd 5589891 2014-05-24 13:45 pg100.txt~~
----------+ 1 Laxori mkpasswd 1659874 2014-05-23 19:19 photo.jpg
-rw-r--r--+ 1 Laxori mkpasswd 1659874 2014-05-24 13:44 photo.jpg~
-rw-r--r--+ 1 Laxori mkpasswd 1659880 2014-05-24 13:44 photo.jpg~.xz
-rw-r--r--+ 1 Laxori mkpasswd 1659874 2014-05-24 13:44 photo.jpg~~

Laxori@Laxori-PC /cygdrive/f/Programming/lzkill
$ python
Python 2.5.2 (r252:60911, Dec  2 2008, 09:26:14)
[GCC 3.4.4 (cygming special, gdc 0.12, using dmd 0.125)] on cygwin
Type "help", "copyright", "credits" or "license" for more information.
>>> 183 + abs(5589891-5589884) + abs(1659874-1659880)
196
Claudiu
la source
Avec les règles actuelles, aucun fichier compressé n'est plus gros. Les règles ont-elles changé? Dans l'affirmative, un tel changement était injuste pour ce programme.
kernigh
@kernigh: Oui, ils ont changé après l'avoir posté. Vraiment, ils auraient dû être comme ils sont maintenant depuis le début.
Claudiu