aboutsummaryrefslogtreecommitdiff
path: root/ecdsa_model.h
diff options
context:
space:
mode:
authorPavel V. Shatov (Meister) <meisterpaul1@yandex.ru>2018-02-25 14:25:49 +0300
committerPavel V. Shatov (Meister) <meisterpaul1@yandex.ru>2018-02-26 13:13:39 +0300
commite718fdfae6443466e566ed6ce1515cdecc215ac0 (patch)
tree4ee792bda9736c063a556a9250447fc1d9fefaf7 /ecdsa_model.h
parentcae8718217846cfaefcbfecd55f9a117731a8d99 (diff)
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.
Diffstat (limited to 'ecdsa_model.h')
-rw-r--r--ecdsa_model.h10
1 files changed, 5 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}