good_key_test.go

Documentation: github.com/letsencrypt/boulder/goodkey

     1  package goodkey
     2  
     3  import (
     4  	"context"
     5  	"crypto/ecdsa"
     6  	"crypto/elliptic"
     7  	"crypto/rand"
     8  	"crypto/rsa"
     9  	"fmt"
    10  	"math/big"
    11  	"testing"
    12  
    13  	"github.com/letsencrypt/boulder/test"
    14  )
    15  
    16  var testingPolicy = &KeyPolicy{
    17  	AllowRSA:           true,
    18  	AllowECDSANISTP256: true,
    19  	AllowECDSANISTP384: true,
    20  }
    21  
    22  func TestUnknownKeyType(t *testing.T) {
    23  	notAKey := struct{}{}
    24  	err := testingPolicy.GoodKey(context.Background(), notAKey)
    25  	test.AssertError(t, err, "Should have rejected a key of unknown type")
    26  	test.AssertEquals(t, err.Error(), "unsupported key type struct {}")
    27  
    28  	// Check for early rejection and that no error is seen from blockedKeys.blocked.
    29  	testingPolicyWithBlockedKeys := *testingPolicy
    30  	testingPolicyWithBlockedKeys.blockedList = &blockedKeys{}
    31  	err = testingPolicyWithBlockedKeys.GoodKey(context.Background(), notAKey)
    32  	test.AssertError(t, err, "Should have rejected a key of unknown type")
    33  	test.AssertEquals(t, err.Error(), "unsupported key type struct {}")
    34  }
    35  
    36  func TestNilKey(t *testing.T) {
    37  	err := testingPolicy.GoodKey(context.Background(), nil)
    38  	test.AssertError(t, err, "Should have rejected a nil key")
    39  	test.AssertEquals(t, err.Error(), "unsupported key type <nil>")
    40  }
    41  
    42  func TestSmallModulus(t *testing.T) {
    43  	pubKey := rsa.PublicKey{
    44  		N: big.NewInt(0),
    45  		E: 65537,
    46  	}
    47  	// 2040 bits
    48  	_, ok := pubKey.N.SetString("104192126510885102608953552259747211060428328569316484779167706297543848858189721071301121307701498317286069484848193969810800653457088975832436062805901725915630417996487259956349018066196416400386483594314258078114607080545265502078791826837453107382149801328758721235866366842649389274931060463277516954884108984101391466769505088222180613883737986792254164577832157921425082478871935498631777878563742033332460445633026471887331001305450139473524438241478798689974351175769895824322173301257621327448162705637127373457350813027123239805772024171112299987923305882261194120410409098448380641378552305583392176287", 10)
    49  	if !ok {
    50  		t.Errorf("error parsing pubkey modulus")
    51  	}
    52  	err := testingPolicy.GoodKey(context.Background(), &pubKey)
    53  	test.AssertError(t, err, "Should have rejected too-short key")
    54  	test.AssertEquals(t, err.Error(), "key size not supported: 2040")
    55  }
    56  
    57  func TestLargeModulus(t *testing.T) {
    58  	pubKey := rsa.PublicKey{
    59  		N: big.NewInt(0),
    60  		E: 65537,
    61  	}
    62  	// 4097 bits
    63  	_, ok := pubKey.N.SetString("1528586537844618544364689295678280797814937047039447018548513699782432768815684971832418418955305671838918285565080181315448131784543332408348488544125812746629522583979538961638790013578302979210481729874191053412386396889481430969071543569003141391030053024684850548909056275565684242965892176703473950844930842702506635531145654194239072799616096020023445127233557468234181352398708456163013484600764686209741158795461806441111028922165846800488957692595308009319392149669715238691709012014980470238746838534949750493558807218940354555205690667168930634644030378921382266510932028134500172599110460167962515262077587741235811653717121760943005253103187409557573174347385738572144714188928416780963680160418832333908040737262282830643745963536624555340279793555475547508851494656512855403492456740439533790565640263514349940712999516725281940465613417922773583725174223806589481568984323871222072582132221706797917380250216291620957692131931099423995355390698925093903005385497308399692769135287821632877871068909305276870015125960884987746154344006895331078411141197233179446805991116541744285238281451294472577537413640009811940462311100056023815261650331552185459228689469446389165886801876700815724561451940764544990177661873073", 10)
    64  	if !ok {
    65  		t.Errorf("error parsing pubkey modulus")
    66  	}
    67  	err := testingPolicy.GoodKey(context.Background(), &pubKey)
    68  	test.AssertError(t, err, "Should have rejected too-long key")
    69  	test.AssertEquals(t, err.Error(), "key size not supported: 4097")
    70  }
    71  
    72  func TestModulusModulo8(t *testing.T) {
    73  	bigOne := big.NewInt(1)
    74  	key := rsa.PublicKey{
    75  		N: bigOne.Lsh(bigOne, 2048),
    76  		E: 5,
    77  	}
    78  	err := testingPolicy.GoodKey(context.Background(), &key)
    79  	test.AssertError(t, err, "Should have rejected modulus with length not divisible by 8")
    80  	test.AssertEquals(t, err.Error(), "key size not supported: 2049")
    81  }
    82  
    83  var mod2048 = big.NewInt(0).Sub(big.NewInt(0).Lsh(big.NewInt(1), 2048), big.NewInt(1))
    84  
    85  func TestNonStandardExp(t *testing.T) {
    86  	evenMod := big.NewInt(0).Add(big.NewInt(1).Lsh(big.NewInt(1), 2047), big.NewInt(2))
    87  	key := rsa.PublicKey{
    88  		N: evenMod,
    89  		E: (1 << 16),
    90  	}
    91  	err := testingPolicy.GoodKey(context.Background(), &key)
    92  	test.AssertError(t, err, "Should have rejected non-standard exponent")
    93  	test.AssertEquals(t, err.Error(), "key exponent must be 65537")
    94  }
    95  
    96  func TestEvenModulus(t *testing.T) {
    97  	evenMod := big.NewInt(0).Add(big.NewInt(1).Lsh(big.NewInt(1), 2047), big.NewInt(2))
    98  	key := rsa.PublicKey{
    99  		N: evenMod,
   100  		E: (1 << 16) + 1,
   101  	}
   102  	err := testingPolicy.GoodKey(context.Background(), &key)
   103  	test.AssertError(t, err, "Should have rejected even modulus")
   104  	test.AssertEquals(t, err.Error(), "key divisible by small prime")
   105  }
   106  
   107  func TestModulusDivisibleBySmallPrime(t *testing.T) {
   108  	key := rsa.PublicKey{
   109  		N: mod2048,
   110  		E: (1 << 16) + 1,
   111  	}
   112  	err := testingPolicy.GoodKey(context.Background(), &key)
   113  	test.AssertError(t, err, "Should have rejected modulus divisible by 3")
   114  	test.AssertEquals(t, err.Error(), "key divisible by small prime")
   115  }
   116  
   117  func TestROCA(t *testing.T) {
   118  	n, ok := big.NewInt(1).SetString("19089470491547632015867380494603366846979936677899040455785311493700173635637619562546319438505971838982429681121352968394792665704951454132311441831732124044135181992768774222852895664400681270897445415599851900461316070972022018317962889565731866601557238345786316235456299813772607869009873279585912430769332375239444892105064608255089298943707214066350230292124208314161171265468111771687514518823144499250339825049199688099820304852696380797616737008621384107235756455735861506433065173933123259184114000282435500939123478591192413006994709825840573671701120771013072419520134975733578923370992644987545261926257", 10)
   119  	if !ok {
   120  		t.Fatal("failed to parse")
   121  	}
   122  	key := rsa.PublicKey{
   123  		N: n,
   124  		E: 65537,
   125  	}
   126  	err := testingPolicy.GoodKey(context.Background(), &key)
   127  	test.AssertError(t, err, "Should have rejected ROCA-weak key")
   128  	test.AssertEquals(t, err.Error(), "key generated by vulnerable Infineon-based hardware")
   129  }
   130  
   131  func TestGoodKey(t *testing.T) {
   132  	private, err := rsa.GenerateKey(rand.Reader, 2048)
   133  	test.AssertNotError(t, err, "Error generating key")
   134  	test.AssertNotError(t, testingPolicy.GoodKey(context.Background(), &private.PublicKey), "Should have accepted good key")
   135  }
   136  
   137  func TestECDSABadCurve(t *testing.T) {
   138  	for _, curve := range invalidCurves {
   139  		private, err := ecdsa.GenerateKey(curve, rand.Reader)
   140  		test.AssertNotError(t, err, "Error generating key")
   141  		err = testingPolicy.GoodKey(context.Background(), &private.PublicKey)
   142  		test.AssertError(t, err, "Should have rejected key with unsupported curve")
   143  		test.AssertEquals(t, err.Error(), fmt.Sprintf("ECDSA curve %s not allowed", curve.Params().Name))
   144  	}
   145  }
   146  
   147  var invalidCurves = []elliptic.Curve{
   148  	elliptic.P224(),
   149  	elliptic.P521(),
   150  }
   151  
   152  var validCurves = []elliptic.Curve{
   153  	elliptic.P256(),
   154  	elliptic.P384(),
   155  }
   156  
   157  func TestECDSAGoodKey(t *testing.T) {
   158  	for _, curve := range validCurves {
   159  		private, err := ecdsa.GenerateKey(curve, rand.Reader)
   160  		test.AssertNotError(t, err, "Error generating key")
   161  		test.AssertNotError(t, testingPolicy.GoodKey(context.Background(), &private.PublicKey), "Should have accepted good key")
   162  	}
   163  }
   164  
   165  func TestECDSANotOnCurveX(t *testing.T) {
   166  	for _, curve := range validCurves {
   167  		// Change a public key so that it is no longer on the curve.
   168  		private, err := ecdsa.GenerateKey(curve, rand.Reader)
   169  		test.AssertNotError(t, err, "Error generating key")
   170  
   171  		private.X.Add(private.X, big.NewInt(1))
   172  		err = testingPolicy.GoodKey(context.Background(), &private.PublicKey)
   173  		test.AssertError(t, err, "Should not have accepted key not on the curve")
   174  		test.AssertEquals(t, err.Error(), "key point is not on the curve")
   175  	}
   176  }
   177  
   178  func TestECDSANotOnCurveY(t *testing.T) {
   179  	for _, curve := range validCurves {
   180  		// Again with Y.
   181  		private, err := ecdsa.GenerateKey(curve, rand.Reader)
   182  		test.AssertNotError(t, err, "Error generating key")
   183  
   184  		// Change the public key so that it is no longer on the curve.
   185  		private.Y.Add(private.Y, big.NewInt(1))
   186  		err = testingPolicy.GoodKey(context.Background(), &private.PublicKey)
   187  		test.AssertError(t, err, "Should not have accepted key not on the curve")
   188  		test.AssertEquals(t, err.Error(), "key point is not on the curve")
   189  	}
   190  }
   191  
   192  func TestECDSANegative(t *testing.T) {
   193  	for _, curve := range validCurves {
   194  		// Check that negative X is not accepted.
   195  		private, err := ecdsa.GenerateKey(curve, rand.Reader)
   196  		test.AssertNotError(t, err, "Error generating key")
   197  
   198  		private.X.Neg(private.X)
   199  		err = testingPolicy.GoodKey(context.Background(), &private.PublicKey)
   200  		test.AssertError(t, err, "Should not have accepted key with negative X")
   201  		test.AssertEquals(t, err.Error(), "key x, y must not be negative")
   202  
   203  		// Check that negative Y is not accepted.
   204  		private.X.Neg(private.X)
   205  		private.Y.Neg(private.Y)
   206  		err = testingPolicy.GoodKey(context.Background(), &private.PublicKey)
   207  		test.AssertError(t, err, "Should not have accepted key with negative Y")
   208  		test.AssertEquals(t, err.Error(), "key x, y must not be negative")
   209  	}
   210  }
   211  
   212  func TestECDSAXOutsideField(t *testing.T) {
   213  	for _, curve := range validCurves {
   214  		// Check that X outside [0, p-1] is not accepted.
   215  		private, err := ecdsa.GenerateKey(curve, rand.Reader)
   216  		test.AssertNotError(t, err, "Error generating key")
   217  
   218  		private.X.Mul(private.X, private.Curve.Params().P)
   219  		err = testingPolicy.GoodKey(context.Background(), &private.PublicKey)
   220  		test.AssertError(t, err, "Should not have accepted key with a X > p-1")
   221  		test.AssertEquals(t, err.Error(), "key x, y must not exceed P-1")
   222  	}
   223  }
   224  
   225  func TestECDSAYOutsideField(t *testing.T) {
   226  	for _, curve := range validCurves {
   227  		// Check that Y outside [0, p-1] is not accepted.
   228  		private, err := ecdsa.GenerateKey(curve, rand.Reader)
   229  		test.AssertNotError(t, err, "Error generating key")
   230  
   231  		private.X.Mul(private.Y, private.Curve.Params().P)
   232  		err = testingPolicy.GoodKey(context.Background(), &private.PublicKey)
   233  		test.AssertError(t, err, "Should not have accepted key with a Y > p-1")
   234  		test.AssertEquals(t, err.Error(), "key x, y must not exceed P-1")
   235  	}
   236  }
   237  
   238  func TestECDSAIdentity(t *testing.T) {
   239  	for _, curve := range validCurves {
   240  		// The point at infinity is 0,0, it should not be accepted.
   241  		public := ecdsa.PublicKey{
   242  			Curve: curve,
   243  			X:     big.NewInt(0),
   244  			Y:     big.NewInt(0),
   245  		}
   246  
   247  		err := testingPolicy.GoodKey(context.Background(), &public)
   248  		test.AssertError(t, err, "Should not have accepted key with point at infinity")
   249  		test.AssertEquals(t, err.Error(), "key x, y must not be the point at infinity")
   250  	}
   251  }
   252  
   253  func TestNonRefKey(t *testing.T) {
   254  	private, err := rsa.GenerateKey(rand.Reader, 2048)
   255  	test.AssertNotError(t, err, "Error generating key")
   256  	test.AssertError(t, testingPolicy.GoodKey(context.Background(), private.PublicKey), "Accepted non-reference key")
   257  }
   258  
   259  func TestDBBlocklistAccept(t *testing.T) {
   260  	for _, testCheck := range []BlockedKeyCheckFunc{
   261  		nil,
   262  		func(context.Context, []byte) (bool, error) {
   263  			return false, nil
   264  		},
   265  	} {
   266  		policy, err := NewKeyPolicy(&Config{}, testCheck)
   267  		test.AssertNotError(t, err, "NewKeyPolicy failed")
   268  
   269  		k, err := ecdsa.GenerateKey(elliptic.P256(), rand.Reader)
   270  		test.AssertNotError(t, err, "ecdsa.GenerateKey failed")
   271  		err = policy.GoodKey(context.Background(), k.Public())
   272  		test.AssertNotError(t, err, "GoodKey failed with a non-blocked key")
   273  	}
   274  }
   275  
   276  func TestDBBlocklistReject(t *testing.T) {
   277  	testCheck := func(context.Context, []byte) (bool, error) {
   278  		return true, nil
   279  	}
   280  
   281  	policy, err := NewKeyPolicy(&Config{}, testCheck)
   282  	test.AssertNotError(t, err, "NewKeyPolicy failed")
   283  
   284  	k, err := ecdsa.GenerateKey(elliptic.P256(), rand.Reader)
   285  	test.AssertNotError(t, err, "ecdsa.GenerateKey failed")
   286  	err = policy.GoodKey(context.Background(), k.Public())
   287  	test.AssertError(t, err, "GoodKey didn't fail with a blocked key")
   288  	test.AssertErrorIs(t, err, ErrBadKey)
   289  	test.AssertEquals(t, err.Error(), "public key is forbidden")
   290  }
   291  
   292  func TestRSAStrangeSize(t *testing.T) {
   293  	k := &rsa.PublicKey{N: big.NewInt(10)}
   294  	err := testingPolicy.GoodKey(context.Background(), k)
   295  	test.AssertError(t, err, "expected GoodKey to fail")
   296  	test.AssertEquals(t, err.Error(), "key size not supported: 4")
   297  }
   298  
   299  func TestCheckPrimeFactorsTooClose(t *testing.T) {
   300  	// The prime factors of 5959 are 59 and 101. The values a and b calculated
   301  	// by Fermat's method will be 80 and 21. The ceil of the square root of 5959
   302  	// is 78. Therefore it takes 3 rounds of Fermat's method to find the factors.
   303  	n := big.NewInt(5959)
   304  	err := checkPrimeFactorsTooClose(n, 2)
   305  	test.AssertNotError(t, err, "factored n in too few iterations")
   306  	err = checkPrimeFactorsTooClose(n, 3)
   307  	test.AssertError(t, err, "failed to factor n")
   308  	test.AssertContains(t, err.Error(), "p: 101")
   309  	test.AssertContains(t, err.Error(), "q: 59")
   310  
   311  	// These factors differ only in their second-to-last digit. They're so close
   312  	// that a single iteration of Fermat's method is sufficient to find them.
   313  	p, ok := new(big.Int).SetString("12451309173743450529024753538187635497858772172998414407116324997634262083672423797183640278969532658774374576700091736519352600717664126766443002156788367", 10)
   314  	test.Assert(t, ok, "failed to create large prime")
   315  	q, ok := new(big.Int).SetString("12451309173743450529024753538187635497858772172998414407116324997634262083672423797183640278969532658774374576700091736519352600717664126766443002156788337", 10)
   316  	test.Assert(t, ok, "failed to create large prime")
   317  	n = n.Mul(p, q)
   318  	err = checkPrimeFactorsTooClose(n, 0)
   319  	test.AssertNotError(t, err, "factored n in too few iterations")
   320  	err = checkPrimeFactorsTooClose(n, 1)
   321  	test.AssertError(t, err, "failed to factor n")
   322  	test.AssertContains(t, err.Error(), fmt.Sprintf("p: %s", p))
   323  	test.AssertContains(t, err.Error(), fmt.Sprintf("q: %s", q))
   324  
   325  	// These factors differ by slightly more than 2^256.
   326  	p, ok = p.SetString("11779932606551869095289494662458707049283241949932278009554252037480401854504909149712949171865707598142483830639739537075502512627849249573564209082969463", 10)
   327  	test.Assert(t, ok, "failed to create large prime")
   328  	q, ok = q.SetString("11779932606551869095289494662458707049283241949932278009554252037480401854503793357623711855670284027157475142731886267090836872063809791989556295953329083", 10)
   329  	test.Assert(t, ok, "failed to create large prime")
   330  	n = n.Mul(p, q)
   331  	err = checkPrimeFactorsTooClose(n, 13)
   332  	test.AssertNotError(t, err, "factored n in too few iterations")
   333  	err = checkPrimeFactorsTooClose(n, 14)
   334  	test.AssertError(t, err, "failed to factor n")
   335  	test.AssertContains(t, err.Error(), fmt.Sprintf("p: %s", p))
   336  	test.AssertContains(t, err.Error(), fmt.Sprintf("q: %s", q))
   337  }
   338  
   339  func benchFermat(rounds int, b *testing.B) {
   340  	n := big.NewInt(0)
   341  	n.SetString("801622717394169050106926578578301725055526605503706912100006286161529273473377413824975745384114446662904851914935980611269769546695796451504160869649117000521094368058953989236438103975426680952076533198797388295193391779933559668812684470909409457778161223896975426492372231040386646816154793996920467596916193680611886097694746368434138296683172992347929528214464827172059378866098534956467670429228681248968588692628197119606249988365750115578731538804653322115223303388019261933988266126675740797091559541980722545880793708750882230374320698192373040882555154628949384420712168289605526223733016176898368282023301917856921049583659644200174763940543991507836551835324807116188739389620816364505209568211448815747330488813651206715564392791134964121857454359816296832013457790067067190116393364546525054134704119475840526673114964766611499226043189928040037210929720682839683846078550615582181112536768195193557758454282232948765374797970874053642822355832904812487562117265271449547063765654262549173209805579494164339236981348054782533307762260970390747872669357067489756517340817289701322583209366268084923373164395703994945233187987667632964509271169622904359262117908604555420100186491963838567445541249128944592555657626247", 10)
   342  	for i := 0; i < b.N; i++ {
   343  		if checkPrimeFactorsTooClose(n, rounds) != nil {
   344  			b.Fatal("factored the unfactorable!")
   345  		}
   346  	}
   347  }
   348  
   349  func BenchmarkFermat1(b *testing.B)     { benchFermat(1, b) }
   350  func BenchmarkFermat10(b *testing.B)    { benchFermat(10, b) }
   351  func BenchmarkFermat100(b *testing.B)   { benchFermat(100, b) }
   352  func BenchmarkFermat1000(b *testing.B)  { benchFermat(1000, b) }
   353  func BenchmarkFermat10000(b *testing.B) { benchFermat(10000, b) }
   354
View as plain text