Generating randomness in userspace

classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

Generating randomness in userspace

Vegard Nossum
Hi,

I've written a small program that gathers randomness from the
uncertainty of scheduling between threads/cores in a multithreaded
program/system. The purpose of this is to generate random numbers
entirely in userspace (in case the /dev/random traffic is somehow
being watched, etc.). Attackers could still get their hands on the
random numbers, but I'm guessing it would be a lot more work than
simply tapping into the kernel/userspace interfaces -- they would have
to peek into the address space of the process generating the numbers.

One way to use this may be to seed a PRNG which runs in parallel with
e.g. /dev/random; XORing them together should yield a bitstream with
quality at least as good as the best of them, and will make it more
difficult to predict the output simply having access to the kernel's
secret state (or the numbers generated by it).

Is this interesting for the OpenSSL project? Or do you have something
like this already? (I could only find the use of certain things like
the current time, pid, uid, etc., which I think an attacker would have
much easier access to.) Or is it not really a concern in the first
place?

I attached my code -- it is not rigorous, but I think I avoided the
worst pitfalls. I'm not sure what kind of entropy/quality the output
has, but it should be better than nothing at all.

$ g++ seed.cc -lpthread -lssl -lcrypto && ./a.out
b41c91f348638116
a165d0fac8b2304e
282d0d24311d7511
[...]

The code works only on x86_64, and probably also only on Linux.


Vegard

