code review 42560043: go.crypto/fortuna: Implements the Fortuna secure random...

go.crypto/fortuna: Implements the Fortuna secure random number generator

Implemented as described in Cryptography Engineering, N. Ferguson,
B. Schneier, T. Kohno, ISBN 978-0-470-47424-2.

Implemented the Generator interface as a stand-alone usable
pseudo-random number generator (PRNG) that has better security
properties than using AES in CTR mode.

A python implementation of the Generator is included in testdata to
confirm the pure determinism of the implementation.

[M-A, 2013-12-15 21:13:38]

Hello golang-dev@googlegroups.com,

I'd like you to review this change to
https://code.google.com/p/go.crypto

[M-A, 2013-12-15 21:16:10]

On 2013/12/15 21:13:38, M-A wrote:
> Hello mailto:golang-dev@googlegroups.com,
> 
> I'd like you to review this change to
> https://code.google.com/p/go.crypto

Oops, I forgot to paste the benchmarks results;
~/...p/go.crypto/fortuna> go test -test.bench=.*
PASS
BenchmarkFortunaLarge-32        500000000                2.46 ns/op
BenchmarkFortuna1Byte-32         1000000              1067 ns/op
BenchmarkFortuna16Bytes-32      50000000                68.0 ns/op
BenchmarkFortunaAddRandomEvent-32        1000000              2734 ns/op
BenchmarkGeneratorLarge-32      1000000000               2.55 ns/op
BenchmarkGenerator1Byte-32       2000000               783 ns/op
BenchmarkGenerator16Bytes-32    50000000                56.3 ns/op
BenchmarkAESCTRLarge-32 500000000                5.36 ns/op
BenchmarkAESCTR1Byte-32 200000000                8.92 ns/op
BenchmarkAESCTR16Bytes-32       500000000                5.36 ns/op
BenchmarkGeneratorReseed-32      1000000              2661 ns/op
ok      code.google.com/p/go.crypto/fortuna     33.641s

So 1 byte reads compare unfavorably but 16 bytes read have a reasonable (10x)
performance degradation over AES-256-CTR. Interestingly, large reads are
actually faster, likely because of the lack of XORing.

[dfc, 2013-12-15 22:04:36]

Why did you run this benchmarks with GOMAXPROCS=32 set ?

On Mon, Dec 16, 2013 at 8:16 AM,  <maruel@chromium.org> wrote:
> On 2013/12/15 21:13:38, M-A wrote:
>>
>> Hello mailto:golang-dev@googlegroups.com,
>
>
>> I'd like you to review this change to
>> https://code.google.com/p/go.crypto
>
>
> Oops, I forgot to paste the benchmarks results;
> ~/...p/go.crypto/fortuna> go test -test.bench=.*
> PASS
> BenchmarkFortunaLarge-32        500000000                2.46 ns/op
> BenchmarkFortuna1Byte-32         1000000              1067 ns/op
> BenchmarkFortuna16Bytes-32      50000000                68.0 ns/op
> BenchmarkFortunaAddRandomEvent-32        1000000              2734 ns/op
> BenchmarkGeneratorLarge-32      1000000000               2.55 ns/op
> BenchmarkGenerator1Byte-32       2000000               783 ns/op
> BenchmarkGenerator16Bytes-32    50000000                56.3 ns/op
> BenchmarkAESCTRLarge-32 500000000                5.36 ns/op
> BenchmarkAESCTR1Byte-32 200000000                8.92 ns/op
> BenchmarkAESCTR16Bytes-32       500000000                5.36 ns/op
> BenchmarkGeneratorReseed-32      1000000              2661 ns/op
> ok      code.google.com/p/go.crypto/fortuna     33.641s
>
> So 1 byte reads compare unfavorably but 16 bytes read have a reasonable
> (10x) performance degradation over AES-256-CTR. Interestingly, large
> reads are actually faster, likely because of the lack of XORing.
>
> https://codereview.appspot.com/42560043/
>
>
> --
>
> ---You received this message because you are subscribed to the Google Groups
> "golang-dev" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to golang-dev+unsubscribe@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.

[minux1, 2013-12-15 22:17:38]

do we really need the pylintrc file? I don't think we'd ever change
the python reference implementation.

(is it possible to add some static test vectors so that we don't
need the python implementation? most of the crypto packages
don't need another implementation for tests)

[M-A, 2013-12-15 23:54:49]

On 2013/12/15 22:04:36, dfc wrote:
> Why did you run this benchmarks with GOMAXPROCS=32 set ?

Because I have 32 cores on my workstation.


On 2013/12/15 22:17:38, minux wrote:
> do we really need the pylintrc file?

No, removed.

> (is it possible to add some static test vectors so that we don't
> need the python implementation? most of the crypto packages
> don't need another implementation for tests)

The .json files are checked in so python is not needed to run the test. The
reason for the python implementation is that the most common one (pycrypto)
doesn't implement the algorithm properly.

[dchest, 2013-12-16 17:16:04]

Here are some comments on implementation. However, I'm skeptical that we need
Fortuna in user space at all. What would you feed to it that kernel doesn't
already feed to /dev/random?

https://codereview.appspot.com/42560043/diff/60001/fortuna/double_hash.go
File fortuna/double_hash.go (right):

https://codereview.appspot.com/42560043/diff/60001/fortuna/double_hash.go#new...
fortuna/double_hash.go:14: // Enough zeros for SHA(d)-512.
But not enough for, e.g. Keccak256 from go.crypto/sha3 package, so DoubleHash
will panic.

https://codereview.appspot.com/42560043/diff/60001/fortuna/fortuna.go
File fortuna/fortuna.go (right):

https://codereview.appspot.com/42560043/diff/60001/fortuna/fortuna.go#newcode25
fortuna/fortuna.go:25: numPools       = 32                     // As described
in the book.
Can you explain for those who don't have a book?

https://codereview.appspot.com/42560043/diff/60001/fortuna/fortuna.go#newcode39
fortuna/fortuna.go:39: // hashed first with SHA-1.
Why SHA-1, and not SHA-256?

BTW, you're describing a concrete implementation detail in interface definition.
Why have this interface at all when you can just export accumulator struct.

https://codereview.appspot.com/42560043/diff/60001/fortuna/fortuna.go#newcode43
fortuna/fortuna.go:43: // countedHash is a hash object that keeps the amount of
data that was written
s/keeps/keeps track of/ ?

https://codereview.appspot.com/42560043/diff/60001/fortuna/fortuna.go#newcode74
fortuna/fortuna.go:74: temp       [numPools / 8 * sha256.Size]byte // Scratch
space used in resseed to save a memory allocation.
s/resseed/reseed/

https://codereview.appspot.com/42560043/diff/60001/fortuna/fortuna.go#newcode110
fortuna/fortuna.go:110: // Pool P_i is included if 2**i is a divisor of
a.numReset
s/numReset/numReseed/

https://codereview.appspot.com/42560043/diff/60001/fortuna/fortuna.go#newcode115
fortuna/fortuna.go:115: a.pools[i].Reset()
Should the pool be protected from leaking? If yes, then the previous call of
Sum() made a copy of hash state:
http://golang.org/src/pkg/crypto/sha256/sha256.go#L136
I guess it's still hanging somewhere even after you called Reset on the current
state. Moreover, Reset() didn't clean the temporary buffer in hash state, it
just set a variable that counts its  length to zero.

Not an elegant solution, but I think you can write a block of some garbage to
hash before resetting it to mitigate this.

https://codereview.appspot.com/42560043/diff/60001/fortuna/fortuna.go#newcode133
fortuna/fortuna.go:133: buffer = h.Sum(make([]byte, 2, 18))
You want 2+h.Size(), which is 22, not 18.

https://codereview.appspot.com/42560043/diff/60001/fortuna/fortuna.go#newcode192
fortuna/fortuna.go:192: a.reseed(time.Now())
Can't you add a bigger amount of non-determinism here by reading from
crypto/rand?

https://codereview.appspot.com/42560043/diff/60001/fortuna/generator.go
File fortuna/generator.go (right):

https://codereview.appspot.com/42560043/diff/60001/fortuna/generator.go#newco...
fortuna/generator.go:24: Reseed(data []byte) // Reseed appends the seed to the
generator internal state.
Instead of declaring this interface, why not return io.ReadWriter from
NewGenerator, like /dev/random? You reseed by writing to it, and generate random
bytes by reading from it.

https://codereview.appspot.com/42560043/diff/60001/fortuna/generator.go#newco...
fortuna/generator.go:49: // h is optional and will default to SHA-256 and
AES-256 for 128 bits of
This reads like the hash is SHA-256 and AES-256.

https://codereview.appspot.com/42560043/diff/60001/fortuna/generator.go#newco...
fortuna/generator.go:98: // Generates as much PRNG data in-place as possible.
This avoid an unneeded
s/avoid/avoids/

https://codereview.appspot.com/42560043/diff/60001/fortuna/generator.go#newco...
fortuna/generator.go:111: if (len(out) % s) != 0 {
Parentheses are not required in condition.

https://codereview.appspot.com/42560043/diff/60001/fortuna/generator.go#newco...
fortuna/generator.go:162: g.generateBlocks(c, g.key)
Unfortunately, the key in expanded form stays in the internal aesCipher struct
(c) until it's garbage collected. The only solution I see is to reimplement AES
here to be able to reuse or clean key bytes.

[M-A, 2013-12-16 19:00:43]

On 2013/12/16 17:16:04, dchest wrote:
> Here are some comments on implementation. However, I'm skeptical that we need
> Fortuna in user space at all. What would you feed to it that kernel doesn't
> already feed to /dev/random?

Thanks for the comments and thoughtful review, it is very appreciated.

About your concern, it is a valid one and yes the user case is specifically in a
sandboxed process which doesn't have access to /dev/random or /dev/urandom.

Note that NewGenerator is also an implementation that is faster than using
AES-CTR in bulk rate generation, which could be appropriate for specific use
cases.

https://codereview.appspot.com/42560043/diff/60001/fortuna/double_hash.go
File fortuna/double_hash.go (right):

https://codereview.appspot.com/42560043/diff/60001/fortuna/double_hash.go#new...
fortuna/double_hash.go:14: // Enough zeros for SHA(d)-512.
On 2013/12/16 17:16:04, dchest wrote:
> But not enough for, e.g. Keccak256 from go.crypto/sha3 package, so DoubleHash
> will panic.

Done.

https://codereview.appspot.com/42560043/diff/60001/fortuna/fortuna.go
File fortuna/fortuna.go (right):

https://codereview.appspot.com/42560043/diff/60001/fortuna/fortuna.go#newcode25
fortuna/fortuna.go:25: numPools       = 32                     // As described
in the book.
On 2013/12/16 17:16:04, dchest wrote:
> Can you explain for those who don't have a book?

Added a small explanation and the direct page reference.

https://codereview.appspot.com/42560043/diff/60001/fortuna/fortuna.go#newcode39
fortuna/fortuna.go:39: // hashed first with SHA-1.
On 2013/12/16 17:16:04, dchest wrote:
> Why SHA-1, and not SHA-256?

Because it's good enough in that case.
 
> BTW, you're describing a concrete implementation detail in interface
definition.

You are totally right, removed.

> Why have this interface at all when you can just export accumulator struct.

That is a good question. I thought it was cleaner to just expose the interface
but I guess I could expose the object itself since we don't expect multiple
implementers. Is that your preference?

https://codereview.appspot.com/42560043/diff/60001/fortuna/fortuna.go#newcode43
fortuna/fortuna.go:43: // countedHash is a hash object that keeps the amount of
data that was written
On 2013/12/16 17:16:04, dchest wrote:
> s/keeps/keeps track of/ ?

Done.

https://codereview.appspot.com/42560043/diff/60001/fortuna/fortuna.go#newcode74
fortuna/fortuna.go:74: temp       [numPools / 8 * sha256.Size]byte // Scratch
space used in resseed to save a memory allocation.
On 2013/12/16 17:16:04, dchest wrote:
> s/resseed/reseed/

Done.

https://codereview.appspot.com/42560043/diff/60001/fortuna/fortuna.go#newcode110
fortuna/fortuna.go:110: // Pool P_i is included if 2**i is a divisor of
a.numReset
On 2013/12/16 17:16:04, dchest wrote:
> s/numReset/numReseed/

Done.

https://codereview.appspot.com/42560043/diff/60001/fortuna/fortuna.go#newcode115
fortuna/fortuna.go:115: a.pools[i].Reset()
On 2013/12/16 17:16:04, dchest wrote:
> Should the pool be protected from leaking? If yes, then the previous call of
> Sum() made a copy of hash state:
> http://golang.org/src/pkg/crypto/sha256/sha256.go#L136
> I guess it's still hanging somewhere even after you called Reset on the
current
> state. Moreover, Reset() didn't clean the temporary buffer in hash state, it
> just set a variable that counts its  length to zero.
> 
> Not an elegant solution, but I think you can write a block of some garbage to
> hash before resetting it to mitigate this.

The other option is to change the stdlib Sum() implementation to call d.Reset()
right after d.checkSum() to zap out the temporary object is it creating. The
cost shouldn't be too adverse.

This would mean this library would be safe potentially only with golang 1.3+ but
the change would benefit everyone from a potential information leak in the heap,
not just this library.

wdyt?

https://codereview.appspot.com/42560043/diff/60001/fortuna/fortuna.go#newcode133
fortuna/fortuna.go:133: buffer = h.Sum(make([]byte, 2, 18))
On 2013/12/16 17:16:04, dchest wrote:
> You want 2+h.Size(), which is 22, not 18.

Oops, replaced with 2+h.Size() so this won't be wrong even if the hashing
algorithm is changed.

https://codereview.appspot.com/42560043/diff/60001/fortuna/fortuna.go#newcode192
fortuna/fortuna.go:192: a.reseed(time.Now())
On 2013/12/16 17:16:04, dchest wrote:
> Can't you add a bigger amount of non-determinism here by reading from
> crypto/rand?

That's a good point but the goal it have a meaningful implementation to replace
crypto/rand when necessary, so it cannot read from there.

https://codereview.appspot.com/42560043/diff/60001/fortuna/generator.go
File fortuna/generator.go (right):

https://codereview.appspot.com/42560043/diff/60001/fortuna/generator.go#newco...
fortuna/generator.go:24: Reseed(data []byte) // Reseed appends the seed to the
generator internal state.
On 2013/12/16 17:16:04, dchest wrote:
> Instead of declaring this interface, why not return io.ReadWriter from
> NewGenerator, like /dev/random? You reseed by writing to it, and generate
random
> bytes by reading from it.

Nice idea, didn't think about that. Done.

https://codereview.appspot.com/42560043/diff/60001/fortuna/generator.go#newco...
fortuna/generator.go:49: // h is optional and will default to SHA-256 and
AES-256 for 128 bits of
On 2013/12/16 17:16:04, dchest wrote:
> This reads like the hash is SHA-256 and AES-256.

Reworked the doc.

https://codereview.appspot.com/42560043/diff/60001/fortuna/generator.go#newco...
fortuna/generator.go:98: // Generates as much PRNG data in-place as possible.
This avoid an unneeded
On 2013/12/16 17:16:04, dchest wrote:
> s/avoid/avoids/

Done.

https://codereview.appspot.com/42560043/diff/60001/fortuna/generator.go#newco...
fortuna/generator.go:111: if (len(out) % s) != 0 {
On 2013/12/16 17:16:04, dchest wrote:
> Parentheses are not required in condition.

Done.

https://codereview.appspot.com/42560043/diff/60001/fortuna/generator.go#newco...
fortuna/generator.go:162: g.generateBlocks(c, g.key)
On 2013/12/16 17:16:04, dchest wrote:
> Unfortunately, the key in expanded form stays in the internal aesCipher struct
> (c) until it's garbage collected. The only solution I see is to reimplement
AES
> here to be able to reuse or clean key bytes.

:/ I'll think about this a bit.

One option is to change crypto/aes/cipher.go to have 2 3 specialized structs
using arrays instead of slices so that they do not linger around without
control. One for each of 16, 24 and 32 bytes.

[gobot, 2013-12-20 16:26:16]

Replacing golang-dev with golang-codereviews.

[M-A, 2013-12-23 19:20:14]

I got three different sets of comments which I replied but I'd like a definitive
answer on the acceptability of this patch in go.crypto.

In particular, I would like if someone could read the Chapter 9 "Generating
Randomness" and confirm that I did properly implement the algorithm as
documented.

You can never be too sure about your random number source (in case you haven't
read the news lately).

Thanks,

M-A

[M-A, 2014-01-05 01:50:33]

Should I consider the silence a 'no' for acceptance? If so, I'll push it on
github.

[dfc, 2014-01-05 01:55:36]

Please wait nil next week, many people are on holiday. 

> On 5 Jan 2014, at 12:50, maruel@chromium.org wrote:
> 
> Should I consider the silence a 'no' for acceptance? If so, I'll push it
> on github.
> 
> https://codereview.appspot.com/42560043/

[bradfitz, 2014-01-05 18:05:05]

R=agl

To determine whether this should go in go.crypto.

[agl1, 2014-01-06 18:03:14]

On Windows and (most?) POSIX systems, the operating system supplies entropy and
we use it via crypto/rand. On these platforms, local entropy gathering isn't
needed.

Perhaps if there was some significant OS without entropy support we might wish
to include Fortuna, but then we would want to put it in crypto/rand. I've not
heard of motivating examples like this yet.

[M-A, 2014-01-22 18:17:50]

On 2014/01/06 18:03:14, agl1 wrote:
> On Windows and (most?) POSIX systems, the operating system supplies entropy
and
> we use it via crypto/rand. On these platforms, local entropy gathering isn't
> needed.
> 
> Perhaps if there was some significant OS without entropy support we might wish
> to include Fortuna, but then we would want to put it in crypto/rand. I've not
> heard of motivating examples like this yet.

I replied off mailing list about a specific use case but I'll comment on here
too. In practice, it happens on sandbox where no file can be opened, like
/dev/urandom. I agree it is a niche market so I don't mind not putting it here
and on a github repo instead. It will still be useful for Google.

[agl1, 2014-01-22 20:54:35]

On 2014/01/22 18:17:50, M-A wrote:
> I don't mind not putting it here
> and on a github repo instead. It will still be useful for Google.

I think this is probably best suited for GitHub, but thanks!

[gobot, 2014-05-25 21:12:13]

R=close (assigned by agl@golang.org)