Sufficiently safe random information for security-critical Guile applications

Sufficiently safe random information for security-critical Guile applications

[Christopher Allan Webber]

Hello!  So, as some of you know, I'm working on a federation
implementation in Guile.  This needs a few things:

 - Random tokens which won't collide, for various purposes
 - The ability to generate a solid random key, which is used for...
 - The ability to generate an HMAC (for signed cooke based sessions)

To start out with, I've wondered how reliable Guile's RNG is.  From the
Guile docs:

 -- Scheme Procedure: random-state-from-platform
 -- C Function: scm_random_state_from_platform ()
     Construct a new random state seeded from a platform-specific source
     of entropy, appropriate for use in non-security-critical
     applications.  Currently ‘/dev/urandom’ is tried first, or else the
     seed is based on the time, date, process ID, an address from a
     freshly allocated heap cell, an address from the local stack frame,
     and a high-resolution timer if available.

Well okay, if I could be sure that an application is using urandom, then
it seems fine, but that doesn't seem clear.  But here's a question: even
if urandom is used for the initial seed, will that be enough?  Depending
on your RNG, you might be likely to see repeats.  See this horror story:

  https://medium.com/@betable/tifu-by-using-math-random-f1c308c4fd9d#.lybr6y64d

Is Guile's RNG ever good enough for a security sensitive application,
even if a reliably random and secure initial seed is provided?  Or
should we only trust it for things like games?

As for what I'm doing, I've figured, I have libgcrypt, which I'm using
for the HMAC, and so for the random tokens, I could use libgcrypt, which
is probably good-enough.  But getting tokens via gcrypt, while not super
slow, isn't really super fast.

So here's some code I have, GPLv3 or later, yadda yadda:

==================================================
(use-modules (system foreign)
             (rnrs bytevectors)
             (guix gcrypt)
             (guix base64))

(define %gcry-weak-random 0)
(define %gcry-strong-random 1)
(define %gcry-very-strong-random 2)