seed.cc (3K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Generating randomness in userspace

Stanislav Meduna
On 11.08.2011 21:33, Vegard Nossum wrote:

> I've written a small program that gathers randomness from the
> uncertainty of scheduling between threads/cores in a multithreaded
> program/system.

Hmm my gut feeling is that this is not random enough that it matters.
The OS schedulers are actually quite predictable, more cores is
not necessarily better (it is more probable to immediately find
an idle one) and the quality varies with load type, thread
priorities etc.

With some load scenarios I'd be not surprised to see the results
only come from a set of a few thousands values the majority
of the time.

Regards
--
                               Stano
______________________________________________________________________
OpenSSL Project                                 http://www.openssl.org
Development Mailing List                       [hidden email]
Automated List Manager                           [hidden email]
Reply | Threaded
Open this post in threaded view
|

Re: Generating randomness in userspace

Kyle Hamilton
In reply to this post by Vegard Nossum
See also http://egd.sourceforge.net/ (Entropy Gathering Daemon, written in perl)

-Kyle H

On Thu, Aug 11, 2011 at 12:33 PM, Vegard Nossum <[hidden email]> wrote:

> Hi,
>
> I've written a small program that gathers randomness from the
> uncertainty of scheduling between threads/cores in a multithreaded
> program/system. The purpose of this is to generate random numbers
> entirely in userspace (in case the /dev/random traffic is somehow
> being watched, etc.). Attackers could still get their hands on the
> random numbers, but I'm guessing it would be a lot more work than
> simply tapping into the kernel/userspace interfaces -- they would have
> to peek into the address space of the process generating the numbers.
>
> One way to use this may be to seed a PRNG which runs in parallel with
> e.g. /dev/random; XORing them together should yield a bitstream with
> quality at least as good as the best of them, and will make it more
> difficult to predict the output simply having access to the kernel's
> secret state (or the numbers generated by it).
>
> Is this interesting for the OpenSSL project? Or do you have something
> like this already? (I could only find the use of certain things like
> the current time, pid, uid, etc., which I think an attacker would have
> much easier access to.) Or is it not really a concern in the first
> place?
>
> I attached my code -- it is not rigorous, but I think I avoided the
> worst pitfalls. I'm not sure what kind of entropy/quality the output
> has, but it should be better than nothing at all.
>
> $ g++ seed.cc -lpthread -lssl -lcrypto && ./a.out
> b41c91f348638116
> a165d0fac8b2304e
> 282d0d24311d7511
> [...]
>
> The code works only on x86_64, and probably also only on Linux.
>
>
> Vegard
>


Verify This Message with Penango.p7s (5K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Generating randomness in userspace

Stanislav Meduna
On 13.08.2011 10:09, Kyle Hamilton wrote:

> See also http://egd.sourceforge.net/ (Entropy Gathering Daemon, written
> in perl)

EGD is meant for systems where the /dev/random is not
present/accessible.

Assuming the /dev/random takes the entropy from all sources
affecting the scheduling of processes such userspace solutions
simply can't return more entropy and using them only generates
a false sense of added security (by obscurity).

Trust your /dev/random and if there are possible attacks on it,
thwart them directly. If you think there is an entropy source
the /dev/random does not use, implement it and submit a patch
to your kernel maintainer. If this is not enough, use a hardware
source of randomness.

Regards
--
                                        Stano
______________________________________________________________________
OpenSSL Project                                 http://www.openssl.org
Development Mailing List                       [hidden email]
Automated List Manager                           [hidden email]
Reply | Threaded
Open this post in threaded view
|

RE: Generating randomness in userspace

Green, Paul
In reply to this post by Vegard Nossum
Vegard Nossum wrote:

> I've written a small program that gathers randomness from the uncertainty of scheduling between threads/cores in a multithreaded program/system.

Welcome to the challenge of generating pseudo-random data correctly, efficiently, quickly, and securely. This is not an easy task. As someone that has worked in this area, allow me to offer a few comments on your approach. I recently devoted a month to this problem and submitted test programs and a patch for the OpenVOS PRNG that is in OpenSSL. Please see RT #2563, which is still awaiting processing by the OpenSSL team. In that request tracker entry, I provide a comprehensive test program for running experiments on obtaining pseudo-random data from the real-time clock. I was able to obtain high-quality pseudo-random data on all hardware platforms used by Stratus OpenVOS customers.

Scheduling algorithms vary from one operating system to the next and often have tweakable parameters that a system administrator can modify to adjust the tradeoff between responsiveness and efficiency. For an open-source package like OpenSSL that must run correctly on a wide variety of operating systems and hardware platforms, these factors alone would make qualifying (testing to the point of attaining confidence) your code quite a challenge.

Your code creates pthreads. I suspect that creating one or more threads is a relatively expensive operation on many operating systems, both in terms of time and in terms of memory. This fact alone would make your approach unsuitable for many applications. (As I recall, the entropy-gathering daemon referenced by Kyle Hamilton stays logged-in so that it can be used by multiple clients, to avoid the overhead of starting up and shutting down).

> The purpose of this is to generate random numbers entirely in userspace (in case the /dev/random traffic is somehow being watched, etc.). Attackers could still get their hands on the random numbers, but I'm guessing it would be a lot more work than simply tapping into the kernel/userspace interfaces -- they would have to peek into the address space of the process generating the numbers.

I'm not sure that I fully understand your concern.  Are you worried that an attacker who is able to execute code on the same hardware platform as OpenSSL can somehow snoop on the data stream that OpenSSL obtains from /dev/random?  If so, then such a scenario implies a very serious security issue for the operating system maintainers. I'm sure that they would take steps to address it if you could prove your assertion.

> One way to use this may be to seed a PRNG which runs in parallel with e.g. /dev/random; XORing them together should yield a bitstream with quality at least as good as the best of them, and will make it more difficult to predict the output simply having access to the kernel's secret state (or the numbers generated by it).

If an unprivileged user-space program has access to the secret internal state of the PRNG, that's a major security issue, and I'm sure that any operating system maintainer would fix the problem as quickly as possible.  Also, I do not believe that XORing two pseudo-random streams of data necessarily increases the entropy of the data. At any rate, you can easily compute the entropy of a stream of data by downloading John Walker's "ent.c" source program from http://www.fourmilab.ch/random.

See Knuth's "The Art of Computer Programming, Volume 2", for a general discussion of generating statistically-correct pseudo-random data using an algorithm.  See Chapter 9 of "Cryptography Engineering" by Niels Ferguson, Bruce Schneier and Tadayoshi Kohno for an excellent discussion of the challenge of generating cryptographic-quality pseudo-random data.

Thanks
PG
--
Sr. Technical Consultant, Stratus Technologies Inc.
Work: +1-978-461-7557; FAX: +1-978-461-3610; Twitter: stratuspaulg


:��I"Ϯ��r�m���� (���Z+�7�zZ)���1���x ��h���W^��^��%����&jם.+-1�ځ��j:+v�������h