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/ed25519: Implement Ed25519ph #31804

Closed
titanous opened this issue May 2, 2019 · 36 comments
Closed

crypto/ed25519: Implement Ed25519ph #31804

titanous opened this issue May 2, 2019 · 36 comments
Assignees
Labels
FeatureRequest NeedsFix The path to resolution is known, but the work has not been done. Proposal Proposal-Accepted Proposal-Crypto Proposal related to crypto packages or other security issues Proposal-FinalCommentPeriod
Milestone

Comments

@titanous
Copy link
Member

titanous commented May 2, 2019

Update, Apr 6 2022: The proposed API is in #31804 (comment).


The Ed25519ph variant specified in RFC 8032 allows signing/verifying a message that has already been hashed with SHA-512 without risking the collision-resistant properties of "PureEdDSA" when using the same keys for messages signed using both schemes.

This is useful in at least two scenarios:

  1. When the private key is isolated to another piece of hardware and passing the entire message to be signed is not possible, for example when using a HSM and signing messages larger than a few KB.
  2. When working with large messages that are too large to be reasonably buffered for the current one-shot API.

This variant can be implemented minimally using the existing crypto.Signer API plus an additional verification function, without encouraging unsafe use by providing easy access to an API that takes an io.Reader or io.Writer.

Due to the additional internal hash initialization, there is no way to implement this without forking the package or upstreaming an implementation patch.

I will send a CL with a proposed implementation.

Relevant: #31727

/cc @zx2c4 @FiloSottile

@gopherbot
Copy link

Change https://golang.org/cl/174941 mentions this issue: ed25519: Implement Ed25519ph

@x30n
Copy link

x30n commented Jul 22, 2019

+1

@Hades32
Copy link

Hades32 commented Jul 26, 2019

Thanks @titanous , this is just what we needed. Confirmed to behave as the reference implementation (libsodium). 👍

Not sure if this is still in time for 1.13... @FiloSottile

@FiloSottile FiloSottile added the NeedsFix The path to resolution is known, but the work has not been done. label Jul 26, 2019
@FiloSottile FiloSottile modified the milestones: Unreleased, Go1.14 Jul 26, 2019
@FiloSottile FiloSottile changed the title x/crypto/ed25519: Implement Ed25519ph crypto/ed25519: Implement Ed25519ph Jul 26, 2019
@FiloSottile
Copy link
Contributor

FiloSottile commented Jul 26, 2019

Too late for Go 1.13, targeting Go 1.14. (crypto/ed25519 is now in the standard library.)

@Yawning
Copy link

Yawning commented Sep 19, 2019

While I understand that the crypto.Signer interface is fixed in stone and can't be changed, if this is going to happen, it would be nice if it supported the full Ed25519ph algorithm as described in the RFC.

As it stands right now, the proposed implementation does not support a domain separation context.

Since there already is a Sign method in the package, and the PR adds VerifyHashed, this could be done by adding SignHashed(privateKey PrivateKey, context, message []byte) []byte and changing the proposed VerifyHashed to take another byte slice.

@FiloSottile
Copy link
Contributor

FiloSottile commented Oct 1, 2019

RFC 8032 defined context independently of pre-hashing, so to support the whole spec we'd also have to support pure Ed25519 with custom context.

I am really not a fan of extending the API surface of a standard library package that should be what we point users to for basic public key signatures. How about this alternative API, which is more extensible and still makes it very opt-in to select the variants?

// Options can be used with PrivateKey.Sign or VerifyWithOptions
// to select Ed25519 variants.
type Options struct {
    // Hash can be zero for regular Ed25519, or crypto.SHA512 for Ed25519ph.
    Hash    crypto.Hash
    Context string
}

func (*Options) HashFunc() crypto.Hash

func VerifyWithOptions(publicKey PublicKey, message, sig []byte, opts *Options) bool

@Yawning
Copy link

Yawning commented Oct 1, 2019

If this proposed API is accepted, then VerifyHashed as proposed in the PR will go away right? I would be in favor of this, since it seems like a cleaner way to support the functionality.

Nitpicking: Is there any particular reason why Context is a string over []byte? I understand they are fairly interchangeable (and string may be more const friendly). I personally would make it a []byte to make it clear that it is an arbitrary "octet string of at most 255 octets" (and include the size limit in a doc string comment).

@FiloSottile
Copy link
Contributor

If this proposed API is accepted, then VerifyHashed as proposed in the PR will go away right? I would be in favor of this, since it seems like a cleaner way to support the functionality.

Yep.

Nitpicking: Is there any particular reason why Context is a string over []byte? I understand they are fairly interchangeable (and string may be more const friendly). I personally would make it a []byte to make it clear that it is an arbitrary "octet string of at most 255 octets" (and include the size limit in a doc string comment).

Mostly consistency, we've used string for contexts elsewhere, in some cases to make it a different type from the message itself (which is not relevant here). I personally think it fits better the nature of the value, because it's usually fixed or at least immutable, often human-readable, and as you say can be a const.

