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

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

crypto/ed25519: Implement Ed25519ph #31804

titanous opened this issue May 2, 2019 · 36 comments
Assignees
Labels
FeatureRequest NeedsFix Proposal Proposal-Accepted Proposal-Crypto Proposal-FinalCommentPeriod
Projects
Milestone

Comments

@titanous
Copy link
Member

@titanous 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

@gopherbot gopherbot commented May 2, 2019

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

@x30n
Copy link

@x30n x30n commented Jul 22, 2019

+1

@Hades32
Copy link

@Hades32 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 label Jul 26, 2019
@FiloSottile FiloSottile removed this from the Unreleased milestone Jul 26, 2019
@FiloSottile FiloSottile added this to the Go1.14 milestone 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 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 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 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 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

@FiloSottile FiloSottile 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.

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 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

@FiloSottile FiloSottile commented Oct 3, 2019

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

@rsc rsc removed this from the Go1.14 milestone Oct 9, 2019
@rsc rsc added this to the Backlog milestone Oct 9, 2019
@smasher164 smasher164 removed this from the Backlog milestone Oct 11, 2019
@smasher164 smasher164 added this to the Go1.14 milestone Oct 11, 2019
@odeke-em
Copy link
Member

@odeke-em odeke-em commented Nov 29, 2019

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.

@odeke-em odeke-em removed this from the Go1.14 milestone Nov 29, 2019
@odeke-em odeke-em added this to the Backlog milestone Nov 29, 2019
@armfazh
Copy link

@armfazh 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 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 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.

@ItalyPaleAle
Copy link

@ItalyPaleAle ItalyPaleAle commented Jan 5, 2022

if you want to use a different hash that provides a 512-bit digest for the pre-hashed message, it will "just work" if you pass in SHA-512 as the hash (though still use SHA-512 internally), because the pre-hashed message is treated as an opaque blob.

That makes sense for 512-bit hashes. But right now the code would fail for anything that isn't 64-bytes long (I see a check that makes sure the input has the length of a SHA-512 hash).

If you want to also use an alternative hash algorithm internally (Eg: for deriving the r scalar), that would require more substantial alterations to the code

I can't speak for others, but from what I'm concerned with, this is not a problem. The reason why I'd like to use Ed25519ph is to sign large files and calculate the hash as a stream on the input, which is not possible with Ed25519. So I'm not concerned with the hashing algorithm used internally.

@Yawning
Copy link

@Yawning Yawning commented Jan 5, 2022

That makes sense for 512-bit hashes. But right now the code would fail for anything that isn't 64-bytes long (I see a check that makes sure the input has the length of a SHA-512 hash).

Then append 256-bits worth of 0s to your digest. You're already doing something non-standard.

@FiloSottile
Copy link
Contributor

@FiloSottile FiloSottile commented Jan 6, 2022

No, Ed25519ph is defined and specified with only a single hash, and that's a good thing. Flexibility in cryptography is a liability, not an asset per se. If SHA-512 turns out to be broken, which considering the progress of cryptanalysis is not a pressing concern, we'll simply specify and implement a new Ed25519 variant that uses a different hash everywhere. If you need to sign a non-SHA-512 hash, you can use pure Ed25519 and understand that domain separation is your responsibility, but I would suggest considering just switching to SHA-512 which on 64-bit platforms is sometimes faster than SHA-256.

@zx2c4
Copy link
Contributor

@zx2c4 zx2c4 commented Jan 6, 2022

However, do you think it would be possible to make the method support more generic hashes?

Something to keep in mind that may not be immediately obvious from looking at the diff in that CL alone is that, regardless of the "prehash" mode, Ed25519 already uses SHA-512 internally (twice on sign, once on verify). That's not something anybody is talking about changing or modularizing here; it works fine. So, given that there's already a necessary SHA-512 code path, why complicate things by adding something different for prehash mode? You can keep your code size small and just re-use the same hash function, SHA-512.

And, as Filippo said, if you do want to go off and do something weird, figuring out how to do that safely should be on you.


If you're curious about how this is specified, here's a line copy and pasted out of the verification phase for Ed25519[ph]:

  1. Compute SHA512(dom2(F, C) || R || A || PH(M))

So interpret that as SHA-512(somestuff concatenated with PH(the message)). Notice how SHA-512 is hard coded there. But what is this PH() function?

Take a look at this section. For Ed25519, the vanilla version, it says:

| PH(x) | x (i.e., the identity function) |

So that simplifies to SHA-512(somestuff concatenated with the message).

But for Ed25519ph, the prehashed version, it says:

For Ed25519ph, [...] PH is SHA512 instead.

So that simplifies to SHA-512(somestuff concatenated with SHA-512(the message)).

At which point you can be somewhat glad things aren't made more complicated by having two different hash functions in there. Were I to write that expression with two different hash functions, you would probably tell me, "that's weird, why not just use the same one?"

@FiloSottile
Copy link
Contributor

@FiloSottile FiloSottile commented Mar 2, 2022

I implemented the API in #31804 (comment) in https://go.dev/cl/373076.

@golang/proposal-review, can we get it on the slate for Go 1.19?

@FiloSottile FiloSottile removed this from the Backlog milestone Mar 2, 2022
@FiloSottile FiloSottile added this to the Go1.19 milestone Mar 2, 2022
@rsc
Copy link
Contributor

@rsc rsc commented Apr 6, 2022

The proposed API is in #31804 (comment).

@cristaloleg
Copy link

@cristaloleg cristaloleg commented Apr 19, 2022

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

@FiloSottile
Copy link
Contributor

@FiloSottile FiloSottile commented Apr 20, 2022

@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 May 4, 2022
@rsc
Copy link
Contributor

@rsc 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

@FiloSottile FiloSottile commented May 5, 2022

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

@gopherbot
Copy link

@gopherbot gopherbot commented May 5, 2022

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

@rsc
Copy link
Contributor

@rsc 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 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 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 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 May 18, 2022
@rsc rsc moved this from Likely Accept to Accepted in Proposals May 25, 2022
@rsc
Copy link
Contributor

@rsc 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

@ianlancetaylor ianlancetaylor commented Jun 24, 2022

CC @golang/security

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

@ianlancetaylor ianlancetaylor removed this from the Go1.19 milestone Jun 24, 2022
@ianlancetaylor ianlancetaylor added this to the Backlog milestone Jun 24, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
FeatureRequest NeedsFix Proposal Proposal-Accepted Proposal-Crypto Proposal-FinalCommentPeriod
Projects
Proposals
Accepted
Status: No status
Development

No branches or pull requests