"(The) use of peer-reviewed cryptographic pseudo-random-number generators (PRNGs) designed to tolerate compromised entropy sources is exactly the right thing to do," McKusick told iTWire in response to comments by the OpenBSD founder Theo de Raadt that FreeBSD was playing catch up.
De Raadt made the comments when asked about reports that FreeBSD would reduce the role of random number generators which are built into processors from Intel and Via, over suspicions that these methods may have been compromised by the National Security Agency.
In a detailed response, McKusick (pictured above) gave an exhaustive summary of the status of FreeBSD with regard to cryptography, based on his discussions with the people doing the work. "As you can see it is neither a simple nor a solved problem," he commented.
|
He said a key feature of FreeBSD's /dev/random was its use of Yarrow, a PRNG first described by Kelsey, Schneier, and Ferguson in a peer-reviewed 1999 article.
"A key design goal in Yarrow was to re-use existing cryptographic primitives such as cryptographic hashes and counter-mode block encryption, rather than to create new ones or try to cut corners," McKusick said. "This choice comes at some computational expense, but gives far greater confidence in the algorithm. Yarrow has since been adopted in several systems including FreeBSD and Mac OS X (though not the same implementations). Yarrow is one of the few published schemes to have seen wide review and discussion."
He said Yarrow consisted of three significant operational parts: an entropy accumulator based on a cryptographic hash (collects entropy), a re-seed mechanism by which entropy was converted into keying material, and a generation mechanism, which used a counter-mode encryption function to generate a pseudo-random sequence.
"SHA1 and 3DES were specified, but these days FreeBSD chooses to use SHA256 and AES," he said. "Mark's implementation allows these to be configured. In addition to the three elements of Yarrow, significant fourth and fifth elements in the FreeBSD implementation are a flexible framework for entropy acquisition from various types of sources (e.g., interrupt timing), and /dev/random itself. It's all a lot more complicated than this simplified description - see the Yarrow paper and Mark's own paper on the topic."
McKusick said Fortuna was a successor algorithm designed by Ferguson and Schneier to address perceived shortcomings in Yarrow: in particular, how and when to distribute entropy from different sources into the PRNG, rather than requiring estimation of entropy - the most criticised aspect of Yarrow.
"Fortuna takes the same approach done in Yarrow of reusing known cryptographic primitives (albeit differently), updated for a more contemporary set of algorithms. Mark is currently implementing Fortuna with the intent of shipping it in FreeBSD 11.0, possibly with a merge to 10.x when it is perceived as ready," he said.
He pointed out that many contemporary CPUs implemented built-in hardware random number generators. "FreeBSD first began to support the VIA generator in FreeBSD 5.3, and support for Intel's rdrand appeared in FreeBSD 9.2," he said. "Somewhere in all the silicon are loops of oscillators or other cute tricks that generate difficult-to-predict output. This is normally 'whitened' by applying a cryptographic hash or encryption in order to distribute what may be a biased random source across a stream of bits equally. Hardware vendors put significant resources into the design of their RNGs as a result of customers who feel strongly that good randomness is required."
McKusick said one downside to whitening of hardware sources, which often occurred in hardware as well, was that it was hard to tell if something had gone wrong with the underlying hardware source. "And things do go wrong: for example, oscillator loops may start just returning 0 because they are feeling a bit moody. Or your chip layout optimiser may remove the random source entirely because, it reasons, the non-deterministic bit of your design is silly anyway, and can be treated as a 'don't care' in optimisation. Both of these have been known to happen. Ideally the low-level hardware source is exposed directly to software so that it can be monitored for nasty edge cases, but this is rarely done."
He said there had been significant debate in the FreeBSD community (and others) about whether and how to blend in-CPU and other hardware random number generators with more conventional entropy collection. "Lately, more weight has been swinging towards feeding hardware sources into entropy input channels, but it's important to remember that when FreeBSD's /dev/random was implemented a decade ago, these randomness sources were only available on low-end VIA CPUs targeted at embedded environments," he said. "Frequently, these CPUs did not have the capacity to run Yarrow efficiently.
"An observation about performance from recent experience: Yarrow currently takes up about 15 per cent of the CPU time on a current low-end embedded CPU. Yarrow is not cheap in its current form, and this was a good motivation to use the cheaper (and possibly stronger) on-CPU mechanisms at the time. Reliable entropy is hard to find, especially early in the boot, and a CPU source is a feature, not a bug."
McKusick said the design choice made in FreeBSD up until FreeBSD 10.0 was that one used a hardware source *or* Yarrow with various entropy sources. "Specifically, FreeBSD 9.2 shipped using 'rdrand' support enabled by default. If you have an Intel CPU supporting this feature, Yarrow will not be used for /dev/random: all randomness comes straight from the CPU's built-in random number generator. As of 10.0, Yarrow is used with hardware sources, and additional entropy for other sources is mixed in. This works quite well: Yarrow is specifically designed to resist attacks by attackers who have compromised one of your entropy sources, as long as there remain other viable sources."
He said as far as he had seen, there was nothing more than media innuendo to suggest that RNGs shipped in off-the-shelf CPUs had been trojaned by NSA, GCHQ, or anyone else. "The worst compromise seen in the wild is the mandating of Dual Elliptic Curve RNG as one of the FIPS PRNG algorithms of choice," he said. "There is significant distrust in this algorithm as it is believed to be kleptographic, and the Snowden revelations lend credence to this allegation. The hardware RNG devices are generally documented as being sufficient to use directly for cryptographic purposes - although some of the past bugs here give us pause."
McKusick said that in any case, it was good engineering practice to blend additional entropy sources in, "and if you're going to do that, Yarrow and Fortuna are good ways to do it. In fact, given the possibility of the on-CPU sources actually being very good, you would be negligent not to mix them in (in a moderated way) using a strong cryptographic RNG - they may be much better than conventional sources, such as TSC-timed interrupt events."
He said that at the time Yarrow was introduced, it was a very expensive algorithm unsuitably for use on the single low-end embedded VIA platform that supported a hardware RNG, making the choice not to put it through Yarrow reasonable.
"With introduction of rdrand on higher-end CPUs, it would have been desirable to make a different choice: feed it through Yarrow along with other sources of entropy. That choice was already made in the FreeBSD 10.0 release cycle. And given recent events, Mark is merging the 10.0 changes to FreeBSD 9.2 to make rdrand pipe through Yarrow," he pointed out.
McKusick pointed out the changes in FreeBSD 10.0 followed on the footsteps of discussions at the 2013 Cambridge and Malta developer summits. "It also comes amidst significant work going on to improve abstractions and performance in /dev/random, and to introduce support for Fortuna. All of this significantly predated Theo's recent comments - and actually, Snowden.
"Mark has been discussing and working on these improvements for several years. Other security-minded FreeBSD developers who are involved in the discussions and implementation include Robert Watson, Brooks Davis and David Chisnall, who have been assisted by their colleagues at the University of Cambridge, Markus Kuhn and Steven Murdoch, who are mathematicians specialising in cryptography. They are collectively reviewing the cryptographic choices, high-level architecture, and implementation choices in FreeBSD's /dev/random. While these discussions were originally motivated by a desire to figure out the right trade-offs in the Fortuna implementation, it rapidly broadened to a more general discussion of the operational concerns for /dev/random in FreeBSD - boot-time integration, interrupt latency, good sources of entropy in the base system, adaptations to Fortuna to improve performance and OS-friendliness, application expectations, etc."
Summing up, McKusick said FreeBSD remained committed to staying on the leading edge of cryptographic engineering, and had a good agenda for further improvement of the design and implementation of /dev/random in the future, namely work being done in collaboration with reputable cryptographers and based on peer-reviewed research.
"It is likely that the work done by Mark and others on /dev/random will itself be subject to academic peer review, and make a significant contribution to the state of the art in cryptography engineering," he added.
