Can HMAC confirm message existence?

Question

I was looking into HMACs and was wondering if a HMAC can verify the existence of a message.

I need to verify another host is (still) holding a large piece of data. I plan to send the host a key and expect a computed hash back. I am considering one of the below methods for the host to generate a unique key confirming the data's continued existence:

• Hash(Encrypt(k, m))
• HMAC(k, m)

I am concerned there might be a way to hash the data, store the hash, and use the hash in the HMAC computation, similar to length extension attacks.

I am using Keccak which as I understand it, should be resistant to this.

Thank you!

EDIT: Cross referencing Crypto oriented question on cryptostack

Answer 1

What you need here is properly called randomized hashing: conceptually, a family of secure hash functions, out of which you pick members at random and use those to hash the message. Typically these are implemented as two-arguement functions that take a "key" or "salt" as first argument, but it's important to understand that this "key" is (potentially) not meant to be secret—they may be revealed to adversaries.

MACs in general don't make good randomized hashes, because the standard MAC security goal is for secret keys—keys that are known only to honest parties, and not adversaries. But HMAC in spite of the name is more than just a MAC—it's built on a secure hash function, so it can be used both as a MAC and as a randomized hash function.

So the short answer is yes, but don't be confused by HMAC's name in this case; HMAC works here because it's a good hash function, not because it's a good MAC. And if you have a good hash function you don't need HMAC for this—hash(salt || msg) should work just fine. I'd use HMAC, nevertheless.

Answer 2

So if I understand you correctly, hosts A and B have a piece of information and A wants to know whether B still possesses it. Why not just ask B to send the data to A?

If the data is large, you might want to hash it and have B send the hash to A. Without the data, B can never make the correct hash.

However, B could generate it once, store the correct hash, and throw the data away. If you want to prevent this, you could use a challenge response system where you have A generate a random number (with a CSPRNG), send it to B, and B has to hash the data together with the random number and send the result to A. Since A has both the correct answer and the number, it can perform the same operation and validate the result.

If you use an HMAC with the random number and the data as the two parameters, I think that should be secure. However, since we're sort-of inventing our own crypto here, you might want to ask https://crypto.stackexchange.com to verify that when computing hash = HMAC(number, data) and storing both the hash and the number (and perhaps intermediate values of the HMAC operation), one cannot compute the correct hash for a new number without the original data.

I wonder why you need this, though. I cannot think of a place where this is currently in use, so I wonder whether there isn't simply an existing solution to the problem you are trying to solve, instead of doing this complicated system with "continued possession of the information".

Oh and Keccak has nothing to do with this. HMACs prevent hash length extension attacks, you don't need to use one specific hash function for that. SHA2 and SHA3 are both fine. There is also no point in hashing an encrypted version. Why bother with encryption? It sounds a bit like you're making crypto soup ;-)

Answer 3

I think the simplest solution is for you to pre-compute a set of hashes of offset+length and then send a request with one of these offset,length pairs every so often.

Whatever you do, you must perform the same operations ahead of time if you expect to delete the data you're uploading, and this method imposes the lowest burden on the storage provider.