[Cryptech-Commits] [user/shatov/ecdsa_fpga_model] 01/01: 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 mo [...]

[git at cryptech.is]

This is an automated email from the git hooks/post-receive script.

meisterpaul1 at yandex.ru pushed a commit to branch fix
in repository user/shatov/ecdsa_fpga_model.

commit e718fdfae6443466e566ed6ce1515cdecc215ac0
Author: Pavel V. Shatov (Meister) <meisterpaul1 at yandex.ru>
AuthorDate: Sun Feb 25 14:25:49 2018 +0300

    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.
---
 ecdsa_model.h        | 10 +++++-----
 ecdsa_model_fpga.cpp | 33 +++++++++++++++++++++++++++++++++
 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
@@ -111,6 +111,39 @@ int main()
 	if (!ok) return EXIT_FAILURE;
 
 
+		//
+		// 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
 		//