Skip to content

Issues around including a PRNG #26

@colmmacc

Description

@colmmacc

Right now s2n uses /dev/urandom for all entropy, per the example of the excellent NaCL library, best summarized by Thomas Ptacek: http://sockpuppet.org/blog/2014/02/25/safely-generate-random-numbers/ .

The performance problem with urandom

The problem with using /dev/urandom though is that it is slow; at present it is the main (and really only) performance bottleneck in s2n. Reading from /dev/urandom involves kernel level locks and context switching. A quick benchmark shows that it's about a hundred times slower than using an in-process PRNG.

Will a PRNG work?

A modern PRNG should be safe to generate unpredictable and randomly distributed data once it has been seeded with about 256 bits of meaningful entropy, an in-process PRNG can be secure in that sense.

Unfortunately PRNGs are also inherently stateful and it is very difficult to guarantee that the internal state won't be replicated between processes. C99 does offer strong guarantees around thread local storage and it's relatively easy to ensure that two threads are seeded independently, but so far I've found no ironclad way to ensure that a fork() , or worse ... syscall(SYS_fork...) won't result in two processes having identically seeded PRNGs. This is particularly bad with TLS, because randomly-distributed data can sometimes be public (explicit IVs) and sometimes be very sensitive and private (PFS key generation).

One initially promising solution is to guard access to the PRNG with a getpid() call, and to detect changes in PID and reseed when needed. Unfortunately this also turns out not to be reliable: http://yarchive.net/comp/linux/getpid_caching.html libc can cache the PID value and get it wrong in some circumstances.

Why this matters

Since it's feasible that s2n will be used inside language runtimes (e.g. the JVM, Ruby, Python ..), it's not unrealistic to expect the calling application to call fork(), vfork() or even syscall(SYS_fork) , it's best to protect against this in a robust way.

Potential solutions

If getentropy()/getrandom() have better locking/performance semantics, using them may help, but these are not widely available. Another solution maybe to use the RDRAND instruction directly where available, but this comes with its own challenges. See also djb's write up at: http://blog.cr.yp.to/20140205-entropy.html.

Metadata

Metadata

Assignees

Labels

No labels
No labels

Type

No type

Projects

No projects

Milestone

No milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions