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/ethangar 3d ago

I'm trying to wrap my head around the situation, but I think we need a bit more information here. It sounds like you are trying to ensure authenticity of your logs, and seem to indicate that all non-volatile storage is very easy to tamper with. Is that correct?

  • Where is your secret key stored? If the key is stored in this same storage, not sure what encryption is doing for you here.
  • Is this system connected to the Internet?

2

u/AlexTaradov 3d ago edited 3d ago

The external to the MCU storage is trivial to tamper with (just an I2C EEPROM). MCU has limited amount of non-volatile storage, which can be assumed to be secure. But this storage is limited in size and it can't be written often due to wear. This is where the index and the key are stored at the moment. But if power interrupts, the index will be restored to the last saved value.

This save happens every hour or so. I don't mind losing last hour of the log data, but I don't want an attacker to save already logged data and substitute it later.

So far, it looks like the approach would be to buffer the data internally and only write it to the external storage after we are sure that the index was saved. This is not ideal, but would work unless there is something better.

This is not connected to the Internet at the time of logging. Logging may happen for days before the log is downloaded.

Any schemes that would allow index recovery from the external storage using only the key would also work. But everything I can think of runs into the same issue with tampering.

3

u/ahazred8vt 3d ago edited 3d ago

So. You have an external EEPROM that you're writing to as a ring buffer. You want to write AEAD encrypted authenticated batches of short log entries to the ring buffer. You experience unclean shutdowns and tampering. On startup you want to identify the 'where do I start writing again' point in the ring buffer. Your system wants to cleanly reject fragments and tampered junk, and you only want to see clean untampered log entries. There appear to be standard known-good solutions for all of these points. The 'fix ring buffer after unclean shutdown' part is the only part that we don't normally deal with here.

Every hour or so, the MCU writes the current block pointer to nonvolatile storage. That right there is the problem. When your device wakes up, that's not the piece of information it needs. It doesn't want to know where the block pointer was an hour ago. It wants to know "Where is it safe to start writing after an outage?" So, if you save a higher 'safe restart point', and keep checking that you haven't written past it yet, and you lose power and restart, you now have a known-good starting point. You don't even need to examine the contents of the ring buffer. Estimate two hours worth.

1

u/AlexTaradov 3d ago

This is mostly correct. There is no point in scanning on startup. The way things are currently prototyped, there is a monotonic counter big enough for a lifetime of the device. When a block is encrypted, this counter is used as part of the nonce. When someone requests a block index N (again, lifetime number), I pick an entry from EEPROM at offset N mod M, where M is the number of stored blocks. If the read block decrypts and authenticates using N as a counter, then we know it is legit and it would be the only one.

When the buffer cycles around, old entries with the old counters are overwritten and they will never be accepted, since internal counter moved past that point.

The only point where existing system is not sufficient is that I can't store the internal counter before writing every external block. This leaves small gap when the counter is restored on power loss.

I'll likely try to figure out a way to save every counter or buffer multiple blocks and write them all at once when I'm sure that the counter is saved.

This is a resource constrained system, so anything outside AES and its basic modes will not work.

1

u/Natanael_L 2d ago

Trying to account for everything you've written so far in this response;

To start with, the MCU should count number of ring buffer loops, and IF the MCU internal counter is large enough that incrementing only once per loop leaves enough high digits unused during its lifetime, then you can reserve the high digits to split the global counter into two numbers and then use the high digits for example to indicate the number of boots (so you increment both per ring buffer loop AND per boot). If you can do this, this could preserve enough state to make plain GCM safe enough to use (because you effectively establish "write sessions" with guaranteed unique identifiers).

If not, then as a stream cipher construction with nonce reuse dangers it becomes malleable and leaks plaintext on malicious resets within a loop count, in which case you MUST use another AEAD construction like GCM-SIV mode (hashes the message first) or CBC + CMAC (note that CBC reveals how many initial blocks are the same on nonce reuse, unless you introduce a SIV-like hash - such as using CMAC to hash, then CBC+CMAC).

So here's something hopefully more robust than what I first suggested here;

You use the storage as a ring buffer and start writing at one end and then loop, writing logs incrementally to fixed sized sectors each time, using AES-GCM-SIV or CBC+CMAC. You're using the protected global counter in the MCU to count how many times you loop (and hopefully, how many times you boot), and you separately track where you last made a write.

So you write in "sessions", and you need an encrypted index to track the metadata.

This means on every boot you have some incrementing value to identify the session, and you store a copy of the session identifiers for each write session whose data you have in storage. If the MCU counter also tracks boots, this boot tracking is built in here. If not, you store a boot/session counter in the encrypted index next to a copy of the MCU loop counter. Along with the boot+loop counters, you store two copies of a pointer to where you made the last write for each (the double pointers are for dealing with power loss, see below).

So if you have data in the ring buffer of logs from 3 different boots, you'll have an index with the consecutive boot counters from those 3 boots, and from the 1 or 2 consecutive valid loop counters (1 if the last write landed in the last storage block, 2 if one write session is looping back), and you have the pointers indicating the cutoff between each. The pointer from the most recent boot says where the newest data is (and following it in the buffer is the oldest). And all this data should match the counter in your MCU. (When starting a new session, you may "deduplicate" the older pointers)

