golang / go

The Go programming language
https://go.dev
BSD 3-Clause "New" or "Revised" License
124.12k stars 17.68k forks source link

x/crypto: add AES-GCM-SIV #54364

Open ericlagergren opened 2 years ago

ericlagergren commented 2 years ago

Update, Jul 26 2023: Current proposal is https://github.com/golang/go/issues/54364#issuecomment-1642676993.


AES-GCM-SIV (RFC 8452) is a nonce misuse-resistant AEAD. When a nonce is reused, AES-GCM-SIV does not immediately fail catastrophically. Instead, it only discloses whether the contents of the messages are the same. It is generally safe to replace usages of AES-GCM with AES-GCM-SIV.

I propose adding a new package called x/crypto/aesgcmsiv. The API is provided below.

const (
    // NonceSize is the size in bytes of an AES-GCM-SIV nonce.
    NonceSize = 12
    // TagSize is the size in bytes of an AES-GCM-SIV
    // authentication tag.
    TagSize = 16
    // MaxPlaintextSize is the size in bytes of the largest
    // allowed plaintext.
    MaxPlaintextSize = 1 << 36
    // MaxAdditionalDataSize is the size in bytes of the largest
    // allowed additional authenticated data.
    MaxAdditionalDataSize = 1 << 36
)

// New creates an instance of AES-GCM-SIV.
// The key must be either 16 bytes for 128-bit AES-GCM-SIV or 32 bytes for
// 256-bit AES-GCM-SIV. All other lengths are an error.
func New(key []byte) (cipher.AEAD, error)
gopherbot commented 2 years ago

Change https://go.dev/cl/404398 mentions this issue: x/crypto: add AES-GCM-SIV

gopherbot commented 2 years ago

Change https://go.dev/cl/404534 mentions this issue: x/crypto: implement POLYVAL

seankhliao commented 2 years ago

cc @golang/security

ericlagergren commented 2 years ago

Friendly ping about this.

bench commented 1 year ago

new 2023 friendly ping :wink: Very interested to see this work merged. What is the next step in the merge process ? cc @FiloSottile

rsc commented 1 year ago

This proposal has been added to the active column of the proposals project and will now be reviewed at the weekly proposal review meetings. — rsc for the proposal review group

rolandshoemaker commented 1 year ago

Adding support for a nonce-misuse resistant AEAD seems like a good idea.

The only real question I have is if we want to mirror the existing GCM API (i.e. splitting the block cipher construction from the GCM construction, see crypto/aes and crypto/cipher), or just provide a one shot New (as proposed in the first comment). I guess there is also a question about if this makes sense to put in x/crypto, or in the standard library (if we want people to actually use it, instead of AES-GCM, it seems somewhat confusing to put it in x/crypto while the former is in the standard library 🤷).

cc @FiloSottile who I think had opinions about the existing AEAD interface design.

ericlagergren commented 1 year ago

if we want to mirror the existing GCM API ... or just provide a one shot New

A two-step API (similar to the existing GCM API) has significantly worse performance. On my M1 it's about 12 cycles per byte instead of ~1. You can see this in the CL I sent—the 'generic' implementation (the purego build tag) uses crypto/aes and is effectively a two-step API.

With a two-step API there is also the chance that somebody uses a different block cipher, which wouldn't be AES-GCM-SIV. 😄

However, it would let somebody use, e.g., a hardware AES encryptor. But, in my experience having to support hardware encryptors, it's unlikely somebody will want to use it piecemeal like that.

I guess there is also a question about if this makes sense to put in x/crypto, or in the standard library

I originally asked for x/crypto because I figured it would be easier for it to get accepted. But I do think that the standard library is the better choice.

rsc commented 1 year ago

@FiloSottile and I discussed and we think we can make this fit the existing AEAD interface with two different constructors: one returns an AEAD that hides the nonce entirely, and the other returns one giving user control over the nonce, for use in protocols that need to do that.

ericlagergren commented 1 year ago

@rsc what is your proposed API?

rsc commented 1 year ago

I'm going to let @FiloSottile comment when he's got it written up.

FiloSottile commented 1 year ago

I would love to clean up the AEAD APIs at some point, but for now in the spirit of not blocking new features on v2 APIs, it would probably make most sense to put GCM-SIV next to GCM, for discoverability. In particular, I would like not to put it next to aes.NewCipher as I don't want to put the good thing next to the thing that must never be used directly.

