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](https://crypto.stackexchange.com/questions/46991/can-hmac-confirm-data-existence)

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