Fooling Proof-of-Storage Protocols. What's the difference with Length-Extension attack?

Question

I've searched a bit for this question, but I haven't found anything, so I've decided to post it here.

Lately I've been reading "Serious Cryptography: A Practical Introduction to Modern Encryption" by Aumasson. In chapter 6 he talks about Hash Functions and as examples, of what can go wrong, he explains the "length extension attack" and "fooling proof-of-storage protocols". He explains that, for example BLAKE2 isn't vulnerable to the first attack because it includes a flag that if it's the last block, it does some things different, so the output cannot be used as the entry for next blocks.

Then he explains the proof-of-storage protocols, namely:

1. The client picks a random value, C, as a challenge.
2. The server computes Hash(M || C) as a response and sends the result to the client.
3. The client also computes Hash(M || C) and checks that it matches the value received from the server.

And why it should be Hash(C || M) instead:

The premise of the paper is that the server shouldn’t be able to fool the client because if the server doesn’t know M, it can’t guess Hash(M || C). But there’s a catch: in reality, Hash will be an iterated hash that processes its input block by block, computing intermediate chaining values between each block. For example, if Hash is SHA-256 and M is 512 bits long (the size of a block in SHA-256), the server can cheat. How? The first time the server receives M, it computes H1 = Compress(H0, M1), the chaining value obtained from SHA-256’s initial value, H0, and from the 512-bit M. It then records H1 in memory and discards M, at which point it no longer stores M. Now when the client sends a random value, C, the server computes Compress(H1, C), after adding the padding to C to fill a complete block, and returns the result as Hash(M || C). The client then believes that, because the server returned the correct value of Hash(M || C), it holds the complete message—except that it may not, as you’ve seen.

My first question, maybe a stupid one, is: Why would the server do that? Why "fool" the client?

And the second one, how is that different from a length extension attack? to which BLAKE2 is not vulnerable, but it is for this one?

Thanks a lot! :)

Answer 1

Why would the server try to "fool" the client?

The server could be paid by the client on the basis of terabyte⋅day stored (that's the pricing model of Amazon S3), but only pretending to store, to make easy money.

The goal of a proof-of-storage protocol is to repel crooks from the remote storage business, and reassure the client that the data is safe, without actually restoring backups (which is expensive, at least due to communication costs, and because there might be an access fee beyond that). Also, checking data returned from the server requires the client to have a way to distinguish that the data is genuine, which requires either the genuine data (expensive, and partially negating the benefits of delegating storage), or some precautions taken at a moment when the genuine data was available. Notice that a rogue server could be successful at guessing which segment of the genuine data will be asked as a test, and/or could use sophisticated algorithms to generate plausible missing data from actually available data; and even make checksums in recognized archive formats (gz, zip..) check OK.

More insidious: the server's operator could pretend to keep data on two storage medium in two different locations, but actually use one, and generate fake data in the rare case of a bad block on the sole hard disk with the data. That roughly halves energy, space, and investment costs, thus makes profits skyrocket, and is hard to prove remotely. Regular use of a proof-of-storage protocol will at least catch the most greedy implementations of that fraud (but not those using some RAID5 on a single site).

How is that different from a length extension attack?

A pure length-extension attacks computes a new hash $H'=\mathcal H(M\mathbin\|C)$ given $H=\mathcal H(M)$ and $C$; while the modified length-extension attack outlined replaces $H$ with a slightly larger amount of information: the internal state of $\mathcal H$ slightly before finalization of the computation leading to $H$. This allows that modified attack to work for any $C$, while for most hashes a pure length-extension attack works only for some very particular $C$ (in the case of SHA-256: starting with a precise string of at least 65 bits uniquely dependent on the length of $M$).

Thus the pure length-extension attack is not enough to foul the would-be proof-of-storage protocol proposed, but a modified length-extension attack is.