One-step or two-step doesn't really make a performance difference, because in practice we already pierce the interface and delegate to a dedicated crypto/aes implementation in NewGCM, and we can do the same in NewGCMSIV. We can also document that NewGCMSIV returns an error if passed anything else than a crypto/aes cipher.Block.

I propose we just mimic GCM for now, and leave all the cleanup (no more two-step, maybe returning concrete types, etc.) for v2. One thing I do want to try, which came up with @rsc, is trying to improve the nonce UX (which always confuses users) within the current AEAD API by pretending the nonce size is zero, and generating it at random, which we can do with AES-GCM-SIV. (This might be worth doing for XChaCha20Poly1305, too.)

package crypto/cipher

// NewGCMSIV returns an AES-GCM-SIV AEAD instance.
// cipher must be created by aes.NewCipher, or NewGCMSIV will return an error.
// The AEAD has NonceSize zero, and the nonce is automatically generated at random
// and prefixed to the ciphertext by Seal, and extracted by Open.
// The combined Overhead (nonce and tag) is 28 bytes.
func NewGCMSIV(cipher Block) (AEAD, error)

// NewGCMSIVWithNonce returns an AES-GCM-SIV AEAD instance.
// cipher must be created by aes.NewCipher, or NewGCMSIVWithNonce will return an error.
// The nonce must be manually managed by the application, and can be generated at random.
func NewGCMSIVWithNonce(cipher Block) (AEAD, error)