We should definitely document the max length, thank you.

@Yawning
Copy link

Yawning commented Oct 3, 2019

I went and implemented this in a package I maintain for dayjob (because dayjob needs ph-with-context support), and have more feedback.

What should happen when Hash is crypto.Hash(0) and Context is ""?

  1. Ed25519ctx with a 0 octet context ("The context input SHOULD NOT be empty.").
  2. Ed25519pure

I went with option 2 as option 1 is somewhat nonsensical and recommended against, though I will happlily change the package to match what the runtime library does. If Context were a byte, this could be disambiguated by nil vs []byte{}, but it's not clear to me if that justifies the loss of consistency and const friendliness, just for the sake of completeness.

Minor: I used opts crypto.SignerOpts for VerifyWithOptions so that it is possible to pass crypto.SHA512 when the context is not required (following PublicKey.Sign). The type naming is somewhat unfortunate, but the ease of use for what I suspect is a common case probably wins out.

@FiloSottile
Copy link
Contributor

What should happen when Hash is crypto.Hash(0) and Context is ""?

  1. Ed25519ctx with a 0 octet context ("The context input SHOULD NOT be empty.").
  2. Ed25519pure

I went with option 2 as option 1 is somewhat nonsensical and recommended against, though I will happlily change the package to match what the runtime library does. If Context were a byte, this could be disambiguated by nil vs []byte{}, but it's not clear to me if that justifies the loss of consistency and const friendliness, just for the sake of completeness.

Yeah, definitely pure if Context is "", the alternative is confusing and not something people should do anyway, but we should document it. I am also not a fan of semantic differences between nil and []byte{} in general.

Minor: I used opts crypto.SignerOpts for VerifyWithOptions so that it is possible to pass crypto.SHA512 when the context is not required (following PublicKey.Sign). The type naming is somewhat unfortunate, but the ease of use for what I suspect is a common case probably wins out.

I thought about that, but I think I'd rather use the concrete type for a few reasons:

  • you can't actually semantically use any other crypto.SignerOpts here, the reason Sign has it is to match an interface which needs the abstraction, VerifyWithOptions has no semantic justification
  • Ed25519ph is not something we need to encourage and make easy, so having to explicitly use Options seems fine
  • interface boxing still causes heap escapes, I think

@odeke-em
Copy link
Member

Thank you for mailing CL 174941 @titanous, unfortunately that didn't make it into the cut before the Go1.14 freeze, but please rebase from master and we'll hopefully get this in for Go1.15. Apologies for lack of eyes on it during Go1.14.

@armfazh
Copy link

armfazh commented Jul 3, 2020

I think this is wrong,

If opts.HashFunc() is crypto.SHA512, the pre-hashed variant Ed25519ph
is used and message is expected to be a SHA-512 hash,

the prehashed mode must do the job internally, i.e. explicitly hashing the (likely to be large) message with SHA-512.
Otherwise, there is no guarantee that the hashed message was generated by SHA-512, it could be generated with another hash function that also outputs the same number of bytes.

@titanous
Copy link
Member Author

titanous commented Jul 9, 2020

the prehashed mode must do the job internally, i.e. explicitly hashing the (likely to be large) message with SHA-512.
Otherwise, there is no guarantee that the hashed message was generated by SHA-512, it could be generated with another hash function that also outputs the same number of bytes.

That is not how the crypto.Signer API works. You are expected to hash the message before calling Sign if a hash function option is specified. For example, look at how the ecdsa package does it.

@armfazh
Copy link

armfazh commented Jul 10, 2020

That is not how the crypto.Signer API works.
You are expected to hash the message before calling Sign if a hash function option is specified. For example, look at how the ecdsa package does it.

Of couse doesn't work like that because crypto.Signer doesn't take into account the use of prehashed signature schemes. Ed25519Ph is one of them, as it prehashes the message internally using always SHA-512.

I acknowledge the lack of a Signer Go interface that handles the new signature schemes for example those in RFC-8032, which enable prehashing and receive domain separation strings as input.

@cristaloleg
Copy link

@FiloSottile kindly ping, looks like 1 small comment in left on your CL.

@FiloSottile
Copy link
Contributor

@cristaloleg this is waiting for the @golang/proposal-review committee, the CL is effectively ready.

@rsc rsc moved this from Incoming to Active in Proposals (old) May 4, 2022
@rsc
Copy link
Contributor

rsc commented May 4, 2022

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
Copy link
Contributor

https://go.dev/cl/373076 is ready ✨

@gopherbot
Copy link

Change https://go.dev/cl/404274 mentions this issue: crypto/ed25519: implement Ed25519ctx and Ed25519ph with context

@rsc
Copy link
Contributor

rsc commented May 11, 2022

