Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

crypto: document non-constant time arithmetic #16821

Closed
pyramids opened this issue Aug 21, 2016 · 8 comments
Closed

crypto: document non-constant time arithmetic #16821

pyramids opened this issue Aug 21, 2016 · 8 comments
Assignees
Milestone

Comments

@pyramids
Copy link

@pyramids pyramids commented Aug 21, 2016

  1. What did you expect to see?

    Constant-time arithmetic (and no data-dependent slice or array indexing) for all cryptographic operations to foil timing side-channel attacks. EDIT: Implementation of constant-time primitives in a similarly caution-inspiringly named package as crypto/subtle.

  2. What did you see instead?

    Use of non-constant time multiplications in https://github.com/golang/go/blob/master/src/math/big/nat.go (used via math/big for example by crypto/elliptic and crypto/rsa). EDIT: Primitives for constant-time comparisons only (but not for other bignum operations) in crypto/subtle.

This is a security issue that should either be documented (if the authors feel it can be ignored, to explain why and how) or addressed by changing the code appropriately.

@cespare
Copy link
Contributor

@cespare cespare commented Aug 21, 2016

/cc @agl

@bradfitz bradfitz changed the title Non-constant time arithmetic in crypto crypto: non-constant time arithmetic Aug 21, 2016
@bradfitz bradfitz added this to the Go1.8Maybe milestone Aug 21, 2016
@griesemer griesemer modified the milestones: Go1.8Maybe, Unplanned Aug 22, 2016
@griesemer
Copy link
Contributor

@griesemer griesemer commented Aug 22, 2016

We certainly can't change the implementation in the near-term - there's too much to change and it's subtle. I let @agl weigh in regarding the need to do so in the first place (or not).

Putting milestone back as far as documentation is concerned.

@griesemer griesemer modified the milestones: Go1.8Maybe, Unplanned Aug 22, 2016
@pyramids
Copy link
Author

@pyramids pyramids commented Aug 22, 2016

#11499 (@agl) claims some elliptic curves (P-224 and the important P-256) do have constant-time implementations in Go (and that, in the context of TLS, others don't really pose a security risk for current certificate practice).

That contradicts my current best guess, as I see math/big used at least occasionally, even in P-256 (https://github.com/golang/go/blob/master/src/crypto/elliptic/p256.go). Math/big normalizes numbers and hence occasionally even truncates away the leading (most significant) word(s) if they are zero, which certainly cannot be constant-time. So far, I would have missed it though, if all of these usages happen to be safe for P-224 and P-256.

Documentation sounds like a very good idea---wouldn't it be good to somehow warn users that at least all elliptic curves other than P-224 and P-256 (and similarly at least generic RSA?) isn't constant-time in Go? Even users who don't stumble across #11499 (or this issue) by pure chance, maybe? Not every project limits itself to using crypto only for TLS; see theupdateframework/notary#94 for nearly having tricked one into making itself unsafer by expanding to other curves.

Of course, a plan to make all this constant-time would be even better from my point of view!

@agl
Copy link
Contributor

@agl agl commented Aug 22, 2016

I've been noting this issue for a long time. I don't mind noting it more strongly if it'll have any effect. Briefly, off the top of my head:

RSA, DSA, DH: none are constant time because math/big isn't.
P-224 and P-256: the interface involves math/big but, apart from the import/export, should be CT.
P-521: not CT as it uses big/math.
AES: generic code uses T-tables, so not CT. amd64 with AESNI is safe though.
GHASH: has tables too, so no. amd64 with AESNI is safe though.

@pyramids
Copy link
Author

@pyramids pyramids commented Aug 22, 2016

Thank you. So what's to be done? Do you feel more CT code would be desirable?

I failed to see any note about CT/non-CT behavior in ECDSA, having turned to https://godoc.org for crypto, crypto/elliptic, crypto/ecdsa and finally the generic (non-P-224/P-256) sources.

I hadn't looked at godoc for crypto/rsa, where I now realize that at least the attribute "constant time" is used indeed and hence, by contrast, might have allowed the inference that other aspects not marked like that are not necessarily CT.

From the point of view of a user: Would it be too much to ask for a warning in the docs, rather than something to be inferred from a seemingly irrelevant sublibrary? Where should I have looked, BTW?

@quentinmit quentinmit added the NeedsFix label Oct 10, 2016
@rsc
Copy link
Contributor

@rsc rsc commented Oct 20, 2016

I sent CL 31573.

@agl, not sure about P-384 nor where to put the comment about DH.

@gopherbot
Copy link

@gopherbot gopherbot commented Oct 20, 2016

CL https://golang.org/cl/31573 mentions this issue.

@rsc rsc modified the milestones: Go1.8, Go1.8Maybe Nov 11, 2016
@rsc rsc changed the title crypto: non-constant time arithmetic crypto: document non-constant time arithmetic Nov 11, 2016
@bradfitz bradfitz assigned rsc and unassigned agl Dec 1, 2016
@bradfitz
Copy link
Contributor

@bradfitz bradfitz commented Dec 1, 2016

Reassigning to @rsc, as @agl has replied on https://go-review.googlesource.com/c/31573/

@gopherbot gopherbot closed this in 850e55b Dec 7, 2016
@golang golang locked and limited conversation to collaborators Dec 7, 2017
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
8 participants
You can’t perform that action at this time.