How do I get /dev/random to work on an Ubuntu virtual machine?

It should 'just work'. Even though the vm has no dedicated physical hardware, it still has access to several very good sources of randomness. For example, it can use the CPU's TSC to time its read from virtual disks, which will ultimately wind up timing physical disks to the billionth of a second. These timings depend on turbulent airflow shear in the hard drive, which is unpredictable.

Similar logic applies to network traffic. Even though the interface is virtualized, so long as the packet originates on a physical network (and isn't local to the box, say originating in another vm), the packet timing depends on the phase offset between the crystal oscillator on the network card and the crystal oscillator that drives the TSC. This is dependent on microscopic zone temperature variations in the two quartz crystals. This too is unpredictable.

If for some reason it's not working, the simplest solution is to write a program to mine entropy and add it to the system pool. The network interface is your most reliable source. For example, you can write code to:

1) Query the TSC.

2) Issue a DNS query to a server known not to be on the same physical machine.

3) Query the TSC when the query completes.

4) Repeat this a few times, accumulating all the TSC values.

5) Perform a secure hash on the accumulated TSC functions.

6) Pass the secure hash function's output to the system's entropy pool.

7) Monitor the entropy pool level, and wait until it's low. When it is, go back to step 1.

Linux has simple IOCTL calls to add entropy to the pool, check the pool's level, and so on. You probably have rngd, which can take entropy from a pipe and feed it to the system pool. You can fill the pipe from any source you want, whether it's the TSC or 'wget' requests from your own entropy source.

I use haveged on all my headless servers that perform cryptographic operations (e.g. TLS handshakes, kerberos, etc). It should be in most Ubuntu versions' package repository: http://packages.ubuntu.com/search?keywords=haveged&searchon=names&suite=all&section=all

haveged uses the HAVAGE algorithm to extract entropy from the internal state of modern processors. Here's an indepth explanation: http://www.irisa.fr/caps/projects/hipsor/

You can check the randomness of generated entropy with the ent package. On my systems the generated entropy from haveged passed all randomness tests by ent

Yeah you can seed it, from:

http://manpages.ubuntu.com/manpages/jaunty/man4/random.4.html

You can just put that into /dev/urandom and it should seed the entropy pool. I was able to confirm this by:

root@mx01-ewr:/proc/sys/kernel/random# cat entropy_avail 
128
root@mx01-ewr:/proc/sys/kernel/random# cat /dev/xvda >/dev/urandom  &
[1] 16187 # just using this as a source of data, you could do ssh hostIP 'cat /dev/random' >... etc
root@mx01-ewr:/proc/sys/kernel/random# cat entropy_avail 
1221
root@mx01-ewr:/proc/sys/kernel/random# cat entropy_avail 
1398

Bonus if you make the ssh command go through a router so it generates entropy *:)