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:

  1. it is stored in an insecure database
  2. can't be replaced by an older version without knowing the key
  3. it only supports increment/decrement operations
  4. if possible, two users, at the same time, should be able to increment the counter (concurrency) without side effects
  5. 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.
  • $\begingroup$ So, even while editing, the data storage is not trustworthy? (It's easier if the attacks only occur while you're "away") $\endgroup$ – deviantfan Jun 14 '17 at 21:54
  • $\begingroup$ With a secure database. Companies like Oracle spend £100s developing very sophisticated storage and transaction engines that will handle security and access control for you. They can even encrypt the entire database on the fly. Any DIY solution is asking for trouble and potential failure. Cryptography is not the solution here. $\endgroup$ – Paul Uszak Jun 14 '17 at 23:29
  • $\begingroup$ I might be wrong, but this question seems more fitting for Security.SE or – probably even better – Serverfault.SE. $\endgroup$ – e-sushi Jun 15 '17 at 13:47

I'm not a professional cryptographer, but you don't seem to be asking a cryptography question. Set aside the encryption part for a second, and I think you're asking for something impossible.

  • The two parties in your example are only communicating over the storage system.

  • The only way they are alerted to new versions is by checking the storage system.

  • And yet, you also say that the storage system is unreliable, or can be hacked.

In that case literally anything can happen.

Even if both parties "remembered" the last versions they saw, either one of them could change the state of the system, do something bad, and then flip it back to an earlier state before the other one noticed. Or, a third party could do the same and fool both of them.

If you had one secure channel, you could use it to prove some things about an insecure channel. But in your example that doesn't exist.

|improve this answer|||||
  • $\begingroup$ As you said, the OP is really asking more of a distributed systems question, about guaranteeing freshness in the presence of Byzantine faults. I think there's an impossibility result for this setting in the literature somewhere, but I can't remember exactly where I read it. $\endgroup$ – pg1989 Jun 15 '17 at 3:22
  • 1
    $\begingroup$ Ah, I think "Building secure file systems out of Byzantine storage" by Mazières and Shasha is the paper I was thinking of. $\endgroup$ – pg1989 Jun 15 '17 at 3:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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