Re: backup manifests - Mailing list pgsql-hackers

On 11/22/19 5:15 PM, Tels wrote:
> On 2019-11-22 20:01, Robert Haas wrote:
>> On Fri, Nov 22, 2019 at 1:10 PM David Steele <david@pgmasters.net> wrote:
> 
>>> > Phrased more positively, if you want a cryptographic hash
>>> > at all, you should probably use one that isn't widely viewed as too
>>> > weak.
>>>
>>> Sure.  There's another advantage to picking an algorithm with lower
>>> collision rates, though.
>>>
>>> CRCs are fine for catching transmission errors (as caveated above) but
>>> not as great for comparing two files for equality.  With strong hashes
>>> you can confidently compare local files against the path, size, and hash
>>> stored in the manifest and save yourself a round-trip to the remote
>>> storage to grab the file if it has not changed locally.
>>
>> I agree in part. I think there are two reasons why a cryptographically
>> strong hash is desirable for delta restore. First, since the checksums
>> are longer, the probability of a false match happening randomly is
>> lower, which is important. Even if the above analysis is correct and
>> the chance of a false match is just 2^-32 with a 32-bit CRC, if you
>> back up ten million files every day, you'll likely get a false match
>> within a few years or less, and once is too often. Second, unlike what
>> I supposed above, the contents of a PostgreSQL data file are not
>> chosen at random, unlike transmission errors, which probably are more
>> or less random. It seems somewhat possible that there is an adversary
>> who is trying to choose the data that gets stored in some particular
>> record so as to create a false checksum match. A CRC is a lot easier
>> to fool than a crytographic hash, so I think that using a CRC of *any*
>> length for this kind of use case would be extremely dangerous no
>> matter the probability of an accidental match.
> 
> Agreed. See above.
> 
> However, if you choose a hash, please do not go below SHA-256. Both MD5
> and SHA-1 already had collision attacks, and these only got to be bound
> to be worse.

I don't think collision attacks are a big consideration in the general
case.  The manifest is generally stored with the backup files so if a
file is modified it is then trivial to modify the manifest as well.

Of course, you could store the manifest separately or even just know the
hash of the manifest and store that separately.  In that case SHA-256
might be useful and it would be good to have the option, which I believe
is the plan.

I do wonder if you could construct a successful collision attack (even
in MD5) that would also result in a valid relation file.  Probably, at
least eventually.

Regards,
-- 
-David
david@pgmasters.net