This commit fixes a theoretical bug in the base point multiplier model. The

model does multiplication using the double-and-add algorithm. When adding two
points P and Q on curves P-256 and P-384, four special cases must be
considered. One of them is P = Q, in that situation the explicit addition
formulae don't work and either 2*P or 2*Q must be returned from the addition
routine. In this model Q is always the base point G, so when P = G, then 2*G
must be returned. Since G is fixed, this model stores precomputed point H = 2*G
and returns it when adding G+G for true constant-time operation. The problem is
that the currently stored coordinates of the point H are wrong. I think I used
the doubling routine (which returns in projective Jacobian coordinates) to
calculate H = 2*G, but then screwed up and forgot to convert it to affine
coordinates before storing x and y.

During multiplication the bits of k are scanned left-to-right, so doubling is
done before addition. This way the only situation when both inputs to the
addition routine are equal to G is when after doubling the result is G. This in
its turn is only possible when k = n + 2 (where n is the order of the base
point G). ECDSA requires integer k to be [1, n-1], so the current wrong
coordinates should never be used in practice. I'm not aware of any attacks
based on this bug, but I feel that it must be fixed, moreover the fix is
straightforward and only involves changing two lines of code used to initialize
arrays. One of the side effects is that the model has a code path that will
never be used under normal operation. This code path can be verified by first
multiplying by k = 2 (special handling for P = G not triggered), then
multiplying by k = n+2 (special handling for P = G triggered). Both
multiplications should produce the same output. In the former case the output
will be calculated on-the-fly, in the latter case the pre-computed coordinates
of H will be used.

2 files changed, 38 insertions, 5 deletions

diff --git a/ecdsa_model.h b/ecdsa_model.h
index fc7e571..4039e25 100644
--- a/ecdsa_model.h
+++ b/ecdsa_model.h
@@ -45,7 +45,7 @@
 // USE_CURVE == 2  -> P-384

 //

 //------------------------------------------------------------------------------

-#define USE_CURVE	2

+#define USE_CURVE	1

 

 

 //------------------------------------------------------------------------------

@@ -79,8 +79,8 @@
 #define P_256_G_Y		{0x4fe342e2, 0xfe1a7f9b, 0x8ee7eb4a, 0x7c0f9e16, 0x2bce3357, 0x6b315ece, 0xcbb64068, 0x37bf51f5}

 

 /* Doubled Base Point */

-#define P_256_H_X		{0x29d05c19, 0x3da77b71, 0x0e863235, 0x38b77e1b, 0x11f904fe, 0xa42998be, 0x16bd8d74, 0x4ece7ad0}

-#define P_256_H_Y		{0xb01cbd1c, 0x01e58065, 0x711814b5, 0x83f061e9, 0xd431cca9, 0x94cea131, 0x3449bf97, 0xc840ae07}

+#define P_256_H_X		{0x7cf27b18, 0x8d034f7e, 0x8a523803, 0x04b51ac3, 0xc08969e2, 0x77f21b35, 0xa60b48fc, 0x47669978}

+#define P_256_H_Y		{0x07775510, 0xdb8ed040, 0x293d9ac6, 0x9f7430db, 0xba7dade6, 0x3ce98229, 0x9e04b79d, 0x227873d1}

 

 /* Base Point Order */

 #define P_256_N			{0xffffffff, 0x00000000, 0xffffffff, 0xffffffff, 0xbce6faad, 0xa7179e84, 0xf3b9cac2, 0xfc632551}

@@ -119,8 +119,8 @@
 #define P_384_G_Y		{0x3617de4a, 0x96262c6f, 0x5d9e98bf, 0x9292dc29, 0xf8f41dbd, 0x289a147c, 0xe9da3113, 0xb5f0b8c0, 0x0a60b1ce, 0x1d7e819d, 0x7a431d7c, 0x90ea0e5f}

 

 /* Doubled Base Point */

-#define P_384_H_X		{0xaaf06bba, 0x82e9f590, 0xe29c71c2, 0x19bea517, 0x23c5893a, 0xe8b0c8cf, 0x4c117c3e, 0xfb57ab8d, 0x55fa1b42, 0x8155ad27, 0x8b574391, 0x1b13ea8a}

-#define P_384_H_Y		{0xc9e821b5, 0x69d9d390, 0xa2616740, 0x6d6d23d6, 0x070be242, 0xd765eb83, 0x1625ceec, 0x4a0f473e, 0xf59f4e30, 0xe2817e62, 0x85bce284, 0x6f15f19d}

+#define P_384_H_X		{0x08d99905, 0x7ba3d2d9, 0x69260045, 0xc55b97f0, 0x89025959, 0xa6f434d6, 0x51d207d1, 0x9fb96e9e, 0x4fe0e86e, 0xbe0e64f8, 0x5b96a9c7, 0x5295df61}

+#define P_384_H_Y		{0x8e80f1fa, 0x5b1b3ced, 0xb7bfe8df, 0xfd6dba74, 0xb275d875, 0xbc6cc43e, 0x904e505f, 0x256ab425, 0x5ffd43e9, 0x4d39e22d, 0x61501e70, 0x0a940e80}

 

 /* Base Point Order */

 #define P_384_N			{0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xc7634d81, 0xf4372ddf, 0x581a0db2, 0x48b0a77a, 0xecec196a, 0xccc52973}

diff --git a/ecdsa_model_fpga.cpp b/ecdsa_model_fpga.cpp
index 8ad0962..546e206 100644
--- a/ecdsa_model_fpga.cpp
+++ b/ecdsa_model_fpga.cpp
@@ -112,6 +112,39 @@ int main()
 

 

 		//

+		// test base point multiplier: H = 2 * G

+		//

+	FPGA_BUFFER two;

+	fpga_modular_add(&ecdsa_one, &ecdsa_one, &two);

+

+	printf("Trying to double the base point...\n\n");

+	ok = test_base_point_multiplier(&two, &ecdsa_h_x, &ecdsa_h_y);

+	if (!ok) return EXIT_FAILURE;

+

+	

+		//

+		// test base point multiplier: G = (n + 1) * G

+		//

+	FPGA_BUFFER n1;

+	fpga_modular_add(&ecdsa_n, &ecdsa_one, &n1);	// n1 = n + 1

+

+	printf("Trying to multiply the base point by its order plus one...\n\n");

+	ok = test_base_point_multiplier(&n1, &ecdsa_g_x, &ecdsa_g_y);

+	if (!ok) return EXIT_FAILURE;

+

+

+		//

+		// test base point multiplier: G = (n + 2) * G

+		//

+	FPGA_BUFFER n2;

+	fpga_modular_add(&ecdsa_n, &two, &n2);	// n2 = n + two

+

+	printf("Trying to multiply the base point by its order plus two...\n\n");

+	ok = test_base_point_multiplier(&n2, &ecdsa_h_x, &ecdsa_h_y);

+	if (!ok) return EXIT_FAILURE;

+

+	

+		//

 		// try to abuse internal point doubler

 		//

 	ok = abuse_internal_point_doubler();