code review 3974041: vmac: Create vmac package

vmac: Create vmac package

[nicksnyder, 2011-01-13 01:24:24]

Hello golang-dev@googlegroups.com (cc: golang-dev@googlegroups.com),

I'd like you to review this change.

[agl1, 2011-01-13 02:01:00]

taking review

[agl1, 2011-01-13 02:13:43]

On Wed, Jan 12, 2011 at 9:01 PM,  <agl@golang.org> wrote:
> taking review

Before I do a review, could you explain the what need you have for
VMAC? VMAC is a rarely used primitive.

Cheers

AGL

[nicksnyder, 2011-01-13 05:27:21]

There is a use case within Google for it. Check out the "Go vmac package"
wave you are already on for a more specific answer. If you think this should
just be a package internal to Google I guess we could do that too.

Nick

On Wed, Jan 12, 2011 at 6:13 PM, Adam Langley <agl@golang.org> wrote:

> On Wed, Jan 12, 2011 at 9:01 PM,  <agl@golang.org> wrote:
> > taking review
>
> Before I do a review, could you explain the what need you have for
> VMAC? VMAC is a rarely used primitive.
>
> Cheers
>
> AGL
>

[agl1, 2011-01-13 17:53:13]

http://codereview.appspot.com/3974041/diff/2001/src/pkg/crypto/vmac/Makefile
File src/pkg/crypto/vmac/Makefile (right):

http://codereview.appspot.com/3974041/diff/2001/src/pkg/crypto/vmac/Makefile#...
src/pkg/crypto/vmac/Makefile:1: # Copyright 2009 The Go Authors. All rights
reserved.
2011

http://codereview.appspot.com/3974041/diff/2001/src/pkg/crypto/vmac/vmac.go
File src/pkg/crypto/vmac/vmac.go (right):

http://codereview.appspot.com/3974041/diff/2001/src/pkg/crypto/vmac/vmac.go#n...
src/pkg/crypto/vmac/vmac.go:10: "crypto/block"
crypto/block is deprecated, use crypto/cipher.

http://codereview.appspot.com/3974041/diff/2001/src/pkg/crypto/vmac/vmac.go#n...
src/pkg/crypto/vmac/vmac.go:17: l1keylen  = 1024
I feel that something like numL1KeyBits and numL1KeyBytes would be more
expressive in the code, although I admit that it's nice to mirror the
specification. Up to you here.

http://codereview.appspot.com/3974041/diff/2001/src/pkg/crypto/vmac/vmac.go#n...
src/pkg/crypto/vmac/vmac.go:22: var m64 = new(big.Int).Lsh(one, 64)             
                                                                         // 2^64
You should consider if the code should really use big. It's a large dependency
and fixed function code is typically 3-4x faster than generic MPI code.

Go doesn't give you a 128-bit type, so the 64-bit mults are truncating I'm
afraid. So I would suggest that you use only 32 bit inputs to the 64-bit mult to
avoid truncation.

Thus, a 128-bit value could be represented as four uint32s. The lack of
add-with-carry is a pain and I did wonder if it would be best to expose addWW
from big, but it's very short so I think I would duplicate it. See addWW_g in
big/arith.go for MPI addition.

For multiplication, treat the four values as a polynomial in 2^32. Thus you need
to calculate (a*2^96 + b*2^64 + c*2^32 + d) * (e*2^96 ...). If you are working
mod 2^128 then any results which fall at 2^128 or above can be dropped.

When you sum the results of the 32x32 mults, the intermediate results will
overflow. You can handle the carries or you could use a polynomial in 2^25 or
2^26 (and five values).

If that's too much work, then just use big.

http://codereview.appspot.com/3974041/diff/2001/src/pkg/crypto/vmac/vmac.go#n...
src/pkg/crypto/vmac/vmac.go:37: func (h *Hash) Write(p []byte) (n int, err
os.Error) {
(I'm skipping much of the code here because I think that it'll change.)

Hash functions should be online, i.e. incremental. Sometimes it's useful to
write very fast, one-shot versions of the code but they should implement a
different interface.

The design here mirrors the specification, but vmac can be made to be
incremental.

L1 works on blocks of 128 bytes and outputs blocks of 16 bytes. If you want to
support 128-bit tags (and you probably should) then you need to keep track of
two streams.

So I suggest that the object have a 128 byte buffer which it fills up and, once
full, transforms via L1.

L2 is more like a standard hash function, it has a fixed length output which is
updated. So, when L1 produces a new value the L2 function should update the
running L2 value. (Again, for 128-bit tags there would need to be two running
values.)

[rsc, 2011-01-13 18:14:23]

This code definitely should not use package big.
The only reason people use vmac is because it
can be implemented efficiently.

To start, you can use a portable 64x64 -> 128 multiply
http://golang.org/src/pkg/runtime/softfloat64.go#L418

Once the code is done we can think about maybe
writing nh in assembly on amd64.  But that's for later.

In general I think you should be using fixed-size
integers instead of fixed-size byte slices whenever
possible.

Russ

[agl1, 2011-01-13 18:19:14]

On Thu, Jan 13, 2011 at 1:14 PM, Russ Cox <rsc@golang.org> wrote:
> To start, you can use a portable 64x64 -> 128 multiply
> http://golang.org/src/pkg/runtime/softfloat64.go#L418

Indeed, any code should be designed so that it would be easy to drop
in asm versions of the critical functions.

I really would consider the advantages of a 25 or 26 bit limb schedule
however. Saturated limbs are obvious, comment but often suboptimal.

Or you could bug for a language change to add 128-bit values like GCC did :)


AGL

[nickdsnyder, 2011-06-13 19:03:33]

I really appreciate all of your comments, but it looks like the amount of
time/effort it would take to fix the code is more than I can muster in the
forseeable future. I posted my code at https://github.com/nicksnyder/vmac.go in
case anyone finds the code useful.

[rsc, 2011-06-13 19:26:54]

removing reviewers