I want two embedded devices (call them master and slave) to communicate with each other. For intellectual property protection, the master must reject fake slave devices (the other way around is a pre but not a requirement).

I'm having no luck finding a scheme that satisfies the following requirements:

* **Authenticated**: For each message received by the slave, only if the slave is genuine it knows how to interpret the message
* **Replay-resistant**: Can't record a conversation with genuine slaves and replay it later with fake slaves,
* **Autonomous**: No third party involved (trusted or not),
* **Fast**: Slave has a slow processor so any number-field theoretic ciphers are out of the question, even for key-exchange

Also:

* No confidentiality required, messages are not secret,
* Messages are short; never in excess of 16 bytes,
* Slaves have a unique serial number that the master receives in plain,
* Only slaves can have a secret embedded in it, not the master (and can be unique for each slave),
* Only master can generate entropy / secure random data,
* Without secure co-processors, SIM or [SAM](https://en.wikipedia.org/wiki/Secure_access_module) modules.

Even though the messages are not secret, they must probably be encrypted nonetheless. If the adversary obtains fake slaves and generates fake commands (i.e. fake master) then they might as well buy everything from the competition. We (as a company) thrive on the broad feature set of the master that interlinks many kinds of slaves.

---

My attempts at thinking of a solution:

* **Public-key cryptography** or **Key-exchange schemes**: Too computationally heavy for the slave.
* **Slave is an encryption-oracle and master knows one (or more) legal plain/ciphertext combinations**: Replay attack.
* **A commutative cipher** $E\_{k1}(E\_{k2}(P)) = E\_{k2}(E\_{k1}(P))$ such that when $E\_{k1}(E\_{k2}(P))$, $E\_{k1}(P)$ and $E\_{k2}(P)$ are all known to an evesdropper, $P$ can't feasibly be retrieved. (*i.e.* CTR mode is out of the question). I have yet to find such a cipher.

I tried to be as thorough as possible, but let me know if I missed some requirements.

[edit] Removed an optional requirement that allowed listen-only fake slaves to co-exist with a real slave.