Select a random number known only to you(r program). Seed your generator with it. Start randomly selecting sectors to write to (directly as a block device), writing a psuedorandom sequence based on your first number and the block identifier. Store a set of what sectors you've written to. (You can bundle them into arbitrarily-large contiguous chunks if this gets too large.) As you write, periodically randomly select a sector you already wrote to and verify that when read it returns the same psuedorandom sequence. I don't just read them back in order to prevent the "save the first few chunks" attack. This will slow down detection a bit, but if I'm working my intuition math correctly it doesn't actually slow it down very much, at the gain of making it impossible for a hostile firmware to know which sectors you're going to ask for.

Using this approach, you can write arbitrarily large of data to a drive with very minimal storage requirements on your end (well within even modern-day embedded RAM availability), while still being able to demand any sector back at any moment and verifying it is correct. Theoretically your psuedorandom number generator ought to by cryptographically secure, and given that you're probably IO bound here and they aren't hard to come by, there's probably no reason to use anything less.

I'm pretty sure the only effective defense against that is to actually store all the data. If you issue a predictable read pattern, you open an attack. If linearly-sampling your previously written blocks turns out to be undesirable you could tweak the sampling distribution, but I bet you wouldn't get much improvement.

Also, come to think of it, if the drive is honest this could be done non-destructively (assuming the undo process is allowed to run to completion) by reading the sector and XOR'ing it, so you could then undo it by a second XOR operation. Further cleverness could even make this reasonably safe to half-complete the undo, then finish later, if you work at it.

It's really much simpler than that:

  cd
  head --bytes=your_card_size /dev/random > tmp
  sha1sum tmp
  cp tmp /media/your_card
  sha1sum /media/your_card/tmp

Never considered using head to get a bytestream from /dev/random. I've always used dd. Thanks for the tip!

If you are on linux, use /dev/urandom.

Since the compromised flash controller allocates the actual sectors to use, it seems like it would be difficult to make a reliable test without generating a large file and then checking it for integrity, which would take a while to run.