1234509 - divide by zero in pqg.c

Status: RESOLVED FIXED

(NSS :: Libraries, defect)

Description

[Franziskus Kiefer [:franziskus]]

makePfromQandSeed and makePrimefromPrimesShaweTaylor functions in pqg.c may divide by zero (outlen).

Comment 1

[Michelangelo De Simone [Offline] [:mds]]

Attachment: Some division-by-zero in pqg.c

Comment 2

[Franziskus Kiefer [:franziskus]]

Comment on attachment 8721585 [details] [diff] [review]
Some division-by-zero in pqg.c

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

hm, I'm not sure if we should do this. We run the entire algorithm then with 0 instead of a reasonable length.

I'd suggest throwing an error if outlen == 0 (i.e. if hashlen == 0) and return. This can only happen if an invalid hash function is used, in which case we probably can't do anything meaningful anyway.

Comment 3

[Michelangelo De Simone [Offline] [:mds]]

(In reply to Franziskus Kiefer [:fkiefer or :franziskus] from comment #2)

> hm, I'm not sure if we should do this. We run the entire algorithm then with
> 0 instead of a reasonable length.

I tend to agree on this, the algorithm could indeed end up generating negative operands when outlen is 0, but the division by 0 would be a more compelling and immediate problem anyway.;)

> I'd suggest throwing an error if outlen == 0 (i.e. if hashlen == 0) and
> return. This can only happen if an invalid hash function is used, in which
> case we probably can't do anything meaningful anyway.

Right. As I think 'outlen' should never be 0 anyway, it'd probably make more sense to leave that 0-check as it is (to make coverity happy) AND also assert a non-zero outlen as soon as possible within the function.

Comment 4

[Michelangelo De Simone [Offline] [:mds]]

Attachment: Some division-by-zero in pqg.c

Comment 5

[Michelangelo De Simone [Offline] [:mds]]

Attachment: Some division-by-zero in pqg.c

Comment 6

[Franziskus Kiefer [:franziskus]]

Comment on attachment 8722232 [details] [diff] [review]
Some division-by-zero in pqg.c

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

comments are the same for both cases.

This patch might make coverity already happy, but not me :) I think we should always catch the case of outlen == 0.

::: lib/freebl/pqg.c
@@ +515,5 @@
>      int i;
>      int iterations;
>      int old_counter;
>  
> +    PORT_Assert(outlen != 0);

PORT_Assert is only active in debug builds [1] and calls abort(). So that's probably not the thing we want here. We can leave it in for debugging, but to catch the case where outlen == 0 in every case we should do an explicit check for outlen == 0 and return an error in that case.

[1] https://dxr.mozilla.org/mozilla-central/rev/789a12291942763bc1e3a89f97e0b82dc1c9d00b/nsprpub/pr/include/prlog.h#207

@@ +548,5 @@
>      ** iterations+1 works better in C.
>      */
>  
>      /* Step 4/16 iterations = ceiling(length/outlen)-1 */
> +    iterations = outlen ? ((length+outlen-1) / outlen) : 0;  /* NOTE: iterations +1 */

this shouldn't be necessary anymore as outlen != 0 if we get here.

Comment 7

[Michelangelo De Simone [Offline] [:mds]]

Attachment: Some division-by-zero in pqg.c

Comment 8

[Michelangelo De Simone [Offline] [:mds]]

(In reply to Franziskus Kiefer [:fkiefer or :franziskus] from comment #6)

> This patch might make coverity already happy, but not me :) I think we
> should always catch the case of outlen == 0.

This should be more or less on the right track to make you happy.:)

Comment 9

[Franziskus Kiefer [:franziskus]]

Comment on attachment 8722706 [details] [diff] [review]
Some division-by-zero in pqg.c

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

that looks good.

I'd like to get a second opinion on this though as it changes behaviour of the function.
Bob you wrote this code, can you have a quick look at this? This returns early if outlen == 0 to avoid a divide by zero and executing the algorithm with 0 outlen, which might lead to other problems.

Comment 10

