You can do even asymmetric crypto. Granted, a computation of one 1024bit RSA transaction takes almost 13 seconds (8.5 if helped with assembly) on a 16MHz 8bit ATmega-class Atmel AVR, but you need that just once per transaction, the rest is symmetric cipher. (The usual modus operandi of these things is generating a random number, using it as a symmetric key, encrypting the message, then encrypting the key with asymmetric cipher and attaching it to the message. Nifty.)
http://evothings.com/is-it-possible-to-secure-micro-controllers-used-within-iot/
And there are FPGA chips that are tiny and cheap and can serve as crypto coprocessors, too.
