Improving Random Seeds in Ubuntu 14.04 LTS Cloud Instances

Tomorrow, February 19, 2014, I will be giving a presentation to the Capital of Texas chapter of ISSA, which will be the first public presentation of a new security feature that has just landed in Ubuntu Trusty (14.04 LTS) in the last 2 weeks -- doing a better job of seeding the pseudo random number generator in Ubuntu cloud images.  You can view my slides here (PDF), or you can read on below.  Enjoy!

Q: Why should I care about randomness? 

A: Because entropy is important!

• Choosing hard-to-guess random keys provide the basis for all operating system security and privacy
• SSL keys
• SSH keys
• GPG keys
• /etc/shadow salts
• TCP sequence numbers
• UUIDs
• dm-crypt keys
• eCryptfs keys
• Entropy is how your computer creates hard-to-guess random keys, and that's essential to the security of all of the above

Q: Where does entropy come from?

A: Hardware, typically.

• Keyboards
• Mouses
• Interrupt requests
• HDD seek timing
• Network activity
• Microphones
• Web cams
• Touch interfaces
• WiFi/RF
• TPM chips
• RdRand
• Entropy Keys
• Pricey IBM crypto cards
• Expensive RSA cards
• USB lava lamps
• Geiger Counters
• Seismographs
• Light/temperature sensors
• And so on

Q: But what about virtual machines, in the cloud, where we have (almost) none of those things?

A: Pseudo random number generators are our only viable alternative.

• In Linux, /dev/random and /dev/urandom are interfaces to the kernel’s entropy pool
• Basically, endless streams of pseudo random bytes
• Some utilities and most programming languages implement their own PRNGs
• But they usually seed from /dev/random or /dev/urandom
• Sometimes, virtio-rng is available, for hosts to feed guests entropy
• But not always

Q: Are Linux PRNGs secure enough?

A: Yes, if they are properly seeded.

• See random(4)
• When a Linux system starts up without much operator interaction, the entropy pool may be in a fairly predictable state
• This reduces the actual amount of noise in the entropy pool below the estimate
• In order to counteract this effect, it helps to carry a random seed across shutdowns and boots
• See /etc/init.d/urandom

...
dd if=/dev/urandom of=$SAVEDFILE bs=$POOLBYTES count=1 >/dev/null 2>&1 

...

Q: And what exactly is a random seed?

A: Basically, its a small catalyst that primes the PRNG pump.

• Let’s pretend the digits of Pi are our random number generator
• The random seed would be a starting point, or “initialization vector”
• e.g. Pick a number between 1 and 20
• say, 18
• Now start reading random numbers

• Not bad...but if you always pick ‘18’...

XKCD on random numbers

RFC 1149.5 specifies 4 as the standard IEEE-vetted random number.

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 one another
• ie, The Cloud
• No keyboard or mouse
• IRQ based hardware is emulated
• Block devices are virtual and cached by hypervisor
• RTC is shared
• The initial random seed is sometimes part of the image, or otherwise chosen from a weak entropy pool

Dilbert on random numbers

Q: Surely you're just being paranoid about this, right?

A: I’m afraid not...

Analysis of the LRNG (2006)

• Little prior documentation on Linux’s random number generator
• Random bits are a limited resource
• Very little entropy in embedded environments
• OpenWRT was the case study
• OS start up consists of a sequence of routine, predictable processes
• Very little demonstrable entropy shortly after boot
• http://j.mp/McV2gT

Black Hat (2009)

• iSec Partners designed a simple algorithm to attack cloud instance SSH keys
• Picked up by Forbes
• http://j.mp/1hcJMPu

Factorable.net (2012)

• Minding Your P’s and Q’s: Detection of Widespread Weak Keys in Network Devices
• Comprehensive, Internet wide scan of public SSH host keys and TLS certificates
• Insecure or poorly seeded RNGs in widespread use
• 5.57% of TLS hosts and 9.60% of SSH hosts share public keys in a vulnerable manner
• They were able to remotely obtain the RSA private keys of 0.50% of TLS hosts and 0.03% of SSH hosts because their public keys shared nontrivial common factors due to poor randomness
• They were able to remotely obtain the DSA private keys for 1.03% of SSH hosts due to repeated signature non-randomness
• http://j.mp/1iPATZx

Dual_EC_DRBG Backdoor (2013)

