[grsec] new gcc plugin: latent entropy extraction

[PaX Team]

hello everyone,

it's time to introduce the newest member of our plugin family to you. the
inspiration came from the work described at https://factorable.net/ that
you should all check out eventually (and do get your keys tested).

the short story is that generating crypto keys while the system's random
pool is low on entropy is not a good idea. and it so happens that some
systems do actually have little entropy after boot when some userland
decides to generate said keys. the end result is not pretty, the details
are in the paper at the above URL.

now there are several ways to improve the situation, some will soon find
their way into the kernel in fact (check out the random tree by Theodore
Ts'o at http://git.kernel.org/?p=linux/kernel/git/tytso/random.git;a=summary).

the basic idea is always to find some potential source of randomness, or
even just deterministic diversity (e.g., a MAC address) and mix that into
the random pools in the hope that enough bits accumulate by the time some
early userland app decides to extract entropy from them.

this is where the new gcc plugin comes in: we can instrument the kernel's
boot code to do some hash-like computation and extract some entropy from
whatever program state we decide to mix into that computation. a similar
idea has in fact been implemented by Larry Highsmith of Subreption fame
in http://www.phrack.org/issues.html?issue=66&id=15 where he (manually)
instrumented the kernel's boot code to extract entropy from a few kernel
variables such as time (jiffies) and context switch counts.

the latent entropy plugin takes this extraction to a whole new level. first,
we define a new global variable that we mix into the kernel's entropy pools
on each initcall. second, each initcall function (and all other boot-only
functions they call) gets instrumented to compute a 'random' number that
gets mixed into this global variable at the end of the function (you can
think of it as an artificially created return value that each instrumented
function computes for our purposes). the computation is a mix of add/xor/rol
(the happy recovery Halvar mix :) with compile-time chosen random constants
and the sequence of these operations follows the instrumented functions's
control flow graph. for the rest of the gory details see the source code ;).

as for the results of this whole adventure: i tried an allnoconfig amd64
kernel in qemu and i still saw a few bits of entropy in the last computed
random function, so i'd like to believe that with real hardware around we
can perhaps generate entropy in useful amounts, but time (and some real
analysis by someone with more free time than me) will tell ;). there's also
some impact on the boot time that i didn't bother to measure because it's
probably in the noise, but feel free to post your numbers. there're also
many ways this code can be tweaked to change the tradeoff between entropy
extraction and boot time impact.

one last note for those who care about binary checksums, reproducibility and
the like: the injected code depends on the compiler version, optimization
switches, kernel config, target architecture, etc (anything that can affect
the control flow graph) and also on gcc's internal random seed generated for
each compilation unit. if you want some determinism in the generated binaries,
make use of -frandom-seed that the latent entropy plugin will honour as well
(or at least that was the intention). the other side of the coin is that even
if you keep all the above variables the same (minus the gcc seed), your kernel
images will still be different and produce a different random pool on boot.

tl;dr: go read the whole thing, there're no shortcuts ;P

cheers,
 PaX Team