Add an optimized 32-bit implementation of the NIST P-256 elliptic curve.

Add an optimized 32-bit implementation of the NIST P-256 elliptic curve.

ecp_256_32.c was written by Adam Langley and was reviewed in
https://codereview.chromium.org/10944017/

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

[wtc, 2013-01-25 02:32:49]

I described below the changes I made to AGL's original NSS
patch in https://bugzilla.mozilla.org/show_bug.cgi?id=831006.

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

https://codereview.chromium.org/12042100/diff/1/mozilla/security/nss/lib/free...
mozilla/security/nss/lib/freebl/ecl/ecl.c:266: #endif /*
NSS_ECC_MORE_THAN_SUITE_B */

I added a comment after this #endif to indicate the
matching #ifdef.

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

https://codereview.chromium.org/12042100/diff/1/mozilla/security/nss/lib/free...
mozilla/security/nss/lib/freebl/ecl/ecp_256.c:385: #ifdef IS_LITTLE_ENDIAN

This is an existing NSS file. Our patch adds lines 385-403
and lines 414-418.

I added #ifdef IS_LITTLE_ENDIAN here and on line 414.

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

https://codereview.chromium.org/12042100/diff/1/mozilla/security/nss/lib/free...
mozilla/security/nss/lib/freebl/ecl/ecp_256_32.c:5: /* A 32-bit implementation
of the NIST P-256 elliptic curve. */

Lines 1-5 used to be one comment block. I separated it into
a license header and a comment.

I also removed <stdint.h>, <stdio.h>, and <stdlib.h> and kept
only <string.h> because the only standard C library functions
I saw in this file are memcpy, memcmp, memset.

https://codereview.chromium.org/12042100/diff/1/mozilla/security/nss/lib/free...
mozilla/security/nss/lib/freebl/ecl/ecp_256_32.c:1249: #ifdef IS_BIG_ENDIAN

I changed #if to #ifdef here.

[Ryan Sleevi, 2013-01-25 03:50:36]

I'm definitely not qualified to review this on the maths side.

I'm still not sure I fully grok when it's appropriate to use mem* directly vs
libutil's PORT_Mem* (which is just a #define to mem* anyways). NSS seems to be a
mix of half and half between one and the other.

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

https://codereview.chromium.org/12042100/diff/1/mozilla/security/nss/lib/free...
mozilla/security/nss/lib/freebl/ecl/ecl.c:273: break;
Why move this out of the MORE_THAN_SUITE_B? Is that going to be an issue for Red
Hat?

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

https://codereview.chromium.org/12042100/diff/1/mozilla/security/nss/lib/free...
mozilla/security/nss/lib/freebl/ecl/ecp_256.c:10: #include <stdlib.h>
Why is this header necessary? libutil tries to hide any need for these functions

https://codereview.chromium.org/12042100/diff/1/mozilla/security/nss/lib/free...
mozilla/security/nss/lib/freebl/ecl/ecp_256.c:207: #ifdef notdef
?

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

https://codereview.chromium.org/12042100/diff/1/mozilla/security/nss/lib/free...
mozilla/security/nss/lib/freebl/ecl/ecp_256_32.c:168: #define
NON_ZERO_TO_ALL_ONES(x) (~((u32) (((s32) ((x)-1)) >> 31)))
Just because this is slipping into more and more code, does it make since to
place this standard-but-undefined behaviour somewhere just as a gatekeeper for
'things might go wrong here'? Are we relying on the fact that a unittest should
fail, were this to not be true?

Should their be a bitsmear alternative 'just in case'?

eg:
x &= 0x80000000; x |= x >> 16;
x |= x >> 8; x |= x >> 4;
x |= x >> 2; x |= x >> 1;

[agl, 2013-01-25 16:04:03]

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

https://codereview.chromium.org/12042100/diff/1/mozilla/security/nss/lib/free...
mozilla/security/nss/lib/freebl/ecl/ecl.c:273: break;
On 2013/01/25 03:50:36, Ryan Sleevi wrote:
> Why move this out of the MORE_THAN_SUITE_B? Is that going to be an issue for
Red
> Hat?

P-256 is part of Suite B, no? I'm not sure why it was classified as "more than
Suite B" in the first place.

If the use of the previously disabled code in ecp_256.c is a problem then it's
quite possible to do without it.

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

https://codereview.chromium.org/12042100/diff/1/mozilla/security/nss/lib/free...
mozilla/security/nss/lib/freebl/ecl/ecp_256_32.c:168: #define
NON_ZERO_TO_ALL_ONES(x) (~((u32) (((s32) ((x)-1)) >> 31)))
On 2013/01/25 03:50:36, Ryan Sleevi wrote:
> Just because this is slipping into more and more code, does it make since to
> place this standard-but-undefined behaviour somewhere just as a gatekeeper for
> 'things might go wrong here'? Are we relying on the fact that a unittest
should
> fail, were this to not be true?

