Debian’s Predictable PRNG and Cloud Computing

As the details of the Debian OpenSSL weak PRNG vulnerability came to light, I saw HD Moore’s Debian OpenSSL Predictable PRNG Toys and wondered how quickly I could generate the same for SSL certificates.  I had also been itching to take Amazon Web Services out for a spin, so it seemed like the perfect opportunity to do so.

Amazon Web Services is best described as a “cloud computing platform.”  Like competitors such as Google’s AppEngine, the main idea is that your application runs in an off-site hosted virtual environment.  Unlike Google’s AppEngine where the application developer must develop to Google’s Python APIs, Amazon’s services are based on language neutral Web APIs and hosted applications run within Xen virtual machine instances.  With Amazon Web Services, you get

  • Elastic Compute Cloud (EC2) – Dynamically launched Xen images with 1 32-bit core, 2 64-bit cores, and 4 64-bit core virtual machines.
  • Simple Storage Service (S3) – Remote storage of unlimited objects up to 5GB allowing download over HTTP and BitTorrent.
  • Simple Queue Service (SQS) – Reliable remote queued messaging.
  • SimpleDB (SDB) – A minimal database for storing structured data and supporting a SQL-like query language.

I used an SQS queue to distribute key generation tasks, 20 EC2 worker instances to generate keys, and an S3 bucket to store the generated keys.  As a simple benchmark, generating all 1310721 possible 1024-bit RSA keys on a 32-bit little endian system took somewhere around 45 minutes.

The design of my system was simple. My local workstation at home would be the controller that divides up the keyspace and populates the SQS work queue with messages indicating the units of work that need to be performed, launches EC2 instances as needed, and monitors the status of running instances. Each EC2 worker job would pull units of work off of the queue until it was empty, store the results in S3, and then shut the virtual machine down once it finished.

EC2 lets you launch pre-configured virtual machine images and, as one may expect, they had a number of Debian-based images with the weak OpenSSL PRNG already. I scripted up a key generating worker job based on HD’s getpid() faker and tested my code on a local VM running an Ubuntu LiveCD and a single EC2 instance. I spent a few hours building ad-hoc scripts using RightScale’s AWS Ruby Gems to push, run, and monitor jobs on EC2.  I launched 20 instances (the default quota) and finally went to sleep for the night.

In the morning, I had all of the 1024, 2048, and 4096-bit keys generated for the default public exponent of 65537 generated.  It turns out that 4096-bit keys are very rare2, so you only really need the 1024 and 2048-bit keys.

So, in summary:

  • 20 EC2 instances generating Debian weak RSA keys: $16
  • A few thousand SQS operations: $ 0.06
  • Transfers between EC2 and S3: $ 0.00
  • Downloading 500 MBs of compressed RSA keys from EC2: < $ 0.01
  • Having your RSA private key: Priceless.


1. 32768 PIDs * 2 different public exponents * whether ~/.rnd exists

2. Lee, Homin K., et al. “Cryptographic Strength of SSL/TLS Servers:
Current and Recent Practices.”
ACM Internet Measurement Conference, October 2007.


  1. Very nice. What was the actual time to completion once you had the EC2 instances all up, running, and generating keys?

  2. Dino Dai Zovi says:

    @Zach Generating all 262,144 1024-bit and 2048-bit keys on 20 small (32-bit) took 4 hours ($0.10 * 20 * 4 = $8), generating the same set for 64-bit on 20 large (64-bit) instances took 2 hours ($.20 * 20 * 2 = $8).

  3. Very neat… So where can download I the keys?🙂

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Get every new post delivered to your Inbox.

Join 5,896 other followers

%d bloggers like this: