Well, after looking at some of the access traces on a scope, I saw groups of 16 byte blocks being sent with huge gaps between them. Of course, 16 bytes is the block length of AES, so that was sort of to be expected streaming the data through AES counter mode, but those gaps are on the order of 10 ms long.

To test out the impact, I commented out the AES block computation that takes place in the counter mode code (effectively gutting the encryption), and sure enough, Orthrus is 5 times faster. It's not a speed demon, by any means, but the performance is actually borderline acceptable (~150 kB/sec instead of ~30 kB/sec).

So... I don't know which direction I'll go from here. I sort of believe the AES engine I'm using is reasonably performant for a software implementation. I'm not sure how adding a hardware accelerator is going to improve things, given that you have to talk to them over some sort of serial bus (either SPI or i2c). Getting a faster chip seems like the most obvious move, but I'm not sure there's a good fit in the AVR family other than moving into BGA territory, which I'd rather not do. Moving away from AES means moving away from a world class crypto engine, which is unacceptable.

Some thinking is definitely called for.