Two devices are communicating only with each other and shall do this with AES encryption. Both devices are offline, have very limited storage and use a small cryptographic coprocessor which is able to perform AES/ECDH/ECDSA/RNG. Also keys and certificates can be stored in it. Any device must work with any other device, as they are not coupled in any way per default.
I planned on doing an ECDH key exchange to create random keys for the AES communication. Then I encountered the MITM problem, which makes ECDH alone invalid for creating random keys out of thin air without further validation.
If I wanted to use ECDSA I would need to store a certificate, which would be static for the entire life of the product, as I can't update it. It would also be the same for every device, as every device must be able to communicate with every other device. If the private key is compromised, so are all the devices.
I could also store a factory key in the devices and use that to transfer a randomly generated keys. For that I could directly use AES and ditch ECDH completely. The problem here is, that the factory key might get compromised, exposing all the other devices using the same key. As mentioned I could use a fixed public/private key pair, but I see no advantage in this case over simply using AES.
Then another problem: One device might stop working, which then needs a replacement. The new device would then have to exchange a new key with the old device. A function would be necessary, that makes the old device ditch its key and accept a new one. If an adversary knows the factory key, he could intercept the new key and listen to the communication.
I am looking for suggestions on how to approach this key exchange problem and make the system as secure as possible. Thanks in advance and BR.