• Dual Elliptic Curve Deterministic Random Bit Generator
• Ratified NIST, ANSI, and ISO standard
• Possible backdoor discovered in 2007
• Bruce Schneier noted that it was “rather obvious”
• Documents leaked by Snowden and published in the New York Times in September 2013 confirm that the NSA deliberately subverted the standard
• http://j.mp/1bJEjrB

Q: Ruh roh...so what can we do about it?

A: For starters, do a better job seeding our PRNGs.

• Securely
• With high quality, unpredictable data
• More sources are better
• As early as possible
• And certainly before generating
• SSH host keys
• SSL certificates
• Or any other critical system DNA
• /etc/init.d/urandom “carries” a random seed across reboots, and ensures that the Linux PRNGs are seeded

Q: But how do we ensure that in cloud guests?

A: Run Ubuntu!

Sorry, shameless plug...

Q: And what is Ubuntu's solution?

A: Meet pollinate.

• pollinate is a new security feature, that seeds the PRNG.
• Introduced in Ubuntu 14.04 LTS cloud images
• Upstart job
• It automatically seeds the Linux PRNG as early as possible, and before SSH keys are generated
• It’s GPLv3 free software
• Simple shell script wrapper around curl
• Fetches random seeds
• From 1 or more entropy servers in a pool
• Writes them into /dev/urandom
• https://launchpad.net/pollinate

Q: What about the back end?

A: Introducing pollen.

• pollen is an entropy-as-a-service implementation
• Works over HTTP and/or HTTPS
• Supports a challenge/response mechanism
• Provides 512 bit (64 byte) random seeds
• It’s AGPL free software
• Implemented in golang
• Less than 50 lines of code
• Fast, efficient, scalable
• Returns the (optional) challenge sha512sum
• And 64 bytes of entropy
• https://launchpad.net/pollen

Q: Golang, did you say?  That sounds cool!

A: Indeed. Around 50 lines of code, cool!

pollen.go

Q: Is there a public entropy service available?

A: Hello, entropy.ubuntu.com.

• Highly available pollen cluster
• TLS/SSL encryption
• Multiple physical servers
• Behind a reverse proxy
• Deployed and scaled with Juju
• Multiple sources of hardware entropy
• High network traffic is always stirring the pot
• AGPL, so source code always available
• Supported by Canonical
• Ubuntu 14.04 LTS cloud instances run pollinate once, at first boot, before generating SSH keys

Q: But what if I don't necessarily trust Canonical?

A: Then use a different entropy service :-)

• Deploy your own pollen
• bzr branch lp:pollen
• sudo apt-get install pollen
• juju deploy pollen
• Add your preferred server(s) to your $POOL
• In /etc/default/pollinate
• In your cloud-init user data
• In progress
• In fact, any URL works if you disable the challenge/response with pollinate -n|--no-challenge
• random.org
• news.google.com
• Or whatever site you like

Q: So does this increase the overall entropy on a system?

A: No, no, no, no, no!

• pollinate seeds your PRNG, securely and properly and as early as possible
• This improves the quality of all random numbers generated thereafter
• pollen provides random seeds over HTTP and/or HTTPS connections
• This information can be fed into your PRNG
• The Linux kernel maintains a very conservative estimate of the number of bits of entropy available, in /proc/sys/kernel/random/entropy_avail
• Note that neither pollen nor pollinate directly affect this quantity estimate!!!

Q: Why the challenge/response in the protocol?

A: Think of it like the Heisenberg Uncertainty Principle.

• The pollinate challenge (via an HTTP POST submission) affects the pollen's PRNG state machine
• pollinate can verify the response and ensure that the pollen server at least “did some work”
• From the perspective of the pollen server administrator, all communications are “stirring the pot”
• Numerous concurrent connections ensure a computationally complex and impossible to reproduce entropy state

Q: What if pollinate gets crappy or compromised or no random seeds?

A: Functionally, it’s no better or worse than it was without pollinate in the mix.

