From e718fdfae6443466e566ed6ce1515cdecc215ac0 Mon Sep 17 00:00:00 2001 From: "Pavel V. Shatov (Meister)" Date: Sun, 25 Feb 2018 14:25:49 +0300 Subject: 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_fpga.cpp | 33 +++++++++++++++++++++++++++++++++ 1 file changed, 33 insertions(+) (limited to 'ecdsa_model_fpga.cpp') 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 // -- cgit v1.2.3