Support big-endian processors. Eliminate the dependency on the

mozilla/security/nss/lib/freebl/ecl/ecp_256_32.c

 /* This Source Code Form is subject to the terms of the Mozilla Public
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 /* A 32-bit implementation of the NIST P-256 elliptic curve. */
 
 #include <string.h>
 
 #include "prtypes.h"
 #include "mpi.h"
@@ skipping 142 matching lines @@
     0x13d8341f, 0x8daefd7, 0x139c972d, 0x6b7ea75, 0xd4a9dde, 0xff163d8, 0x81d55d7, 0xa5bef68, 0xb7b30d8,
     0xbe73d6f, 0xaa88141, 0xd976c81, 0x7e7a9cc, 0x18beb771, 0xd773cbd, 0x13f51951, 0x9d0c177, 0x1c49a78,
 };
 
 /* Field element operations:
  */
 
 /* NON_ZERO_TO_ALL_ONES returns:
  *   0xffffffff for 0 < x <= 2**31
  *   0 for x == 0 or x > 2**31.
- *
- * This macro assumes that right-shifting a signed number shifts in the MSB on
- * the left. This is not ensured by the C standard, but is true on the CPUs
- * that we're targetting with this code (x86 and ARM).
  */
-#define NON_ZERO_TO_ALL_ONES(x) (~((u32) (((s32) ((x)-1)) >> 31)))
+#define NON_ZERO_TO_ALL_ONES(x) ((((x) - 1) >> 31) - 1)

[Ryan Sleevi, 2013/01/31 22:53:38]

Suggestion: Add u32 casts to make sure that the unsigned underflow and shifts
are well-defined. I haven't checked all the calls, but I note Adam's original
behaviour made sure to make this obvious, especially with the right-shift.

[wtc, 2013/02/01 05:28:04]

Thank you for the suggestion. The argument |x| is always
a |limb|, which is a u32. I will document this.

Since |x| is a u32, the original macro must use the s32
cast before the right shift.

 
 /* felem_reduce_carry adds a multiple of p in order to cancel |carry|,
  * which is a term at 2**257.
  *
  * On entry: carry < 2**3, inout[0,2,...] < 2**29, inout[1,3,...] < 2**28.
  * On exit: inout[0,2,..] < 2**30, inout[1,3,...] < 2**29.
  */
 static void felem_reduce_carry(felem inout, limb carry)
 {
     const u32 carry_mask = NON_ZERO_TO_ALL_ONES(carry);
@@ skipping 954 matching lines @@
         if (i) {
             point_double(nx, ny, nz, nx, ny, nz);
         }
         for (j = 0; j <= 32; j += 32) {
             char bit0 = get_bit(scalar, 31 - i + j);
             char bit1 = get_bit(scalar, 95 - i + j);
             char bit2 = get_bit(scalar, 159 - i + j);
             char bit3 = get_bit(scalar, 223 - i + j);
             limb index = bit0 | (bit1 << 1) | (bit2 << 2) | (bit3 << 3);
 
             table_offset = ((((s32)j) << (32-6)) >> 31) & (30*NLIMBS);

[wtc, 2013/02/01 05:28:04]

Here j is 0 or 32 (1 << 5). So this can be simplified to

    table_offset = ~(((u32)j >> 5) - 1) & (30*NLIMBS);
or
    table_offset = (j >> 5) * (30*NLIMBS);
	
If multiplication is as fast as the other instructions,
the latter seems preferrable.

[wtc, 2013/02/01 05:35:40]

A better solution:

    table_offset = 0;
    for (j = 0; j <= 32; j += 32) {
        ...

        select_affine_point(px, py, kPrecomputed + table_offset, index);
        table_offset += 30*NLIMBS;

[agl, 2013/02/01 18:45:17]

I like this, thanks.

             select_affine_point(px, py, kPrecomputed + table_offset, index);
 
             /* Since scalar is less than the order of the group, we know that
              * {nx,ny,nz} != {px,py,1}, unless both are zero, which we handle
              * below.
              */
             point_add_mixed(tx, ty, tz, nx, ny, nz, px, py);
             /* The result of point_add_mixed is incorrect if {nx,ny,nz} is zero
              * (a.k.a.  the point at infinity). We handle that situation by
              * copying the point from the table.
@@ skipping 68 matching lines @@
         }
 
         index = scalar[31 - i / 2];
         if ((i & 1) == 1) {
             index &= 15;
         } else {
             index >>= 4;
         }
 
         /* See the comments in scalar_base_mult about handling infinities. */
         select_jacobian_point(px, py, pz, (limb *) precomp, index);

[wtc, 2013/01/31 22:46:05]

Why is this (limb *) cast necessary?

Is there some way to avoid it? I found that
    precomp
    precomp[0]
    precomp[0][0]
    precomp[0][0][0]
all compile with no warning on Mac OS X. I have no idea
which form is preferrable :-)

[agl, 2013/02/01 18:45:17]

ecp_256_32.c:1233:2: warning: passing argument 4 of ‘select_jacobian_point’ from
incompatible pointer type [enabled by default]
ecp_256_32.c:1075:13: note: expected ‘const limb *’ but argument is of type
‘limb (*)[3][9]’

$ gcc --version
gcc (Ubuntu/Linaro 4.6.3-1ubuntu5) 4.6.3

[wtc, 2013/02/01 19:28:35]

Thanks for the compiler warning message. I changed this to
precomp[0][0].

         point_add(tx, ty, tz, nx, ny, nz, px, py, pz);
         copy_conditional(nx, px, n_is_infinity_mask);
         copy_conditional(ny, py, n_is_infinity_mask);
         copy_conditional(nz, pz, n_is_infinity_mask);
 
         p_is_noninfinite_mask = ((s32) ~ (index - 1)) >> 31;

[wtc, 2013/02/01 05:28:04]

Here |index| is 0, ..., 15. So this can be rewritten as

    p_is_noninfinite_mask = NON_ZERO_TO_ALL_ONES(index);

[agl, 2013/02/01 18:45:17]

Agreed.

         mask = p_is_noninfinite_mask & ~n_is_infinity_mask;
         copy_conditional(nx, tx, mask);
         copy_conditional(ny, ty, mask);
         copy_conditional(nz, tz, mask);
         n_is_infinity_mask &= ~p_is_noninfinite_mask;
     }
 }
 
 /* Interface with Freebl: */
 