• In fact, you can `dd if=/dev/zero of=/dev/random` if you like, without harming your entropy quality
• All writes to the Linux PRNG are whitened with SHA1 and mixed into the entropy pool
• Of course it doesn’t help, but it doesn’t hurt either
• Your overall security is back to the same level it was when your cloud or virtual machine booted at an only slightly random initial state
• Note the permissions on /dev/*random
• crw-rw-rw- 1 root root 1, 8 Feb 10 15:50 /dev/random
• crw-rw-rw- 1 root root 1, 9 Feb 10 15:50 /dev/urandom
• It's a bummer of course, but there's no new compromise

Q: What about SSL compromises, or CA Man-in-the-Middle attacks?

A: We are mitigating that by bundling the public certificates in the client.

• The pollinate package ships the public certificate of entropy.ubuntu.com
• /etc/pollinate/entropy.ubuntu.com.pem
• And curl uses this certificate exclusively by default
• If this really is your concern (and perhaps it should be!)
• Add more URLs to the $POOL variable in /etc/default/pollinate
• Put one of those behind your firewall
• You simply need to ensure that at least one of those is outside of the control of your attackers

Q: What information gets logged by the pollen server?

A: The usual web server debug info.

• The current timestamp
• The incoming client IP/port
• At entropy.ubuntu.com, the client IP/port is actually filtered out by the load balancer
• The browser user-agent string
• Basically, the exact same information that Chrome/Firefox/Safari sends
• You can override if you like in /etc/default/pollinate
• The challenge/response, and the generated seed are never logged!

Feb 11 20:44:54 x230 2014-02-11T20:44:54-06:00 x230 pollen[28821] Server received challenge from [127.0.0.1:55440, pollinate/4.1-0ubuntu1 curl/7.32.0-1ubuntu1.3 Ubuntu/13.10 GNU/Linux/3.11.0-15-generic/x86_64] at [1392173094634146155]

Feb 11 20:44:54 x230 2014-02-11T20:44:54-06:00 x230 pollen[28821] Server sent response to [127.0.0.1:55440, pollinate/4.1-0ubuntu1 curl/7.32.0-1ubuntu1.3 Ubuntu/13.10 GNU/Linux/3.11.0-15-generic/x86_64] at [1392173094634191843]

Q: Have the code or design been audited?

A: Yes, but more feedback is welcome!

• All of the source is available
• Service design and hardware specs are available
• The Ubuntu Security team has reviewed the design and implementation
• All feedback has been incorporated
• At least 3 different Linux security experts outside of Canonical have reviewed the design and/or implementation
• All feedback has been incorporated

Q: Where can I find more information?

A: Read Up!

• Ubuntu Security
• https://wiki.ubuntu.com/Security/Features
• Browse code and file bugs
• https://launchpad.net/pollen
• https://launchpad.net/pollinate
• Documentation
• http://manpg.es/pollinate.1
• http://manpg.es/pollen.8

Stay safe out there!
:-Dustin

Seed /dev/urandom through Metadata (EC2, OpenStack, Eucalyptus)

If you attended my talk about Entropy at the OpenStack Summit in San Diego earlier this month, or you read my post and slides here on my blog, you noticed that I had a few suggestions as to how we might improve entropy in Linux cloud instances and virtual machines.

There's one very easy approach that you can handle entirely on your end, when launching an instance, if you use Ubuntu's cloud-init utility, which consumes the user-data field from the metadata service.

You simply need to use ec2-run-instances or euca-run-instances with the --user-data-file option.

Cloud-init supports a directive called write_files.  Here, you can specify a path, ownerships, permissions, encoding, and content of a given file, which cloud-init will write a boot time.  Leveraging, this, you can simply "create" (actually, just append to) the psuedo random device that the Linux kernel provides at /dev/urandom, with is owned by root:root and permissioned rw-rw-rw-.  The stanza should look like this:

write_files:
-   encoding: b64
    content: $SEED
    owner: root:root
    path: /dev/urandom
    perms: '0666'

Now, you'll need to generate this using a script on your end, and populate the $SEED variable.  To do that, simply use this on your host system where you launch your cloud instance:

SEED="$(head -c 512 /dev/urandom | base64 -w 0)"

This command will read 512 bytes from your locale system's /dev/urandom and base64 encode it without wrapping lines.  You could, alternatively, read from your local system's /dev/random if you have enough time and entropy.

Using the recipe above, you can ensure that your instance has at least some bit (actually, 4096 bits) of randomness that was collected outside of your cloud provider's environment.

I'm representing Gazzang this week at the Ubuntu Developer Summit this week in Copenhagen, Denmark pushing for better security, entropy, and key management inside of Ubuntu's cloud images.

Cheers,
:-Dustin