3 ms·
Off the top of my head, how about: Compression: gzip the file and tacking a crypto hash on the end. Discard if not shorter and store the original instead. De
by willvarfar 5y ago
Off the top of my head, how about:
Compression: gzip the file and tacking a crypto hash on the end. Discard if not shorter and store the original instead.
Decompression: if has gzip header and the crypto hash at the end matches, unzip. Else return source as is.
Have I just paradoxically compressed something?
- im3w1l 5y agoWell let's analyze it using the game from the paper. An attacker could do the following I believe: 1. Take something compressible like x0=AAAA... 2. Compress to get y0. 3. Take x1=y0. Compress to get y1. Now most likely y0=y1 meaning that decompressing y1 doesn't give x1, so you lost. But if y1 != y0, then 4. Take x{i+1} = y{i} and compress. Eventually there will be a collision. Preventing this is why the author's scheme is so complex.
- svara 5y agoThat doesn't work, since there's no way to distinguish a compressed file from an uncompressed file that just happens to have the same contents. The hash doesn't help with that since that has collisions, it's the same pigeon hole issue. Most files in the space of all possible files will be essentially random and not compress, and adding a header will make them larger.
- willvarfar 5y agoA compressed file is distinguished by being a valid gzip file with a valid hash. Such a file won’t compress a second time, so the length will remain unchanged. Then, decompressing twice will also generate the same output.
- comex 5y agoThen what happens if the user starts with a file that happens to be a valid gzip file with a valid hash, compresses it twice, and decompresses it twice?
- nuccy 5y agoOk, then what if we save some space for the single bit indicator (compressed/non compressed) by following a simple algorithm: 1. Look for at least two as long as possible identical peaces with arbitrary bit offset from the beginning. 2. Record value and length (common for all peaces) and offsets for each peace. 3. Create and prepend a header with following fields: compressed_flag, piece length, pieces count, piece value, pieces offsets list, content Obviously if the file is very small this approach will not work. But assuming that we know the file size (which is the loophole here), we can pre-calculate which is a threshold file size to consider to be with a header, and what is too short so uncompressed headerless content is being saved there. P.S. To remove the loophole possibility the streams of data should be rather considered instead of files.
- detaro 5y agoFails if fed its own output again if that was compressed before, and now goes in the uncompressed case.
- willvarfar 5y agoCompress file A generated compressed file B. Compress file B fails to make it shorter, so the generated file C is actually identical to B. We’ve just compressed twice. Uncompressing twice generates A again.
- deleted 5y ago[deleted]