search

golang / go

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

crypto: import fiat-crypto implementations #40171

Open mdempsky opened 4 years ago

mdempsky commented 4 years ago

The fiat-crypto project (https://github.com/mit-plv/fiat-crypto) generates formally-verified, high-performance modular arithmetic implementations, useful for crypto primitives like Curve25519, Poly1305, and the NIST ECC curves that are used within the Go standard library. They're currently working on a Go backend.

BoringSSL has imported their implementations for Curve25519 and P-256: https://boringssl.googlesource.com/boringssl/+/master/third_party/fiat/

At https://go-review.googlesource.com/c/crypto/+/242177, I've uploaded a WIP CL that imports their Curve25519 implementation (w/ minor tweaks), and demonstrates a significant performance improvement over the current "generic" implementation. (The existing amd64 assembly implementation is still considerably faster though.)

This proposal is to import and make use of those implementations.

Open questions:

  1. Which algorithms should be imported? BoringSSL only imports two. Should we import more?

  2. Do we import both 32-bit and 64-bit implementations? We could import just one implementation and still get a performance speedup (e.g., 386 sees a -10% performance boost with curve25519_fiat_64.go, and amd64 sees a -30% boost with curve25519_fiat_32.go), but they do better still with the CPU-appropriate implementations (-30% for 386 w/ 32-bit, and -61% for amd64 w/ 64-bit).

  3. How should the code be imported? E.g., should it be separated into a third_party or vendor directory with its own LICENSE file like how BoringSSL does it?

/cc @agl @FiloSottile

mdempsky commented 4 years ago

fiat-crypto's 64-bit P-224 implementation is about 2x as fast as Go's existing portable, constant-time P-224 implementation on amd64. Their 32-bit implementation is about the same speed on 386.

I expect P-256 will be similar to Curve25519 (i.e., existing assembly implementations are faster, but still worth measuring), but using fiat-crypto for P-384 and P-521 should be both much faster and provide a constant-time implementation (unlike the current, generic math/big code).

mdempsky commented 4 years ago

@agl @FiloSottile Ping.

While here, I'll point out the fiat-crypto implementation also speeds up curve25519 on ppc64le:

name               old time/op   new time/op   delta
ScalarBaseMult-32    152µs ± 1%     92µs ± 4%  -39.82%  (p=0.000 n=17+20)

name               old speed     new speed     delta
ScalarBaseMult-32  210kB/s ± 0%  347kB/s ± 2%  +65.27%  (p=0.000 n=17+17)

(I don't have any ARM workstations to readily benchmark on.)

rsc commented 4 years ago

I do have some concerns about adding new license notice requirements in the libraries, because those transitively apply to every Go binary anyone builds (that imports net/http at least).

I would feel much more comfortable about this if we could get the code contributed under CLA so that the Go license notice would cover it.

mdempsky commented 4 years ago

@JasonGross Do you think we can get fiat-crypto's Go code contributed under Google's CLA? The normal process is documented at https://golang.org/doc/contribute.html#cla.

rsc commented 4 years ago

Ping @JasonGross. We'd be happy to use this code but don't want to impose new notice requirements on every Go binary.

JasonGross commented 4 years ago

Ah, sorry, I meant to follow up on this earlier. As discussed on https://github.com/openssl/openssl/pull/12201#discussion_r472664494, MIT unfortunately doesn't permit signing CLAs on projects that it holds copyright to. :-/

rsc commented 4 years ago

@JasonGross, thanks for replying. I certainly understand MIT not wanting to complete CLAs.

An alternative solution to our problem of imposing new notice requirements on every Go binary would be if the generator outputs could be licensed under a non-attribution license such as MIT-0 or a source-code-attribution-only license such as BSD-1-Clause.

Do you think that is a possibility?

JasonGross commented 4 years ago

That seems quite likely. Let me chat with me colleagues and see if it's feasible.

rsc commented 4 years ago

Thanks very much.

JasonGross commented 4 years ago

@rsc We're in the process of re-licensing under user's choice, MIT OR BSD-1-Clause. However, it seems that BSD-1-Clause is not listed under https://pkg.go.dev/license-policy, even though MIT-0 and BSD-0-Clause are. Is this an oversight? Will BSD-1-Clause in fact be sufficient?

ianlancetaylor commented 4 years ago

BSD-1-clause should be fine for our purposes. Thanks very much for tackling this.

I don't know why it's not listed in pkg.go.dev. Maybe it's just not very common. CC @jba .

jba commented 4 years ago

Looking into it.

rsc commented 4 years ago

BSD-1-Clause will be fine, thanks.

rsc commented 4 years ago

Based on the discussion above, this seems like a likely accept.

JasonGross commented 4 years ago

I've gotten approval from everyone and have prepared https://github.com/mit-plv/fiat-crypto/pull/881. Hopefully we'll get it merged in the next couple of days.

JasonGross commented 4 years ago

The code has now been relicensed under MIT OR BSD-1-Clause OR Apache-2.0

ianlancetaylor commented 4 years ago

Thanks!

rsc commented 4 years ago

Thanks so much @JasonGross!

Accepted.

FiloSottile commented 4 years ago

Thank you @JasonGross and everyone! Excited for this to move forward.

We can start by importing the P-384 and P-521 implementations, which currently are bad enough that they'd get the most benefit, and then move to the other fields.

The next step is figuring out a reproducible process to generate the code, and get the output clean enough to pass code review (so we are not tied forever to the code generator, if need be). Happy to help with that in the coming weeks.

mmcloughlin commented 4 years ago

Regarding code generation from fiat-crypto, ecckiila might be useful to look at. This was used for P-384 and P-521 in NSS 3.55.

JasonGross commented 4 years ago

Note, by the way, that we currently test our Rust Crate on our CI against crypto tests in Dalek, and we test our generated C code against BoringSSL tests. Currently our Go CI only checks that the code compiles, but we'd love to extend it with any sort of integration tests you think might make sense.

Note also that if you want to include the code generator in your process (rather than just fetching our checked-in generated code), our CI is probably a pretty decent place to start, as we regenerate all the code from scratch on every CI run to make sure that we're aware of any changes to the generated code.

And, of course, I'm happy to help with and support any changes you want made to the generated code itself.

odeke-em commented 3 years ago

I am kindly moving this to Go1.17, as there hasn’t been much action since October 2020.

mdempsky commented 3 years ago

Since Go 1.17 development should be opening up again in the near future, it seems like a good time to discuss how to move forward here.

Would it make sense for the fiat-crypto project to provide a Go module that can be vendored into the standard library, analogous to the rust crate they provide? Or is it preferred for the Go project to own running the generators and checking in the generated code somewhere?

JasonGross commented 3 years ago

If the deployment of the Go module can be automated in the way the Rust crate currently is, I'm happy to merge a PR that does that (and do any additional registration steps necessary).

mdempsky commented 3 years ago

@JasonGross I think it would just require creating a go.mod file (e.g., go mod init github.com/mit-plv/fiat-crypto/fiat-go/src in your fiat-go/src directory), and then users can just import "githtub.com/mit-plv/fiat-crypto/fiat-go/src" and the Go command knows how to fetch your source.

It would require that the code directory is buildable with go build ./... though. Currently, https://github.com/mit-plv/fiat-crypto/tree/master/fiat-go/src has source files from a bunch of different Go packages grouped together (e.g., curve25519_32.go is package fiat_25519, but p224_32.go is fiat_p224). Is it reasonable to split those into separate subdirectories for each package? Alternatively, generating them all in the same package (e.g., package fiat) is probably fine too, as the linker can easily omit any unused code.

One last detail is the APIs need to be exported from the package (i.e., start with an uppercase letter), at least the functionality expected to be used by end users. Conventionally, Go uses mixed caps identifiers (e.g., MixedCaps or mixedCaps). There's typically some leeway allowed for generated code (esp. since this package probably wouldn't be used directly by end users, but instead via higher-level standard library APIs), but to the extent that it's possible to reasonably follow those conventions, I think that would be appreciated.

Happy to chat further if you have more questions. Also, @FiloSottile may have more opinions on how this should be integrated, as owner of Go's crypto packages.

JasonGross commented 3 years ago

I'm nearly done with a PR to adjust the casing conventions. Two questions there: What's the convention for package names? Is the convention for type identifiers the same as for function identifiers?

I'm not sure what to do about the packages, though. In particular, right now the 32-bit and 64-bit implementations have identical identifier names, but live in different file names. (This is useful, for example, in C, where you can just #include a different file depending on the machine architecture and otherwise write the same code.) I'm happy to either put everything in the same package, or put everything in directories according to the package (does the directory have to be named identically to the package?), whichever is desired.

JasonGross commented 3 years ago

@mdempsky Could you review https://github.com/mit-plv/fiat-crypto/pull/907 and let me know if the name adjustments seem good?

egonelbre commented 3 years ago

@JasonGross few things that stood out to me:

egonelbre commented 3 years ago

PS: it's worthwhile to wait for @mdempsky-s comments, since he has probably a better vision how to integrate this than me.

mdempsky commented 3 years ago

@JasonGross Thanks, I'll comment on that PR.

JasonGross commented 3 years ago

https://github.com/mit-plv/fiat-crypto/pull/907 has been merged, so things like import "github.com/mit-plv/fiat-crypto/fiat-go/32/curve25519" should work now. Out of curiosity, what does vendoring the module into the Go standard library look like / consist of?

mdempsky commented 3 years ago

@JasonGross Thanks!

It looks like https://pkg.go.dev/github.com/mit-plv/fiat-crypto/fiat-go/32/curve25519 is confused about the license though. I'm guessing because the fiat-crypto repo doesn't contain any of the files mentioned in https://pkg.go.dev/license-policy. Do you think you could rename the COPYRIGHT file to COPYING? Then hopefully licensecheck will approve it.

As for vendoring, it just amounts to copying snapshots of Go module sources into the Go project's repo for redistribution. You can see the Go modules that are currently vendored at https://github.com/golang/go/tree/master/src/vendor and https://github.com/golang/go/tree/master/src/cmd/vendor. I don't think there's any action you'll need to take there.

JasonGross commented 3 years ago

I'm guessing the actual issue is that the licensing files are at the project root rather than at the root of the fiat-go directory, given that https://pkg.go.dev/license-policy claims to discover licenses in LICENSE-APACHE and LICENSE-MIT, both of which we have. If this doesn't work (how do I get https://pkg.go.dev/github.com/mit-plv/fiat-crypto/fiat-go to bump the version to the latest commit?), I'm happy to try renaming COPYRIGHT to COPYING, though note that this may not be enough, as we release under "MIT OR Apache-2.0 OR BSD-1-Clause", and GitHub, for example, does not recognize this SPDX expression (crates.io, on the other hand, does seem to support "OR", and I cannot tell whether or not https://github.com/google/licensecheck supports multiple licenses / how it handles this case.

JasonGross commented 3 years ago

As for vendoring, it just amounts to copying snapshots of Go module sources into the Go project's repo for redistribution. You can see the Go modules that are currently vendored at https://github.com/golang/go/tree/master/src/vendor and https://github.com/golang/go/tree/master/src/cmd/vendor. I don't think there's any action you'll need to take there.

Sounds good! Do updates to the snapshots happen automatically? On some schedule?

mdempsky commented 3 years ago

I'm guessing the actual issue is that the licensing files are at the project root rather than at the root of the fiat-go directory, given that https://pkg.go.dev/license-policy claims to discover licenses in LICENSE-APACHE and LICENSE-MIT, both of which we have.

Hm, good point. I also wonder if it's getting confused because of multiple licenses. I've filed #44758 to look into this.

At least I don't think this should be blocking for being able to actually use fiat-go. It just prevents being able to see the documentation via the pkg.go.dev interface. I think it's a good sign that it fetched the module at all.

how do I get https://pkg.go.dev/github.com/mit-plv/fiat-crypto/fiat-go to bump the version to the latest commit?

Sorry, I'm not sure. I think it periodically refreshes. I'm not sure how often.

Do updates to the snapshots happen automatically? On some schedule?

They're done manually. Usually shortly before each release, and then as needed/appropriate for development between releases.

Do you think that should work for fiat-go too? What's the process been like for providing code to other projects?

mdempsky commented 3 years ago

And just as I post that last comment, it looks like pkg.go.dev updated, and it does recognize the license now: https://pkg.go.dev/github.com/mit-plv/fiat-crypto/fiat-go@v0.0.0-20210303142032-cc0899379641/32/curve25519

josharian commented 3 years ago

The 1.17 window is closing soon. I'm excited about seeing this go in. What's the current status and next steps?

gopherbot commented 3 years ago

Change https://golang.org/cl/314889 mentions this issue: curve25519: use fiat-go

mdempsky commented 3 years ago

@josharian Are there any primitives in particular that you're interested in? Filippo and I are looking at importing a few implementations -- I've got curve25519 working, and he's looking at P-384 and P-521.

josharian commented 3 years ago

curve25519, blake2s, and chacha20poly1305

cc @zx2c4

mdempsky commented 3 years ago

@josharian Thanks. fiat-crypto currently only implements primitives for elliptic curves, so curve25519 of that list. amd64 already has fast assembly code for curve25519, but CL 314889 may help on arm/arm64 (or any other non-amd64 CPUs).

FiloSottile commented 3 years ago

One could also use fiat-crypto for Poly1305, although we already have decent specialized code for it.

mdempsky commented 3 years ago

Oops, right. I figured fiat-crypto could theoretically generate poly1305 code, but didn't realize they already do; list of available primitives here: https://github.com/mit-plv/fiat-crypto/tree/master/fiat-go/64

I suspect fiat-crypto for poly1305 could help 32-bit CPUs, but probably not much (if any) for 64-bit CPUs.

josharian commented 3 years ago

Yeah, my main interest is arm64. :) Any chance of getting CL 314889 in?

mdempsky commented 3 years ago

@josharian It's out for review at the moment. I think it should be able to make it.

Also, if you're able to benchmark it on arm64, I think that would be handy. (I only have convenient access to 386, amd64, and ppc64le.)

FiloSottile commented 3 years ago

Based on a bit of experimentation, it looks like these would be the implementations that we'd benefit the most from importing:

Less likely to be worth importing are:

Am I missing any? Does that sound like a good categorization?

armfazh commented 3 years ago

What about the scalar fields of P-256 and friends?

FiloSottile commented 3 years ago

What about the scalar fields of P-256 and friends?

Good question!

As far as I can remember, the only place where we do scalar field arithmetic with P curves is in crypto/ecdsa, where we use straight big.Int unless the curve has a custom Inverse(k *big.Int) *big.Int, which only P-256 on amd64, arm64, and s390x do.

Really, what we need is a whole new API for NIST curves, one that doesn't use big.Int and provides scalar fields, but until then it's not easy to find a place to import those implementations to. When we get there, we should use fiat to implement those fields.

FiloSottile commented 3 years ago

I misread some build tags, P-256 has a constant time generic fallback implementation, so not a high priority, probably.

gopherbot commented 3 years ago

Change https://golang.org/cl/315274 mentions this issue: crypto/elliptic: make P-521 scalar multiplication constant time