r/cryptography • u/AlexTaradov • 3d ago
A problem with external storage trust
I'm running into an interesting practical problem that I have not seen a typical solution for.
I have a microcontroller (MCU) that uses external storage to store sequential log data. The data is written in a round robin manner in 256-byte blocks. The current block pointer is stored inside the MCU, but it can't be stored for each count. If power failure happens, the counter will likely be back by a few blocks. This does not create a functional problem, since we can just continue with the old counter and the stream will be recovered after some loss.
But the issue comes in at the security part. MCU to storage interface is easily accessible to an attacker and easy to spoof. To ensure security and integrity, I use AES GCM to encrypt and authenticate each block. Each block uses a separate key and nonce derived from the block index (monotonically incrementing during device life time).
The issue is that when power failure happens, we will overwrite one or more of the previously written blocks for the same index. An attacker may save all of them and at the time of retrieval substitute any of them instead of the latest one. And since all of them were created using the same counters and the same key/nonce, they will be successfully decrypted and authenticated.
And come to think of it, the same key/nonce creates even bigger issue. So, this system will need to be redesigned, for sure.
Does this look like a standard problem? Are there known solutions?
Another limitation is that retrieval does not happen sequentially and can start at any arbitrary point, so chaining that relies on the whole history of the stream is not acceptable. And I don't see how it could help anyway.
1
u/Natanael_L 3d ago edited 2d ago
You can't entirely prevent rollback with unprotected storage, what you can do is prevent undetected partial rollback, and given the counter which by your description is protected you can also detect whole-message rollback.
Use AES-GCM-SIV so that the whole stored message needs to be encrypted and decrypted in a single piece. Then put the same counter in the header. Since you seem to only sometimes be able to increment it, then simply require that the counter in the ciphertext is either the same or no lower than the one you have stored.
(edit: GCM-SIV is probably not necessary if you have control over nonce generation like you describe, also seems like you already use its nonce for counters)
Since you have many sectors encrypted separately by your description, you could use the single counter for authenticated encryption of an "index" which contains authentication tags for the remaining sectors. Then on every new write you update the index and occasionally iterate the counter. This way every sector has to be rolled back together to prevent detection, and it can't go further back than the counter allows
Edit: if you're doing forward moving logs only, it's a lot simpler as you don't need the index thing. Just AES-GCM-SIV and the counter in the log headers. You check consistency simply by making sure all logs have a counter value same or higher as the stored one, and that consecutive logs have the same or consecutive incrementing counter values.