Re: backup manifests

Moin,

On 2019-11-22 23:30, David Steele wrote:
> 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(at)pgmasters(dot)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.

That is true. However, a simple way around this is to sign the manifest
with a public key l(GPG or similiar). And if the manifest contains
strong, hard-to-forge hashes, we got a mure more secure backup, where
(almost) nobody else can alter the manifest, nor can he mount easy
collision attacks against the single files.

Without the strong hashes it would be pointless to sign the manifest.

> 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.

With MD5, certainly. One way is to have two block of 512 bits that hash
to the different MD5s. It is trivial to re-use one already existing from
the known examples.

Here is one, where the researchers constructed 12 PDFs that all
have the same MD5 hash:

https://www.win.tue.nl/hashclash/Nostradamus/

If you insert one of these blocks into a relation and dump it, you could
swap it (probably?) out on disk for the other block. I'm not sure this
is of practical usage as an attack, tho. It would, however, cast doubt
on the integrity of the backup and prove that MD5 is useless.

OTOH, finding a full collision with MD5 should also be in reach with
todays hardware. It is hard find exact numbers but this:

https://www.win.tue.nl/hashclash/SingleBlock/

gives the following numbers for 2008/2009:

"Finding the birthday bits took 47 hours (expected was 3 days) on the
cluster of 215 Playstation 3 game consoles at LACAL, EPFL. This is
roughly equivalent to 400,000 hours on a single PC core. The single
near-collision block construction took 18 hours and 20 minutes on a
single PC core."

Today one can probably compute it on a single GPU in mere hours. And you
can rent massive amounts of them in the cloud for real cheap.

Here are a few, now a bit dated, references:

https://blog.codinghorror.com/speed-hashing/
http://codahale.com/how-to-safely-store-a-password/

Best regards,

Tels