(define* (gen-random-bv #:optional (bv-length 50)
                        (level %gcry-strong-random))
  (let* ((ptr (libgcrypt-func "gcry_randomize"))
         (proc (pointer->procedure void ptr `(* ,size_t ,int))) ; buffer, length, level
         (bv (make-bytevector bv-length))
         (bv-ptr (bytevector->pointer bv)))
    (proc bv-ptr bv-length %gcry-strong-random)
    bv))

(define* (gen-random-token #:optional (bv-length 50)
                           (level %gcry-strong-random))
  (base64-encode (gen-random-bv bv-length level)
                 0 bv-length #f #t base64url-alphabet))
==================================================

So you can use gen-random-token like so:

scheme@(guile-user)> (gen-random-token)
$27 = "XRtMvTmfnQGRCWgA8BqVGFPUB3pOvFn5Us9Qc0JhecL4uxFZkwvb_jeFk8CpPC7TWbw"

Horray, a random token!  It's probably secure, as in, it probably won't
collide with anything, because it's quite large and I suspect that
libgcrypt knows what it's doing about reasonably-secureness in its RNG.
(But what do I know?)

It's not very fast though.  I can generate ~5k tokens per second, which
isn't so bad.

scheme@(guile-user)> ,time (do ((i 1 (1+ i)))
                               ((> i 10000))
                             (gen-random-token))
;; 1.890826s real time, 1.959617s run time.  0.293538s spent in GC.

Much of that is taken up by the base64 encoding... if we tear that out:

scheme@(guile-user)> ,time (do ((i 1 (1+ i)))
                               ((> i 10000))
                             (gen-random-bv))
;; 0.440007s real time, 0.430297s run time.  0.000000s spent in GC.

So that's a bit better.

But it could be a lot faster.  Here's something a lot faster, but it
depends on our RNG being reliable:

  https://github.com/cwebber/pubstrate/blob/master/pubstrate/webapp/auth.scm#L53

(Sorry for the GitHub link, it will be moved shortly.)

That's a lot faster:

scheme@(guile-user)> ,time (do ((i 1 (1+ i)))
                               ((> i 10000))
                             (gen-bearer-token))
;; 0.226487s real time, 0.235521s run time.  0.024290s spent in GC.

... and probably could be even faster if I weren't making a string by
appending a list together.

So I've thought, maybe I could generate an initial seed like so:

==================================================
(define* (big-random-number #:optional (bytes 50))
  "Generate a quite large random number, probably suitable for seeding an RNG"
  ;; @@: Is * a sensible way to combine this?
  (apply * (bytevector->uint-list (gen-random-bv bytes %gcry-very-strong-random)
                                  (native-endianness)
                                  8)))

(set! *random-state* (seed->random-state (big-random-number)))
==================================================

Ie, rely on libgcrypt to provide the initial seed.  I'd assume libgcrypt
would provide reliably pretty good random information, even in the
absence of urandom.

So!  Does someone much better informed than I am have any insights? :)

 - Chris

Re: Sufficiently safe random information for security-critical Guile applications

[Josh Datko]

On Fri, 2016-08-26 at 14:59 -0500, Christopher Allan Webber wrote:
> Hello!  So, as some of you know, I'm working on a federation
> implementation in Guile.  This needs a few things:
> 
>  - Random tokens which won't collide, for various purposes

There's a function in libgcrypt, gcry_create_nonce. Perhaps this would
provide better performance in this use-case. From the libgcrypt 1.6.4
manual:

void gcry_create_nonce (unsigned char *buffer, size t length)

Fill buffer with length unpredictable bytes. This is commonly called a
nonce and may also be used for initialization vectors and padding. This
is an extra function nearly independent of the other random function
for 3 reasons: It better protects the regular random generator’s
internal state, provides better performance and does not drain the
precious entropy pool


>  - The ability to generate a solid random key, which is used for...

Well, besides this unfortunate recent bug/cve (http://formal.iti.kit.ed
u/~klebanov/pubs/libgcrypt-cve-2016-6313.pdf), I would take
cryptographic PRNG over a non-one, with no offense to the guile
developers.

>  - The ability to generate an HMAC (for signed cooke based sessions)

HMAC is deterministic, so once you have your key generated, there is no
random input into HMAC (besides the key of course).

> 
> So!  Does someone much better informed than I am have any insights?
> :)
> 

Seeding one RNG (/dev/random) from another (libgcrypt) doesn't sit well
with me. The problem you need to seed a PRNG from ideally, real random.
How did you generate *that* random? Well, you quickly have a Rube
Goldberg machine.

At the application level, perhaps the best you can do is hope that the
sys admin of that machine has probably seeding /dev/random. Which, is
probably naive, but I'm not sure there is a good solution at your
layer.

Re: Sufficiently safe random information for security-critical Guile applications

[Christopher Allan Webber]

Josh Datko writes:

> On Fri, 2016-08-26 at 14:59 -0500, Christopher Allan Webber wrote:
>> Hello!So, as some of you know, I'm working on a federation
>> implementation in Guile.This needs a few things:
>> 
>> - Random tokens which won't collide, for various purposes
>
> There's a function in libgcrypt, gcry_create_nonce. Perhaps this would
> provide better performance in this use-case. From the libgcrypt 1.6.4
> manual:
>
> void gcry_create_nonce (unsigned char *buffer, size t length)
>
> Fill buffer with length unpredictable bytes. This is commonly called a
> nonce and may also be used for initialization vectors and padding. This
> is an extra function nearly independent of the other random function
> for 3 reasons: It better protects the regular random generator’s
> internal state, provides better performance and does not drain the
> precious entropy pool

That seems to fill 300k 50-length bytevectors with random data per
second, which is quite good.

At that point, it's really the base64 encoding in guile which is slowing
things down, which I suspect might be much faster in Guile 2.1.X
(but I haven't tested it yet).

>> - The ability to generate a solid random key, which is used for...
>
> Well, besides this unfortunate recent bug/cve (http://formal.iti.kit.ed
> u/~klebanov/pubs/libgcrypt-cve-2016-6313.pdf), I would take
> cryptographic PRNG over a non-one, with no offense to the guile
> developers.

I think you're right.  I did a bit more research (full caveat: I know
nearly nothing about these things, or this section of the codebase,
aside from what I looked into yesterday) and it looks like Guile is
using the same Multiply With Carry RNG that was installed in 1999:

/*
 * The prepackaged RNG
 *
 * This is the MWC (Multiply With Carry) random number generator
 * described by George Marsaglia at the Department of Statistics and
 * Supercomputer Computations Research Institute, The Florida State
 * University (http://stat.fsu.edu/~geo).
 *
 * It uses 64 bits, has a period of 4578426017172946943 (4.6e18), and
 * passes all tests in the DIEHARD test suite
 * (http://stat.fsu.edu/~geo/diehard.html)
 */

As it turns out, Multiply With Carry was the same PRNG used in V8, in
the article I previously linked to where troubles were described:

  https://medium.com/@betable/tifu-by-using-math-random-f1c308c4fd9d#.a7q1tgev9

It looks like most other languages are using the Mersenne Twister,
though I don't know if that is necessarily better, or if V8's
implementation was just not really good, or really anything about it.

But yes, I think trusting a crypto library's PRNG for security-critical
stuff is probably the right move.  The recent CVE sorta sucks, but also,
it's good that it's getting that much review to run into those kinds of
problems.

>> - The ability to generate an HMAC (for signed cooke based sessions)
>
> HMAC is deterministic, so once you have your key generated, there is no
> random input into HMAC (besides the key of course).

Right, I just need an initial good value... and even if that were on the
longer end of generation, it would only need to be done once.


>> So!Does someone much better informed than I am have any insights?
>> :)
>> 
>
> Seeding one RNG (/dev/random) from another (libgcrypt) doesn't sit well
> with me. The problem you need to seed a PRNG from ideally, real random.
> How did you generate *that* random? Well, you quickly have a Rube
> Goldberg machine.

Well, and here I was going to throw all my energy into a new random
number generating device scavenged from an old Boggle dice dome, some
original red-box D20s, and a webcam... oh well.

In all seriousness, good point. :)

Anyway, I'll trust in libgcrypt to do the right thing for now.  Thanks
for the input!

 - Chris

Re: Sufficiently safe random information for security-critical Guile applications

[Andy Wingo]

Hi :)

Josh (and the manual) is right -- don't use Guile's RNG for
security-sensitive purposes.  Mostly it's just for games, monte-carlo
simulations and the like.  I wish it were a CSPRNG but it's not; oh
well.

The quality of the PRNG is a separate issue.  MWC could be improved, but
JS impls at least moved to xorshift128+ or something like that.  Anyway
a separate topic entirely.

For sufficiently random sequences of bytes for cryptographic purposes, I
recommend get-bytevector-n on /dev/urandom.

Andy