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
- 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.
- Interrupt requests
- HDD seek timing
- Network activity
- Web cams
- Touch interfaces
- TPM chips
- Entropy Keys
- Pricey IBM crypto cards
- Expensive RSA cards
- USB lava lamps
- Geiger Counters
- 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
Black Hat (2009)
- iSec Partners designed a simple algorithm to attack cloud instance SSH keys
- Picked up by Forbes
- 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
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
Q: Ruh roh...so what can we do about it?
A: For starters, do a better job seeding our PRNGs.
- 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
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
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
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
- 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 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 
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
- Browse code and file bugs
Stay safe out there!