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