1194073 - mp_sqrt produces sometimes wrong results

Status: RESOLVED FIXED

(NSS :: Libraries, defect)

Description

[Hanno Boeck]

Attachment: sample c code showing bug in mp_sqrt

The mp_sqrt function will sometimes produce wrong results.
I tested this by fuzzing the function input and checking the plausibility of the results. mp_sqrt is defined as the floor of the square root, therefore the input should be between the square of the result and the square of the result+1. See attached code example.

I saw that there is bug #436748 also about a miscalculation in mp_sqrt(), but I can't reproduce that one. I think it's a different bug that has been silently fixed and someone forgot to close it.

mp_sqrt() is as far as I can see only used in rsa_get_primes_from_exponents(). This is not attacker controlled input, therefore this probably has no security impact, but to be on the safe side I'll mark it as security until others have confirmed this.

Comment 1

[Hanno Boeck]

Forgot this: One simple example input causing this bug is
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00

Others are
FFFFFFFF019BFE0EA2F9DCF1F800DFDE
FFFFFFFFA6A6A69FB6A6A6A6A6A6FF01

Comment 2

[Ryan Sleevi]

Dirty secret: I'm awful at math. Redirecting to ekr for triage, although perhaps Watson may be good to take this on.

Comment 3

[Eric Rescorla (:ekr)]

Let's start with Barnes

Comment 4

[Franziskus Kiefer [:franziskus]]

There are multiple ways to fix this. The easiest would be to use a different guess for the first iteration. I'm not sure what the reasoning behind the shift is (s_mp_rshd(&x, used / 2)), but I'd simply remove that, which solves the bug. However, the algorithm should theoretically work with any starting point. While, I'm not sure about the actual bug, I also don't understand how the algorithm is implemented. Rewriting it in the common form (x_i+1 = (x_i^2+a)/2) works just fine.

Comment 5

[Richard Barnes [:rbarnes]]

I agree with Hanno that mp_sqrt isn't used outside of MPI, except for RSA_PopulatePrivateKey (via rsa_get_primes_from_exponents).

The algorithm in RSA_PopulatePrivateKey is actually wrong -- we're revising it in Bug 992240.  And skimming through the draft patch that's there, it looks like it removes the need for mp_sqrt.

mp_sqrt is not a public function, so the standard API consistency requirements don't apply.  Can we just land Bug 922240, then get rid of it?

Comment 6

[Hanno Boeck]

While mp_sqrt is not part of the nss public api it is exposed as part of libmpi if this is built separately. I'm not sure if libmpi has any users appart from nss itself and whether nss considers libmpi to have a stable api. If not then removal of the function seems to be the right thing to do.

Comment 7

[Franziskus Kiefer [:franziskus]]

Attachment: removing mp_sqrt

this removes mp_sqrt. it requires bug 992240 to land first.

Comment 8

[Franziskus Kiefer [:franziskus]]

libmpi is considered internal, so we're free change the interface

Comment 9

[Richard Barnes [:rbarnes]]

Comment on attachment 8679344 [details] [diff] [review]
removing mp_sqrt

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

LGTM

Bob: Any objection to removing this from mpi?

Comment 10

[Franziskus Kiefer [:franziskus]]

This is an edge case of mp_sqrt, which is used only in rsa_get_primes_from_exponents where the result is checked again, i.e. even if we run into the case that mp_sqrt calculates a wrong result, the only function using the result would discard it. So don't think this is a security-sensitive bug.

Comment 11

[Andrew McCreight [:mccr8]]

I'm marking this sec-other per comment 10. It sounds like it could be unhidden if people agree it isn't security sensitive.

There's also a reviewed patch here if somebody wants to land it...

Comment 12

[Hanno Boeck]

Yes, I think it can be unhidden. For the patch to land I think the patch in #992240 has to land first. Not sure why this hasn't happened yet, it's from June 2014.

Comment 14

[Franziskus Kiefer [:franziskus]]

https://hg.mozilla.org/projects/nss/rev/233a44e96b22