On the content itself, it sounds like if you're not targeting a specific service, you could code this up and launch a few hundred c1.xlarge spot instances (larger instances => fewer neighbors) and just collect keys. Or am I totally underestimating the amount of manual work required post-processing?
On an unrelated note, isn't the attack described in the paper not a timing attack because it gets the information by reading the cache instead of reading the clock?
What I'm curious about is if it would be possible to use a network of participating VMs on a public cloud to pass around messages untraceably from one party to another. Should certainly be easier to execute than the attack scenario they studied.
The following paper by the same authors, from a few months later, appears to be the published-paper version of that research, though, which is probably more useful: http://pages.cs.wisc.edu/~rist/papers/cloudsec.html