This API has the annoying property of making crypto/cipher (and/or crypto/aes) depend on crypto/rand, which unfortunately depends on math/big. Maybe we should just move the actual RNG to crypto/internal/rand, and avoid that chain in other packages which default to crypto/rand, too. (I wish we made all GenerateKey functions not even take a Reader and read from crypto/rand, but that's for another v2.)

ericlagergren commented 1 year ago

That sounds good to me. I’ll send a new CL then.

rsc commented 1 year ago

We should definitely move the actual generator to a crypto/internal/rand to avoid a math/big dependency from crypto/cipher or crypto/aes.

rsc commented 1 year ago

Using https://github.com/golang/go/issues/54364#issuecomment-1642676993, have all remaining concerns been addressed?

magical commented 1 year ago

Are the two constructors compatible with each other; e.g. can one side encrypt with the random nonce API and the other side decrypt with the explicit API?

var key = []byte{...}
block, err := aes.NewCipher(key)
if err != nil { panic(err) }

a, err := cipher.NewGCMSIV(block)
if err != nil { panic(err) }

nonceAndCiphertext := a.Seal(nil, nil, []byte("hello"), nil)

nonce := nonceAndCiphertext[:12]
ciphertext := nonceAndCiphertext[12:]

b, err := cipher.NewGCMSIVWithNonce(block)
if err != nil { panic(err) }

plaintext, err := b.Open(nil, nonce, ciphertext, nil)

if err != nil {
  fmt.Println("decryption failed")
} else {
  fmt.Println(string(plaintext))
}
ericlagergren commented 1 year ago

Are the two constructors compatible with each other; e.g. can one side encrypt with the random nonce API and the other side decrypt with the explicit API?

var key = []byte{...}
block, err := aes.NewCipher(key)
if err != nil { panic(err) }

a, err := cipher.NewGCMSIV(block)
if err != nil { panic(err) }

nonceAndCiphertext := a.Seal(nil, nil, []byte("hello"), nil)

nonce := nonceAndCiphertext[:12]
ciphertext := nonceAndCiphertext[12:]

b, err := cipher.NewGCMSIVWithNonce(block)
if err != nil { panic(err) }

plaintext, err := b.Open(nil, nonce, ciphertext, nil)

if err != nil {
  fmt.Println("decryption failed")
} else {
  fmt.Println(string(plaintext))
}

I would assume so. That’s how I’m implementing it, anyway.

magical commented 1 year ago

I would think so too, but i wanted to check. I imagine that this sort of use would be common when implementing protocols that want a random nonce and already have a specific place for it in their message format, not necessarily as a prefix of the ciphertext.

FiloSottile commented 1 year ago

The two APIs would be compatible with each other, but applications that need to separate the nonce I expect would just use NewGCMSIVWithNonce on both sides.

rsc commented 1 year ago

Based on the discussion above, this proposal seems like a likely accept. — rsc for the proposal review group

gopherbot commented 1 year ago

Change https://go.dev/cl/516278 mentions this issue: crypto: implement POLYVAL

ericlagergren commented 1 year ago

@FiloSottile do you want me to implement BoringSSL as well? It's not FIPS, of course.

ericlagergren commented 1 year ago

I don't think NewGCMSIV is (exactly) compatible with AEAD. Its Seal and Open methods require dst and plaintext/ciphertext to overlap entirely, or not at all. But because we're prepending a nonce, there will always be an overlap if len(input) >= 12. For example: https://go.dev/play/p/luGBvr4a2s3

Of course, we can work around this by making a copy of the input block(s) being processed, but this has some drawbacks:

  1. We end up copying 2x as many bytes as before.
  2. It complicates the assembly implementation.
  3. It precludes encrypting N blocks at a time.
  4. I'm not sure how it affects the interleaved (single pass) implementation.

We could always just have a slow path for that degenerate case. But then there would be a surprising performance cliff for users who are already likely concerned about performance by reusing the input.

ericlagergren commented 1 year ago

Assuming I'm not missing an obvious way of getting this working, my two cents is that we should implement out the manual nonce version now and save the automatic nonce API for v2.

rsc commented 1 year ago

Ping @FiloSottile for thoughts.

rsc commented 1 year ago

This proposal has been added to the active column of the proposals project and will now be reviewed at the weekly proposal review meetings. — rsc for the proposal review group

FiloSottile commented 1 year ago

@ericlagergren that's a good observation, but I think it can be handled as an implementation concern.

In Open it's not a problem, the rule is perfect overlap or none because it's the easier thing to document and enforce, but the actual thing the assembly usually needs is "output pointer is <= input pointer" and that's true for Open with a nonce.

In Seal we do have to write 12 bytes ahead of where we are reading, but that's less than a block, we can totally do it with a little extra complexity, by reading one block ahead and keeping it around in registers. Might turn out almost free. It would be nice if the API didn't force this, and v2 can be nicer, but I don't think it's a reason not to implement a safer API. A dramatically performance-sensitive user can use NewGCMSIVWithNonce.

rsc commented 1 year ago

With @FiloSottile's response, are there any remaining concerns with the API in https://github.com/golang/go/issues/54364#issuecomment-1642676993?

ericlagergren commented 1 year ago

I agree with Filippo. Go is long overdue for MRAE. I might not implement N-wide assembly for the random nonce API, though. But we can chat about that on the CL.

edit: goofy email formatting

rsc commented 1 year ago

Based on the discussion above, this proposal seems like a likely accept. — rsc for the proposal review group

rsc commented 1 year ago

No change in consensus, so accepted. 🎉 This issue now tracks the work of implementing the proposal. — rsc for the proposal review group

The proposal details are as follows.

In crypto/cipher, we add the following new API:

package crypto/cipher

// NewGCMSIV returns an AES-GCM-SIV AEAD instance.
// cipher must be created by aes.NewCipher, or NewGCMSIV will return an error.
// The AEAD has NonceSize zero, and the nonce is automatically generated at random
// and prefixed to the ciphertext by Seal, and extracted by Open.
// The combined Overhead (nonce and tag) is 28 bytes.
func NewGCMSIV(cipher Block) (AEAD, error)

// NewGCMSIVWithNonce returns an AES-GCM-SIV AEAD instance.
// cipher must be created by aes.NewCipher, or NewGCMSIVWithNonce will return an error.
// The nonce must be manually managed by the application, and can be generated at random.
func NewGCMSIVWithNonce(cipher Block) (AEAD, error)

We will move the randomness generation from crypto/rand to crypto/internal/rand so that crypto/cipher can import crypto/internal/rand and avoid crypto/rand’s dependency on math/big. We should add a specific rule in deps_test.go ensuring that crypto/cipher does not depend on math/big.

gopherbot commented 1 year ago

Change https://go.dev/cl/538395 mentions this issue: crypto/rand: move CSPRNG to crypto/internal/rand

Ratio2 commented 1 week ago

@ericlagergren looks like the patch needs to be updated due to merge conflicts https://go.dev/cl/538395

ericlagergren commented 1 week ago

@ericlagergren looks like the patch needs to be updated due to merge conflicts https://go.dev/cl/538395

Yes. I think it's prudent to wait until the FIPS changes have settled and stabilized. And also idk if @FiloSottile will have time to review it right now with all the other crypto changes. (Lmk if you disagree with either of those, Filippo.)

FiloSottile commented 1 week ago

Yeah, sorry for the review lag, but it'd be best to land this after this round of FIPS changes. We're trying to keep GCM-SIV in mind to accomodate it in the structure of the new internal packages.