[gnutls-devel] lock-free random generator

classic Classic list List threaded Threaded
7 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

[gnutls-devel] lock-free random generator

Nikos Mavrogiannopoulos-2
Hi,
 One of the items that have been on my todo-list after discussing with
application writers of multi-threaded applications (mainly servers),
is addressing the issue of synchronization for the random generator.
Currently gnutls provides a "central" random generator based on yarrow
(for keys) and salsa20 (for nonces) primitives, and it is thread safe
by utilizing mutexes over it. An application that has more than
100-200 threads is most likely to spend more time in synchronization
rather than the random generator itself. A solution to that would be
to provide a thread-local random generator which will work lock-free,
at the cost of additional memory per-thread -around 600-700 bytes for
the current generator-.

I have an experimental patch set, implementing this idea at:
https://gitlab.com/gnutls/gnutls/merge_requests/259

On the patch above, the additional cost per thread will only be for
threads actually utilizing gnutls, and in particular the random
generator, as the required memory will be allocated after the first
call to gnutls_rnd() by the thread.

Are there any objections on such an enhancement to gnutls, or
suggestions on how such a lock-free random generator could be improved
(in terms of memory utilization for example)?

regards,
Nikos

_______________________________________________
Gnutls-devel mailing list
[hidden email]
http://lists.gnupg.org/mailman/listinfo/gnutls-devel
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [gnutls-devel] lock-free random generator

Niels Möller-2
Nikos Mavrogiannopoulos <[hidden email]> writes:

> Currently gnutls provides a "central" random generator based on yarrow
> (for keys) and salsa20 (for nonces) primitives, and it is thread safe
> by utilizing mutexes over it. An application that has more than
> 100-200 threads is most likely to spend more time in synchronization
> rather than the random generator itself. A solution to that would be
> to provide a thread-local random generator which will work lock-free,
> at the cost of additional memory per-thread -around 600-700 bytes for
> the current generator-.

Would it make sense to handle the two cases differently, with a
thread-local nonce-generator, but stick to a global key-generator
protected by a mutex?

I imagine there are a lot more calls for nonces than for keys?

For the yarrow reseed logic, I think it may be preferable with a global
instance.

Regards,
/Niels

--
Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677.
Internet email is subject to wholesale government surveillance.

_______________________________________________
Gnutls-devel mailing list
[hidden email]
http://lists.gnupg.org/mailman/listinfo/gnutls-devel
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [gnutls-devel] lock-free random generator

Nikos Mavrogiannopoulos-2
On Sun, Feb 19, 2017 at 7:17 PM, Niels Möller <[hidden email]> wrote:

>> Currently gnutls provides a "central" random generator based on yarrow
>> (for keys) and salsa20 (for nonces) primitives, and it is thread safe
>> by utilizing mutexes over it. An application that has more than
>> 100-200 threads is most likely to spend more time in synchronization
>> rather than the random generator itself. A solution to that would be
>> to provide a thread-local random generator which will work lock-free,
>> at the cost of additional memory per-thread -around 600-700 bytes for
>> the current generator-.
>
> Would it make sense to handle the two cases differently, with a
> thread-local nonce-generator, but stick to a global key-generator
> protected by a mutex?
>
> I imagine there are a lot more calls for nonces than for keys?

Certainly. Currently, there is at least a single call for key
generation on each established TLS session, meaning that the
bottleneck will remain, for the case where multiple threads are used
to host multiple sessions - it will be reduced to a single place
however -.

> For the yarrow reseed logic, I think it may be preferable with a global instance.

If we need yarrow, your recommendation seems to be the right approach.
However, another thought it has been bugging me lately, is whether we
need yarrow in gnutls. It looks quite suited for something central
like /dev/urandom which has several maybe untrusted inputs, but for
gnutls which seeds from /dev/urandom (or the equivalent system calls),
having a PRNG which concerns itself with manipulation of input may not
be adding the security it is perceived to add.

regards,
Nikos

_______________________________________________
Gnutls-devel mailing list
[hidden email]
http://lists.gnupg.org/mailman/listinfo/gnutls-devel
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [gnutls-devel] lock-free random generator

Nikos Mavrogiannopoulos-2
On Mon, Feb 20, 2017 at 8:14 AM, Nikos Mavrogiannopoulos
<[hidden email]> wrote:

>> For the yarrow reseed logic, I think it may be preferable with a global instance.
> If we need yarrow, your recommendation seems to be the right approach.
> However, another thought it has been bugging me lately, is whether we
> need yarrow in gnutls. It looks quite suited for something central
> like /dev/urandom which has several maybe untrusted inputs, but for
> gnutls which seeds from /dev/urandom (or the equivalent system calls),
> having a PRNG which concerns itself with manipulation of input may not
> be adding the security it is perceived to add.

And to answer myself, I do not think we need something complex as
yarrow in gnutls. Older systems may have needed it, but today we can
rely on /dev/urandom and getentropy() interfaces, and as such I no
longer it is necessary to bring that complexity to gnutls.

I've redesigned the whole random generator and provided a high level
description at:
https://gitlab.com/gnutls/gnutls/blob/c6a01ff6c5a44a19b5f6dba9280da96cc28f92d8/doc/cha-crypto.texi#L111

