We're aware this isn't exactly optimal. Suggestions welcome.
Re: Key revocation, that's a good question and we should probably think hard about it. It's trivial to create a new stream, but obviously that could be a pain for various reasons.
Yeah no SSL support on Arduino-capable hardware is a bummer. I have been able to do Amazon's signature generation on an Arduino without too much trouble though (just need to run SHA256 hash algorithm a few times). I would definitely think about key revocation and renewal since folks will need it if someone steals their keys.
The other method might be, as a sibling said, HMAC the message with a shared private key. If you can specify that clocks should be pretty close, your reply attack window becomes small.
Security on 8-bit microcontrollers is one of the hardest problems we've encountered when building this service, and I think it's going to take a lot of community support to help us figure out a good solution that works on most devices. Thanks for all of the input so far!