csidh_test.go

Documentation: github.com/cloudflare/circl/dh/csidh

     1  package csidh
     2  
     3  import (
     4  	"bytes"
     5  	"crypto/rand"
     6  	"encoding/binary"
     7  	"encoding/hex"
     8  	"encoding/json"
     9  	"os"
    10  	"testing"
    11  
    12  	. "github.com/cloudflare/circl/internal/test"
    13  )
    14  
    15  // Possible values for "Status"
    16  const (
    17  	Valid               = iota // Indicates that shared secret must be agreed correctly
    18  	ValidPublicKey2            // Public key 2 must succeed validation
    19  	InvalidSharedSecret        // Calculated shared secret must be different than test vector
    20  	InvalidPublicKey1          // Public key 1 generated from private key must be different than test vector
    21  	InvalidPublicKey2          // Public key 2 must fail validation
    22  )
    23  
    24  var StatusValues = map[int]string{
    25  	Valid:               "valid",
    26  	ValidPublicKey2:     "valid_public_key2",
    27  	InvalidSharedSecret: "invalid_shared_secret",
    28  	InvalidPublicKey1:   "invalid_public_key1",
    29  	InvalidPublicKey2:   "invalid_public_key2",
    30  }
    31  
    32  var rng = rand.Reader
    33  
    34  type TestVector struct {
    35  	ID     int    `json:"Id"`
    36  	Pk1    string `json:"Pk1"`
    37  	Pr1    string `json:"Pr1"`
    38  	Pk2    string `json:"Pk2"`
    39  	Ss     string `json:"Ss"`
    40  	Status string `json:"status"`
    41  }
    42  
    43  type TestVectors struct {
    44  	Vectors []TestVector `json:"Vectors"`
    45  }
    46  
    47  func TestCompare64(t *testing.T) {
    48  	const s uint64 = 0xFFFFFFFFFFFFFFFF
    49  	val1 := fp{0, 2, 3, 4, 5, 6, 7, 8}
    50  	val2 := fp{s, s, s, s, s, s, s, s}
    51  	var zero fp
    52  
    53  	if !zero.isZero() {
    54  		t.Errorf("isZero returned true, where it should be false")
    55  	}
    56  	if val1.isZero() {
    57  		t.Errorf("isZero returned false, where it should be true")
    58  	}
    59  	if val2.isZero() {
    60  		t.Errorf("isZero returned false, where it should be true")
    61  	}
    62  }
    63  
    64  func TestEphemeralKeyExchange(t *testing.T) {
    65  	var ss1, ss2 [64]byte
    66  	var prv1, prv2 PrivateKey
    67  	var pub1, pub2 PublicKey
    68  
    69  	prvBytes1 := []byte{0xaa, 0x54, 0xe4, 0xd4, 0xd0, 0xbd, 0xee, 0xcb, 0xf4, 0xd0, 0xc2, 0xbc, 0x52, 0x44, 0x11, 0xee, 0xe1, 0x14, 0xd2, 0x24, 0xe5, 0x0, 0xcc, 0xf5, 0xc0, 0xe1, 0x1e, 0xb3, 0x43, 0x52, 0x45, 0xbe, 0xfb, 0x54, 0xc0, 0x55, 0xb2}
    70  	prv1.Import(prvBytes1)
    71  	GeneratePublicKey(&pub1, &prv1, rng)
    72  
    73  	CheckNoErr(t, GeneratePrivateKey(&prv2, rng), "PrivateKey generation failed")
    74  	GeneratePublicKey(&pub2, &prv2, rng)
    75  
    76  	CheckOk(
    77  		DeriveSecret(&ss1, &pub1, &prv2, rng),
    78  		"Derivation failed", t)
    79  	CheckOk(
    80  		DeriveSecret(&ss2, &pub2, &prv1, rng),
    81  		"Derivation failed", t)
    82  
    83  	if !bytes.Equal(ss1[:], ss2[:]) {
    84  		t.Error("ss1 != ss2")
    85  	}
    86  }
    87  
    88  func TestPrivateKeyExportImport(t *testing.T) {
    89  	var buf [37]byte
    90  	for i := 0; i < numIter; i++ {
    91  		var prv1, prv2 PrivateKey
    92  		CheckNoErr(t, GeneratePrivateKey(&prv1, rng), "PrivateKey generation failed")
    93  		prv1.Export(buf[:])
    94  		prv2.Import(buf[:])
    95  
    96  		for i := 0; i < len(prv1.e); i++ {
    97  			if prv1.e[i] != prv2.e[i] {
    98  				t.Error("Error occurred when public key export/import")
    99  			}
   100  		}
   101  	}
   102  }
   103  
   104  func TestValidateNegative(t *testing.T) {
   105  	pk := PublicKey{a: p}
   106  	pk.a[0]++
   107  	if Validate(&pk, rng) {
   108  		t.Error("Public key > p has been validated")
   109  	}
   110  
   111  	pk = PublicKey{a: p}
   112  	if Validate(&pk, rng) {
   113  		t.Error("Public key == p has been validated")
   114  	}
   115  
   116  	pk = PublicKey{a: two}
   117  	if Validate(&pk, rng) {
   118  		t.Error("Public key == 2 has been validated")
   119  	}
   120  
   121  	pk = PublicKey{a: twoNeg}
   122  	if Validate(&pk, rng) {
   123  		t.Error("Public key == -2 has been validated")
   124  	}
   125  }
   126  
   127  func TestPublicKeyExportImport(t *testing.T) {
   128  	var buf [64]byte
   129  	eq64 := func(x, y []uint64) bool {
   130  		for i := range x {
   131  			if x[i] != y[i] {
   132  				return false
   133  			}
   134  		}
   135  		return true
   136  	}
   137  
   138  	for i := 0; i < numIter; i++ {
   139  		var prv PrivateKey
   140  		var pub1, pub2 PublicKey
   141  		CheckNoErr(t, GeneratePrivateKey(&prv, rng), "PrivateKey generation failed")
   142  		GeneratePublicKey(&pub1, &prv, rng)
   143  
   144  		pub1.Export(buf[:])
   145  		pub2.Import(buf[:])
   146  
   147  		if !eq64(pub1.a[:], pub2.a[:]) {
   148  			t.Error("Error occurred when public key export/import")
   149  		}
   150  	}
   151  }
   152  
   153  // Test vectors generated by reference implementation.
   154  func TestKAT(t *testing.T) {
   155  	var tests TestVectors
   156  	// Helper checks if e==true and reports an error if not.
   157  	checkExpr := func(e bool, vec *TestVector, t *testing.T, msg string) {
   158  		t.Helper()
   159  		if !e {
   160  			t.Errorf("[Test ID=%d] "+msg, vec.ID)
   161  		}
   162  	}
   163  	// checkSharedSecret implements nominal case - imports asymmetric keys for
   164  	// both parties, derives secret key and compares it to value in test vector.
   165  	// Comparison must succeed in case status is "Valid" in any other case
   166  	// it must fail.
   167  	checkSharedSecret := func(vec *TestVector, t *testing.T, status int) {
   168  		var prv1 PrivateKey
   169  		var pub1, pub2 PublicKey
   170  		var ss [SharedSecretSize]byte
   171  
   172  		prBuf, err := hex.DecodeString(vec.Pr1)
   173  		if err != nil {
   174  			t.Fatal(err)
   175  		}
   176  		checkExpr(prv1.Import(prBuf[:]), vec, t, "PrivateKey wrong")
   177  		pkBuf, err := hex.DecodeString(vec.Pk1)
   178  		if err != nil {
   179  			t.Fatal(err)
   180  		}
   181  		checkExpr(pub1.Import(pkBuf[:]), vec, t, "PublicKey 1 wrong")
   182  		pkBuf, err = hex.DecodeString(vec.Pk2)
   183  		if err != nil {
   184  			t.Fatal(err)
   185  		}
   186  		checkExpr(pub2.Import(pkBuf[:]), vec, t, "PublicKey 2 wrong")
   187  		checkExpr(DeriveSecret(&ss, &pub2, &prv1, rng), vec, t, "Error when deriving key")
   188  		ssExp, err := hex.DecodeString(vec.Ss)
   189  		if err != nil {
   190  			t.Fatal(err)
   191  		}
   192  		checkExpr(bytes.Equal(ss[:], ssExp) == (status == Valid), vec, t, "Unexpected value of shared secret")
   193  	}
   194  	// checkPublicKey1 imports public and private key for one party A
   195  	// and tries to generate public key for a private key. After that
   196  	// it compares generated key to a key from test vector. Comparison
   197  	// must fail.
   198  	checkPublicKey1 := func(vec *TestVector, t *testing.T) {
   199  		var prv PrivateKey
   200  		var pub PublicKey
   201  		var pubBytesGot [PublicKeySize]byte
   202  
   203  		prBuf, err := hex.DecodeString(vec.Pr1)
   204  		if err != nil {
   205  			t.Fatal(err)
   206  		}
   207  
   208  		pubBytesExp, err := hex.DecodeString(vec.Pk1)
   209  		if err != nil {
   210  			t.Fatal(err)
   211  		}
   212  
   213  		checkExpr(
   214  			prv.Import(prBuf[:]),
   215  			vec, t, "PrivateKey wrong")
   216  
   217  		// Generate public key
   218  		CheckNoErr(t, GeneratePrivateKey(&prv, rng), "PrivateKey generation failed")
   219  		pub.Export(pubBytesGot[:])
   220  
   221  		// pubBytesGot must be different than pubBytesExp
   222  		checkExpr(
   223  			!bytes.Equal(pubBytesGot[:], pubBytesExp),
   224  			vec, t, "Public key generated is the same as public key from the test vector")
   225  	}
   226  	// checkPublicKey2 the goal is to test key validation. Test tries to
   227  	// import public key for B and ensure that import succeeds in case
   228  	// status is "Valid" and fails otherwise.
   229  	checkPublicKey2 := func(vec *TestVector, t *testing.T, status int) {
   230  		var pub PublicKey
   231  		pubBytesExp, err := hex.DecodeString(vec.Pk2)
   232  		if err != nil {
   233  			t.Fatal(err)
   234  		}
   235  		// Import validates an input, so it must fail
   236  		pub.Import(pubBytesExp[:])
   237  		checkExpr(
   238  			Validate(&pub, rng) == (status == Valid || status == ValidPublicKey2),
   239  			vec, t, "PublicKey has been validated correctly")
   240  	}
   241  	// Load test data
   242  	file, err := os.Open(katFile)
   243  	if err != nil {
   244  		t.Fatal(err.Error())
   245  	}
   246  	err = json.NewDecoder(file).Decode(&tests)
   247  	if err != nil {
   248  		t.Fatal(err.Error())
   249  	}
   250  	// Loop over numIter test cases
   251  	// The algorithm is relatively slow, so it tests a smaller number.
   252  	N := len(tests.Vectors)
   253  	var buf [2]byte
   254  	for i := 0; i < numIter; i++ {
   255  		_, _ = rand.Read(buf[:])
   256  		idx := binary.LittleEndian.Uint16(buf[:]) % uint16(N)
   257  		test := tests.Vectors[idx]
   258  		switch test.Status {
   259  		case StatusValues[Valid]:
   260  			checkSharedSecret(&test, t, Valid)
   261  			checkPublicKey2(&test, t, Valid)
   262  		case StatusValues[InvalidSharedSecret]:
   263  			checkSharedSecret(&test, t, InvalidSharedSecret)
   264  		case StatusValues[InvalidPublicKey1]:
   265  			checkPublicKey1(&test, t)
   266  		case StatusValues[InvalidPublicKey2]:
   267  			checkPublicKey2(&test, t, InvalidPublicKey2)
   268  		case StatusValues[InvalidPublicKey2]:
   269  			checkPublicKey2(&test, t, InvalidPublicKey2)
   270  		case StatusValues[ValidPublicKey2]:
   271  			checkPublicKey2(&test, t, ValidPublicKey2)
   272  		}
   273  	}
   274  }
   275  
   276  var (
   277  	prv1, prv2 PrivateKey
   278  	pub1, pub2 PublicKey
   279  )
   280  
   281  // Private key generation.
   282  func BenchmarkGeneratePrivate(b *testing.B) {
   283  	for n := 0; n < b.N; n++ {
   284  		_ = GeneratePrivateKey(&prv1, rng)
   285  	}
   286  }
   287  
   288  // Public key generation from private (group action on empty key).
   289  func BenchmarkGenerateKeyPair(b *testing.B) {
   290  	for n := 0; n < b.N; n++ {
   291  		var pub PublicKey
   292  		_ = GeneratePrivateKey(&prv1, rng)
   293  		GeneratePublicKey(&pub, &prv1, rng)
   294  	}
   295  }
   296  
   297  // Benchmark validation on same key multiple times.
   298  func BenchmarkValidate(b *testing.B) {
   299  	prvBytes := []byte{0xaa, 0x54, 0xe4, 0xd4, 0xd0, 0xbd, 0xee, 0xcb, 0xf4, 0xd0, 0xc2, 0xbc, 0x52, 0x44, 0x11, 0xee, 0xe1, 0x14, 0xd2, 0x24, 0xe5, 0x0, 0xcc, 0xf5, 0xc0, 0xe1, 0x1e, 0xb3, 0x43, 0x52, 0x45, 0xbe, 0xfb, 0x54, 0xc0, 0x55, 0xb2}
   300  	prv1.Import(prvBytes)
   301  
   302  	var pub PublicKey
   303  	GeneratePublicKey(&pub, &prv1, rng)
   304  
   305  	for n := 0; n < b.N; n++ {
   306  		Validate(&pub, rng)
   307  	}
   308  }
   309  
   310  // Benchmark validation on random (most probably wrong) key.
   311  func BenchmarkValidateRandom(b *testing.B) {
   312  	var tmp [64]byte
   313  	var pub PublicKey
   314  
   315  	// Initialize seed
   316  	for n := 0; n < b.N; n++ {
   317  		if _, err := rng.Read(tmp[:]); err != nil {
   318  			b.FailNow()
   319  		}
   320  		pub.Import(tmp[:])
   321  	}
   322  }
   323  
   324  // Benchmark validation on different keys.
   325  func BenchmarkValidateGenerated(b *testing.B) {
   326  	for n := 0; n < b.N; n++ {
   327  		_ = GeneratePrivateKey(&prv1, rng)
   328  		GeneratePublicKey(&pub1, &prv1, rng)
   329  		Validate(&pub1, rng)
   330  	}
   331  }
   332  
   333  // Generate some keys and benchmark derive.
   334  func BenchmarkDerive(b *testing.B) {
   335  	var ss [64]byte
   336  
   337  	_ = GeneratePrivateKey(&prv1, rng)
   338  	GeneratePublicKey(&pub1, &prv1, rng)
   339  
   340  	_ = GeneratePrivateKey(&prv2, rng)
   341  	GeneratePublicKey(&pub2, &prv2, rng)
   342  
   343  	b.ResetTimer()
   344  	for n := 0; n < b.N; n++ {
   345  		DeriveSecret(&ss, &pub2, &prv1, rng)
   346  	}
   347  }
   348  
   349  // Benchmarks both - key generation and derivation.
   350  func BenchmarkDeriveGenerated(b *testing.B) {
   351  	var ss [64]byte
   352  
   353  	for n := 0; n < b.N; n++ {
   354  		_ = GeneratePrivateKey(&prv1, rng)
   355  		GeneratePublicKey(&pub1, &prv1, rng)
   356  
   357  		_ = GeneratePrivateKey(&prv2, rng)
   358  		GeneratePublicKey(&pub2, &prv2, rng)
   359  
   360  		DeriveSecret(&ss, &pub2, &prv1, rng)
   361  	}
   362  }
   363
View as plain text