crypto/galois

[Luke Curley]

Hey guys,

I've written a new crypto package that I'd like to replace crypto/cipher NewGCM: https://codereview.appspot.com/56530043/

Introduction http://en.wikipedia.org/wiki/Galois/Counter_Mode

Galois Counter Mode is a cipher mode that provides authenticated encryption with minimal performance overhead. The authentication works by producing a 16-byte tag based on the data, such that changing the ciphertext would cause the tags to mismatch and prevent decryption. Additionally, unencrypted data can authenticated as well.

GCM uses CTR for encryption and a function called GHASH to produce the authentication tag. GHASH uses multiplication over a galois finite field to continuously update the sum. The benefit of using GCM/GHASH instead of a traditional HMAC is primarily improved performance, including native hardware support (AES-NI).

New Features

• Dramatically improved performance for processors with AES-NI support.
  
• Support for variable-length nonces.
• Support for variable-length authentication tags.
• Supports streaming (does not require all data upfront).
• Implements hash.Hash (for GMAC) and cipher.Block (for GCM)

Old API http://golang.org/pkg/crypto/cipher/#AEAD

# use nonce, write data if given, encrypt plaintext if given, append ciphertext and auth to dst if given and return it.

gcm.Seal(dst, nonce, plaintext, data []byte) (ciphertextPlusAuth []byte)

# use nonce, write data if given, verify auth, decrypt ciphertext if given, append plaintext to dst if given and return it.

gcm.Open(dst, nonce, ciphertextPlusAuth, data []byte) (plaintext []byte, err error)

The result of so many optional parameters is a lot of seemingly random "nil" values. Note that this API cannot support variable length tags, as both the ciphertext and the tag would have a variable length.

New API https://codereview.appspot.com/56530043/patch/120001/130005

# authenticate additional data and update the sum (optional)

Write(data []byte) 

# encrypt the plaintext to ciphertext and update the sum (optional)

Encrypt(ciphertext, plaintext []byte)

# append the current authentication sum and return it

Sum(auth []byte) []byte

# decrypt the ciphertext to plaintext and update the sum (optional)

Decrypt(plaintext, ciphertext []byte)

# verify current authentication sum matches the given one

Verify(auth []byte) err

The biggest problem with this API is that you MUST remember to call Verify after Decrypting all of the data and before using the plaintext. Otherwise, you lose the authentication piece and along with it, the whole point of using GCM.

Performance

AES-NI support (Sandy Bridge+) available:

benchmark                   old ns/op    new ns/op    delta

BenchmarkAESGCMEncrypt1K        17379         5471  -68.52%

BenchmarkAESGCMDecrypt1K        17341         5466  -68.48%

BenchmarkAESGCMWrite1K          14171         3115  -78.02%

benchmark                    old MB/s     new MB/s  speedup

BenchmarkAESGCMEncrypt1K        58.92       187.16    3.18x

BenchmarkAESGCMDecrypt1K        59.05       187.32    3.17x

BenchmarkAESGCMWrite1K          72.26       328.72    4.55x

Fallback code:

benchmark                   old ns/op    new ns/op    delta

BenchmarkAESGCMEncrypt1K        17379        15613  -10.16%

BenchmarkAESGCMDecrypt1K        17341        15648   -9.76%

BenchmarkAESGCMWrite1K          14171        13238   -6.58%

benchmark                    old MB/s     new MB/s  speedup

BenchmarkAESGCMEncrypt1K        58.92        65.58    1.11x

BenchmarkAESGCMDecrypt1K        59.05        65.44    1.11x

BenchmarkAESGCMWrite1K          72.26        77.35    1.07x

