New answers tagged challenge-response
Even after your updates, the first part seems unnecessary. However, steps 4-5 do indeed prevent the attacker from learning future nonces they could ask the key MAC values for. So the protocol steps 4-7 would be secure with a secure MAC. I agree with CodesInChaos that using HMAC would be better, because H(m||k) has some weaknesses, while HMAC is standard. ...
From your question, I believe that what you are looking for is a proof of storage. I will point you in the direction of one paper, and you can use that to look for other work on the topic.
Top 50 recent answers are included