[Franziskus Kiefer [:franziskus]]

Comment on attachment 8722706 [details] [diff] [review]
Some division-by-zero in pqg.c

adding more people, hoping someone has time to have a look

Comment 11

[Wan-Teh Chang]

Comment on attachment 8722706 [details] [diff] [review]
Some division-by-zero in pqg.c

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

Hi Michelangelo and Franziskus,

I think this patch is a step in the right direction, but it
seems incomplete. I suggest we search for "HASH_ResultLen"
in lib/freebl/pqg.c and fix all occurrences.

Alternatively, we can inspect the code and check for hashtype
only at strategic places. We may need to add assertions, after
the checks, to help Coverity.

Based on my perusal of the code, I think hashtype is always
a valid value, so we just need to figure out the best way to
help Coverity (and a human code reader) to see that.

::: lib/freebl/pqg.c
@@ +516,5 @@
>      int iterations;
>      int old_counter;
>  
> +    if (outlen == 0)
> +        return rv;

IMPORTANT: we should set an error code before returning SECFailure.

In this case, it turns out that we already set the error code (to
SEC_ERROR_INVALID_ARGS) in HASH_GetRawHashObject. But there is one
case: hashType == HASH_AlgNULL is not considered an error, but its
|length| field is 0.

So I suggest we set the error code here. Also, rewrite the code to
make it clear where the error first occurs.

    int hashlen;
    int outlen;

    hashlen = HASH_ResultLen(hashtype);
    if (hashlen == 0) {
        PORT_SetError(SEC_ERROR_INVALID_ALGORITHM);
        return rv;
    }
    outlen = hashlen*PR_BITS_PER_BYTE;

Note that I use SEC_ERROR_INVALID_ALGORITHM instead of 
SEC_ERROR_INVALID_ARGS.

UPDATE: searching for "HASH_ResultLen" in lib/freebl/pqg.c,
I found a lot of similar occurrences of this problem. So
I think it is better to have HASH_ResultLen set the error
code, like this:

static unsigned int
HASH_ResultLen(HASH_HashType type)
{
    const SECHashObject *hash_obj = HASH_GetRawHashObject(type);
    if (hash_obj == NULL || hash_obj->length == 0) {
        PORT_SetError(SEC_ERROR_INVALID_ALGORITHM);
        return 0;
    }
    return hash_obj->length;
}

But I suspect the best solution is to change HASH_GetRawHashObject()
to return NULL for hashType == HASH_AlgNULL.

@@ +1010,5 @@
>      CHECK_MPI_OK( mp_init(&twoQ) );
>      CHECK_MPI_OK( mp_init(&tmp)  );
>      CHECK_MPI_OK( mp_init(&V_n)  );
>  
>      hashlen = HASH_ResultLen(hashtype);

As noted above, I think we should instead check hashlen:

    if (hashlen == 0) {
        rv = SECFailure;
        goto cleanuo;
    }

Comment 12

[Franziskus Kiefer [:franziskus]]

Michelangelo can you follow up on Wan-Teh's comment?

Comment 13

[Michelangelo De Simone [Offline] [:mds]]

