1// Copyright 2011 The Go Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style
3// license that can be found in the LICENSE file.
4
5package ecdsa
6
7import (
8	"bufio"
9	"bytes"
10	"compress/bzip2"
11	"crypto/elliptic"
12	"crypto/internal/bigmod"
13	"crypto/rand"
14	"crypto/sha1"
15	"crypto/sha256"
16	"crypto/sha512"
17	"encoding/hex"
18	"hash"
19	"io"
20	"math/big"
21	"os"
22	"strings"
23	"testing"
24)
25
26func testAllCurves(t *testing.T, f func(*testing.T, elliptic.Curve)) {
27	tests := []struct {
28		name  string
29		curve elliptic.Curve
30	}{
31		{"P256", elliptic.P256()},
32		{"P224", elliptic.P224()},
33		{"P384", elliptic.P384()},
34		{"P521", elliptic.P521()},
35		{"P256/Generic", genericParamsForCurve(elliptic.P256())},
36	}
37	if testing.Short() {
38		tests = tests[:1]
39	}
40	for _, test := range tests {
41		curve := test.curve
42		t.Run(test.name, func(t *testing.T) {
43			t.Parallel()
44			f(t, curve)
45		})
46	}
47}
48
49// genericParamsForCurve returns the dereferenced CurveParams for
50// the specified curve. This is used to avoid the logic for
51// upgrading a curve to its specific implementation, forcing
52// usage of the generic implementation.
53func genericParamsForCurve(c elliptic.Curve) *elliptic.CurveParams {
54	d := *(c.Params())
55	return &d
56}
57
58func TestKeyGeneration(t *testing.T) {
59	testAllCurves(t, testKeyGeneration)
60}
61
62func testKeyGeneration(t *testing.T, c elliptic.Curve) {
63	priv, err := GenerateKey(c, rand.Reader)
64	if err != nil {
65		t.Fatal(err)
66	}
67	if !c.IsOnCurve(priv.PublicKey.X, priv.PublicKey.Y) {
68		t.Errorf("public key invalid: %s", err)
69	}
70}
71
72func TestSignAndVerify(t *testing.T) {
73	testAllCurves(t, testSignAndVerify)
74}
75
76func testSignAndVerify(t *testing.T, c elliptic.Curve) {
77	priv, _ := GenerateKey(c, rand.Reader)
78
79	hashed := []byte("testing")
80	r, s, err := Sign(rand.Reader, priv, hashed)
81	if err != nil {
82		t.Errorf("error signing: %s", err)
83		return
84	}
85
86	if !Verify(&priv.PublicKey, hashed, r, s) {
87		t.Errorf("Verify failed")
88	}
89
90	hashed[0] ^= 0xff
91	if Verify(&priv.PublicKey, hashed, r, s) {
92		t.Errorf("Verify always works!")
93	}
94}
95
96func TestSignAndVerifyASN1(t *testing.T) {
97	testAllCurves(t, testSignAndVerifyASN1)
98}
99
100func testSignAndVerifyASN1(t *testing.T, c elliptic.Curve) {
101	priv, _ := GenerateKey(c, rand.Reader)
102
103	hashed := []byte("testing")
104	sig, err := SignASN1(rand.Reader, priv, hashed)
105	if err != nil {
106		t.Errorf("error signing: %s", err)
107		return
108	}
109
110	if !VerifyASN1(&priv.PublicKey, hashed, sig) {
111		t.Errorf("VerifyASN1 failed")
112	}
113
114	hashed[0] ^= 0xff
115	if VerifyASN1(&priv.PublicKey, hashed, sig) {
116		t.Errorf("VerifyASN1 always works!")
117	}
118}
119
120func TestNonceSafety(t *testing.T) {
121	testAllCurves(t, testNonceSafety)
122}
123
124func testNonceSafety(t *testing.T, c elliptic.Curve) {
125	priv, _ := GenerateKey(c, rand.Reader)
126
127	hashed := []byte("testing")
128	r0, s0, err := Sign(zeroReader, priv, hashed)
129	if err != nil {
130		t.Errorf("error signing: %s", err)
131		return
132	}
133
134	hashed = []byte("testing...")
135	r1, s1, err := Sign(zeroReader, priv, hashed)
136	if err != nil {
137		t.Errorf("error signing: %s", err)
138		return
139	}
140
141	if s0.Cmp(s1) == 0 {
142		// This should never happen.
143		t.Errorf("the signatures on two different messages were the same")
144	}
145
146	if r0.Cmp(r1) == 0 {
147		t.Errorf("the nonce used for two different messages was the same")
148	}
149}
150
151func TestINDCCA(t *testing.T) {
152	testAllCurves(t, testINDCCA)
153}
154
155func testINDCCA(t *testing.T, c elliptic.Curve) {
156	priv, _ := GenerateKey(c, rand.Reader)
157
158	hashed := []byte("testing")
159	r0, s0, err := Sign(rand.Reader, priv, hashed)
160	if err != nil {
161		t.Errorf("error signing: %s", err)
162		return
163	}
164
165	r1, s1, err := Sign(rand.Reader, priv, hashed)
166	if err != nil {
167		t.Errorf("error signing: %s", err)
168		return
169	}
170
171	if s0.Cmp(s1) == 0 {
172		t.Errorf("two signatures of the same message produced the same result")
173	}
174
175	if r0.Cmp(r1) == 0 {
176		t.Errorf("two signatures of the same message produced the same nonce")
177	}
178}
179
180func fromHex(s string) *big.Int {
181	r, ok := new(big.Int).SetString(s, 16)
182	if !ok {
183		panic("bad hex")
184	}
185	return r
186}
187
188func TestVectors(t *testing.T) {
189	// This test runs the full set of NIST test vectors from
190	// https://csrc.nist.gov/groups/STM/cavp/documents/dss/186-3ecdsatestvectors.zip
191	//
192	// The SigVer.rsp file has been edited to remove test vectors for
193	// unsupported algorithms and has been compressed.
194
195	if testing.Short() {
196		return
197	}
198
199	f, err := os.Open("testdata/SigVer.rsp.bz2")
200	if err != nil {
201		t.Fatal(err)
202	}
203
204	buf := bufio.NewReader(bzip2.NewReader(f))
205
206	lineNo := 1
207	var h hash.Hash
208	var msg []byte
209	var hashed []byte
210	var r, s *big.Int
211	pub := new(PublicKey)
212
213	for {
214		line, err := buf.ReadString('\n')
215		if len(line) == 0 {
216			if err == io.EOF {
217				break
218			}
219			t.Fatalf("error reading from input: %s", err)
220		}
221		lineNo++
222		// Need to remove \r\n from the end of the line.
223		if !strings.HasSuffix(line, "\r\n") {
224			t.Fatalf("bad line ending (expected \\r\\n) on line %d", lineNo)
225		}
226		line = line[:len(line)-2]
227
228		if len(line) == 0 || line[0] == '#' {
229			continue
230		}
231
232		if line[0] == '[' {
233			line = line[1 : len(line)-1]
234			curve, hash, _ := strings.Cut(line, ",")
235
236			switch curve {
237			case "P-224":
238				pub.Curve = elliptic.P224()
239			case "P-256":
240				pub.Curve = elliptic.P256()
241			case "P-384":
242				pub.Curve = elliptic.P384()
243			case "P-521":
244				pub.Curve = elliptic.P521()
245			default:
246				pub.Curve = nil
247			}
248
249			switch hash {
250			case "SHA-1":
251				h = sha1.New()
252			case "SHA-224":
253				h = sha256.New224()
254			case "SHA-256":
255				h = sha256.New()
256			case "SHA-384":
257				h = sha512.New384()
258			case "SHA-512":
259				h = sha512.New()
260			default:
261				h = nil
262			}
263
264			continue
265		}
266
267		if h == nil || pub.Curve == nil {
268			continue
269		}
270
271		switch {
272		case strings.HasPrefix(line, "Msg = "):
273			if msg, err = hex.DecodeString(line[6:]); err != nil {
274				t.Fatalf("failed to decode message on line %d: %s", lineNo, err)
275			}
276		case strings.HasPrefix(line, "Qx = "):
277			pub.X = fromHex(line[5:])
278		case strings.HasPrefix(line, "Qy = "):
279			pub.Y = fromHex(line[5:])
280		case strings.HasPrefix(line, "R = "):
281			r = fromHex(line[4:])
282		case strings.HasPrefix(line, "S = "):
283			s = fromHex(line[4:])
284		case strings.HasPrefix(line, "Result = "):
285			expected := line[9] == 'P'
286			h.Reset()
287			h.Write(msg)
288			hashed := h.Sum(hashed[:0])
289			if Verify(pub, hashed, r, s) != expected {
290				t.Fatalf("incorrect result on line %d", lineNo)
291			}
292		default:
293			t.Fatalf("unknown variable on line %d: %s", lineNo, line)
294		}
295	}
296}
297
298func TestNegativeInputs(t *testing.T) {
299	testAllCurves(t, testNegativeInputs)
300}
301
302func testNegativeInputs(t *testing.T, curve elliptic.Curve) {
303	key, err := GenerateKey(curve, rand.Reader)
304	if err != nil {
305		t.Errorf("failed to generate key")
306	}
307
308	var hash [32]byte
309	r := new(big.Int).SetInt64(1)
310	r.Lsh(r, 550 /* larger than any supported curve */)
311	r.Neg(r)
312
313	if Verify(&key.PublicKey, hash[:], r, r) {
314		t.Errorf("bogus signature accepted")
315	}
316}
317
318func TestZeroHashSignature(t *testing.T) {
319	testAllCurves(t, testZeroHashSignature)
320}
321
322func testZeroHashSignature(t *testing.T, curve elliptic.Curve) {
323	zeroHash := make([]byte, 64)
324
325	privKey, err := GenerateKey(curve, rand.Reader)
326	if err != nil {
327		panic(err)
328	}
329
330	// Sign a hash consisting of all zeros.
331	r, s, err := Sign(rand.Reader, privKey, zeroHash)
332	if err != nil {
333		panic(err)
334	}
335
336	// Confirm that it can be verified.
337	if !Verify(&privKey.PublicKey, zeroHash, r, s) {
338		t.Errorf("zero hash signature verify failed for %T", curve)
339	}
340}
341
342func TestRandomPoint(t *testing.T) {
343	t.Run("P-224", func(t *testing.T) { testRandomPoint(t, p224()) })
344	t.Run("P-256", func(t *testing.T) { testRandomPoint(t, p256()) })
345	t.Run("P-384", func(t *testing.T) { testRandomPoint(t, p384()) })
346	t.Run("P-521", func(t *testing.T) { testRandomPoint(t, p521()) })
347}
348
349func testRandomPoint[Point nistPoint[Point]](t *testing.T, c *nistCurve[Point]) {
350	t.Cleanup(func() { testingOnlyRejectionSamplingLooped = nil })
351	var loopCount int
352	testingOnlyRejectionSamplingLooped = func() { loopCount++ }
353
354	// A sequence of all ones will generate 2^N-1, which should be rejected.
355	// (Unless, for example, we are masking too many bits.)
356	r := io.MultiReader(bytes.NewReader(bytes.Repeat([]byte{0xff}, 100)), rand.Reader)
357	if k, p, err := randomPoint(c, r); err != nil {
358		t.Fatal(err)
359	} else if k.IsZero() == 1 {
360		t.Error("k is zero")
361	} else if p.Bytes()[0] != 4 {
362		t.Error("p is infinity")
363	}
364	if loopCount == 0 {
365		t.Error("overflow was not rejected")
366	}
367	loopCount = 0
368
369	// A sequence of all zeroes will generate zero, which should be rejected.
370	r = io.MultiReader(bytes.NewReader(bytes.Repeat([]byte{0}, 100)), rand.Reader)
371	if k, p, err := randomPoint(c, r); err != nil {
372		t.Fatal(err)
373	} else if k.IsZero() == 1 {
374		t.Error("k is zero")
375	} else if p.Bytes()[0] != 4 {
376		t.Error("p is infinity")
377	}
378	if loopCount == 0 {
379		t.Error("zero was not rejected")
380	}
381	loopCount = 0
382
383	// P-256 has a 2⁻³² chance or randomly hitting a rejection. For P-224 it's
384	// 2⁻¹¹², for P-384 it's 2⁻¹⁹⁴, and for P-521 it's 2⁻²⁶², so if we hit in
385	// tests, something is horribly wrong. (For example, we are masking the
386	// wrong bits.)
387	if c.curve == elliptic.P256() {
388		return
389	}
390	if k, p, err := randomPoint(c, rand.Reader); err != nil {
391		t.Fatal(err)
392	} else if k.IsZero() == 1 {
393		t.Error("k is zero")
394	} else if p.Bytes()[0] != 4 {
395		t.Error("p is infinity")
396	}
397	if loopCount > 0 {
398		t.Error("unexpected rejection")
399	}
400}
401
402func TestHashToNat(t *testing.T) {
403	t.Run("P-224", func(t *testing.T) { testHashToNat(t, p224()) })
404	t.Run("P-256", func(t *testing.T) { testHashToNat(t, p256()) })
405	t.Run("P-384", func(t *testing.T) { testHashToNat(t, p384()) })
406	t.Run("P-521", func(t *testing.T) { testHashToNat(t, p521()) })
407}
408
409func testHashToNat[Point nistPoint[Point]](t *testing.T, c *nistCurve[Point]) {
410	for l := 0; l < 600; l++ {
411		h := bytes.Repeat([]byte{0xff}, l)
412		hashToNat(c, bigmod.NewNat(), h)
413	}
414}
415
416func TestZeroSignature(t *testing.T) {
417	testAllCurves(t, testZeroSignature)
418}
419
420func testZeroSignature(t *testing.T, curve elliptic.Curve) {
421	privKey, err := GenerateKey(curve, rand.Reader)
422	if err != nil {
423		panic(err)
424	}
425
426	if Verify(&privKey.PublicKey, make([]byte, 64), big.NewInt(0), big.NewInt(0)) {
427		t.Errorf("Verify with r,s=0 succeeded: %T", curve)
428	}
429}
430
431func TestNegativeSignature(t *testing.T) {
432	testAllCurves(t, testNegativeSignature)
433}
434
435func testNegativeSignature(t *testing.T, curve elliptic.Curve) {
436	zeroHash := make([]byte, 64)
437
438	privKey, err := GenerateKey(curve, rand.Reader)
439	if err != nil {
440		panic(err)
441	}
442	r, s, err := Sign(rand.Reader, privKey, zeroHash)
443	if err != nil {
444		panic(err)
445	}
446
447	r = r.Neg(r)
448	if Verify(&privKey.PublicKey, zeroHash, r, s) {
449		t.Errorf("Verify with r=-r succeeded: %T", curve)
450	}
451}
452
453func TestRPlusNSignature(t *testing.T) {
454	testAllCurves(t, testRPlusNSignature)
455}
456
457func testRPlusNSignature(t *testing.T, curve elliptic.Curve) {
458	zeroHash := make([]byte, 64)
459
460	privKey, err := GenerateKey(curve, rand.Reader)
461	if err != nil {
462		panic(err)
463	}
464	r, s, err := Sign(rand.Reader, privKey, zeroHash)
465	if err != nil {
466		panic(err)
467	}
468
469	r = r.Add(r, curve.Params().N)
470	if Verify(&privKey.PublicKey, zeroHash, r, s) {
471		t.Errorf("Verify with r=r+n succeeded: %T", curve)
472	}
473}
474
475func TestRMinusNSignature(t *testing.T) {
476	testAllCurves(t, testRMinusNSignature)
477}
478
479func testRMinusNSignature(t *testing.T, curve elliptic.Curve) {
480	zeroHash := make([]byte, 64)
481
482	privKey, err := GenerateKey(curve, rand.Reader)
483	if err != nil {
484		panic(err)
485	}
486	r, s, err := Sign(rand.Reader, privKey, zeroHash)
487	if err != nil {
488		panic(err)
489	}
490
491	r = r.Sub(r, curve.Params().N)
492	if Verify(&privKey.PublicKey, zeroHash, r, s) {
493		t.Errorf("Verify with r=r-n succeeded: %T", curve)
494	}
495}
496
497func randomPointForCurve(curve elliptic.Curve, rand io.Reader) error {
498	switch curve.Params() {
499	case elliptic.P224().Params():
500		_, _, err := randomPoint(p224(), rand)
501		return err
502	case elliptic.P256().Params():
503		_, _, err := randomPoint(p256(), rand)
504		return err
505	case elliptic.P384().Params():
506		_, _, err := randomPoint(p384(), rand)
507		return err
508	case elliptic.P521().Params():
509		_, _, err := randomPoint(p521(), rand)
510		return err
511	default:
512		panic("unknown curve")
513	}
514}
515
516func benchmarkAllCurves(b *testing.B, f func(*testing.B, elliptic.Curve)) {
517	tests := []struct {
518		name  string
519		curve elliptic.Curve
520	}{
521		{"P256", elliptic.P256()},
522		{"P384", elliptic.P384()},
523		{"P521", elliptic.P521()},
524	}
525	for _, test := range tests {
526		curve := test.curve
527		b.Run(test.name, func(b *testing.B) {
528			f(b, curve)
529		})
530	}
531}
532
533func BenchmarkSign(b *testing.B) {
534	benchmarkAllCurves(b, func(b *testing.B, curve elliptic.Curve) {
535		r := bufio.NewReaderSize(rand.Reader, 1<<15)
536		priv, err := GenerateKey(curve, r)
537		if err != nil {
538			b.Fatal(err)
539		}
540		hashed := []byte("testing")
541
542		b.ReportAllocs()
543		b.ResetTimer()
544		for i := 0; i < b.N; i++ {
545			sig, err := SignASN1(r, priv, hashed)
546			if err != nil {
547				b.Fatal(err)
548			}
549			// Prevent the compiler from optimizing out the operation.
550			hashed[0] = sig[0]
551		}
552	})
553}
554
555func BenchmarkVerify(b *testing.B) {
556	benchmarkAllCurves(b, func(b *testing.B, curve elliptic.Curve) {
557		r := bufio.NewReaderSize(rand.Reader, 1<<15)
558		priv, err := GenerateKey(curve, r)
559		if err != nil {
560			b.Fatal(err)
561		}
562		hashed := []byte("testing")
563		sig, err := SignASN1(r, priv, hashed)
564		if err != nil {
565			b.Fatal(err)
566		}
567
568		b.ReportAllocs()
569		b.ResetTimer()
570		for i := 0; i < b.N; i++ {
571			if !VerifyASN1(&priv.PublicKey, hashed, sig) {
572				b.Fatal("verify failed")
573			}
574		}
575	})
576}
577
578func BenchmarkGenerateKey(b *testing.B) {
579	benchmarkAllCurves(b, func(b *testing.B, curve elliptic.Curve) {
580		r := bufio.NewReaderSize(rand.Reader, 1<<15)
581		b.ReportAllocs()
582		b.ResetTimer()
583		for i := 0; i < b.N; i++ {
584			if _, err := GenerateKey(curve, r); err != nil {
585				b.Fatal(err)
586			}
587		}
588	})
589}
590