Is there an existing AE protocol with forward secrecy for embedded devices?

Question

I'm working on an embedded device that is connected to a computer over an untrusted channel. According to my threat model I need authentication and encryption on the wire with perfect forward secrecy. Both endpoints have a pre-shared key and/or each other's authentic public keys, as well as secure random number generators (although not requiring a secure RNG on the device is a plus). All messages on the wire are fixed-length (16 bytes, i.e. 128 bits).

I'm looking for an existing cryptographic protocol satisfying these properties that would be reasonably simple to implement.

The "toy" protocol I've come up so far is performing an Elliptic-curve Diffie-Hellman key exchange (wrapped in AES-CCM with pre-shared key for authentication), then running a key derivation function on ECDH shared secret and using the result as session key for AES-CCM that encrypts and authenticates data. AES-CCM is used to authenticate ECDH because of limited amount of space code on the device, so I have to use as little primitives as possible.

But I don't want to use a protocol that I've just made up (for obvious reasons) and protocols like TLS, OTR and SSH are way too complex for use in embedded devices. Is there a simpler protocol that provides authentication and encryption with forward secrecy that I could use?

Update: to clarify, establishing a connection doesn't have to be fast, so I can afford a lot of computation. The only requirements for asymmetric crypto is keeping the keys short, hence elliptic-curve cryptography instead of discrete logarithms.

Answer 1

I've finally found a solution - some variants of key ratcheting, e.g. the one used in SCIMP, provide perfect forward secrecy assuming an initial shared secret is established without any asymmetric crypto, and they don't even require a secure random number generator on any of the endpoints!

In this case all we need for an authenticated and encrypted protocol with perfect forward secrecy a symmetric cypher, an authenticated encryption mode for said cypher (e.g. EAX) and a hash. We can even ditch the RNG on the embedded device.

This is not a complete protocol, but gets us most of the way to one, and it's dramatically simpler both in the implementation and the number of required primitives than TLS.

The hard part is proper handling of message losses on the wire without opening up to downgrade attacks, but it's easier than correct custom implementations of asymmetric crypto.

Ironically, nobody I asked could tell me about using such key ratcheting for perfect forward secrecy. Our team has come up with the scheme on its own and only after that I've found it in literature.