Assume I encrypt a message, A1, and save it. Later I replace the message A1 with a new message, A2. I do not trust the message storage. Now I want to read the last message. How can I verify that I've read the last message? An attacker can substitute the message A2 with A1 and I will not notice that.
The first idea is to memorize the last message. This will work with last message, but how can I verify that I have all my messages in the database? I think I can save a signed list of message signatures together with the date of last modification of the database. This way I only need to memorize the last database edit date. Will call this the control message. I also need to make sure that there was no substitution while I compose the control message.
How is this done usually?
What I need, is a secure counter. A counter with properties:
- it is stored in an insecure database
- can't be replaced by an older version without knowing the key
- it only supports increment/decrement operations
- if possible, two users, at the same time, should be able to increment the counter (concurrency) without side effects
- the counter can fail with some probability. Instead of N, it can be sometimes set to N-1. I do not want an attacker to set the counter.