Old thread, but the good question, and the few answers here are not always specific to AWS machines or even Cloud VMs, as mentioned in the question, so I'll suggest taking a look at a recommendation from the Lemur team, that applies for wider scenarios: "The amount of effort you wish to expend ensuring that Lemur has good entropy to draw from is up to your specific risk tolerance and how Lemur is configured. If you wish to generate more entropy for your system we would suggest you take a look at the following resources:" and they proceed to recommend haveged.
For those interested in reading more about the issues with low entropy, the following paper, An Analysis of OpenSSL's Random Number Generator, and references, is worth a read.
The ability to generate high entropy random numbers is crucial to the
generation of secret keys, initialization vectors, and other values
that the security of cryptographic operations depends on.
This article, Improving Random Seeds in Ubuntu 14.04 LTS Cloud Instances, about Ubuntu's efforts towards improving entropy in the cloud, describes the issues and possible solutions (pollen) in much more detail:
Q: So my OS generates an initial seed at first boot?
A: Yep, but
computers are predictable, especially VMs. Computers are inherently
deterministic And thus, bad at generating randomness Real hardware can
provide quality entropy But virtual machines are basically clones of
The Ubuntu solution still may not meet the OP's requirements as it is an "entropy-as-a-service" solution, however (according to the developer) it is "fast, efficient, and scalable."
To move from theory to practice, check out Prangster if you are interested in assessing how good your PRNG is:
Now our goal is to determine the seed that produced a given sample of
pseudorandom output, and in doing so, conclude with certainty the use
of an insecure PRNG and prepare to attack the application that uses
it. This is the primary function of the Prangster tool; all it needs
is the output and the right PRNG and alphabet