Support big-endian processors. Eliminate the dependency on the

Support big-endian processors. Eliminate the dependency on the
implementation-defined behavior of right-shifting a negative signed
integer.

R=agl@chromium.org,rsleevi@chromium.org
BUG=172178
TEST=no build or test failures on iOS, Mac, and Windows

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

(agl: please note my last comment below about memcpy.)

This should address all technical issues for upstream NSS.

I remember Fedora supports PowerPC, so the big-endian support
should eliminate that concern.

I didn't find any endianness dependency in the P-256 code
proper. The code that assumes little-endian order is all
in the interface with Freebl.

https://codereview.chromium.org/12137003/diff/1/mozilla/security/nss/lib/free...
File mozilla/security/nss/lib/freebl/ecl/ecp_256_32.c (right):

https://codereview.chromium.org/12137003/diff/1/mozilla/security/nss/lib/free...
mozilla/security/nss/lib/freebl/ecl/ecp_256_32.c:1228: select_jacobian_point(px,
py, pz, (limb *) precomp, index);

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 :-)

https://codereview.chromium.org/12137003/diff/1/mozilla/security/nss/lib/free...
mozilla/security/nss/lib/freebl/ecl/ecp_256_32.c:1263: #ifdef MP_USE_UINT_DIGIT

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...

https://codereview.chromium.org/12137003/diff/1/mozilla/security/nss/lib/free...
mozilla/security/nss/lib/freebl/ecl/ecp_256_32.c:1367: memcpy(out_scalar,
MP_DIGITS(n), MP_USED(n) * sizeof(mp_digit));

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?

[Ryan Sleevi, 2013-01-31 22:53:37]

https://codereview.chromium.org/12137003/diff/1/mozilla/security/nss/lib/free...
File mozilla/security/nss/lib/freebl/ecl/ecp_256_32.c (right):

https://codereview.chromium.org/12137003/diff/1/mozilla/security/nss/lib/free...
mozilla/security/nss/lib/freebl/ecl/ecp_256_32.c:164: #define
NON_ZERO_TO_ALL_ONES(x) ((((x) - 1) >> 31) - 1)
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]

By searching for "s32" and ">> 31", I found two other places
that assume right-shifting a signed integer does an arithmetic
shift. I suggested how to rewrite them.

https://codereview.chromium.org/12137003/diff/1/mozilla/security/nss/lib/free...
File mozilla/security/nss/lib/freebl/ecl/ecp_256_32.c (right):

https://codereview.chromium.org/12137003/diff/1/mozilla/security/nss/lib/free...
mozilla/security/nss/lib/freebl/ecl/ecp_256_32.c:164: #define
NON_ZERO_TO_ALL_ONES(x) ((((x) - 1) >> 31) - 1)

On 2013/01/31 22:53:38, Ryan Sleevi wrote:
> Suggestion: Add u32 casts to make sure that the unsigned underflow and shifts
> are well-defined.

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.

https://codereview.chromium.org/12137003/diff/1/mozilla/security/nss/lib/free...
mozilla/security/nss/lib/freebl/ecl/ecp_256_32.c:1139: table_offset = ((((s32)j)
<< (32-6)) >> 31) & (30*NLIMBS);

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.

https://codereview.chromium.org/12137003/diff/1/mozilla/security/nss/lib/free...
mozilla/security/nss/lib/freebl/ecl/ecp_256_32.c:1234: p_is_noninfinite_mask =
((s32) ~ (index - 1)) >> 31;

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

    p_is_noninfinite_mask = NON_ZERO_TO_ALL_ONES(index);

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

https://codereview.chromium.org/12137003/diff/1/mozilla/security/nss/lib/free...
File mozilla/security/nss/lib/freebl/ecl/ecp_256_32.c (right):

https://codereview.chromium.org/12137003/diff/1/mozilla/security/nss/lib/free...
mozilla/security/nss/lib/freebl/ecl/ecp_256_32.c:1139: table_offset = ((((s32)j)
<< (32-6)) >> 31) & (30*NLIMBS);

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:16]

https://codereview.chromium.org/12137003/diff/1/mozilla/security/nss/lib/free...
File mozilla/security/nss/lib/freebl/ecl/ecp_256_32.c (right):

