How to provide integrity even though using Authenticated Encryption?

Question

Gilles made the following comment here:

using authenticated encryption does not guarantee integrity, only authenticity. You can't detect a rollback.

From what I gathered:

• Authenticated Encryption provides authenticity of the data see here.

• Authenticated Encryption is basically computing a MAC at the same time as you encrypt see here.

We have the usual 3 properties as follow:

confidentiality: only the authorized users can read the data (and understand it).

integrity: the users have the guarantee that the data have not been modified, or in other words only the authorized users can modify the data.

authenticity: the users have the guarantee that the data/entities are who they are (this is different from identification).

Gilles' scenario is the following:

1. Our beloved Alice store some data on a server, using Authenticated Encryption.
2. At some point Eve hacks into her server and take a copy of the encrypted data.
3. Alice store some data again on the server, still using her secure Authenticated Encryption.
4. Eve replace the data by the ones she took earlier (thus the tag is still valid).

Therefore we have a rollback. Bob accessing the data can see that they are authentic, i.e. they do come from Alice.

Can we consider that the integrity of the data is preserved or not ? At the same time they have been modified (the replacement) but the previous data have not been modified (in order to keep the Authentication Tag valid). Should the property of integrity not being preserved in this case?

Is there any scheme at all that provide such property or is it something that should be provided using another way (e.g. a version system that is not kept at the same place as the data) ? In other words, is there any Encryption scheme that allows to detect roll backs (as far as I know, there isn't) ?

---

I do see that if the data have been modified then the Authentication is not provided anymore as the tag won't match. Or from a logical point of view:

$$\neg Integrity \implies \neg Authenticity$$

thus using the logical contraposition we get:

$$Authenticity \implies Integrity$$

Which seems to contradict Gilles' comment.

Answer 1

There are several concepts of integrity. Authenticity can be thought of as integrity of the association between data and its creator/modifier/sender. There is also integrity of the internal structure of data and multiple integrity definitions inside database management.

Note also, that cryptography cannot help to prevent integrity violations, it can merely help to detect them. Thus, when I mention that integrity is enforced cryptographically, it means that there are cryptographic means to detect unauthorized modifications, not to actually prevent any. In its strictest sense of the word, cryptography can not preserve integrity either.

Not all integrity concepts are straightforward to enforce cryptographically. Thus, the answer to the question depends on the exact definition of data integrity: if we consider the individual data item or content structure visible to Alice, the integrity of that is preserved.

However, considering the integrity of the history of versions of the database, integrity is not preserved.

If Eve has such access to the database that she is able to masquerade as Alice to the database, not much can be done. I assume in the following that Eve's access to the database does not include access to the database private keys or the authentication process between database and Alice.

To prevent unauthorized rollbacks such as these, versioning control is basically required. The database should have internal structures (metadata) indicating the latest update number, and Alice should include this number in her authenticated data. To enforce the association cryptographically, the database would need to sign the db-internal version number together with the version sent by Alice during each update. Bob can then compare the signed db-internal version to the version by Alice inside her authenticated data.

An alternative method to do this is, of course, blockchains. They are append-only databases, where rollbacks are not feasible. With blockchains, Eve's access to the database could be wider, and still rollbacks would be unfeasible. However, integrating blockchain-functionality into conventional databases would be a separate topic in itself - but if the rollback is a major problem in a database designed for some large-scale but well-defined function, blockchains might be worthwhile.

Answer 2

Can we consider that the integrity of the data is preserved or not? At the same time they have been modified (the replacement) but the previous data have not been modified (in order to keep the Authentication Tag valid). Should the property of integrity not being preserved in this case?

Indeed, integrity is preserved. Or rather - as Mikko reminded me again - the absence of it can be detected.

Is there any scheme at all that provide such property or is it something that should be provided using another way (e.g. a version system that is not kept at the same place as the data)? In other words, is there any Encryption scheme that allows to detect roll backs (as far as I know, there isn't)?

It should be provided another way. There are several ways of providing protection against replay attacks because that's usually how this property is described (rather than rollback attacks).

The point of those is however to validate the freshness of the message within the context of the message. That's not something that can be provided by an algorithm alone.

That doesn't mean that authenticated ciphers do not have provisions to authenticate the context information itself. Authenticated ciphers are usually AEAD ciphers: Authenticated Encryption with Associated Data. This lets you add plaintext Additional Authenticated Data in case the context data needs to be send in the plain.

You can think of context (meta-) data such as sender, recipient, message number, date/time for message expiry etc. that can all be used to identify individual messages.

---

Closely related is the notion of time-stamping services that can provide a verifiable time stamp for the messages. Time stamping is however often used with non-repudiation rather than authenticated ciphers.