+/* BYTESWAP_MP_DIGIT_TO_LE swaps the bytes of a mp_digit to
+ * little-endian order.
+ */
 #ifdef IS_BIG_ENDIAN
-#error "This code needs a little-endian processor"
+#ifdef __APPLE__
+#include <libkern/OSByteOrder.h>
+#define BYTESWAP32(x) OSSwapInt32(x)
+#define BYTESWAP64(x) OSSwapInt64(x)
+#else
+#define BYTESWAP32(x) \
+    ((x) >> 24 | (x) >> 8 & 0xff00 | ((x) & 0xff00) << 8 | (x) << 24)
+#define BYTESWAP64(x) \
+    ((x) >> 56 | (x) >> 40 & 0xff00 | \
+     (x) >> 24 & 0xff0000 | (x) >> 8 & 0xff000000 | \
+     ((x) & 0xff000000) << 8 | ((x) & 0xff0000) << 24 | \
+     ((x) & 0xff00) << 40 | (x) << 56)
 #endif
 
-static const u32 kRInvDigits[8] = {
+#ifdef MP_USE_UINT_DIGIT

[wtc, 2013/01/31 22:46:05]

If this macro is defined, mp_digit is 32-bit. Otherwise,
mp_digit is 64-bit (either unsigned long long or 64-bit
unsigned long). See

http://bonsai.mozilla.org/cvsblame.cgi?file=mozilla/security/nss/lib/freebl/m...

+#define BYTESWAP_MP_DIGIT_TO_LE(x) BYTESWAP32(BYTESWAP32(x))
+#else
+#define BYTESWAP_MP_DIGIT_TO_LE(x) BYTESWAP64(BYTESWAP64(x))
+#endif
+#endif /* IS_BIG_ENDIAN */
+
+#ifdef MP_USE_UINT_DIGIT
+static const mp_digit kRInvDigits[8] = {
     0x80000000, 1, 0xffffffff, 0,
     0x80000001, 0xfffffffe, 1, 0x7fffffff
 };
+#else
+static const mp_digit kRInvDigits[4] = {
+    PR_UINT64(0x180000000),  0xffffffff,
+    PR_UINT64(0xfffffffe80000001), PR_UINT64(0x7fffffff00000001)
+};
+#endif
 #define MP_DIGITS_IN_256_BITS (32/sizeof(mp_digit))
 static const mp_int kRInv = {
     MP_ZPOS,
     MP_DIGITS_IN_256_BITS,
     MP_DIGITS_IN_256_BITS,
-    /* Because we are running on a little-endian processor, this cast works for
-     * both 32 and 64-bit processors.
-     */
     (mp_digit*) kRInvDigits
 };
 
 static const limb kTwo28 = 0x10000000;
 static const limb kTwo29 = 0x20000000;
 
 /* to_montgomery sets out = R*in. */
 static mp_err to_montgomery(felem out, const mp_int *in, const ECGroup *group)
 {
     /* There are no MPI functions for bitshift operations and we wish to shift
@@ skipping 60 matching lines @@
 
 /* scalar_from_mp_int sets out_scalar=n, where n < the group order. */
 static void scalar_from_mp_int(u8 out_scalar[32], const mp_int *n)
 {
     /* We require that |n| is less than the order of the group and therefore it
      * will fit into |scalar|. However, these is a timing side-channel here that
      * we cannot avoid: if |n| is sufficiently small it may be one or more words
      * too short and we'll copy less data.
      */
     memset(out_scalar, 0, 32);
+#ifdef IS_LITTLE_ENDIAN
     memcpy(out_scalar, MP_DIGITS(n), MP_USED(n) * sizeof(mp_digit));

[wtc, 2013/01/31 22:46:05]

I found that this memcpy is done without checking that
MP_USED(n) * sizeof(mp_digit) <= 32.

Is this what your FIXME comment on line 1391 refers to?

[agl, 2013/02/01 18:45:17]

Yes. I had forgotten about that.

Is there a #define that can be used so that the check is only enabled in debug
mode? NDEBUG is the typical one but I don't know if NSS uses it. (It doesn't
appear to be common at least.)

There's ECL_DEBUG, but that's no obviously enabled in any build.

[wtc, 2013/02/01 19:28:35]

NSS uses both DEBUG and NDEBUG. DEBUG is more commonly
used.

+#else
+    {
+        mp_size i;
+        mp_digit swapped[MP_DIGITS_IN_256_BITS];
+        for (i = 0; i < MP_USED(n); i++) {
+            swapped[i] = BYTESWAP_MP_DIGIT_TO_LE(MP_DIGIT(n, i));
+        }
+        memcpy(out_scalar, swapped, MP_USED(n) * sizeof(mp_digit));
+    }
+#endif
 }
 
 /* ec_GFp_nistp256_base_point_mul sets {out_x,out_y} = nG, where n is < the
  * order of the group.
  */
 static mp_err ec_GFp_nistp256_base_point_mul(const mp_int *n,
                                              mp_int *out_x, mp_int *out_y,
                                              const ECGroup *group)
 {
     u8 scalar[32];
     felem x, y, z, x_affine, y_affine;
     mp_err res;
 
     /* FIXME(agl): test that n < order. */

[wtc, 2013/02/01 19:28:35]

I added an assertion to scalar_from_mp_int to ensure that
memcpy won't overflow the out_scalar buffer. It is weaker
than testing that n < order.

To test that n < order, I'd need to repeat the test in
all three point multiplication methods. Do you think it
is enough to just prevent buffer overflow in
scalar_from_mp_int?

Do you think an assertion (compiled away in release builds)
is enough?

 
     scalar_from_mp_int(scalar, n);
     scalar_base_mult(x, y, z, scalar);
     point_to_affine(x_affine, y_affine, x, y, z);
     MP_CHECKOK(from_montgomery(out_x, x_affine, group));
     MP_CHECKOK(from_montgomery(out_y, y_affine, group));
 
 CLEANUP:
     return res;
 }
@@ skipping 91 matching lines @@
 /* Wire in fast point multiplication for named curves. */
 mp_err ec_group_set_gfp256_32(ECGroup *group, ECCurveName name)
 {
     if (name == ECCurve_NIST_P256) {
         group->base_point_mul = &ec_GFp_nistp256_base_point_mul;
         group->point_mul = &ec_GFp_nistp256_point_mul;
         group->points_mul = &ec_GFp_nistp256_points_mul_vartime;
     }
     return MP_OKAY;
 }