https://codereview.chromium.org/12137003/diff/1/mozilla/security/nss/lib/free...
mozilla/security/nss/lib/freebl/ecl/ecp_256_32.c:1139: table_offset = ((((s32)j)
<< (32-6)) >> 31) & (30*NLIMBS);
On 2013/02/01 05:35:40, wtc wrote:
> A better solution:
> 
>     table_offset = 0;
>     for (j = 0; j <= 32; j += 32) {
 
I like this, thanks.

https://codereview.chromium.org/12137003/diff/1/mozilla/security/nss/lib/free...
mozilla/security/nss/lib/freebl/ecl/ecp_256_32.c:1228: select_jacobian_point(px,
py, pz, (limb *) precomp, index);
On 2013/01/31 22:46:05, wtc wrote:
> Why is this (limb *) cast necessary?

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

https://codereview.chromium.org/12137003/diff/1/mozilla/security/nss/lib/free...
mozilla/security/nss/lib/freebl/ecl/ecp_256_32.c:1234: p_is_noninfinite_mask =
((s32) ~ (index - 1)) >> 31;
On 2013/02/01 05:28:04, wtc wrote:
> Here |index| is 0, ..., 15. So this can be rewritten as 
>     p_is_noninfinite_mask = NON_ZERO_TO_ALL_ONES(index);

Agreed.

https://codereview.chromium.org/12137003/diff/1/mozilla/security/nss/lib/free...
mozilla/security/nss/lib/freebl/ecl/ecp_256_32.c:1367: memcpy(out_scalar,
MP_DIGITS(n), MP_USED(n) * sizeof(mp_digit));
On 2013/01/31 22:46:05, wtc wrote:
> 
> 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?

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]

Please review patch set 2.

https://codereview.chromium.org/12137003/diff/1/mozilla/security/nss/lib/free...
File mozilla/security/nss/lib/freebl/ecl/ecp_256_32.c (right):

https://codereview.chromium.org/12137003/diff/1/mozilla/security/nss/lib/free...
mozilla/security/nss/lib/freebl/ecl/ecp_256_32.c:1228: select_jacobian_point(px,
py, pz, (limb *) precomp, index);

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

https://codereview.chromium.org/12137003/diff/1/mozilla/security/nss/lib/free...
mozilla/security/nss/lib/freebl/ecl/ecp_256_32.c:1367: memcpy(out_scalar,
MP_DIGITS(n), MP_USED(n) * sizeof(mp_digit));

On 2013/02/01 18:45:17, agl wrote:
>
> 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.)

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

https://codereview.chromium.org/12137003/diff/1/mozilla/security/nss/lib/free...
mozilla/security/nss/lib/freebl/ecl/ecp_256_32.c:1391: /* FIXME(agl): test that
n < order. */

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?

[agl, 2013-02-02 20:34:26]

LGTM

https://codereview.chromium.org/12137003/diff/7001/mozilla/security/nss/lib/f...
File mozilla/security/nss/lib/freebl/ecl/ecp_256_32.c (left):

https://codereview.chromium.org/12137003/diff/7001/mozilla/security/nss/lib/f...
mozilla/security/nss/lib/freebl/ecl/ecp_256_32.c:1359: /* FIXME(agl): test that
n < order. */
I think this TODO should remain. I'll write something in a DEBUG section to
ensure this.

https://codereview.chromium.org/12137003/diff/7001/mozilla/security/nss/lib/f...
File mozilla/security/nss/lib/freebl/ecl/ecp_256_32.c (right):

https://codereview.chromium.org/12137003/diff/7001/mozilla/security/nss/lib/f...
mozilla/security/nss/lib/freebl/ecl/ecp_256_32.c:1257: #define BYTESWAP32(x) \
This only works if x is unsigned, but I believe that's ok here.

[wtc, 2013-02-04 20:29:39]

I added the TODO(agl) comment back in patch set 3. I also
removed ecp_256_32.c from nss-curve-p256.patch because I'm
worried that applying the patch again may append the file's
contents to an existing ecp_256_32.c file in the source tree.

[commit-bot: I haz the power, 2013-02-04 20:29:55]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/wtc@chromium.org/12137003/12001

[commit-bot: I haz the power, 2013-02-04 20:30:08]

Change committed as 180499