(In reply to Franziskus Kiefer [:fkiefer or :franziskus] from comment #12)
> Michelangelo can you follow up on Wan-Teh's comment?

That's on top of my list. I'm busy with a new hire event in MV (no laptop).
I'll be fixing that as soon as I'm done with this.

Comment 14

[Michelangelo De Simone [Offline] [:mds]]

(In reply to Wan-Teh Chang from comment #11)

Hi Wan-Teh,

> But I suspect the best solution is to change HASH_GetRawHashObject()
> to return NULL for hashType == HASH_AlgNULL.
...snip...
> >      hashlen = HASH_ResultLen(hashtype);
> As noted above, I think we should instead check hashlen:

If I understood correctly you're suggesting to:

1. Fix all the occurrences of HASH_GetRawHashObject() to return NULL for hashType == HASH_AlgNULL, AND
2. Return early (SECFailure) whenever hashlen is 0.

Am I correct in this assumption?

Comment 15

[Franziskus Kiefer [:franziskus]]

added CID 1132659 but there are more occurrences in this file where the result of HASH_ResultLen is used without properly checking it. We should probably fix all of them.

Comment 16

[Wan-Teh Chang]

Hi Michelangelo and Franziskus,

I'm beginning to think that this bug is INVALID. Please see my explanation
below.

(In reply to Michelangelo De Simone from comment #14)
> (In reply to Wan-Teh Chang from comment #11)
> 
> If I understood correctly you're suggesting to:
> 
> 1. Fix all the occurrences of HASH_GetRawHashObject() to return NULL for
> hashType == HASH_AlgNULL, AND
> 2. Return early (SECFailure) whenever hashlen is 0.
> 
> Am I correct in this assumption?

We should analyze the HASH_HashType arguments in the pqg.c file.
It is possible that they are always valid values.

For example, neither getFirstHash() nor getNextHash() return
HASH_AlgNULL, and the HASH_AlgTOTAL return value from getNextHash()
is skipped by its caller. So it seems that
hashlen = HASH_ResultLen(hashtype) cannot possibly be 0 in the
pqg.c file.

Do you agree?

Comment 17

[Wan-Teh Chang]

I see that this is reported by Coverity. This may be beyond the ability
of a static analysis tool like Coverity. We'll need to either have
Coverity ignore this, or tweak our code to help Coverity understand it.

Comment 18

[Wan-Teh Chang]

Attachment: Declare the internal functions in pqg.c as static.

Not sure if this will help Coverity, but this is a
good idea in general.

Comment 19

[Franziskus Kiefer [:franziskus]]

(In reply to Wan-Teh Chang from comment #16)
> Hi Michelangelo and Franziskus,
> 
> I'm beginning to think that this bug is INVALID. Please see my explanation
> below.
> We should analyze the HASH_HashType arguments in the pqg.c file.
> It is possible that they are always valid values.
> 
> For example, neither getFirstHash() nor getNextHash() return
> HASH_AlgNULL, and the HASH_AlgTOTAL return value from getNextHash()
> is skipped by its caller. So it seems that
> hashlen = HASH_ResultLen(hashtype) cannot possibly be 0 in the
> pqg.c file.
> 
> Do you agree?

Thanks for your comments Wan-Teh.
Having a closer look at this there are two ways the result of HASH_ResultLen becoming 0 (both triggered in HASH_GetRawHashObject): i) hashType < HASH_AlgNULL || hashType >= HASH_AlgTOTAL ii) hashType == HASH_AlgNULL
However, the way it is used this should never be the case as you noticed.

This is something Coverity probably can't figure out. I don't think making it static would help. But I can simply mark it as false positive in Coverity. Adding a check for hashlen == 0 would not hurt though.

But we should maybe have a look at the raw hash function [1] all this originates in. It is also used in other contexts where the fed in hashType might be HASH_AlgNULL and the result is used in a division.

[1] https://dxr.mozilla.org/nss/source/nss/lib/freebl/rawhash.c#154

Comment 20

[Franziskus Kiefer [:franziskus]]

Comment on attachment 8733663 [details] [diff] [review]
Declare the internal functions in pqg.c as static.

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

as I suspected this doesn't solve the problem that static analysis tools complain about this. I just did a scan-build with this patch and it still complains about division by zero.

Comment 21

[Wan-Teh Chang]

Comment on attachment 8733663 [details] [diff] [review]
Declare the internal functions in pqg.c as static.

Hi Franzikus: I'm sorry I was confusing in stating the
purpose of this patch. I said:

  Not sure if this will help Coverity, but this is a
  good idea in general.

I should have emphasized that this patch is a good
idea, regardless of this Coverity issue. Marking internal
functions as static help human code reviewers because we
know we don't need to look at other files for callers of
those functions. So, please reconsider this patch as a
general improvement, rather than an attempt to fix the
Coverity issue (which it also was).

Comment 22

[Wan-Teh Chang]

(In reply to Franziskus Kiefer [:fkiefer or :franziskus] from comment #19)
>
> This is something Coverity probably can't figure out. I don't think making
> it static would help. But I can simply mark it as false positive in
> Coverity. Adding a check for hashlen == 0 would not hurt though.

Marking the issue as false positive should be considered last. We can
try asserting that HASH_ResultLen does not return 0:

static unsigned int
HASH_ResultLen(HASH_HashType type)
{
    const SECHashObject *hash_obj = HASH_GetRawHashObject(type);
    PORT_Assert(hash_obj != NULL);
    PORT_Assert(hash_obj->length != 0);
    return hash_obj->length;
}

This requires Coverity understands PORT_Assert / PR_ASSERT,
which should already be the case.

If this doesn't work, I am inclined to suggest we just add
the hashlen == 0 checks as we originally planned, and use
the SEC_ERROR_LIBRARY_FAILURE error code, which is stronger
than SEC_ERROR_INVALID_ARGS, because getting hashlen == 0
in this file would be an NSS internal bug.

Also, I'm beginning to think HASH_GetRawHashObject() should
also return NULL if hashType == HASH_AlgNULL. It is risky
to return the null hash object to the caller.

Comment 23

[Franziskus Kiefer [:franziskus]]

Comment on attachment 8733663 [details] [diff] [review]
Declare the internal functions in pqg.c as static.

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

Ah, sorry for the misunderstanding. Yes adding the static here makes sense.

Comment 24

[Wan-Teh Chang]

Comment on attachment 8733663 [details] [diff] [review]
Declare the internal functions in pqg.c as static.

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

https://hg.mozilla.org/projects/nss/rev/d10acc9804cc

Comment 25

[Franziskus Kiefer [:franziskus]]

Attachment: divide-null.patch

Taking this over. 
I added an error in HASH_ResultLen (that's the same now as in sechash). The asserts in addition silence scan-build (I hope coverity as well).
HASH_GetRawHashObject now also considers the hashType == HASH_AlgNULL case an error and returns null.

Comment 26

[Wan-Teh Chang]

(In reply to Franziskus Kiefer [:fkiefer or :franziskus] from comment #25)
> Created attachment 8768499 [details] [diff] [review]
> divide-null.patch
> 
> Taking this over. 
> I added an error in HASH_ResultLen (that's the same now as in sechash).

I don't understand why you said the HASH_ResultLen in pqg.c is the same
now as in sechash. Here is the HASH_ResultLen in sechash.c:

/* returns zero if hash type invalid. */
unsigned int
HASH_ResultLen(HASH_HashType type)
{
    if ((type < HASH_AlgNULL) || (type >= HASH_AlgTOTAL)) {
        PORT_SetError(SEC_ERROR_INVALID_ALGORITHM);
        return (0);
    }

    return (SECHashObjects[type].length);
}

It looks very different to me.

Comment 27

[Wan-Teh Chang]

Comment on attachment 8768499 [details] [diff] [review]
divide-null.patch

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

r=wtc. I forgot the context of this bug, so I assume you're
implementing what I suggested in comment 22.

::: lib/freebl/pqg.c
@@ +181,2 @@
>      if (hash_obj == NULL) {
> +        PORT_SetError(SEC_ERROR_LIBRARY_FAILURE);

Note that HASH_GetRawHashObject() already sets an error code
when it returns NULL. So this PORT_SetError() call merely
replaces the error code. Please add a comment to document
that this HASH_ResultLen() function is only called with a
valid hash type (that is not HASH_AlgNULL), so if
HASH_GetRawHashObject returns NULL, it is a bug, hence the
SEC_ERROR_LIBRARY_FAILURE error.

@@ +183,2 @@
>  	return 0;
>      }

Nit: Please put PORT_Assert(hash_obj->length != 0) after the if
statement. After the if statement, we know hash_obj is not
null, so we can evaluate hash_obj->length.

Comment 28

[Franziskus Kiefer [:franziskus]]

thanks for the review.
landed as https://hg.mozilla.org/projects/nss/rev/660d4b130458