Status

NSS
Libraries
RESOLVED FIXED
2 years ago
2 years ago

People

(Reporter: fkiefer, Assigned: ttaubert)

Tracking

(Blocks: 1 bug)

trunk

Firefox Tracking Flags

(firefox45 affected)

Details

Attachments

(4 attachments, 4 obsolete attachments)

The mpi function mp_cmp_int is not very efficient, let's rewrite it.
Created attachment 8684779 [details] [diff] [review]
mp_cmp_int rewrite

First checking mp sign and if it has more than one digit, i.e. is obviously larger/smaller than the long, otherwise compare the first digit with the long (in this case the mp has only one digit).
Attachment #8684779 - Flags: review?(martin.thomson)
Comment on attachment 8684779 [details] [diff] [review]
mp_cmp_int rewrite

Review of attachment 8684779 [details] [diff] [review]:
-----------------------------------------------------------------

This assumes that sizeof(mp_digit) <= sizeof(long), which is not guaranteed.

::: lib/freebl/mpi/mpi.c
@@ -1700,5 @@
>  {
> -  mp_int  tmp;
> -  int     out;
> -
> -  ARGCHK(a != NULL, MP_EQ);

You dropped the ARGCHK, please restore that.

@@ +1714,5 @@
> +  }
> +
> +  /* here a is only one digit so we can just compare that one
> +   * get the signed first digit of a */
> +  long aLong = MP_SIGN(a) ? -1L * (long)MP_DIGIT(a, 0) : MP_DIGIT(a, 0);

This overflows when sizeof(mp_digit) == sizeof(long).
Attachment #8684779 - Flags: review?(martin.thomson)
A few testcases might be a good idea.  Even then, you won't necessarily catch all the problems.
Created attachment 8685435 [details] [diff] [review]
mp_cmp_int rewrite

right, that should be handled now as well. The tests that are there are passing, I added a few more (next patch).
Attachment #8684779 - Attachment is obsolete: true
Attachment #8685435 - Flags: review?(martin.thomson)
Created attachment 8685436 [details] [diff] [review]
mp_cmp_int rewrite - tests

adding a few more tests for edge cases.
Attachment #8685436 - Flags: review?(martin.thomson)
Comment on attachment 8685435 [details] [diff] [review]
mp_cmp_int rewrite

Review of attachment 8685435 [details] [diff] [review]:
-----------------------------------------------------------------

