1

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

3
  • Yes, looks like it might work. It his however lot to compute, so maybe also sent a range with it. You can only verify the answer if you precomputed them for a few keys (or have all of the data yourself)
    – eckes
    Apr 29, 2017 at 13:59
  • There is BTW a problem, if your backup peer gets the HMAC queries and answer them correctly this does proof it has the data, but it does not proof that it will give it to you. Also if you want to sent your challenges regularly you might need to precomputed thousands of them which can be quite CPU intensive.
    – eckes
    Apr 29, 2017 at 14:04
  • @eckes I have a 1% chance of requesting the full data back on every confirmation request and require one confirmation an hour and expire the block after two weeks. A peer is expected to store more than one block and each block has a X% chance the HMAC being requested every check.
    – deadfire19
    Apr 29, 2017 at 14:45

3 Answers 3

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.

0

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 ;-)

1
  • Thanks. As Host A no longer holds the data I pre-compute the salts and HMACs. What you asked to post on crypto.stack is exactly what I was wondering. I need this for a distributed backup platform I'm building for my final year project at university. (mbrn.io) Host B is a peer that stores backup information. I know Keccak has inherent protection against length extension, that could have affected the intermediate values.
    – deadfire19
    Apr 28, 2017 at 0:04
0

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.

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .