code review 7474049: hkdf: implemented hash based key derivation.

hkdf: implemented hash based key derivation.

Detailed description in RFC 5869.

[karalabe, 2013-03-07 22:44:58]

Hello agl@chromium.org, minux.ma@gmail.com (cc: golang-dev@googlegroups.com),

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

[karalabe, 2013-03-08 17:45:48]

Added a usage example to make the whole module nicer :)

[agl1, 2013-03-12 15:12:15]

At the high level, we've not exposed a KDF API before and it's unclear whether a
Reader interface is the right one. The alternative would be to pass in a length,
or a []byte to be filled, and have it be a one-shot operation.

However, since one typically takes a number of outputs (a couple of keys and a
couple of IVs) from a KDF, the Reader interface may save people having to
manually split up a single output so I think I like it.

However, the implementation itself allocates far more than is needed. I can fix
this up before landing if you wish but I've pointed out a few cases in case you
wish to iterate yourself.

(p.s. have you signed the CLA?)

https://codereview.appspot.com/7474049/diff/17001/hkdf/hkdf.go
File hkdf/hkdf.go (right):

https://codereview.appspot.com/7474049/diff/17001/hkdf/hkdf.go#newcode44
hkdf/hkdf.go:44: input := append(f.prev, append(f.info, f.counter)...)
this is better written as two, non-nested appends. The nested append is actually
copying f.info into a new buffer just to append a single byte and returning it.
input can also be reused between iterations.

https://codereview.appspot.com/7474049/diff/17001/hkdf/hkdf.go#newcode46
hkdf/hkdf.go:46: expander := hmac.New(f.hash, f.prk)
the HMAC from New can be passed in and Reset() rather than creating afresh each
time.

https://codereview.appspot.com/7474049/diff/17001/hkdf/hkdf.go#newcode48
hkdf/hkdf.go:48: output := expander.Sum(nil)
in the case where the full hash result fits in p, it could be written directly.

https://codereview.appspot.com/7474049/diff/17001/hkdf/hkdf.go#newcode63
hkdf/hkdf.go:63: func New(hash func() hash.Hash, master []byte, salt []byte,
info []byte) io.Reader {
argument names should either be commonly used, or match the RFC. Thus I would
call "master" either "secret" or "ikm".

https://codereview.appspot.com/7474049/diff/17001/hkdf/hkdf.go#newcode64
hkdf/hkdf.go:64: extractor := hmac.New(hash, salt)
If a salt is not provided, hash.Size() zero bytes should be used.

https://codereview.appspot.com/7474049/diff/17001/hkdf/hkdf.go#newcode67
hkdf/hkdf.go:67: return &hkdf{hash, hash().Size(), extractor.Sum(nil), info, 1,
[]byte{}, []byte{}}
s/[]byte{}/nil/

[karalabe, 2013-03-12 15:38:36]

I think I'll manage the fixes, I'll commit in a few hours, just let me finish up
something first.

Btw, there's one slight design change I've added since the review request:
instead of passing in "hash-maker" functions, I've changed to the crypto.Hash
enums:

hkdf.New(sha1.New, ...) -> hkdf.New(crypto.SHA1, ...)

Which design do you prefer? The original or the crypto-enum one? (the latter is
available at https://github.com/karalabe/iris/blob/master/crypto/hkdf/hkdf.go ).

PS: Yes I've signed the CLA (at least the digital version)

[agl, 2013-03-12 15:45:40]

On Tue, Mar 12, 2013 at 11:38 AM,  <peterke@gmail.com> wrote:
> Btw, there's one slight design change I've added since the review
> request: instead of passing in "hash-maker" functions, I've changed to
> the crypto.Hash enums:

Passing in the function is more canonical.


Cheers

AGL

[karalabe, 2013-03-12 17:10:55]

Issues should be resolved now, please check it again.

[karalabe, 2013-04-09 15:35:46]

Added some benchmarks in the mean time.

Intel(R) Core(TM) i7-2600 CPU @ 3.40GHz:
Benchmark16ByteMd5Single      500000   3870 ns/op   4.13 MB/s
Benchmark20ByteSha1Single     500000   4706 ns/op   4.25 MB/s
Benchmark32ByteSha256Single   200000   8759 ns/op   3.65 MB/s
Benchmark64ByteSha512Single   200000  11790 ns/op   5.43 MB/s
Benchmark8ByteMd5Stream      5000000    720 ns/op  11.11 MB/s
Benchmark16ByteMd5Stream     1000000   1403 ns/op  11.40 MB/s
Benchmark8ByteSha1Stream     5000000    746 ns/op  10.71 MB/s
Benchmark20ByteSha1Stream    1000000   1795 ns/op  11.14 MB/s
Benchmark8ByteSha256Stream   2000000    897 ns/op   8.91 MB/s
Benchmark32ByteSha256Stream   500000   3482 ns/op   9.19 MB/s
Benchmark8ByteSha512Stream   5000000    626 ns/op  12.76 MB/s
Benchmark64ByteSha512Stream   500000   4767 ns/op  13.42 MB/s

[karalabe, 2013-12-16 23:47:56]

Ok, this kind of got forgotten. Any intentions of including it?

[agl1, 2013-12-19 21:10:13]

https://codereview.appspot.com/7474049/diff/32001/hkdf/hkdf.go
File hkdf/hkdf.go (right):

https://codereview.appspot.com/7474049/diff/32001/hkdf/hkdf.go#newcode6
hkdf/hkdf.go:6: // Function (HKDF) as defined in Internet Engineering Task
Force, Request for
s/Internet Engineering Task Force, Request for Comments 5869/RFC 5869/

https://codereview.appspot.com/7474049/diff/32001/hkdf/hkdf.go#newcode9
hkdf/hkdf.go:9: // An HKDF is a cryptographic key derivation function (KDF) with
the goal of
s/An//

https://codereview.appspot.com/7474049/diff/32001/hkdf/hkdf.go#newcode43
hkdf/hkdf.go:43: if len(f.cache) > need {
The use of offset and need feels odd for Go code vs reslicing:

(note: not actually tested.)

todo := len(n)
remains := len(f.cache) + int(255-f.counter+1)*f.size
if remains < need {
  return 0, errors.New(fmt.Sprintf("entropy limit reached %d < %d"
    , remains, need))
}

n := copy(p, f.cache)
f.cache = f.cache[n:]
p = p[n:]

var input []byte

for len(p) > 0 {
  input = append(input[:0], f.prev...)
  input = append(input, f.info...)
  input = append(input, counter)

  f.expander.Reset()
  f.expander.Write(input)
  f.prev = f.expander.Sum(f.prev[:0])
  f.counter++

  f.cache = f.prev
  n := copy(p, f.cache)
  f.cache = f.cache[n:]
  p = p[n:]
}

return todo, nil

https://codereview.appspot.com/7474049/diff/32001/hkdf/hkdf_test.go
File hkdf/hkdf_test.go (right):

https://codereview.appspot.com/7474049/diff/32001/hkdf/hkdf_test.go#newcode290
hkdf/hkdf_test.go:290: func Benchmark16ByteMd5Single(b *testing.B) {
MD and SHA in these function names.

[gobot, 2013-12-20 16:21:43]

Replacing golang-dev with golang-codereviews.

[agl1, 2014-01-14 14:25:32]

Any interest in continuing with this?

[karalabe, 2014-01-29 09:10:53]

On 2014/01/14 14:25:32, agl1 wrote:
> Any interest in continuing with this?

Yes, yes. Sorry for not responding, I'm prepping a demo for the FOSDEM Go
devroom for the weekend and it takes up all my time. But I'll get back to this
asap.

[karalabe, 2014-02-10 19:17:13]

Please take another look.

I've updated the code as requested. I reorganized your proposal a bit to twist a
few more drops of performance out of it.

Previous version benchmarks (i7-2600):
Benchmark16ByteMd5Single         2000000              2801 ns/op           5.71
MB/s
Benchmark20ByteSha1Single        1000000              3277 ns/op           6.10
MB/s
Benchmark32ByteSha256Single      1000000              6946 ns/op           4.61
MB/s
Benchmark64ByteSha512Single       500000              9458 ns/op           6.77
MB/s
Benchmark8ByteMd5Stream         10000000               465 ns/op          17.19
MB/s
Benchmark16ByteMd5Stream         5000000               909 ns/op          17.60
MB/s
Benchmark8ByteSha1Stream        20000000               449 ns/op          17.79
MB/s
Benchmark20ByteSha1Stream        5000000              1084 ns/op          18.44
MB/s
Benchmark8ByteSha256Stream      10000000               696 ns/op          11.49
MB/s
Benchmark32ByteSha256Stream      2000000              2723 ns/op          11.75
MB/s
Benchmark8ByteSha512Stream      10000000               489 ns/op          16.36
MB/s
Benchmark64ByteSha512Stream      1000000              3761 ns/op          17.01
MB/s

Current version benchmarks:
Benchmark16ByteMD5Single         2000000              2799 ns/op           5.71
MB/s
Benchmark20ByteSHA1Single        1000000              3276 ns/op           6.10
MB/s
Benchmark32ByteSHA256Single      1000000              6942 ns/op           4.61
MB/s
Benchmark64ByteSHA512Single       500000              9455 ns/op           6.77
MB/s
Benchmark8ByteMD5Stream         20000000               433 ns/op          18.44
MB/s
Benchmark16ByteMD5Stream        10000000               848 ns/op          18.86
MB/s
Benchmark8ByteSHA1Stream        20000000               421 ns/op          18.97
MB/s
Benchmark20ByteSHA1Stream        5000000              1021 ns/op          19.57
MB/s
Benchmark8ByteSHA256Stream      10000000               673 ns/op          11.88
MB/s
Benchmark32ByteSHA256Stream      2000000              2636 ns/op          12.14
MB/s
Benchmark8ByteSHA512Stream      10000000               476 ns/op          16.79
MB/s
Benchmark64ByteSHA512Stream      1000000              3664 ns/op          17.47
MB/s

[agl1, 2014-02-12 19:03:54]

LGTM. I'll make these changes before landing because they're small. Thanks!

https://codereview.appspot.com/7474049/diff/76001/hkdf/example_test.go
File hkdf/example_test.go (right):

https://codereview.appspot.com/7474049/diff/76001/hkdf/example_test.go#newcode1
hkdf/example_test.go:1: // Copyright 2013 The Go Authors. All rights reserved.
2014 and blank line after copyright.

https://codereview.appspot.com/7474049/diff/76001/hkdf/hkdf.go
File hkdf/hkdf.go (right):

https://codereview.appspot.com/7474049/diff/76001/hkdf/hkdf.go#newcode1
hkdf/hkdf.go:1: // Copyright 2013 The Go Authors. All rights reserved.
2014

https://codereview.appspot.com/7474049/diff/76001/hkdf/hkdf.go#newcode9
hkdf/hkdf.go:9: // expanding some limited size input keying material into one or
more
kill "some" and "size".

https://codereview.appspot.com/7474049/diff/76001/hkdf/hkdf.go#newcode39
hkdf/hkdf.go:39: return 0, errors.New(fmt.Sprintf("entropy limit reached %d <
%d", remains, need))
"hkdf:" as prefix to the error message and also errors.New(fmt.Sprintf(...)) is
fmt.Errorf(...). In this case I'd drop the numbers in the error message because
it pulls in fmt, which is a big package just for this.

https://codereview.appspot.com/7474049/diff/76001/hkdf/hkdf.go#newcode69
hkdf/hkdf.go:69: func New(hash func() hash.Hash, secret []byte, salt []byte,
info []byte) io.Reader {
"secret, salt, info" since they have the same type.

https://codereview.appspot.com/7474049/diff/76001/hkdf/hkdf_test.go
File hkdf/hkdf_test.go (right):

https://codereview.appspot.com/7474049/diff/76001/hkdf/hkdf_test.go#newcode1
hkdf/hkdf_test.go:1: // Copyright 2013 The Go Authors. All rights reserved.
2014

[agl1, 2014-02-12 19:08:38]

*** Submitted as
https://code.google.com/p/go/source/detail?r=dc7486a41a09&repo=crypto ***

go.crypto/hkdf: implement hash-based, key derivation.

Detailed description in RFC 5869.

LGTM=agl
R=agl, minux.ma
CC=golang-codereviews
https://codereview.appspot.com/7474049

Committer: Adam Langley <agl@golang.org>