I am aware that it is possible to use a block cipher with the GCM-mode to provide authenticity, but this does not completely do what I need.
I have a cloud storage provider I do not completely trust, in particular when it comes to rolling back the data. I use AES-GCM to encrypt and authenticate the data, but what prevents the server from rolling the file back to a previous version? As far as I understand this would still decrypt without any issues because the old auth tag matches with the old encrypted data?
I read the answer to another question here, but in the first part of the answer kelalaka mentioned 4 bullet points that he marked as "not helping" and in the second part of the answer there is still some state required on the client to detect anything.
What can I use to detect, at least as a human, that the data was rolled back? I thought about using Hash-Trees, as per the answer to the question above, (with HMACs instead of hashes alone) and add the timestamp from the latest changes to the HMAC of the root directory. This way the client application could check if the timestamp matches with the root HMAC and the user can see if the retrieved timestamp (displayed as a date) makes sense. Also, when the application was used on the client previously, the application could detect the rollback when the timestamp is smaller than the one that was retrieved in the latest valid retrieval.
Would this be a feasible extension to the answer kelalaka mentioned? When updating it is sufficient to renew the hmacs from the file to the root, which does not seem to bad, and when retrieving the data a human can check roughly if the data is up-to-date.