::: lib/freebl/mpi/mpi.c
@@ +1723,5 @@
> +   * Note that in this case a and z have the same sign */
> +  aLong = (unsigned long)MP_DIGIT(a, 0);
> +  if (aLong == labs(z)) {
> +    return MP_EQ;
> +  } else if ((aLong < labs(z) || aLong > labs(z)) && z < 0) {

Um, this is wrong still.  This statement equates to just (z < 0)

If you added PR_STATIC_ASSERT(sizeof(long) <= sizeof(mp_digit)) and built this on win32 with MP_USE_UINT_DIGIT, this assert will fail.

I think that you could do better with a new method: mp_err mp_get_int(const mp_int *a, long *z);

That could return an error if there isn't enough space and then this function could be made to work based on that (if it's too big to fit in a long, then it's clearly too big).

const unsigned int longBits = sizeof(long) - 1; /* less one for sign bit */
const unsigned int digitBits = sizeof(mp_digit);
int i = 0;

*z = 0;
do {
  mp_digit x = MP_DIGIT(a, i);
  if ((unsigned long)x >= (1UL << (longBits - i * digitBits))) {
    return MP_RANGE;
  }
  *z |= (long)x << (i * digitBits);
  ++i;
} while (i * digitBits < longBits);
if (MP_SIGN(a)) {
  *z *= -1;
}
Attachment #8685435 - Flags: review?(martin.thomson)
Comment on attachment 8685436 [details] [diff] [review]
mp_cmp_int rewrite - tests

Review of attachment 8685436 [details] [diff] [review]:
-----------------------------------------------------------------

::: lib/freebl/mpi/mpi-test.c
@@ +1694,5 @@
> +    return 1;
> +  }
> +  mp_read_radix(&a, mp3, 16);
> +  if(mp_cmp_int(&a, 0xCAEF2E4D7C5) <= 0 ||
> +     (mp_cmp_int(&a, -13945538926533) <= 0)) {

The problem with these tests is that these numbers might not be valid on all platforms and build configurations.  I think that you could use LONG_MAX though.
Attachment #8685436 - Flags: review?(martin.thomson)
Created attachment 8686025 [details] [diff] [review]
mp_cmp_int rewrite

oh, I totally forgot about 32bit :/ Only saw the overflow on signed and unsigned long.

I don't think we have to make it that complicated. In case long is not big enough we use ulong long (or int as fallback) for mp_digit. So using an unsigned long long here should be enough to safely get the mp_digit.

> This statement equates to just (z < 0)
yes... should've stayed home yesterday.
doing (aLong > labs(z) && z >= 0) || (aLong < labs(z) && z < 0) should do the job now.

I'm otherwise happy to use the suggested mp_get_int, but I think that over-complicates things.
Attachment #8685435 - Attachment is obsolete: true
Attachment #8686025 - Flags: review?(martin.thomson)
Created attachment 8686026 [details] [diff] [review]
mp_cmp_int rewrite - tests

changed the tests to work on all platforms. I don't think we have to test the MAX, the more interesting thing is if the comparison works if the mp_digit at position 0 of the mp is the same as the long (but mp has more than one mp_digit).

Also added another test case that would've broken with the older versions of the patch.
Attachment #8685436 - Attachment is obsolete: true
Attachment #8686026 - Flags: review?(martin.thomson)
if (sizeof(long) - 1 >= sizeof(mp_digit)) && (z > (1L<< sizeof(mp_digit)) then this fails because LONG_MAX will be expressed as two mp_digits.

Updated

2 years ago
Attachment #8686025 - Flags: review?(martin.thomson)
Comment on attachment 8686026 [details] [diff] [review]
mp_cmp_int rewrite - tests

Review of attachment 8686026 [details] [diff] [review]:
-----------------------------------------------------------------

These look like an improvement.  I think that we need some more tests.  In particular, ones where the second digit is zero, but the third or higher digit is non-zero.  Also, more tests around the upper end of the range of values for a long would be good on all platforms.  e.g.,

mp_set_int(&x, LONG_MAX - 1);
mp_cmp_int(&x, LONG_MAX) == MP_LT
mp_cmp_int(&x, LONG_MAX-1) == MP_EQ
mp_cmp_int(&x, LONG_MAX-2) == MP_GT

Also LONG_MIN

These are unlikely to be problematic on most systems, if any, but it would be good to have them as a sanity check.
Attachment #8686026 - Flags: review?(martin.thomson)
(Assignee)

Comment 13

2 years ago
Created attachment 8733319 [details] [diff] [review]
0001-Bug-1222908-Remove-mp_cmp_int.patch

Talked this through with Franziskus a few minutes ago and the best solution seems to be to remove mp_cmp_int() as proposed by mt in bug 1220683 comment #17.

This patch removes mp_cmp_int() and replaces it with |MP_SIGN(&group->curvea) && mp_cmp_mag(&group->curvea, 3)| in the only place that uses it, which is ec_GFp_pt_dbl_jac().
Attachment #8733319 - Flags: review?(rrelyea)
Attachment #8733319 - Flags: review?(martin.thomson)
Attachment #8733319 - Flags: review?(franziskuskiefer)
(Assignee)

Comment 14

2 years ago
Comment on attachment 8733319 [details] [diff] [review]
0001-Bug-1222908-Remove-mp_cmp_int.patch

Wait, that doesn't compile.
Attachment #8733319 - Flags: review?(rrelyea)
Attachment #8733319 - Flags: review?(martin.thomson)
Attachment #8733319 - Flags: review?(franziskuskiefer)
(Assignee)

Comment 15

2 years ago
Created attachment 8733323 [details] [diff] [review]
0001-Bug-1222908-Remove-mp_cmp_int.patch, v2

This is a little closer to what mt suggested, I mistakenly thought I could use mp_cmp_mag().

What this patch does differently is that it checks for |MP_USED() == 1|, this is in line with the current behavior, every mp_cmp* function returns MP_GT if USED(a) > USED(b) and MP_LT if USED(a) < USED(b).
Attachment #8733319 - Attachment is obsolete: true
Attachment #8733323 - Flags: review?(rrelyea)
Attachment #8733323 - Flags: review?(martin.thomson)
Attachment #8733323 - Flags: review?(franziskuskiefer)
Comment on attachment 8733323 [details] [diff] [review]
0001-Bug-1222908-Remove-mp_cmp_int.patch, v2

Review of attachment 8733323 [details] [diff] [review]:
-----------------------------------------------------------------

lgtm
Attachment #8733323 - Flags: review?(franziskuskiefer) → review+
(Assignee)

Updated

2 years ago
Blocks: 1259050
Comment on attachment 8733323 [details] [diff] [review]
0001-Bug-1222908-Remove-mp_cmp_int.patch, v2

Review of attachment 8733323 [details] [diff] [review]:
-----------------------------------------------------------------

If everywhere else assumes that digits (past 0) are non-zero, that's good enough for me if Bob is happy.
Attachment #8733323 - Flags: review?(martin.thomson) → review+

Comment 18

2 years ago
Comment on attachment 8733323 [details] [diff] [review]
0001-Bug-1222908-Remove-mp_cmp_int.patch, v2

Review of attachment 8733323 [details] [diff] [review]:
-----------------------------------------------------------------

This works. The mp_int was probably only used because the value was negative.
That being said, none of our supporting curves have a curvea value = -3.

To answer Martin's question, the only way this could fail is we would get a false negative if the mpi value isn't clamped (which it should be since it' basically a curve constant we read in and just use). clamping always normalizes and drops any leading zero digits.

This wouldn't necessarily work on an intermediate value, though most mpi functions clamp their output before returning.

bob
Attachment #8733323 - Flags: review?(rrelyea) → review+
(Assignee)

Comment 19

2 years ago
https://hg.mozilla.org/projects/nss/rev/0a8c335651a0
Status: NEW → RESOLVED
Last Resolved: 2 years ago
Resolution: --- → FIXED
(Assignee)

Updated

2 years ago
Assignee: franziskuskiefer → ttaubert
You need to log in before you can comment on or make changes to this bug.