[Cryptography] RFC possible changes for Linux random device

[Sandy Harris]

Jonathan Thornburg <jthorn at astro.indiana.edu> wrote:

> On Fri, Sep 12, 2014 at 07:18:58PM -0400, Sandy Harris wrote:
>> I have some experimental code to replace parts of random.c
> ...
>
> Without knowing the full set of design goals and the threat model,
> it's very difficult to evaluate the code.  That is, we don't know what
> you're trying to accomplish -- is your new code supposed to

> * be faster?

At least as fast. The newer code such as GCM is faster than
SHA-1 in TLS or IPsec authentication so there is hope this
might be faster, but that is not a critical goal.

> * to be stronger against cryptographic analysis of its output?

At least as strong. The goal is that the basic mixing be as
strong then extra things improve it. Adding the counter[],
mixing in process info in loop_urandom(), ...

> * provide high-quality randomness earlier in the boot sequence?

That is critically important and not a problem I claim to solve.

I do provide a mechanism to insert different random constants
for every version compiled. This is utterly useless in many
cases and only a minor complication for attacks against
others, but if you compile your own kernel for a firewall it
comes close to being a full solution.

More important, the GCM hash can be run over any data
so it provides a clean interface for mixing in various things
at boot time or before an output sequence.

Running it over volatile kernel data structures (process
list, page tables, ...) might provide extra entropy at boot
time or later. I do not know the kernel code well enough
to tell how useful this might be.

Running it over data expected to be different for each
machine (hardware info such as the structs for network
interfaces) can work like salt in a password hash; this
is not expected to contribute entropy but it makes some
attacks (particularly using tables to speed up brute force)
a great deal harder.

In loop_urandom() I suggest running it over the task
struct for the process that is reading the device.
>From the comments there:

    This depends on a different aspect of the
    system than anything else in the driver,
    namely the order in which user processes
    ask for data and the current state of those
    processes.

    Except on very simple embedded systems,
    this should be hard to guess. It should be
    impossible to monitor unless the attacker
    is logged into the system or has left a
    background process running on it. Even
    then, monitoring it would not be easy.

I also add a global counter[]; comments on that:

    There is only one counter[] and one count() function to
    update it. mix_last() calls that so the count is affected
    by all output operations on any pool. It is initialised
    randomly and only affects outputs indirectly. The counter
    value should therefore be quite difficult for an enemy to
    discover.

    mix_last() also mixes in the counter so it affects all
    output from any pool and all feedback into any pool.

    That is, this counter provides a way for operations on
    any pool to automatically influence both of the other
    pools, albeit in an indirect and rather limited way.

On a simple embedded system there might be few enough
processes that both the task struct stuff and counter[]
would be knowable or guessable, hence nearly useless.

On a relatively complex & busy system, though, either
of them alone might be enough to make outputs random
(though they are never used alone, always with pool data
mixed in too). The counter[] directly affects all outputs
and feedback into all pools and loop_urandom() updates
the other pools.

> * use less kernel memory?

Not a goal.

> * be more resistant to cache or timing attacks by malicious user code
>   running the local processor?
> * more resistant to cache or power-consumption side-channel attacks
>   mounted by an attacker with physical (but not software) access to
>   the local processor & memory?
> * be more resistant to timing attacks by attackers on the local network?

Not goals I considered.

There are papers on timing attacks on AES-GCM and on a variant
that resists them.
http://cr.yp.to/antiforgery/cachetiming-20050414.pdf
www.iacr.org/archive/ches2009/57470001/57470001.pdf

I have not yet done more than scan those papers. Clearly if this
were considered for real use, those would need to influence the
implementation.