Re: 16 bit checksums limit dar's potential

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Hello,

Ryan Thomas wrote :
> With all the effort that went into making dar as limitless as possible,
> I'm stuck wondering why 16 bit checksums were chosen.    16 checksum
> bits only covers 65536 possible checksums.  And because of dar's almost
> limitless potential, it's very easy to create archives that expose the
> weakness of 16 bit checksums.

If this is that easy, please provide a real example with a real archive. ;-)

> 
>  
> 
> Some examples:
> 
>  
> 
> Once an archive holds 65537 files, then you are guaranteed that 2 files
> have the same checksum.    If the contents of those files were flipped
> somehow in the archive, testing would not detect this.

The use of the checksum is not to detect the flipping of the whole
file's content (while it is of great help here too) but to detect the
modification of the contents in each file's data. As describes in the
man page in the paragraph about -t option:
http://dar.linux.free.fr/doc/man/dar.html you will see the expected
probability of detection depending on the number of bit errors by file.

Of course, when your file length increase, the probability or bit error
increases, and the probability of detection by this mechanism decreases
in consequence. However, if you plan to store your archive on a
unreliable support, it is strongly advised to use Parchive to build
parity/recovery data that will let you repair any modified dar archive.

Now, let's consider what steps a bit modification would have to pass for
it lead dar to restore another file's data in place of the correct one
without detecting it.

Such bit modification should take place in the catalogue stored in the
archive at the place of the offset that points to the place where to
read the data of a given file. This modification would most of the time
break the possibility to uncompress the archive's catalogue and would
thus be noted during the -t test option. Assuming you could however
properly uncompress the catalogue and get this modification in the
location of the data of a given file, you would then have to be able to
uncompress data starting at this new position (which is rarely the case
taken an arbitrary byte sequence) and this for the expected length of
the file (compressed data expect a well defined structured data sequence
to work). If by chance again, you would find such a sequence you would
then have it to end properly for the decompression engine to reports end
of file... (when dar has extracted the expected amount of byte with no
error reported from the compression engine, it checks that the
compression engine reports an "end of file" status, meaning that no more
data is expected to be read). Well, assuming you got this sequence and
completed faked the decompression engine for it exactly uncompressed the
N bytes of data where N is the file's data length, you would then have
to get on this new uncompressed data sequence the same 16 bits CRC value
 as the one which is stored within the catalogue for this same file. As
you reported this has 1 chance on 65536 to be the case, whatever is the
size of your file. Then and only then, dar would restore the wrong data
for that file and keep reporting no error. So you get to be very lucky, no?

I guess it would not be that easy to find a particular archive with a
single bit modification that would let dar transparently ignore this
modification and not restore the archive properly.

it would be even more improbable if you were also using encryption ...
but... yes, that would be still a non null probability.

However, if you find this detection mechanism unsuited to your needs,
you should rather use -d option to compare the archive data to what it
has been built upon.

And if you are even more paranoid, I suggest restoring the archive in a
 temporary directory and compare the source and temporary directories
trees with other means than dar, like a recursive diff for example. I
have been doing it many times for stressing/testing dar. I guess
depending on the value you attach to the archived data, it could be
interesting to you too.

To my point of view, I don't see any problem in this CRC auxiliary
mechanism, whatever it is 16, 128 or 1024 bits CRC, the principle stay
the same, the weakness stay the same, still in the perspective of a
"limitless application" as you write.

> 
>  
> 
> 16 bit checksums make it impossible to implement an effective
> approximate "diff" operation that uses only checksum information from
> the catalog and the filesystem.    An approximate diff operation like
> this would be very useful in my opinion because I could keep all the
> catalog files online and use the quick diff based on checksum from the
> catalog to determine whether or not I had to fetch the physical media
> holding the full dar archive to address a possible file corruption.
> 

If you want to detect corruptions on your real living filesystem I
suggest using RAID systems and ECC RAM. If you want instead to compare
archive content to its original source, you have the -d option or the
diff command, that performs the exact comparison byte by byte. I just
wonder who would like to approximate a "diff"? To be approximatively
sure the data is properly saved???

Anyway, dar is not a corruption detection tool, it is a
backup/restoration tool, no more. It includes some weak mechanisms to
detect internal archive coherence (among which the 16 bits CRC), no
more. By the way, it also includes an internal weak encryption
mechanism, no more. For all that is strong encryption, or robust data
corruption detection and recovery, it relies respectively on libssl and
Parchive, two external tools that do have for aim strong encryption and
data corruption detection and recovery, and not backup/restoration.

>  
> 
> The same approximate diff operation could be used to implement an
> incremental archive option that relied on checksums instead of
> timestamps.  At 16 bits I wouldn't trust that check.  At 128 bits I
> would.
> 

This is not in that objective that 16 bits checksum have been added.
Now, having a differential backup done based on timestamps lets no
chance for error: If a timestamps (last modification date) has not
changed since the last backup, you are 100% sure the file has not
changed and may safely skip its data in the context of a differential
backup.

Instead when a 16 bits or 128 bits or whatsoever N bits checksum is
unchanged it does *never* warranty at a rate of 100% that you properly
detect whether a file has changed or not, whatever it is 16, 128 or even
more bits of length. You then take the risk to not backup a change in
your data, still in the context of a differential backup.

Hopefully, the 16 bits CRC placed in dar is not used for that purpose!


>  
> 
> Also long checksums allow dar catalogs to be used as a tool to manage
> filesystem redundancy.

Sorry, this is not dar's purpose. See RAID systems for that.

>  If strong, cryptographic checksums (128bits or
> longer) are used then checksum collusions can be checked to detect cases
> where the same data is being stored over and over again.
> 
>  
> 
>  
> 
> Is there any interest in getting larger checksums in dar?
>

Not really. There is a balance to take into account between the archive
overhead and the archive reliability. The current balance seems
adequate, the archive overhead stay small, while it let detect archive
incoherence for most if not all the case when dar is used over normal
hard disk and memory (where data corruption is very rare). Dar has even
been reported to be an interesting stressing tool for memory, where even
a Linux system could work properly for many days and on which dar failed
to properly backup much data due to what has been lately reported to be
a corruption in RAM memory (see dar-support mailing-list archive).

For those users that need to use dar on unreliable systems or media,
there are specific tools like RAID or ECC memories for system and
Parchive for media. Parchive will of course increase the overhead but
this is its aim for redundancy purpose, it is even easily adjustable to
fits the user needs of hoverhead/redundancy ratio. I Strongly recommend
using Parchive, it is efficient, simple of use and can be easily
integrated with dar with the use of DUC files or scripts (see
http://dar.linux.free.fr/doc/samples/index.html ) In particular if using
dar over unreliable support or manipulating very precious data. (see
http://dar.linux.free.fr/doc/Good_Backup_Practice.html for more).

> 
>  
> 
> Thanks,
> 
> Ryan Thomas
> 
>
Regards,
Denis.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.7 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFHm3+1pC5CI8gYGlIRArEnAJsHt7gaq5IXs+UsG4c5ohYA3EwRLwCgsO8T
tZjELwawHuXjNTkFfKqluBg=
=jPFc
-----END PGP SIGNATURE-----

-------------------------------------------------------------------------
This SF.net email is sponsored by: Microsoft
Defy all challenges. Microsoft(R) Visual Studio 2008.
http://clk.atdmt.com/MRT/go/vse0120000070mrt/direct/01/