Updating the secret key used for HMAC I am designing a distributed system, composed by a set of physically distributed embedded devices (8 bit cores with less than 1 KB of RAM). The devices need to be able to authenticate the originator of the commands they receive, and for that purpose I chose HMAC.

Each device has a secret key, and a central server knows all of the keys (somewhat similar to a RADIUS server). When a user wants to send a command to a device, it first sends the message to the central server which will append the correct HMAC to it. The user then sends the authenticated message to device, the HMAC is sucessfully verified and the message processed.

My question: is it possible to update the secret key on the device using only this scheme? Since there is no encryption, the new key would be sent in plaintext. I was wandering if a secret sharing mechanism would work for this case.
Does your embedded device have access to a random input source and a bidirectional channel?

If not, then there will only ever be as much entropy on the chip as you put on it to begin with, so there's no purpose in updating the key.

If so, then just do an authenticated key exchange and generate a new shared symmetric key occasionally.  ECC is best for bandwidth starved devices and lattices are best for computation starved devices.