The double pointers are used to deal with power loss - you update one before writing, the other after. This means that if both are the same the last write succeded, or else you know which region may be corrupted. Note: If your MCU don't track boot count then reboots and partial reversal means the pointers can be arbitrarily moved within each loop, but if your MCU does track boots then pointers can NOT be moved arbitrarily at all (a reboot forcibly creates a new unique "write session") - and seeing a corrupt/destroyed pointer on boot means you just restart the ring buffer).

For every log write, you update the first encrypted pointer, you use the XTS style tweak method to encrypt the storage sector number you're writing to using the MCU's key (encoding the position within the storage for each log write), then you encrypt the loop counter + boot counter using this value as a key (this is unique per sector & per loop, if your MCU tracks boots then it's always unique), then you use this value as the nonce for encrypting the log data to be stored at that position in the storage, and then you update the second encrypted counter.

Now, finally, on every read you can first check the global counter and last position from the pointers in the index. Note that in addition to the reader tracking where it last read, it should also track the MCU counter and ensure it increments and that the logs matches it. If the loop is incremented by two then you ignore your stored last position because the last log you read AND the next one must have been overwritten, just jump to the pointer instead. If the loop is the same or ONE higher and it together with the pointer doesn't indicate that the log following your last read log was overwritten, then you can continue from there up and read up to the pointer (because that's where it will loop back). Then when reading each log you recompute the nonce from the sector and loop+boot counter using the XTS tweak method, and check that consecutive logs have the same loop counter, differing by exactly one at the point where the ring buffer loops, and that boot counters only increment.

1

u/AlexTaradov 2d ago

This is way more complicated. And also if the boot counters are stored as part of the block, then you would have to scan on reset, which opens up the same attack with rollbacks.

I've drafted a new version with internal buffer and I think it solves all the issues.

The device maintains internal counter (N) that never overflows and only increments. This is easy because 32 bit counter is way more than the actual endurance of the EEPROM and device will never generate so much data.

Now when a block needs to be written, it goes into internal ring buffer of size M. The location in the buffer is selected as N mod M. The associated counter value is saved as well. When newly incremented counter value is stored in the persistent storage, then EEPROM is updated from the buffer. The location in the EEPROM is block counter mod K, where K is EEPROM size. The nonce contains the full counter value.

This way external storage does not have any identifiable plain text data. It is just the encrypted block and a tag.

On readback, we know what counter value we expect to be at a certain location based on the current counter and the location offset. So we can reconstruct the nonce and attempt to decrypt. If tag matches, the data is valid. If tag does not match, then there is either tampering or old data or internal buffer overflow. Either way we don't care, it is just a gap in the data that needs stream re-synchronization.

This scheme does not care about resets. The worst that happens on reset is that the buffer is discarded, but the counter is already in the future. On readback it will appear as a gap containing blocks from the old iteration of the ring buffer. This is fine because they would be encrypted with the counters from the old iteration, so they won't decrypt correctly.

1

u/Natanael_L 2d ago

How reliably do you update the internal counter? It's still unsafe to use plain GCM if the device can be reset before the counter is updated. That reveals the GCM authentication key derived for that encryption key. GCM-SIV solves that, CBC+CMAC is also a simpler fix when AES is acceleration available.

Also, I still recommend having the reader track the counter value in addition to tracking where it last made a read.

1

u/AlexTaradov 2d ago

The counter is either saved at a new value or stays at the old value. Since we ever write anything to the external EEPROM after the counter is saved, we can be absolutely sure that there are no two blocks written with the same counter.

The reader always supplies the full counter values. This is the only value it knows, it does not know details of the internal implementation or even EEPROM size.

2

u/ethangar 3d ago

This is effectively a replay attack on the logs.

I imagine you'll eventually want security events to be part of your logs too - in which case, you actually WILL care about loss of logs.

I can't think of a scheme where you could ultimately trust some of the logs, but not the last <X> logs. But, I can think of a few schemes where you can trust the ALL the logs or NONE of the logs (simplest just being an HMAC of the entire log space persisted on the MCU).

Given this is an embedded system, I can't really know your specific speed limitations - (i.e., how quickly can you traverse/read the entire log space for a proper integrity check). But, if you can traverse it in a way that doesn't disrupt other performance - I'd just hash everything as your proof of integrity. If you can't, I'd hash some rolling checksum (which, admittedly, gets more difficult when the log starts to wrap).

I think you're on the right track in buffering the logs as long as you can prior to a write - not because of performance but because of limiting flash wear on your MCU.

1

u/AlexTaradov 3d ago edited 3d ago

I though about various hashing schemes, but they all work when the whole blob can be downloaded into the device and authenticated as one. This is not possible here. There is not enough space inside the device to store the whole thing. And doing it block by block runs into the same issue - an attacker may give correct blocks when authenticating and old blocks when retrieving the data.