I have two hosts, A and B. Host A gives host B a large piece of data and deletes it. Host A then needs to periodically confirm host B is holding the piece of data.

Before deleting the data Host A precomputes multiple HMACs with a CSPRNG generated random number (a salt). When Host A needs B to confirm the data still exists, it sends a salt to B, B then computes the HMAC returns it to A.

Is this cryptographically sound?

When computing HMAC(number, data) can you use an intermediate values instead of the actual data? Keccak is used if this affects the answer.

EDIT: Cross Referencing question on security stackexchange

  • 3
    $\begingroup$ That sounds pretty solid. FYI, you're essentially describing a proof of retrievability, which has been studied quite widely in cryptography literature. Here is a nice survey. $\endgroup$
    – pg1989
    Apr 28, 2017 at 1:59
  • $\begingroup$ In your last paragraph, do you mean HMAC(number, Keccak(data))? Don't think that'll work... $\endgroup$
    – Paul Uszak
    Apr 28, 2017 at 2:15
  • $\begingroup$ @PaulUszak Using Keccak as the cryptograpically secure hash function required for HMAC, instead of SHA-2 which is more vulnerable to length extension attacks. $\endgroup$
    – deadfire19
    Apr 28, 2017 at 2:22
  • $\begingroup$ @pg1989 That's very useful, I needed some references for my dissertation. Thanks! $\endgroup$
    – deadfire19
    Apr 28, 2017 at 2:24
  • 3
    $\begingroup$ With Keccak you do not need to use HMAC, you can use KMAC instead, which is much more efficient $\endgroup$ Apr 28, 2017 at 9:49

1 Answer 1


An attack in this context would be being able to compute valid responses to salt challenges while in possession of information lesser than the piece of data (message).

Lets assume the salt is either the same size as that of the hash function's block or is padded to that size. In essence, the first iteration of the hash function is solely computed with the salt.

Each time you challenge with a salt you are challenging with new state values of the hash function. Basically a new hash function (different default values).

To be able to attack this you would need to break the one-way property of the hash function. You would need to create associativity rules for the hash function - compute iterations of the hash function on the message in such a way that the result can be applied to an arbitrary initial state.

  • $\begingroup$ The reasoning made in this answer requires improvement. In particular, it would be false to state that if H is a secure hash (e.g. in the ROM, preimage resistant..), then being able to compute H(salt || data) or even H((salt xor opad) ||H((salt xor ipad) || data) proves knowledge of data. We need to consider the inner structure of the hash! $\endgroup$
    – fgrieu
    Apr 28, 2017 at 6:55
  • $\begingroup$ It is possible to make a secure hash such that its data can be compressed. For example, modify SHA-256 into SHA'-256 by changing its compression function F(state, block) to F'(state, block) = F(state, (F(C,block) ||C) ) where C is a 256-bit public constant. Now you can compute HMAC-SHA'-256(salt, data) without storing the full data, only about half of that, by keeping F(C,block) rather than block for each block of data. $\endgroup$
    – fgrieu
    Apr 28, 2017 at 7:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.