Use TLS_DHE_PSK_WITH_AES_256_CBC_SHA with a large Pre-Shared Key. Send over Seed.
Create a secure network session over which we can send some entropy.
/dev/urandom is foul. (I agree with @SteveSether, this is a kernel bug.)
Assumption: Any protocol you try to create between client and server will, in the end, rediscover TLS or Kerberos (Public Key or Symmetric Key), therefore, you should just use one of these or one like these.
Caveat: It is impossible to preserve Perfect Forward Secrecy without good entropy on both the server and the client. Although it helps to get entropy to the client, in the end this is a fool's errand. See discussion at the end.
With that caveat, let's dive in.
To fetch entropy from server, we require:
- Secrecy of the entropy
- Server Authentication
- #1 & #2 imply: Secure Network Protocol with Perfect Forward Secrecy
- TLS w/ DHE and Mutual RSA
- TLS w/ DHE and PSK
- TLS non-standard extension
TLS with DHE and Mutual Authentication
I had to study TLSv1.2 to figure out this wouldn't work. As noted in the question, the client isn't random, so its ephemeral can be known and Eve can compute the Master Secret. I had hoped TLS used the Client's RSA Key to protect the secrecy of the ephemeral(s). It doesn't.
TLS with DHE and Pre-Shared Key
Some people don't like this class of cipher suites. However, those arguments apply to humans as the holder of the PSK, not a computer. This works just fine for large PSKs. There are some security considerations, the most interesting one worth noting is a dictionary/brute-force attack. From RFC 4279:
For the DHE_PSK ciphersuites, an attacker can obtain the information
by getting a valid client to attempt connection with the attacker.
Passive eavesdropping alone is not sufficient.
In our case, this could be done as an observation attack due to lack of entropy on client. A sufficiently large PSK should eliminate brute forcing the Master Secret, in any event.
Use this one.
TLS Non-Standard Extension
For fun, I was thinking what if we could extend TLS somehow?
During TLS's mutual authentication step, the client and the server exchange their certificates and proofs. If the client could use an Encryption Cert instead of a Signing Cert (this is easily done, Sign and Decrypt are isomorphic), it would tell the server to modify the DHE exchange. During the DHE exchange, server sends its ephemeral as
Sign(Encrypt(B,Key_C),Key_S). Only the client can decrypt the server's ephemeral, only the server could have sent it. This keeps the server's ephemeral secret, which normally doesn't need to be. However, because we are trying to create a secure channel that Eve cannot penetrate and client doesn't have entropy for its ephemeral (a,A), hiding B will do the trick.
In summary, modify TLS_DHE_RSA with Mutual Authentication
- client uses Encryption Cert
- client authenticates by Decrypting some Nonce
- Server hides its DHE ephemeral using Client's Encryption Key.
Know anyone on the IETF committee for TLSv1.3?
As suggested above, any other solution (RSA or Secret key provisioning with Nonces, etc.) recreates TLS or Kerberos, so why bother? You'll be taking on all of the challenges of rolling your own network authentication protocol without the vast analysis these protocols have endured.
Just use TLS with DHE and a Pre-Shared Key and send the Seed over that secure channel. It's a standard protocol, it has all of the properties you require, it's easy to set up and it doesn't suffer from too many problems. See below, however.
Discussion: A Fool's Errand and Broken Promises
We need entropy to make good on the promise of Perfect Forward Secrecy (PFS). The client doesn't have it and can't make it, so we are trying to get it from the server. We can use regular old cryptography (RSA or symmetric) to send the entropy. However, if the RSA Private Key or the Symmetric Key are exposed, Eve can use that Key to decrypt the server packet containing the Seed. How bad is this?
Assume after the client received its entropy, it only ran TLS+DHE+RSA for all communications. That has PFS, right? The problem is that once PRNG(Seed) is exposed, Eve, who was eavesdropping and recorded every network session in and out of the client, knows the secret part of the DH ephemeral produced by the client (B=g^b%P) and can rebuild Master Key from every (g,P,A) by doing K=A^b%P. Boom! PFS is gone.
We can't use PFS to send the Seed to client, because client's first DH exchange has the same exact problem. Once a secret key (RSA or PSK) is exposed, Eve can recompute the DH Master Key protecting the session with the Seed. Any other attempt at creating a secure channel or secret message suffers the same fate.
So, without client entropy we can have Current Secrecy for all algorithms. However, exposing any Key used to protect the transfer of the Seed exposes all sessions built using PRNG(Seed).
/dev/urandom has to work in a client VM to get Perfect Forward Secrecy.