UBSan: left shift of negative value in DER_GetInteger_Util

RESOLVED FIXED in Firefox 47

Status

NSS
Libraries
RESOLVED FIXED
2 years ago
4 months ago

People

(Reporter: tsmith, Assigned: fkiefer)

Tracking

(Blocks: 1 bug, {sec-moderate})

trunk
3.23
sec-moderate
Dependency tree / graph

Firefox Tracking Flags

(firefox45 wontfix, firefox46 wontfix, firefox47 fixed, firefox-esr38 wontfix, firefox-esr4550+ fixed)

Details

(Whiteboard: [adv-main47+])

Attachments

(4 attachments, 5 obsolete attachments)

(Reporter)

Description

2 years ago
Created attachment 8683168 [details]
test_case.der

I found this while fuzzing the CERT_DecodeBasicConstraintValue function. This function seems to be created to handle overflows while converting data but I'm not sure how this functionality (left shifting a negative value) is handled by different compilers or how this should be written differently, I'll leave it up to someone more qualified to answer such questions.

dersubr.c:205:14: runtime error: left shift of negative value -1
    #0 0x7fc7039213bf in DER_GetInteger_Util /home/user/code/san_nss/nss/lib/util/dersubr.c:205:14
    #1 0x7fc7045c6469 in CERT_DecodeBasicConstraintValue /home/user/code/san_nss/nss/lib/certdb/xbsconst.c:127:17
    #2 0x4df70b in Fuzz_CERT_DecodeBasicConstraintValue /home/user/code/san_nss/nss/cmd/checkcert/checkcert.c:80:7
    #3 0x4e114c in fuzz /home/user/code/san_nss/nss/cmd/checkcert/checkcert.c:181:5
    #4 0x4e267c in main /home/user/code/san_nss/nss/cmd/checkcert/checkcert.c:248:5
    #5 0x7fc7024f7ec4 in __libc_start_main /build/buildd/eglibc-2.19/csu/libc-start.c:287
    #6 0x419305 in _start (/home/user/Desktop/cert-decode/checkcert+0x419305)

SUMMARY: AddressSanitizer: undefined-behavior dersubr.c:205:14 in
Franziskus: please take a stab at giving this bug a security rating
Flags: needinfo?(franziskuskiefer)
checkcert has been removed (has never been shipped anyway). But the function in question |DER_GetInteger| is used in many other places to decode certificates.

While a left shift of a negative number can be fine according to the C standard

> The result of E1 << E2 is E1 left-shifted E2 bit positions; vacated bits are filled with zeros. [...] If E1 has a signed type and nonnegative value, and E1 × 2^E2 is representable in the result type, then that is the resulting value; otherwise, the behavior is undefined.

and especially gcc has extensions to handle other cases as well [1], this is a problem that should get fixed.

Regarding security rating, I can see many cases where this could be used to stop things from working properly but nothing where this could be exploited purposefully as the result is (if not correct) probably random or fixed (depending on the compiler).

[1] https://gcc.gnu.org/onlinedocs/gcc/Integers-implementation.html
Flags: needinfo?(franziskuskiefer)
Keywords: sec-moderate
Created attachment 8699455 [details] [diff] [review]
Bug1221620.patch

this would a way to avoid the left shift on negative numbers, it can probably be done more elegant though
Assignee: nobody → franziskuskiefer
Comment on attachment 8699455 [details] [diff] [review]
Bug1221620.patch

Martin, can you have a look at this or forward to someone more appropriate? Not sure if there's a nicer way to fix this, but this should work.
Attachment #8699455 - Flags: review?(martin.thomson)
Comment on attachment 8699455 [details] [diff] [review]
Bug1221620.patch

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

