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: add edge case tests #40478

Closed
FiloSottile opened this issue Jul 29, 2020 · 4 comments
Closed

crypto/ed25519: add edge case tests #40478

FiloSottile opened this issue Jul 29, 2020 · 4 comments
Labels
FrozenDueToAge NeedsFix The path to resolution is known, but the work has not been done. Unfortunate
Milestone

Comments

@FiloSottile
Copy link
Contributor

We'll want to add tests for the edge cases that led to #40475.

Ideally, they would go into Wycheproof and run from there, making sure they run against all architectures.

/cc @hdevalence @katiehockman

@cagedmantis cagedmantis added this to the Backlog milestone Jul 29, 2020
@cagedmantis cagedmantis added the NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. label Jul 29, 2020
@hdevalence
Copy link
Contributor

https://github.com/hdevalence/ed25519consensus is a fork of crypto/ed25519 with a VerifyConsensus method implementing the ZIP215 validation rules described in that repo. (Please forgive my Go, I don't write it regularly).

Relevant to this issue, the zip215_test.go file in that repo has a list of 196 = 14^2 test vectors consisting of purported (public key, signature) pairs on the message b"Zcash". These are constructed by taking pairs from a list of 14 encodings of low-order points, 8 of which are canonically encoded and 6 of which are non-canonically encoded.

The difference between (my interpretation of) RFC 8032 and the current Go behaviour can be visualized as follows:

RFC 8032 (as interpreted) Go crypto/ed25519
rfc8032 go-crypto-ed25519

On the left, the dark shade indicates MUST-reject (according to RFC 8032, which was written after this implementation and is incompatible with it), medium indicates MAY-accept, light indicates MUST-accept. (RFC 8032 does not require implementations to agree on whether signatures are valid). On the right, dark and light indicate rejected and accepted, respectively.

Note that all of these test cases require carefully crafted public keys. Therefore, there's no security issue with the signatures themselves, because an attacker who can control the public key can sign any message whatsoever. The problem is just the inconsistency, which could allow, e.g., a malicious party to inject faults into a consensus algorithm and cause consensus divergence.

@FiloSottile FiloSottile added NeedsFix The path to resolution is known, but the work has not been done. Unfortunate and removed NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. labels Oct 5, 2020
@FiloSottile FiloSottile modified the milestones: Backlog, Go1.16 Oct 5, 2020
@FiloSottile FiloSottile self-assigned this Oct 5, 2020
@FiloSottile
Copy link
Contributor Author

There's more context in @hdevalence's article here: https://hdevalence.ca/blog/2020-10-04-its-25519am

Indeed, since there is no security risk we probably should not change the behavior now and risk forking some blockchains. We'll add test cases and a paragraph to the docs.

@odeke-em
Copy link
Member

odeke-em commented Feb 5, 2021

Thanks for the report @FiloSottile and for the details and work @hdevalence! We didn't get much action for the edge cases and Go1.16 is due, thus I shall kindly punt this to Go1.17. @hdevalence, it would be awesome to have you as a contributor to the Go project, your work on ed25519 is much appreciated too. I kindly nudge you @hdevalence to feel free to send some changes for Go1.17 and we'll review.

@odeke-em odeke-em modified the milestones: Go1.16, Go1.17 Feb 5, 2021
@gopherbot
Copy link

Change https://golang.org/cl/304349 mentions this issue: crypto/ed25519: add comprehensive edge-case test vectors

@golang golang locked and limited conversation to collaborators Apr 5, 2022
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
FrozenDueToAge NeedsFix The path to resolution is known, but the work has not been done. Unfortunate
Projects
None yet
Development

No branches or pull requests

5 participants