Are there any cryptographically secure (in terms of confidentiality) key exchange schemes which are usable if one partner in the connection is entirely deterministic and has absolutely no entropy? I know the basics of the operation of several asymmetric ciphers but am not a cryptographer. I wonder this because it seems like it would be easy to provide initial entropy to embedded devices through an encrypted connection without running into the chicken and egg problem of needing entropy to securely connect to a service to retrieve entropy. If this is possible, is authentication also possible?
A deterministic device initially holding no secret information can no establish any secret information thru public channels.
The argument is elementary: that device can be fully simulated by an adversary, which can thus determine any information that device may contain.
What do you want to achieve with the key exchange. If you have a pre shared secret and you want to create a new session key. Only one side needs randomness. It's trivial to encrypt a new key and send it. You can also use asymmetric encryption the same way. If you want pefect forward secrecy such a simple encrypt and send a new random key won't suffice. I don't think it's possible without randomness. All PFS mechanisms I know have DH/ECDH in them somewhere.
If one side doesn't have any randomness he doesn't have anything which isn't derived from his long term secret and messages he recieved. So after compromising the long term secret one would be able to simulate what he did with the captured messages. And get the old session key.