* New hardware architecture

 * Randomized test vector

1 files changed, 539 insertions, 0 deletions

diff --git a/ecdsa_fpga_model.cpp b/ecdsa_fpga_model.cpp
new file mode 100644
index 0000000..182c2ab
--- /dev/null
+++ b/ecdsa_fpga_model.cpp
@@ -0,0 +1,539 @@
+//------------------------------------------------------------------------------
+//
+// ecdsa_fpga_model.cpp
+// --------------------------------------------
+// Base point scalar multiplier model for ECDSA
+//
+// Authors: Pavel Shatov
+//
+// Copyright (c) 2015-2016, 2018 NORDUnet A/S
+//
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are met:
+//
+// - Redistributions of source code must retain the above copyright notice,
+//   this list of conditions and the following disclaimer.
+//
+// - Redistributions in binary form must reproduce the above copyright notice,
+//   this list of conditions and the following disclaimer in the documentation
+//   and/or other materials provided with the distribution.
+//
+// - Neither the name of the NORDUnet nor the names of its contributors may be
+//   used to endorse or promote products derived from this software without
+//   specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+// ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
+// LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+// CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+// SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+// CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+// ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+// POSSIBILITY OF SUCH DAMAGE.
+//
+//------------------------------------------------------------------------------
+
+
+//------------------------------------------------------------------------------
+// Headers
+//------------------------------------------------------------------------------
+#include <stdio.h>
+#include <stdlib.h>
+
+
+//------------------------------------------------------------------------------
+// Microcode Switch
+//------------------------------------------------------------------------------
+#define USE_MICROCODE
+
+
+//------------------------------------------------------------------------------
+// More Headers
+//------------------------------------------------------------------------------
+#include "ecdsa_fpga_model.h"
+
+
+//------------------------------------------------------------------------------
+// Prototypes
+//------------------------------------------------------------------------------
+void fpga_model_init ();
+
+bool test_base_point_multiplier (const FPGA_BUFFER *k,
+                                 const FPGA_BUFFER *qx,
+                                 const FPGA_BUFFER *qy);
+
+bool abuse_internal_point_adder   ();
+bool abuse_internal_point_doubler ();
+
+
+//------------------------------------------------------------------------------
+// Locals
+//------------------------------------------------------------------------------
+static FPGA_BUFFER ecdsa_d_nsa;
+static FPGA_BUFFER ecdsa_qx_nsa;
+static FPGA_BUFFER ecdsa_qy_nsa;
+
+static FPGA_BUFFER ecdsa_k_nsa;
+static FPGA_BUFFER ecdsa_rx_nsa;
+static FPGA_BUFFER ecdsa_ry_nsa;
+
+static FPGA_BUFFER ecdsa_d_random;
+static FPGA_BUFFER ecdsa_qx_random;
+static FPGA_BUFFER ecdsa_qy_random;
+
+
+//------------------------------------------------------------------------------
+int main()
+//------------------------------------------------------------------------------
+{
+    bool    ok;     // flag
+
+        // initialize buffers
+    fpga_multiword_init();
+    fpga_modular_init();
+    fpga_curve_init();
+    fpga_model_init();
+
+	printf("ECDSA_UOP_OPERAND_COUNT == %d\n\n", ECDSA_UOP_OPERAND_COUNT);
+
+		// test base point multiplier: Q = d * G
+    printf("Trying to derive public key from private key (NSA test vector)...\n\n");
+    ok = test_base_point_multiplier(&ecdsa_d_nsa, &ecdsa_qx_nsa, &ecdsa_qy_nsa);
+    if (!ok) return EXIT_FAILURE;
+
+        // test base point multiplier: R = k * G
+    printf("Trying to sign something (NSA test vector)...\n\n");
+    ok = test_base_point_multiplier(&ecdsa_k_nsa, &ecdsa_rx_nsa, &ecdsa_ry_nsa);
+    if (!ok) return EXIT_FAILURE;
+
+		// test base point multiplier: Q = d * G
+    printf("Trying to derive public key from private key (random test vector)...\n\n");
+    ok = test_base_point_multiplier(&ecdsa_d_random, &ecdsa_qx_random, &ecdsa_qy_random);
+    if (!ok) return EXIT_FAILURE;
+
+        // test base point multiplier: O = n * G
+    printf("Trying to multiply the base point by its order...\n\n");
+    ok = test_base_point_multiplier(&ECDSA_N, &ECDSA_ZERO, &ECDSA_ZERO);
+    if (!ok) return EXIT_FAILURE;
+
+        // now run some intricate tests...
+
+        /* Excerpt from the commit message e718fdfae6443466e566ed6ce1515cdecc215ac0:
+
+        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.
+    
+        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], 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.
+         */
+
+
+		// 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_HX, &ECDSA_HY);
+    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_GX, &ECDSA_GY);
+    if (!ok) return EXIT_FAILURE;
+
+        // test base point multiplier: H = (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_HX, &ECDSA_HY);
+    if (!ok) return EXIT_FAILURE;
+
+        // ..and some more tests
+
+        // try to abuse internal point doubler
+    ok = abuse_internal_point_doubler();
+    if (!ok) return EXIT_FAILURE;
+    
+        // try to abuse internal point adder
+    ok = abuse_internal_point_adder();
+    if (!ok) return EXIT_FAILURE;
+
+        // everything went just fine
+    return EXIT_SUCCESS;
+}
+
+
+//------------------------------------------------------------------------------
+void fpga_model_init()
+//------------------------------------------------------------------------------
+{
+    int w;  // word counter
+
+    FPGA_BUFFER tmp_d_nsa  = ECDSA_D_NSA_INIT, tmp_k_nsa = ECDSA_K_NSA_INIT;
+    FPGA_BUFFER tmp_qx_nsa = ECDSA_QX_NSA_INIT, tmp_rx_nsa = ECDSA_RX_NSA_INIT;
+    FPGA_BUFFER tmp_qy_nsa = ECDSA_QY_NSA_INIT, tmp_ry_nsa = ECDSA_RY_NSA_INIT;
+
+	FPGA_BUFFER tmp_d_random  = ECDSA_D_RANDOM_INIT;
+    FPGA_BUFFER tmp_qx_random = ECDSA_QX_RANDOM_INIT;
+    FPGA_BUFFER tmp_qy_random = ECDSA_QY_RANDOM_INIT;
+
+        // fill buffers for large multi-word integers
+    for (w=0; w<FPGA_OPERAND_NUM_WORDS; w++)
+    {
+        ecdsa_d_nsa.words[w] = tmp_d_nsa.words[FPGA_OPERAND_NUM_WORDS - (w+1)];
+        ecdsa_qx_nsa.words[w] = tmp_qx_nsa.words[FPGA_OPERAND_NUM_WORDS - (w+1)];
+        ecdsa_qy_nsa.words[w] = tmp_qy_nsa.words[FPGA_OPERAND_NUM_WORDS - (w+1)];
+
+        ecdsa_k_nsa.words[w] = tmp_k_nsa.words[FPGA_OPERAND_NUM_WORDS - (w+1)];
+        ecdsa_rx_nsa.words[w] = tmp_rx_nsa.words[FPGA_OPERAND_NUM_WORDS - (w+1)];
+        ecdsa_ry_nsa.words[w] = tmp_ry_nsa.words[FPGA_OPERAND_NUM_WORDS - (w+1)];
+
+		ecdsa_d_random.words[w] = tmp_d_random.words[FPGA_OPERAND_NUM_WORDS - (w+1)];
+        ecdsa_qx_random.words[w] = tmp_qx_random.words[FPGA_OPERAND_NUM_WORDS - (w+1)];
+        ecdsa_qy_random.words[w] = tmp_qy_random.words[FPGA_OPERAND_NUM_WORDS - (w+1)];
+    }
+}
+
+
+//------------------------------------------------------------------------------
+bool test_base_point_multiplier (const FPGA_BUFFER *k,
+                                 const FPGA_BUFFER *qx,
+                                 const FPGA_BUFFER *qy)
+//------------------------------------------------------------------------------
+//
+// k - multiplier
+//
+// qx, qy - expected coordinates of product
+//
+// Returns true when point (rx,ry) = k * G matches the point (qx,qy).
+//
+//------------------------------------------------------------------------------
+{
+    bool ok;                // flag
+    FPGA_BUFFER rx, ry;     // result
+
+        // run the model
+    fpga_curve_base_scalar_multiply(k, &rx, &ry);
+
+        // handle result
+    ok = compare_fpga_buffers(qx, qy, &rx, &ry);
+
+    if (!ok)
+    {   printf("\n    ERROR\n\n");
+        return false;
+    }
+    else printf("\n    OK\n\n");
+
+        // everything went just fine
+    return true;
+}
+
+
+//------------------------------------------------------------------------------
+bool compare_fpga_buffers(  const FPGA_BUFFER *az,
+                            const FPGA_BUFFER *bz)
+//------------------------------------------------------------------------------
+//
+// Compare z-coordinates of two points and return true when they match.
+//
+//------------------------------------------------------------------------------
+{
+    int w;  // word counter
+
+        // print all the values
+    print_fpga_buffer("  Expected:   Z = ", az);
+    print_fpga_buffer("  Calculated: Z = ", bz);
+
+        // compare values
+    for (w=0; w<FPGA_OPERAND_NUM_WORDS; w++)
+    {
+            // compare x
+        if (az->words[w] != bz->words[w]) return false;
+    }
+
+        // values are the same
+    return true;
+}
+
+
+//------------------------------------------------------------------------------
+bool compare_fpga_buffers(  const FPGA_BUFFER *ax,
+                            const FPGA_BUFFER *ay,
+                            const FPGA_BUFFER *bx,
+                            const FPGA_BUFFER *by)
+//------------------------------------------------------------------------------
+//
+// Compare affine coordinates of two points and return true when they match.
+//
+//------------------------------------------------------------------------------
+{
+    int w;  // word counter
+
+        // print all the values
+    print_fpga_buffer("  Expected:   X = ", ax);
+    print_fpga_buffer("  Calculated: X = ", bx);
+    printf("\n");
+    print_fpga_buffer("  Expected:   Y = ", ay);
+    print_fpga_buffer("  Calculated: Y = ", by);
+
+        // compare values
+    for (w=0; w<FPGA_OPERAND_NUM_WORDS; w++)
+    {
+            // compare x
+        if (ax->words[w] != bx->words[w]) return false;
+
+            // compare y
+        if (ay->words[w] != by->words[w]) return false;
+    }
+
+        // values are the same
+    return true;
+}
+
+
+//------------------------------------------------------------------------------
+bool compare_fpga_buffers(  const FPGA_BUFFER *ax,
+                            const FPGA_BUFFER *ay,
+                            const FPGA_BUFFER *az,
+                            const FPGA_BUFFER *bx,
+                            const FPGA_BUFFER *by,
+                            const FPGA_BUFFER *bz)
+//------------------------------------------------------------------------------
+//
+// Compare projective coordinates of two points and return true when they match.
+//
+//------------------------------------------------------------------------------
+{
+    int w;  // word counter
+
+        // print all the values
+    print_fpga_buffer("  Expected:   X = ", ax);
+    print_fpga_buffer("  Calculated: X = ", bx);
+    printf("\n");
+    print_fpga_buffer("  Expected:   Y = ", ay);
+    print_fpga_buffer("  Calculated: Y = ", by);
+    printf("\n");
+    print_fpga_buffer("  Expected:   Z = ", az);
+    print_fpga_buffer("  Calculated: Z = ", bz);
+
+        // compare values
+    for (w=0; w<FPGA_OPERAND_NUM_WORDS; w++)
+    {
+            // compare x
+        if (ax->words[w] != bx->words[w]) return false;
+
+            // compare y
+        if (ay->words[w] != by->words[w]) return false;
+
+            // compare z
+        if (az->words[w] != bz->words[w]) return false;
+    }
+
+        // values are the same
+    return true;
+}
+
+
+//------------------------------------------------------------------------------
+void print_fpga_buffer(const char *s, const FPGA_BUFFER *buf)
+//------------------------------------------------------------------------------
+//
+// Pretty print large multi-word integer.
+//
+//------------------------------------------------------------------------------
+{
+    int w;  // word counter
+
+        // print header
+    printf("%s", s);
+
+        // print all bytes
+    for (w=FPGA_OPERAND_NUM_WORDS; w>0; w--)
+    {   
+        printf("%08x", buf->words[w-1]);
+
+            // insert space after every group of 4 bytes
+        if (w > 1) printf(" ");
+    }
+
+        // print footer
+    printf("\n");
+}
+
+
+//------------------------------------------------------------------------------
+void print_fpga_buffer_nodelim(const char *s, const FPGA_BUFFER *buf)
+//------------------------------------------------------------------------------
+//
+// Pretty print large multi-word integer.
+//
+//------------------------------------------------------------------------------
+{
+    int w;  // word counter
+
+        // print header
+    printf("%s", s);
+
+        // print all bytes
+    for (w=FPGA_OPERAND_NUM_WORDS; w>0; w--)
+        printf("%08x", buf->words[w-1]);
+
+        // print footer
+    printf("\n");
+}
+
+
+//------------------------------------------------------------------------------
+bool abuse_internal_point_doubler()
+//------------------------------------------------------------------------------
+//
+// This routine tries to abuse the internal curve point doubler by forcing it
+// to double point at infinity.
+//
+//------------------------------------------------------------------------------
+{
+    int w;      // word counter
+    bool ok;    // flag
+    
+    FPGA_BUFFER px, py, pz;     // input
+    FPGA_BUFFER qx, qy, qz;     // output
+
+        // set P.X and P.Y to some "random" garbage and P.Z to zero
+    for (w=0; w<FPGA_OPERAND_NUM_WORDS; w++)
+    {   px.words[w] = ECDSA_GX.words[w] ^ ECDSA_HX.words[w];
+        py.words[w] = ECDSA_GY.words[w] ^ ECDSA_HY.words[w];
+    }
+    fpga_multiword_copy(&ECDSA_ZERO, &pz);
+
+        // try to double point at infinity (should produce point at infinity)
+    printf("Trying to double something at infinity...\n\n");
+    fpga_curve_double_jacobian(&px, &py, &pz, &qx, &qy, &qz);
+
+        // handle result
+    ok = compare_fpga_buffers(&ECDSA_ZERO, &qz);
+    if (! ok)
+    {   printf("\n    ERROR\n\n");
+        return false;
+    }
+    else printf("\n    OK\n\n");
+
+        // everything went just fine
+    return true;
+}
+
+
+//------------------------------------------------------------------------------
+bool abuse_internal_point_adder()
+//------------------------------------------------------------------------------
+//
+// This routine tries to abuse the internal curve point adder by forcing it to
+// go throgh all the possible "corner cases".
+//
+//------------------------------------------------------------------------------
+{
+    int w;      // word counter 
+    bool ok;    // flag
+
+    FPGA_BUFFER px, py, pz;     // input
+    FPGA_BUFFER rx, ry, rz;     // output
+
+    //
+    // try to add point at infinity to the base point
+    //
+    {
+            // set P.X and P.Y to some "random" garbage and P.Z to zero
+        for (w=0; w<FPGA_OPERAND_NUM_WORDS; w++)
+        {   px.words[w] = ECDSA_GX.words[w] ^ ECDSA_HX.words[w];
+            py.words[w] = ECDSA_GY.words[w] ^ ECDSA_HY.words[w];
+        }
+        fpga_multiword_copy(&ECDSA_ZERO, &pz);
+
+            // run addition proceduce
+        printf("Trying to add something at infinity to the base point...\n\n");
+        fpga_curve_add_jacobian(&px, &py, &pz, &rx, &ry, &rz);
+
+            // handle result
+        ok = compare_fpga_buffers(&ECDSA_GX, &ECDSA_GY, &ECDSA_ONE, &rx, &ry, &rz);
+        if (! ok)
+        {   printf("\n    ERROR\n\n");
+            return false;
+        }
+        else printf("\n    OK\n\n");
+    }
+
+    //
+    // try to add the base point to itself
+    //
+    {
+            // set P to G
+        fpga_multiword_copy(&ECDSA_GX, &px);
+        fpga_multiword_copy(&ECDSA_GY, &py);
+        fpga_multiword_copy(&ECDSA_ONE, &pz);
+
+            // run addition proceduce
+        printf("Trying to add the base point to itself...\n\n");
+        fpga_curve_add_jacobian(&px, &py, &pz, &rx, &ry, &rz);
+
+            // handle result
+        ok = compare_fpga_buffers(&ECDSA_HX, &ECDSA_HY, &ECDSA_ONE, &rx, &ry, &rz);
+        if (! ok)
+        {   printf("\n    ERROR\n\n");
+            return false;
+        }
+        else printf("\n    OK\n\n");
+    }
+
+    //
+    // try to add the base point to its opposite
+    //
+    {
+            // set P to (G.X, -G.Y, 1)
+        fpga_multiword_copy(&ECDSA_ZERO, &px);
+        fpga_multiword_copy(&ECDSA_ZERO, &py);
+        fpga_multiword_copy(&ECDSA_ONE,  &pz);
+
+        fpga_modular_add(&ECDSA_ZERO, &ECDSA_GX, &px);
+        fpga_modular_sub(&ECDSA_ZERO, &ECDSA_GY, &py);
+
+            // run addition proceduce
+        printf("Trying to add the base point to its opposite...\n\n");
+        fpga_curve_add_jacobian(&px, &py, &pz, &rx, &ry, &rz);
+
+            // handle result
+        ok = compare_fpga_buffers(&ECDSA_ONE, &ECDSA_ONE, &ECDSA_ZERO, &rx, &ry, &rz);
+        if (! ok)
+        {   printf("\n    ERROR\n\n");
+            return false;
+        }
+        else printf("\n    OK\n\n");
+    }
+
+        // everything went just fine
+    return true;
+}
+
+
+//------------------------------------------------------------------------------
+// End-of-File
+//------------------------------------------------------------------------------