There are numerous papers on optimizing GCM and the performance can be improved further, but this is a good start. GCM is also a TLS cipher (and Go's default) but I'm not sure if its covered in existing benchmarks.

Backwards-Compatibility

Obviously, this new API is not backwards compatible. The old API is modeled after NaCl, but I wanted to make something modeled after Go. The ability to stream data is great for reducing latency, and being able to chain Write and Encrypt/Decrypt calls avoids having to allocate and manage a large buffer. In addition, the old API could not support variable length tags as defined in the spec.

My suggestion would be to provide crypto/galois, and remove crypto/cipher.NewGCM in the coming or next release. It's not a popular function and this will not affect most users.

[Caleb Spare]

Hi Luke, are you aware of the Go 1 compatibility promise?

http://golang.org/doc/go1compat

--
 
---
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+...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

[Luke Curley]

I was not.

I guess that means making a compatibility wrapper for cipher but recommending the new package instead.

Alternatively, I could keep the old api but would have to remove streaming  and variable length tag support.

[Adam Langley]

The CLMUL support would be very nice to have although, as Han-wen
noted, the license of the Intel code makes it unclear if we can copy
it like that.

The Seal and Open functions do have too many []byte arguments,
although I think the problem is one of transposition (as only one is
really optional) because Go isn't Objective C. However, the proposed
API has the major weakness that it returns unauthenticated plaintext.
This is something that should be avoided wherever possible and
streaming APIs encourage more bad behaviour in protocols by making it
easy to skip on chunking and therefore impose problems on good APIs at
the other end.

A different sized tag implies that it's a different AEAD
(https://tools.ietf.org/search/rfc5116), which is fine, but, so far
only the construction used in TLS is implemented.


Cheers

AGL

[Luke Curley]

I have no idea about the licensing implications. It does seem odd that Intel would publish 10+ implementations as a white paper but prohibit their usage. Let me know if we can't use this and I can re-implement, maybe even make it faster.

My views on Verify is that it's akin to never reusing the same key/IV pair. It's stated as requirement in the documentation and examples but is never enforced for the sake of compatibility (?). Failing to use Verify downgrades GCM to CTR, but may be worth the risk to provide a better API in other areas. Failing to use a unique key/iv pair, on the other hand, completely breaks security...

The GCM spec says the tag length is variable, while TLS forces it to be 16 bytes. GCM is used outside of TLS and variable length tags are useful when bytes matter.

My biggest gripe with the current API is the way the authentication tag is appended to the ciphertext. It's not part of the spec, so for compatibility you have to append or slice the last 16 bytes. The API uses append so it will make a full copy unless dst has the capacity for these extra 16 bytes, which is often not true if you're trying to reuse a buffer. And of course it prevents variable length tags. Nothing is a deal breaker, it's just particularly cumbersome and shouldn't be the official API.

An alternate solution could be to make the tag a separate argument and not use append:

Seal(ciphertextDst, nonce, plaintext, data []byte) (auth []byte)

Open(plaintextDst, nonce, ciphertext, auth, data []byte) (error err)

But it's still a C API, and not something you'd expect to see in Go.

And thanks so much AGL for the original implementation. I went into this with just the intention of improving performance, but maybe got a little carried away trying to improve everything.

[Adam Langley]

On Mon, Jan 27, 2014 at 2:51 PM, Luke Curley <qpi...@gmail.com> wrote:
> My biggest gripe with the current API is the way the authentication tag is
> appended to the ciphertext. It's not part of the spec, so for compatibility
> you have to append or slice the last 16 bytes. The API uses append so it
> will make a full copy unless dst has the capacity for these extra 16 bytes,
> which is often not true if you're trying to reuse a buffer. And of course it
> prevents variable length tags. Nothing is a deal breaker, it's just
> particularly cumbersome and shouldn't be the official API.

Variable length nonces are fine with the current API, but not
currently supported. A different length nonce is a different AEAD,
e.g. NewGCMWithTagLength(aes, 12).

The idea behind AEADs is to create a higher level abstraction that is
easier to use. If the tags aren't put at the end then, again, it's a
different AEAD. The above API is appearing in PKCS#11, OpenSSL, Go and
NaCl are there's significant value in avoiding the problems that arise
from expecting people to compose the lower-level primitives
themselves.

Sealing will create a new buffer if you don't have one, but operating
in place isn't style Go style. If you do need to operate in place then
you'll need to create slices with appropriate extra space, but that's
true anyway because one usually needs to put framing information
around the data.


Cheers

AGL

[Luke Curley]

Okay, so I made a rookie mistake and didn't know about the compatibility guarantee. I'll rework my performance improvements so it's compatible with the current API and avoids any licensing issues.

I still think the API is poor, but that's a debate for another day (Go 2.0).