This was discussed a bit before being added to the minutes, and the comments have been uniformly positive. Does anyone object to adding this API? (#31804 (comment))

@armfazh
Copy link

armfazh commented May 11, 2022

Take a look at the API used in CIRCL.

// VerifyAny returns true if the signature is valid. Failure cases are invalid
// signature, or when the public key cannot be decoded.
// This function supports all the three signature variants defined in RFC-8032,
// namely Ed25519 (or pure EdDSA), Ed25519Ph, and Ed25519Ctx.
// The opts.HashFunc() must return zero to specify either Ed25519 or Ed25519Ctx
// variant. This can be achieved by passing crypto.Hash(0) as the value for opts.
// The opts.HashFunc() must return SHA512 to specify the Ed25519Ph variant.
// This can be achieved by passing crypto.SHA512 as the value for opts.
// Use a SignerOptions struct to pass a context string for signing.
func VerifyAny(public PublicKey, message, signature []byte, opts crypto.SignerOpts) bool {
	var ctx string
	var scheme SchemeID
	if o, ok := opts.(SignerOptions); ok {
		ctx = o.Context
		scheme = o.Scheme
	}

	switch true {
	case scheme == ED25519 && opts.HashFunc() == crypto.Hash(0):
		return Verify(public, message, signature)
	case scheme == ED25519Ph && opts.HashFunc() == crypto.SHA512:
		return VerifyPh(public, message, signature, ctx)
	case scheme == ED25519Ctx && opts.HashFunc() == crypto.Hash(0) && len(ctx) > 0:
		return VerifyWithCtx(public, message, signature, ctx)
	default:
		return false
	}
}

https://github.com/cloudflare/circl/blob/master/sign/ed25519/ed25519.go#L372

@Yawning
Copy link

Yawning commented May 11, 2022

For what it's worth, over the last few years, I have had no issues with using the API as proposed in this issue.

@rsc
Copy link
Contributor

rsc commented May 18, 2022

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

@rsc rsc moved this from Active to Likely Accept in Proposals (old) May 18, 2022
@rsc rsc moved this from Likely Accept to Accepted in Proposals (old) May 25, 2022
@rsc
Copy link
Contributor

rsc commented May 25, 2022

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

@ianlancetaylor
Copy link
Contributor

CC @golang/security

Looks like this didn't make 1.19. Moving to backlog. Please recategorize as appropriate.

@ianlancetaylor ianlancetaylor modified the milestones: Go1.19, Backlog Jun 24, 2022
gopherbot pushed a commit that referenced this issue Oct 24, 2022
Updates #31804

Change-Id: I5a48dfc57401576902674aff20b557e4a8ce8ab8
Reviewed-on: https://go-review.googlesource.com/c/go/+/373076
Reviewed-by: Filippo Valsorda <valsorda@google.com>
Reviewed-by: Michael Knyszek <mknyszek@google.com>
Run-TryBot: Filippo Valsorda <filippo@golang.org>
Reviewed-by: Roland Shoemaker <roland@golang.org>
TryBot-Result: Gopher Robot <gobot@golang.org>
Reviewed-by: Katie Hockman <katie@golang.org>
Reviewed-by: David Chase <drchase@google.com>
romaindoumenc pushed a commit to TroutSoftware/go that referenced this issue Nov 3, 2022
Updates golang#31804

Change-Id: I5a48dfc57401576902674aff20b557e4a8ce8ab8
Reviewed-on: https://go-review.googlesource.com/c/go/+/373076
Reviewed-by: Filippo Valsorda <valsorda@google.com>
Reviewed-by: Michael Knyszek <mknyszek@google.com>
Run-TryBot: Filippo Valsorda <filippo@golang.org>
Reviewed-by: Roland Shoemaker <roland@golang.org>
TryBot-Result: Gopher Robot <gobot@golang.org>
Reviewed-by: Katie Hockman <katie@golang.org>
Reviewed-by: David Chase <drchase@google.com>
felixge pushed a commit to felixge/go that referenced this issue Nov 21, 2022
This is missing a test for Ed25519ph with context, since the RFC doesn't
provide one.

Fixes golang#31804

Change-Id: I20947374c51c6b22fb2835317d00edf816c9a2d2
Reviewed-on: https://go-review.googlesource.com/c/go/+/404274
Auto-Submit: Filippo Valsorda <filippo@golang.org>
TryBot-Result: Gopher Robot <gobot@golang.org>
Run-TryBot: Filippo Valsorda <filippo@golang.org>
Reviewed-by: Cherry Mui <cherryyz@google.com>
Reviewed-by: Roland Shoemaker <roland@golang.org>
@dmitshur dmitshur modified the milestones: Backlog, Go1.20 Jun 4, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
FeatureRequest NeedsFix The path to resolution is known, but the work has not been done. Proposal Proposal-Accepted Proposal-Crypto Proposal related to crypto packages or other security issues Proposal-FinalCommentPeriod
Projects
Development

No branches or pull requests