Authentication scheme to protect against fake devices

Question

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 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.}

Answer 1

There is no cryptographic solution, that is one secure under the assumption that keys are the only secrets.

The requirement Authenticated and Replay-resistant imply that fake slaves can't interpret commands intended for genuine ones; hence the use of encryption. Since the master is assumed unable to hold any secret, only public key cryptography with a private key in the slave could secure that encryption, or its key establishment. And the slaves are hypothesized not powerful enough for that.

This is not changed even if we relax the requirements to allow:

• Random number generation in the slave (which often is possible, especially in a device with a secret; e.g. by enciphering a counter held in EEPROM memory, or careful accumulation of entropy from analog sources, including clock drift and timing of external stimulus).
• Public-key cryptography in the slave limited to the public-key side (a PIC18F24Q10 costing less than a dollar can do the public-key side of RSA in a fraction of a second, and that might be needed only once the first time an instance of the master establish connection).

For something with cryptographic security, we need at least one of:

• Public-key cryptography with a private key in the slave; that rules out RSA, perhaps not ECC (depends on hardware, power budget..).
• Some secret in the master (see final section)

---

Cryptography can help on one thing: the serial number of each genuine slave can come with a static cryptographic signature written at factory and checked by the master. That won't prevent cloning genuine slaves with their serial number and signature, but will make it impossible to manufacture a larger quantity of clones with distinct serial numbers than one has managed to gather signatures; it might also allow to blacklist clones according to serial number (e.g. in new releases of the master).

On the slave side that requires only persistent storage and transmission of about 64 bytes with EdDSA, for 128-bit security (and slightly more compact signatures exist). The master checks the signature against a public key that it embeds (we must assume integrity of the master). The private key is used only for production of genuine slave devices.

---

White-box cryptography (our tag white-box) could allow a secret in the master. Even though it typically fails under determined attack, that's the closest thing to a satisfactory solution. Sketch:

• slave is asked and gives its serial number;
• master uses white-box crypto to encipher that serial number using a master key implemented by the white box, and that gives the slave's diversified secret that was written in the slave at fabrication time;
• master and slave now have a shared secret and use (authenticated) symmetric encryption like AES-GCM (though if the genuine slave is to be protected against replay, it neeeds a RNG or a persitent storage).

Refinements:

• white-box crypto is used in the master beyond computation of the slave's diversified secret;
• use of a session key for the authenticated symmetric encryption;
• the slave contains several secrets, and selects which it uses according to a key version given by the master (that allows to recover from extraction of the master key from the white box; slave clones made using that will stop to work with new releases of the master, which can use improved white-box crypto);
• use of a static cryptographic signature (see second section), best transmitted only encrypted by the slaves to make their collection slightly harder.

Answer 2

I believe it is impossible to do what you want without breaking your guidelines or security. You must be able to establish a secure connection at least once to share secret information between slave and master. Unless you have a shared secret initially, or you use a public key scheme, you don't have any way of establishing this connection.

Assuming you do have a shared secret, or you can use public key a single time, you could use a secret nonce for both replay resistance and authentication, and even encryption if you decide to keep the message private.

To do this, you would generate some 128+ bit random number N in the master, communicate it (encrypted with shared secret/public key) with the slave, then for each message, hash N with the message and send the hash along with the message. After each message, increment N. Both the slave and master should be tracking the same secret N, meaning the master can recalculate the hash to validate the message and authenticate the slave. And because N changes with each message, the system is replay-resistant. By hashing the message with the number, you also gain some message integrity, meaning nobody can change the contents of your message, because then the hash would not match.

And of course, if this is a real world problem and you have physical access to the devices, you could share some secret via physical media, this would be the most secure method (assuming any copies of the secret are destroyed).