The corresponding code is at:
https://gitlab.com/gnutls/gnutls/merge_requests/259

regards,
Nikos

_______________________________________________
Gnutls-devel mailing list
[hidden email]
http://lists.gnupg.org/mailman/listinfo/gnutls-devel
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [gnutls-devel] lock-free random generator

Niels Möller-2
Nikos Mavrogiannopoulos <[hidden email]> writes:

> And to answer myself, I do not think we need something complex as
> yarrow in gnutls. Older systems may have needed it, but today we can
> rely on /dev/urandom and getentropy() interfaces, and as such I no
> longer it is necessary to bring that complexity to gnutls.

Makes sense to me too. But do you plan any fallback for other systems? I
guess one could require the use of some separate randomness gathering
daemon.

What about MacOS and Microsoft Windows, do they have something
comparable to /dev/random these days?

Then I'd expect that there are quite some systems out there, where
getting adequate randomness isn't easy. Like small embedded systems, and
it's also unclear to me how /dev/random works on virtual machines. But
just using a mixer like yarrow or fortuna isn't enough, since the tricky
problem is the sourcing of the mixer.

Regards,
/Niels

--
Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677.
Internet email is subject to wholesale government surveillance.

_______________________________________________
Gnutls-devel mailing list
[hidden email]
http://lists.gnupg.org/mailman/listinfo/gnutls-devel
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [gnutls-devel] lock-free random generator

Nikos Mavrogiannopoulos-2
On Tue, Feb 28, 2017 at 7:57 AM, Niels Möller <[hidden email]> wrote:

> Nikos Mavrogiannopoulos <[hidden email]> writes:
>
>> And to answer myself, I do not think we need something complex as
>> yarrow in gnutls. Older systems may have needed it, but today we can
>> rely on /dev/urandom and getentropy() interfaces, and as such I no
>> longer it is necessary to bring that complexity to gnutls.
>
> Makes sense to me too. But do you plan any fallback for other systems? I
> guess one could require the use of some separate randomness gathering
> daemon.

No. Few releases ago I've dropped support for EGD (entropy gathering
daemon). No-one has complained so I guess such special systems most
likely use specialized libraries rather than "OS" libraries like
gnutls.

> What about MacOS and Microsoft Windows, do they have something
> comparable to /dev/random these days?

Both are supported via their native interfaces. Newer versions of
MacOS have getentropy() and older ones have /dev/urandom. Windows has
CryptGenRandom() for quite some time.

> Then I'd expect that there are quite some systems out there, where
> getting adequate randomness isn't easy. Like small embedded systems, and
> it's also unclear to me how /dev/random works on virtual machines. But
> just using a mixer like yarrow or fortuna isn't enough, since the tricky
> problem is the sourcing of the mixer.

In such small systems, even something like the (now-legacy) EGD would
be insufficient. Each of them would require some custom code, which
could be abstracted as a system call like getentropy() - especially if
that gets into posix. I don't think it makes sense to add code for
such systems without ensuring that it handles a large class of it, or
that at least it is a very common system to ignore.

regards,
Nikos

_______________________________________________
Gnutls-devel mailing list
[hidden email]
http://lists.gnupg.org/mailman/listinfo/gnutls-devel
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [gnutls-devel] lock-free random generator

Nikos Mavrogiannopoulos-2
In reply to this post by Nikos Mavrogiannopoulos-2
On Mon, Feb 27, 2017 at 12:00 PM, Nikos Mavrogiannopoulos
<[hidden email]> wrote:

> On Mon, Feb 20, 2017 at 8:14 AM, Nikos Mavrogiannopoulos
> <[hidden email]> wrote:
>
>>> For the yarrow reseed logic, I think it may be preferable with a global instance.
>> If we need yarrow, your recommendation seems to be the right approach.
>> However, another thought it has been bugging me lately, is whether we
>> need yarrow in gnutls. It looks quite suited for something central
>> like /dev/urandom which has several maybe untrusted inputs, but for
>> gnutls which seeds from /dev/urandom (or the equivalent system calls),
>> having a PRNG which concerns itself with manipulation of input may not
>> be adding the security it is perceived to add.
>
> And to answer myself, I do not think we need something complex as
> yarrow in gnutls. Older systems may have needed it, but today we can
> rely on /dev/urandom and getentropy() interfaces, and as such I no
> longer it is necessary to bring that complexity to gnutls.
>
> I've redesigned the whole random generator and provided a high level
> description at:
> https://gitlab.com/gnutls/gnutls/blob/c6a01ff6c5a44a19b5f6dba9280da96cc28f92d8/doc/cha-crypto.texi#L111
>
> The corresponding code is at:
> https://gitlab.com/gnutls/gnutls/merge_requests/259

It is now merged in master [0]. In the process the gnutls PRNG got
even more simplified and improved.

regards,
Nikos


[0]. https://gitlab.com/gnutls/gnutls/merge_requests/259/diffs#20cb879c7f2aafd5e7d471c7fbb46f640f4a0149_519_524

_______________________________________________
Gnutls-devel mailing list
[hidden email]
http://lists.gnupg.org/mailman/listinfo/gnutls-devel
Loading...