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