I'd love to put it in nspr or somewhere similar. Preferably with an #if
defined(__x86_64__) || defined(__whatever_arm_uses__) with the bitsmeared
version as an alternative.

However, in the interests of keeping the patches limited so far I've been
copying it as it's only a one-liner and somewhat obscure.

[wtc, 2013-01-27 00:11:17]

Thank you for your comments. Please review patch set 2.

I figured out a way to avoid adding ecp_256.c.

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

https://codereview.chromium.org/12042100/diff/1/mozilla/security/nss/lib/free...
mozilla/security/nss/lib/freebl/ecl/ecl.c:273: break;

On 2013/01/25 16:04:03, agl wrote:
>
> If the use of the previously disabled code in ecp_256.c is a problem then it's
> quite possible to do without it.

In patch set 2, I eliminated the need for ecp_256.c.

We still need to use ECGroup_consGFp instead of ECGroup_consGFp_mont,
which NSS is currently using by default (see line 277).

I found that ECGroup_consGFp differs from ECGroup_consGFp_mont in
only three methods: field_mul, field_sqr, and field_div:

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

(field_enc and field_dec are just the necessary encoding
and decoding functions for the Montgomery form.)

The implementations of those three methods in ECGroup_consGFp
simply call MPI functions:
http://mxr.mozilla.org/security/ident?i=ec_GFp_mul
http://mxr.mozilla.org/security/ident?i=ec_GFp_sqr
http://mxr.mozilla.org/security/ident?i=ec_GFp_div

So it should be fine to use ECGroup_consGFp when
NSS_ECC_MORE_THAN_SUITE_B is not defined.

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

https://codereview.chromium.org/12042100/diff/1/mozilla/security/nss/lib/free...
mozilla/security/nss/lib/freebl/ecl/ecp_256.c:10: #include <stdlib.h>

On 2013/01/25 03:50:36, Ryan Sleevi wrote:
> Why is this header necessary? libutil tries to hide any need for these
functions

This is likely to have been copied from another file that
was the model for this file. Many programmers don't try
to minimize header dependencies.

I don't find any calls to Standard C library functions in
this file. I'll create an upstream NSS patch to remove
this header.

https://codereview.chromium.org/12042100/diff/1/mozilla/security/nss/lib/free...
mozilla/security/nss/lib/freebl/ecl/ecp_256.c:207: #ifdef notdef

On 2013/01/25 03:50:36, Ryan Sleevi wrote:
> ?

Bob Relyea often uses this to comment out a block of code.
(Based on my research, Bob Relyea was the original author of
this file.)

https://codereview.chromium.org/12042100/diff/7001/mozilla/security/nss/lib/f...
File mozilla/security/nss/lib/freebl/ecl/ecl-priv.h (right):

https://codereview.chromium.org/12042100/diff/7001/mozilla/security/nss/lib/f...
mozilla/security/nss/lib/freebl/ecl/ecl-priv.h:239: /* Optimized point
multiplication */

agl: since your code is used to override these three methods:
base_point_mul, point_mul, points_mul
I am describing it as "optimized point multiplication" in
comments. I hope that is accurate.

[agl, 2013-01-28 21:42:20]

lgtm

[commit-bot: I haz the power, 2013-01-28 22:31:17]

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

[commit-bot: I haz the power, 2013-01-28 22:31:31]

Change committed as 179208

[wtc, 2013-01-31 16:59:02]

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

https://codereview.chromium.org/12042100/diff/1/mozilla/security/nss/lib/free...
mozilla/security/nss/lib/freebl/ecl/ecp_256_32.c:168: #define
NON_ZERO_TO_ALL_ONES(x) (~((u32) (((s32) ((x)-1)) >> 31)))

On 2013/01/25 03:50:36, Ryan Sleevi wrote:
>
> Should their be a bitsmear alternative 'just in case'?
> 
> eg:
> x &= 0x80000000; x |= x >> 16;
> x |= x >> 8; x |= x >> 4;
> x |= x >> 2; x |= x >> 1;

After I worked out the detail (including plugging in Ryan's
constantTimeCondition code from the NSS RSA-OAEP patch),
I found that the result is simply

u32 NonZeroToAllOnes(u32 x) {
  x = (x - 1) >> 31;
  return x - 1;
}

or in macro form:

#define NON_ZERO_TO_ALL_ONES(x) ((((x)-1) >> 31) - 1)

This should be equally fast. I hope I didn't make a mistake.