Re: [Lzip-bug] Range_decoder omits internal error check

[Antonio Diaz Diaz]

Hello John,

John Reiser wrote:
> In lzip-1.2-pre1/decoder.h there is a missing internal error check: a
> successful decode of an LZMA stream must produce  (0==Range_decoder.code) .
> All range coder+decoder pairs have this property.  The final value
> of the "accumulator" after a successful decode must equal
> the initial value before the encode.

Why should I include such a weak check? It is unable to detect any error 
in the matchfinder. Even a bug in the range decoder can leave code==0 
and still produce corrupt data.

The main advantage of the integrity checking performed by lzip, gzip, 
bzip2, etc, is that it is independent of the compression/decompression 
code. Remember that integrity checking is intended to protect from any 
kind of accidental data corruption, including that produced by bugs in 
the code.


> Also, the README file contains the claim:
>    The chances of data corruption going undetected are microscopic,
>    less than one chance in 4000 million for each file processed.
> It is true that the chance of random errors being not detected
> by CRC-32 is 2**-32.  However, the claim is false because random errors
> are not the only kind.  A determined attacker (or severely broken hardware)
> with access to at least 32 consecutive bits can corrupt the file arbitrarily,
> yet still force CRC-32 to give the same checksum.  Except for covering
> slightly more end-to-end processing of the stream, then lzip's use of CRC-32
> is not much stronger than checking (0==Range_decoder.code), yet takes
> much more time and space.

Integrity checking protects against accidental data corruption, not 
against intentional attacks. Even so, an attacker with access to 32 
consecutive bits of the compressed file can't do what you claim. It is 
the CRC of the uncompressed data what is checked, not the compressed file.

OTOH, an attacker with access to the whole compressed file can simply 
replace it, but I suppose you won't claim this is a fault in lzip.

In fact the chances of data corruption going undetected are far less 
than one chance in 4000 million for each file processed, because the 
corrupt file has to be decompressed without triggering a decoder error 
and the resulting uncompressed data have the same CRC-32 and size than 
the original.

WRT time and space, CRC calculation takes less than 10% of decompression 
time and adds 4 bytes to the compressed file. It is a price I am more 
than willing to pay for the safety it provides.


Regards,
Antonio.