Open Radar

 
As of Safari 11.1, we can no longer reproduce this.

Summary:

crypto.subtle.generateKey({{ name: "ECDSA", namedCurve: "P-256", }, true, ["sign", "verify"]) will occasionally (about 1 out of 200 times) produce keys that when exported contain points that are not on curve P-256.

The most apparent symptom is that Safari will fail when attempting to verify signatures created with these keys. But other browsers refuse to import these keys.

Summary for crypto team:

A few JWK exported ECDSA generated keys give x,y pairs that are not on the curve.

We do not know if the bug is in the generator or in the exporter.

Steps to Reproduce:

Overview of how to reproduce.

1. Generate a large number of keys (say 500).
2. Export to JWK.
3. Test validity of the keys.

There are multiple ways to test the validity of the generated keys.

- Sign data using the key and then attempt to verify the signature.
- Mathematically compute that the x and y values correspond to a point on curve P-256
- Import the exported keys into other browsers.

All three tests confirm that some bad keys are generated.

For steps 1 and 2, see the attached files [...] Note that as keys are randomly generated, each run of the script will produce a different 500 keys.

In that output file of 500 private keys, three are bad. Those are 

{"pubKey":{"crv":"P-256","ext":true,"key_ops":["verify"],"kty":"EC","x":"TE1MHGJ
Pz423Ih79CX8Z2LajPocPH40piEkYWeLPnLc","y":"y-8R78D0yL9YtgL4FNVDIzU0HGNkWaCQ5Pz3E
YX0TQA","kid":"foo-122"},"priKey":{"crv":"P-256","ext":true,"key_ops":["sign"],"
kty":"EC","x":"TE1MHGJPz423Ih79CX8Z2LajPocPH40piEkYWeLPnLc","y":"y-8R78D0yL9YtgL
4FNVDIzU0HGNkWaCQ5Pz3EYX0TQA","kid":"foo-122","d":"G8dmImGl4O1zkCyZuHLIE7_B1wgat
nKlkv4gB5o20j4"}}

{"pubKey":{"crv":"P-256","ext":true,"key_ops":["verify"],"kty":"EC","x":"mgmwh6D8f3KlrDsKNrHH4gwf39ME0L74Zhdrp-pdwQA","y":"rtDmfYZq8_WN7WxJugLhoZCtOMntI3vk_0JaNwTATF4","kid":"foo-435"},"priKey":{"crv":"P-256","ext":true,"key_ops":["sign"],"kty":"EC","x":"mgmwh6D8f3KlrDsKNrHH4gwf39ME0L74Zhdrp-pdwQA","y":"rtDmfYZq8_WN7WxJugLhoZCtOMntI3vk_0JaNwTATF4","kid":"foo-435","d":"FArmFpREGoAYhJDHBzi48EY_qO2pc0vtm6a1ZKneHSc"}}

{"pubKey":{"crv":"P-256","ext":true,"key_ops":["verify"],"kty":"EC","x":"E8BDqZcRjbq1SRIyOG5xs6-bY-_CkXrPhgUfZFXAcAA","y":"zv3PL2kftp_HDH5cFlVKgolDi_FDFmQp5KqbeDBEZL4","kid":"foo-467"},"priKey":{"crv":"P-256","ext":true,"key_ops":["sign"],"kty":"EC","x":"E8BDqZcRjbq1SRIyOG5xs6-bY-_CkXrPhgUfZFXAcAA","y":"zv3PL2kftp_HDH5cFlVKgolDi_FDFmQp5KqbeDBEZL4","kid":"foo-467","d":"sJbK6CMys6slIxheRTq0AZge64hZMv-P9k9hPuB1Agc"}}

To test these sample load testKeys.js[...]

Expected Results:

All generated keys should pass all tests

Actual Results:

A few generated/exported keys fail. 

Impact: [...]

Speculation:

We suspect that the Safari bug is in creating the representation of x. That may be in the generation process or it may be in the export process. (Hey, we have to leave something for you to test.)

The reason for this is that some of the bad keys we've seen have x values which cannot correspond to any y. Given the x of E8BDqZcRjbq1SRIyOG5xs6-bY-_CkXrPhgUfZFXAcAA in foo-467 computing y^2 := x^3 - 3x + b (where b and the modulus are defined in curve P-256) results in a y^2 that is not a quadratic residue in the underlying group.

The other two bad keys do allow us to compute a y^2 that do happen to be quadratic residues, but do not correspond to the y given in the exported key.

We have only tested P-256 keys.

Note for open-radar readers:

The actual rdar contained several attachments with testing and generating scripts, as well as buckets full of generated test data and screenshots.

Security: We did not see any security implications of this issue but filed it under Security nonetheeless, as misbehavior of some cryptographic routine is something that needs to be treated as a security issue until determined otherwise. Apple has since confirmed that there are no security implications, and reclassified it. Only after that reclassification are we sharing this publicly.