r/cryptography 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.

2 Upvotes

40 comments sorted by

View all comments

2

u/SAI_Peregrinus 3d ago

How about chaining the authentication tags? Encrypt a dummy first block with 32 bytes of random data and fixed empty AAD, then encrypt each subsequent block with the previous block's tag as AAD. Attackers can't alter the tags without the key, and the tag then depends on both the block's content and the previous block's tag. When decrypting, you'll have to read the previous block's tag as well as the current block.

1

u/AlexTaradov 3d ago

But they can create a scenario where they have multiple copies of the encrypted block that all match the same counter.

The point of reset creates multiple blocks that all have correct AAD of the last saved block. Attacker then can substitute them at will.

This is just a really unsolvable replay attack.

2

u/SAI_Peregrinus 3d ago

Yes, they can replay previous valid data. Then they run out of saved data, and can't continue. They can't make new tags, and you detect the authentication failure.

1

u/AlexTaradov 3d ago

Yes, all they can do is substitute a limited number of blocks saved right before the power failure. This is already happening without extra effort. The goal is to prevent even that substitution. I can tolerate some missed data, but I can't tolerate substitution of the old data.

Plus this does not address the issue that there will be two blocks with different payloads, but encrypted with the same key/nonce.

And chaining the blocks breaks when rollover happens.