Dmitry's suggestion to use AES in counter mode sounds good to me, assuming that you only need confidentiality, and not integrity protection. (Counter mode, like most stream ciphers, is very malleable.)
One trick you can use to save a bit of space is to use the current time as part of the nonce. (Of course, this only works if your devices have fairly well synchronized clocks.) To make this scheme more robust against slight clock skew, you should transmit a few of the least significant bits of the timestamp as part of the message, so that the receiver can adjust their timestamp to match it.
For instance, let's say that your devices have clocks that are assumed to be synchronized to within one minute of each other, that they'll need to transmit at most 256 messages per second, and that there are at most 256 devices communicating with each other. Then you could use the following four-byte header for each message:
- Byte 1: Sender ID.
- Byte 2: Receiver ID.
- Byte 3: Eight least-significant bits of the current time (in seconds since epoch).
- Byte 4: An 8-bit message counter, reset whenever byte 3 changes.
This header would be transmitted in the clear, at the beginning of each message. The remaining 28 bytes can then contain data encrypted using AES-CTR (or some other stream cipher), with a 16-byte IV constructed as follows.
- Bytes 1–8: A unique 8-byte identifier for this group of devices.
- Bytes 9–10: Sender and receiver IDs (from header bytes 1 & 2; included to ensure that IVs are not reused between different pairs of devices).
- Bytes 11–14: A 32-bit timestamp (seconds since epoch; byte 14 = header byte 3).
- Byte 15: Message counter (header byte 4).
- Byte 16: Within-message block counter (really needs just one bit for two-block messages, but using a whole byte leaves some expansion room).
For the sender, constructing this IV is straightforward. For the receiver, the only complication is that they'll need to reconstruct the sender's timestamp for bytes 11–14, by picking the nearest time that matches the 8-bit timestamp in the header. (This might be either in the past or in the future, due to clock skew.) One way to implement that is as follows:
- Initialize message timestamp to current time.
- Replace lowest 8 bits of message timestamp with byte 3 from message header.
- If message timestamp is more than 128 seconds in the past, increment it by 256 seconds.
- If message timestamp is more than 128 seconds in the future, decrement it by 256 seconds.
Optionally, if the reconstructed timestamp is off by more than 64 seconds (or so), the receiver may wish to initiate a time resynchronization protocol. Note that, with any time resynchronization scheme that potentially involves adjusting clocks backwards by a full second, either the devide ID or the group ID should be changed to prevent IV reuse.
In cases where the clock skew is only slight, it may be preferable to use a gradual adjustment scheme (i.e. telling the skewed device to count seconds a little slower or a little faster) that doesn't involve sudden time jumps. Or, alternatively, you could always have all the devices adjust their clocks foward to match the fastest-running clock (which might gradually shift them away from "true" time, but would keep them in sync without backwards time jumps). One way to handle this would be to separately track "true time" and a guaranteed monotonely increasing "message time", storing an offset between these.
Of course, you can adjust this header depending on your timing, message rate and device count needs. For example:
If you have good clock synchronization, you can increase the clock resolution (to, say, one millisecond) to allow a higher message rate.
If all your devices communicate with a single central controller (and not directly with each other), you can replace the sender and receiver IDs with a single device ID and a single direction bit indicating whether the message is to or from the controller. (Technically, you don't even need to transmit the direction bit, since the receiver will always know what it should be; but you do still need to include it in the IV.)
If your transmissions are very bursty, you can use more bits for the message counter, and less for the truncated timestamp. Conversely, if your messages are sent at regular intervals, you can use less bits for the message counter, or even eliminate it entirely. (Technically, you only need one or two timestamp bits, while the rest can be part of the counter; however, the higher the resolution of the message timestamps is, the easier and safer it is to recover if, say, your device suddenly loses power and forgets the current message counter value.)
The important thing is to ensure that, no matter what happens, the same IV is never used twice. Also, since CTR mode does not offer integrity protection, you should make sure to design your underlying protocol to be robust against both garbage messages, and messages that might have been deliberately modified by an attacker. For certain critical messages (like time synchronization commands, or other messages that could be used to adjust encryption or other essential operation parameters), this may require the use of a MAC at a higher protocol level.