::: lib/util/dersubr.c
@@ +178,5 @@
>  long
>  DER_GetInteger(const SECItem *it)
>  {
> +    long ival = 0, copy = 0;
> +    int negative = 0, count = 0;

Negative can be PR_BOOL.

@@ +197,1 @@
>      ofloinit = ival & overflow;

This is a bad statement: ofloinit will be zero.

@@ +198,5 @@
>  
>      while (len) {
>  	if ((ival & overflow) != ofloinit) {
>  	    PORT_SetError(SEC_ERROR_BAD_DER);
>  	    if (ival < 0) {

You should change this to if (negative)

@@ +212,5 @@
> +    	copy = ival;
> +    	while (copy >>= 1) ++count;
> +    	negativeMask <<= count;
> +    	ival |= negativeMask;
> +    }

I don't understand this at all.  Why not just

if (negative) {
  return -ival;
}

LONG_MIN is dealt with above.
Attachment #8699455 - Flags: review?(martin.thomson)
(In reply to Martin Thomson [:mt:] from comment #5)
> Comment on attachment 8699455 [details] [diff] [review]
> Bug1221620.patch
> 
> Review of attachment 8699455 [details] [diff] [review]:
> -----------------------------------------------------------------
> @@ +212,5 @@
> > +    	copy = ival;
> > +    	while (copy >>= 1) ++count;
> > +    	negativeMask <<= count;
> > +    	ival |= negativeMask;
> > +    }
> 
> I don't understand this at all.  Why not just
> 
> if (negative) {
>   return -ival;
> }
> 
> LONG_MIN is dealt with above.

agree with the other comments, but we can't just return -ival because ival is a wrong value here. What I do in the patch is (in the case we have a negative number) to fill ival with the correct bits but with a wrong sign, i.e. ival in this case is a wrong number as long as we don't make it negative (make leading digits 1).

For example let the number be -126 like in the test case, then ival becomes 000...10000010, such that -ival=-130. But we need 111...10000010=-126.

Do you have a better idea to do that?
Flags: needinfo?(martin.thomson)
Ahh, it's not sign and modulus, which is obvious.

Standard twos complement math should do.  If you think of a two-octet encoding of ival = 0x8000 (32768), then the actual value is 0x8000 - 0x10000 (-32768).  So save the length and subtract (1 << (length * 8)).   Or: long mask = (1 << (length * 8 - 1)); ival &= ~mask; ival -= mask;

If you had to deal with LONG_MIN you would skip this step since the upper bit would be in place, but you don't have to worry since the overflow check traps that.
Flags: needinfo?(martin.thomson)
Created attachment 8707829 [details] [diff] [review]
Bug1221620.patch

simplified the patch along the lines of your comments.

Maybe we should also think about getting tests for the DER encoder/decoder.
Attachment #8699455 - Attachment is obsolete: true
Attachment #8707829 - Flags: review?(martin.thomson)
Comment on attachment 8707829 [details] [diff] [review]
Bug1221620.patch

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

::: lib/util/dersubr.c
@@ +184,3 @@
>      unsigned char *cp = it->data;
>      unsigned long overflow = 0x1ffUL << (((sizeof(ival) - 1) * 8) - 1);
> +    unsigned long mask = 1 << ((len  * 8) - 1);

You can defer this calculation until it's needed by moving this to the if (negative && ival) {} block.  The compiler probably will do this for you if it's good, but no sense in being too reliant on that.
Attachment #8707829 - Flags: review?(martin.thomson) → review+
Franziskus, regarding comment 8, perhaps you could take a stab at writing some test around this function for this bug.  That might make me more confident about landing a change to a central piece of code.  If you could satisfy yourself that you aren't changing functionality, that would help too.  I think that a new gtest shouldn't be hard to setup (see pk11_gtests for an example); testing correct decode of 0, -1, 1, and LONG_MAX - 1, LONG_MIN + 1, and maybe a few shorter encodings.  Add checks for failures at LONG_MAX and LONG_MIN and for len == 0 and you have pretty solid coverage of the function.

n.b., generating inputs should be easy:

long x = htonl(LONG_MIN);
SECItem input = { siBuffer, &x, sizeof(x) };
EXPECT_EQ(LONG_MIN, DER_GetInteger(input));
Created attachment 8708990 [details] [diff] [review]
Bug1221620.patch

tests were necessary, can you have a look again?
I changed the following:
i) in the case the number is negative, |overflow| has to be only |FF00...| instead of |FF800...|. 
ii) we have to do anything additional in the negative case only if |(overflow & ival) == 0|
Attachment #8707829 - Attachment is obsolete: true
Attachment #8708990 - Flags: review?(martin.thomson)
Created attachment 8708992 [details] [diff] [review]
Bug1221620-tests.patch

gtests for DER_GetInteger
Attachment #8708992 - Flags: review?(martin.thomson)
Comment on attachment 8708992 [details] [diff] [review]
Bug1221620-tests.patch

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

This is pretty good, but there are a few things to fix up.

Note that you should also add der_gtests to tests/all.sh in all the places that ssl_gtests can be found.

::: external_tests/der_gtest/der_getint_unittest.cc
@@ +16,5 @@
> +namespace nss_test {
> +
> +class DERIntegerDecodingTest : public ::testing::Test {
> + public:
> +  void DER_GetInteger_Test(long number, unsigned char *derNumber,

The naming convention here is:

FunctionName

parameter_name

I think that I would just call this TestGetInteger

@@ +26,5 @@
> +};
> +
> +TEST_F(DERIntegerDecodingTest, DecodeLongMinus126) {
> +  unsigned char der[] = {0x82};
> +  DER_GetInteger_Test(-126, &der[0], 1);

Be consistent and just use `der` rather than `&der[0]`.  Also, use sizeof(der) for the last parameter.

@@ +51,5 @@
> +}
> +
> +TEST_F(DERIntegerDecodingTest, DecodeLongMax) {
> +  unsigned char der[] = {0x7F, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF};
> +  DER_GetInteger_Test(LONG_MAX, der, 8);

This test won't work on platforms where sizeof(long) != 8.  It's trickier, but you need to construct the value to get these right.

unsigned char der[sizeof(long)];
long v = htonl(LONG_MAX);
memcpy(der, v, sizeof(long));

@@ +56,5 @@
> +}
> +
> +TEST_F(DERIntegerDecodingTest, DecodeLongMin) {
> +  unsigned char der[] = {0xFF, 0x80, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00};
> +  DER_GetInteger_Test(LONG_MIN, der, 9);

Is the leading octet actually necessary here?  I'd have thought that 0x80000... would produce the same result.

@@ +83,5 @@
> +// test too long, too small numbers, and zero-length
> +
> +TEST_F(DERIntegerDecodingTest, DecodeLongMinMinus1) {
> +  unsigned char der[] = {0xFF, 0x80, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00};
> +  DER_GetInteger_Test(LONG_MIN, der, 9);

This looks like LONG_MIN to me.  Isn't LONG_MIN - 1 == 0xff7ffffffffffffffff ?

Also, please check that PORT_GetError() == SEC_ERROR_BAD_DER (here and below).

@@ +95,5 @@
> +// NOTE: Death tests use fork()
> +TEST_F(DERIntegerDecodingTest, DecodeLongZeroLength) {
> +  unsigned char der[0];
> +  SECItem input = {siBuffer, der, 0};
> +  EXPECT_DEATH(DER_GetInteger(&input), "");

Hmm, maybe we should just drop this test.  If the tests are compiled in debug mode, they will only call PORT_GetError.
Attachment #8708992 - Flags: review?(martin.thomson)
Attachment #8708990 - Flags: review?(martin.thomson) → review+
Created attachment 8709907 [details] [diff] [review]
Bug1221620-tests.patch

thanks for the review, so how about this?

htonl unfortunately doesn't work here as it's 32-bit (htonll would be 64). So I just built it by hand depending on sizeof(long).
Attachment #8708992 - Attachment is obsolete: true
Attachment #8709907 - Flags: review?(martin.thomson)
Comment on attachment 8709907 [details] [diff] [review]
Bug1221620-tests.patch

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

A few nits and a minor bug.

::: external_tests/der_gtest/der_getint_unittest.cc
@@ +23,5 @@
> +  {
> +    SECItem input = {siBuffer, der_number, len};
> +    EXPECT_EQ(number, DER_GetInteger(&input));
> +    if (error_expected) {
> +      EXPECT_EQ(PORT_GetError(), SEC_ERROR_BAD_DER);

Switch the arguments.  gtests put the fixed value first (yeah, it's odd).

Given that you only have two uses of this, I would just put this check in the two places that it is needed and save on the extra argument in every test.

@@ +118,5 @@
> +// TEST_F(DERIntegerDecodingTest, DecodeLongZeroLength) {
> +//   unsigned char der[0];
> +//   SECItem input = {siBuffer, der, sizeof(der), true};
> +//   EXPECT_DEATH(DER_GetInteger(&input), "");
> +// }

I think that we can safely delete this.  Comments only rot.

::: tests/der_gtests/der_gtests.sh
@@ +1,1 @@
> +#! /bin/bash

This file is starting to look a little boilerplate-y.

@@ +56,5 @@
> +
> +  # Temporarily disable asserts for PKCS#11 slot leakage (Bug 1168425)
> +  unset NSS_STRICT_SHUTDOWN
> +  PK11GTESTREPORT="${DERGTESTDIR}/report.xml"
> +  ${BINDIR}/der_gtest -d "${DERGTESTDIR}" --gtest_output=xml:"${PK11GTESTREPORT}"

The variable names here are wrong.  Another reason for me to refactor these.
Attachment #8709907 - Flags: review?(martin.thomson) → review+
Created attachment 8711694 [details] [diff] [review]
Bug1221620-tests.patch

fixed nits, mt can you do the check in (3.23 probably)?

I filed bug 1242565 to follow up on the gtest startup scripts.
Attachment #8709907 - Attachment is obsolete: true
Flags: needinfo?(martin.thomson)
Yeah, I'll check it in, but we're still frozen for 3.22 release.
Created attachment 8712572 [details] [diff] [review]
Bug1221620-tests.patch

oops, just noticed I uploaded the old version last time
Attachment #8711694 - Attachment is obsolete: true

Updated

a year ago
Keywords: checkin-needed
OK, I've checked these in

https://hg.mozilla.org/projects/nss/rev/8d78a5ae260a
https://hg.mozilla.org/projects/nss/rev/99beadb15243

I had to fix the script though.  So the tests aren't accurate.
Status: NEW → RESOLVED
Last Resolved: a year ago
Flags: needinfo?(martin.thomson)
Resolution: --- → FIXED
Target Milestone: --- → 3.23
Keywords: checkin-needed
Group: crypto-core-security → core-security-release
The tests don't build on Windows.

external_tests/der_gtest/der_getint_unittest.cc:
  #include <netinet/in.h>

File doesn't appear to be available on Windows?

d:/slavedir/1-win-x32-DBG/hg/nss/external_tests/der_gtest/der_getint_unittest.cc(12) : fatal error C1083: Cannot open include file: 'netinet/in.h': No such file or directory
attempted bustage fix:
https://hg.mozilla.org/projects/nss/rev/5cbc92f72be3
Created attachment 8716242 [details] [diff] [review]
Bug1221620-followup.patch

that include is actually not necessary anymore, removed it (the correct header for windows would've been Winsock2.h)
Attachment #8716242 - Flags: review?(kaie)

Updated

a year ago
Attachment #8716242 - Flags: review?(kaie) → review+

Updated

11 months ago
status-firefox45: affected → wontfix
status-firefox46: --- → wontfix
status-firefox47: --- → fixed
status-firefox-esr38: --- → wontfix
status-firefox-esr45: --- → affected

Updated

11 months ago
Whiteboard: [adv-main47++]

Updated

11 months ago
Whiteboard: [adv-main47++] → [adv-main47+]
status-firefox-esr45: affected → wontfix
Depends on: 1306948
Tracking upstream NSS 3.21.3 security updates for the ESR-45 "50+" release.
status-firefox-esr45: wontfix → affected
tracking-firefox-esr45: --- → 50+

Comment 24

6 months ago
NSS_3_21_BRANCH
https://hg.mozilla.org/projects/nss/rev/9061e00062e5

Updated

6 months ago
Blocks: 1310009
Fixed in bug 1310009
status-firefox-esr45: affected → fixed
Group: core-security-release
You need to log in before you can comment on or make changes to this bug.