1202868 - (CVE-2015-7182) ASN.1 decoder heap overflow when decoding constructed OCTET STRING that mixes indefinite and definite length encodings

Status: RESOLVED FIXED

(NSS :: Libraries, defect)

Description

[Dana Keeler (she/her) (use needinfo) [:keeler]]

Attachment: checkcert.c

I discovered this when investigating bug 1192028. Consider the following ASN.1:

24 0A           [OCTET STRING | CONSTRUCTED] [length is 10 bytes]
   24 80        [OCTET STRING | CONSTRUCTED] [indefinite length]
      04 01 01  [OCTET STRING] [length is 1] [value is 1]
   00 00        [end of indefinite length contents marker]
   04 01 02     [OCTET STRING] [length is 1] [value is 2]

If I understand correctly, this is valid ASN.1 and is equivalent to 04 02 01 02 (i.e. an OCTET STRING of length 2 with value 01 02).

However, under ASAN using a setup similar to bug 1192028 (see attached), this results in a use-after-poison that I believe could be parleyed into a heap overflow.

Comment 1

[Dana Keeler (she/her) (use needinfo) [:keeler]]

Attachment: valid.bin

Here's the input as a binary file, in case others are interested in that by itself.

Comment 2

[Ryan Sleevi]

David: I agree with your analysis, and this appears to be the root cause of Bug 1192323.

Are you actively working on a fix for this?

Comment 3

[Tyson Smith [:tsmith]]

I made a fuzzing harness out of the attached c file. So far I've seen:
bug 1202931
bug 1202932
bug 1202936

Comment 4

[Dana Keeler (she/her) (use needinfo) [:keeler]]

(In reply to Ryan Sleevi from comment #2)
> Are you actively working on a fix for this?

Not at the moment - I'm focusing on bug 1192028 for now (I almost have a patch ready for that).

Comment 5

[Ryan Sleevi]

OK, I'll see about getting a fix for this and related OCTET STRING bugs.

Tyson, could you cc me on the new ones?

Comment 6

[Tyson Smith [:tsmith]]

Attachment: asn1_fuzz_harness.c

To use this:
1) rename to checkcert.c
2) place in nss/cmd/checkcert/
3) build with ASan
4) run ./checkcert <test_case>

Comment 7

[Ryan Sleevi]

(In reply to Tyson Smith [:tsmith] from comment #6)
> Created attachment 8658805 [details]
> asn1_fuzz_harness.c
> 
> To use this:
> 1) rename to checkcert.c
> 2) place in nss/cmd/checkcert/
> 3) build with ASan
> 4) run ./checkcert <test_case>

This test harness has a bug :)

You do data.len = sizeof(bytes), rather than data.len = length.

Comment 8

[Ryan Sleevi]

Sorry, that's length - 1, because of the ftell(fp) + 1

Comment 9

[Tyson Smith [:tsmith]]

Attachment: asn1_fuzz_harness.c

Comment 10

[Ryan Sleevi]

Dumping current mental state:

The issue appears to be with how/when NSS decides to allocate the SECItem for OCTET STRINGs with indefinite length encoding. While I'm still investigating, the 'use after poison' itself comes from the fact that the SECItem used to store the resulting string is allocated under a states (in the sec_asn1d_push_state) sense mark, that state is popped (thus freeing all allocated since the mark), and then another state trying to write into that string.

I'll try to work out a proper fix for this, but it appears to be due to the mark ordering getting messed up.

Comment 11

[Ryan Sleevi]

So I was a bit incorrect in comment #10, but now have a solution I'm going to try to convince myself is correct. Simply changing line 1726 in http://mxr.mozilla.org/nss/source/lib/util/secasn1d.c#1726 from
"if (item != NULL && item->data != NULL)" 
to
"if (item != NULL && item->data != NULL && item != state->dest)"

Resolves this. [Still running tests under ASAN to make sure it doesn't cause new data]

My notes about the invariants and states:
- We start off with an initial state whose state->dest is set to the caller-supplied SECItem. This is the top-level state, working from the template of OCTET_STRING_Template (e.g. what we, the caller, supplied)
- We parse the identifier (beforeIdentifier -> afterIdentifier) and length (beforeLength -> afterLength) of the outer-most encoding - which is an OCTET_STRING of Length 10
- During afterLength, it calls sec_asn1d_prepare_for_contents, which allocates 10 bytes (contents_length) for our dest buffer. This is done at http://mxr.mozilla.org/nss/source/lib/util/secasn1d.c#1244
  - During the first allocation, our top-level state has
    * state->pending = 10
    * state->contents_length = 10
    * state->consumed = 2
    * state->indefinite = 0
    * state->substring = 0
- We push a new state on the stack - SEC_OctetStringTemplate - and initialize it. During this, we preserve/propogate "item" (aka state->dest) to the new, sub-state. This is the "where do put the strings" bit, and will be non-null (because of the above)
  - In doing so, we set sub-state's substring = PR_TRUE ( http://mxr.mozilla.org/nss/source/lib/util/secasn1d.c#1324 )

At this point, we have a stack of two states. The top-level state is still in duringConstructedString, and the 'sub' state (Sub1) is now the active one, processing SEC_OctetStringTemplate from the beginning

- Sub1 goes through beginIdentifier/endIdentifier and beforeLength/afterLength states.
  - This time, no data is allocated. |item| (line 1178) points to dest, which has a 10-byte buffer (but len == 0).
  - However, this time, we're a substring (because of the outer wrapper, state->substring == 1), so we hit http://mxr.mozilla.org/nss/source/lib/util/secasn1d.c#1198
  - Because item->data != NULL, alloc_len = 0
  - During this, the Sub1 state has:
    * state->pending = 0 (because it was an indefinite length)
    * state->contents_length = 0 (again, indefinite length)
    * state->consumed = 2
    * state->indefinite = 1
    * state->substring = 1 (because of the line 1324 for the parent state)
- We now create *another* state on the stack - SEC_OctetStringTemplate - and initialize it. Again, "item" (aka state->dest) is preserved for the new-substate, substring = PR_TRUE.

Now we have a stack of three states. The first two are in duringConstructedString, with a new state (sub2) in a pristine state

- Sub2 goes through the beginIdentifier/endIdentifier and beforeLength/afterLength dance, reading a simple octet string with a definite length (1)
  - During sec_asn1d_prepare_for_contents, it sets up state->pending and state->contents_length (to 1 byte each)
  - We again meet the conditions of line 1198 (a substring), and because the 10-byte buffer is allocated, alloc_len is set to 0 (line 1212)
  - Because it's a simple type (not constructed), and not-indefinite, we fall through to line 1340, which sets up the next state (duringLeaf)
  - We end up in sec_asn1d_parse_leaf and copy the first byte into item->data (10 bytes), aka dest.


Now, this is where the bug manifests, and why the fix works. Sub2 has finished, copying one byte to our destination, and rolls off the state stack when it encounters the EOC octet for Sub1. Sub1 then advances in the state machine, which is to call sec_asn1d_next_substring

When the bug manifests, we add the 1 byte string (aka 'dest' aka state->dest, sub1->dest, sub2->dest aka child->dest) to a list of substrings to be concatenated together into a unified string. The "bug" is that we already directly copied the data into dest, so the need to concat substrings isn't there - it's an artifact of the fact that sub1 is indefinite, so line 1723 hits.

Despite the fact that state is definite, and allocated 10 bytes, because sub1 is indefinite, it thinks it needs to concatenate all of the sub1 substrings, because sub1's dest "should" have come from our pool, but in fact came from 'their' pool (because the parent was definite)

We add child (aka sub2) to the subitems via sec_asn1d_add_to_subitem, but then here's the bug. We *reset* item->data / item->len, which is sub2->dest, but that ends up mutating sub1->dest and state->dest, because we're not mutating a copy of the SECItem, but the *same* secitem (aka Dest).

This is a leak (well, 'our' arena will catch it), but it's also why the bug manifests - we erase all state of the strings we've decoded so far.

Then sub1 bubbles through sec_asn1d_concat_substrings. Here, we allocate a new string (line 2070) - but that string length is based only on the length of all of sub1's substrings (1), not the length of state (10). Again, we're directly mutating item here, so we set item->len to 1, and item->data to point to a 1-byte array.

When sub1 finishes processing, we bubble back up to state (the parent state), which is still a constructed string. We then read another substring (we'll call this sub3), simple, definite length. Because state->dest is set, it's filtered through to sub3->dest.

When sub3 enters the sec_asn1d_parse_leaf phase, it still has substring == 1, but contents_length = 1, consumed = 2., but state->dest has len = 1, data = (buffer of 1 byte, due to sub1 ruining it all during concat_substrings). As a result, when it hits line 1536 and tries to PORT_Memcpy, it tries to write one byte past the allocation - and things explode.


My fix tries to address this by causing sub1 to never enter the substring concatenation phase, because it's already part of its parents substring concatenation phase (state), and so everything just writes to the strings directly, and sec_asn1d_parse_leaf is set to len = 2, data = [2 bytes used, of a 10 byte buffer]. It's wasteful, yes, but that's what the existing code intended ( see http://mxr.mozilla.org/nss/source/lib/util/secasn1d.c#1180 )

It does this by trying (to its best approximation) to determine when substring writing is not needed, due to the outer-string having been preallocated.

The problem is I'm not sure if this introduces new issues when an indefinite-length octet string is encoded as part of another template object (i.e. not part of a containing outer string). That's what I'm hoping tests will shake out.

Tyson, if you have your fuzzing harness, can you apply the one-line fix and see if this shakes out any new issues in your fuzzers?

Comment 12

[Tyson Smith [:tsmith]]

Attachment: call_stack_orig.txt

As a starting point, this is what I get when I run valid.bin unfuzzed with the fuzz harness.

Comment 13

[Tyson Smith [:tsmith]]

Attachment: call_stack_with_patch.txt

After applying the one line change I no longer see a crash when running valid.bin but I am still seeing that crash.

Comment 14

[Tyson Smith [:tsmith]]

Attachment: repro.bin

Comment 15

[Ryan Sleevi]

Thanks, Tyson! Your new test case from Comment #14 is resolved with dkeeler's fix for Bug 1192028.

I think with both our fixes, things should be happy fuzzy times. So I'm gonna do that and see what I can shake out, as I think both are 'probably' correct :)

Comment 16

[Ryan Sleevi]

And I'm wrong. Turns out my 'fix' introduces new crashes, since the SEC_ASN1_ANY family are treated as constructed strings (why? because they both deal with subitems)

With my both our fixes applied, the following demonstrates the bug in my code:
unsigned char id_000000_sig_06_src_000047_op_havoc_rep_8[] = {
  0x30, 0x4d, 0x02, 0x01, 0x05, 0x30, 0x80, 0x06, 0x02, 0x01, 0x05, 0x30,
  0x80, 0x06, 0x09, 0x2a, 0x86, 0x48, 0x86, 0xf7, 0x00, 0x48, 0x86, 0xf7,
  0x64, 0x00
};
unsigned int id_000000_sig_06_src_000047_op_havoc_rep_8_len = 26;

Which might alternatively be written as
0x30, 0x4d  		[CONSTRUCTED SEQUENCE, length = 77]
  0x02, 0x01  			[INTEGER, length = 1]
    0x05        			Value = 5
  0x30, 0x80		[CONSTRUCTED SEQUENCE, indefinite length]
    0x06, 0x02			[OBJECT ID, length = 2]
      0x01, 0x05			Value
    0x30, 0x80			[CONSTRUCTED SEQUENCE, indefinite length]
      0x06, 0x09			[OBJECT ID, length = 9]
        0x2a, 0x86, 0x48, 0x86, 0xf7, 0x00, 0x48, 0x86, 0xf7
      0x64, 0x00			[Application context, 64, length = 0]

This can be decoded using

SECKEYPrivateKeyInfo output;
memset(&output, 0, sizeof(output));
if (SEC_ASN1DecodeItem(temparena, &output, SEC_ASN1_GET(SECKEY_PrivateKeyInfoTemplate), &data) != SECSuccess) {


The relevant part of SECKEY_PrivateKeyInfoTemplate is http://mxr.mozilla.org/nss/source/lib/pk11wrap/pk11pk12.c#111 and http://mxr.mozilla.org/nss/source/lib/pk11wrap/pk11pk12.c#91

The bug (in my fix) is that the following types - http://mxr.mozilla.org/nss/source/lib/util/secasn1d.c#1153 - are treated as constructed strings (yes, "ANY" is treated as a constructed string). If the outer type (in this case, the CONSTRUCTED SEQUENCE) is indefinite, then the children are *not* copying into the parents type, and it all goes terribly messy.

So 'yay', my new code causes new bugs. Will try for a different fix and then fuzzing that fix, since at least I've got a decent harness now for fuzzing SECKEY_PrivateKeyInfo significantly faster than via PK11_ImportDER*

Comment 17

[Ryan Sleevi]

You could further simplify the fuzz harness by using a SECAlgorithmID & SECOID_AlgorithmIDTemplate - since that invokes the ANY syntax for the parameters, that gives you maximum coverage for the ASN.1 types involved. More robust than octet string parsing, but less setup than trying to create a SECKEYPrivateKey

Comment 18

[Ryan Sleevi]

Alright, new fix that I'm presently re-fuzzing (combined with keeler's patch), which properly detects whether we're in a true constructed string type (where the child elements must all be the same tag as the parent, and where the parent may have pre-allocated a structure to receive the decoded string) or if we're in a SEC_ASN1_ANY (and friends) type, in which the parent won't necessarily have pre-allocated the structure (but could have).

With this fix, it passes the 31 variations of the crash I found with my fix, along with all of Tyson's identified crashes.

Comment 19

[Ryan Sleevi]

New version of the patch (since partial diffs are such a pain right now, plus it needs to be cleaned up to conform to style), from http://mxr.mozilla.org/nss/source/lib/util/secasn1d.c#1726

Needs the fix from Bug 1205157 and from Bug 1192028 to be useful for fuzzing

        item = (SECItem *)(child->dest);
-       if (item != NULL && item->data != NULL) {
+        PRBool copying_in_place = PR_FALSE;
+        sec_asn1d_state *temp_state = state;
+        while (temp_state && item == temp_state->dest && temp_state->indefinite) {
+            sec_asn1d_state *parent = sec_asn1d_get_enclosing_construct(temp_state);
+            if (!parent || parent->underlying_kind != temp_state->underlying_kind) {
+                break;
+            }
+            if (!parent->indefinite) {
+                copying_in_place = PR_TRUE;
+                break;
+            }
+            temp_state = parent;
+        }
+        if (item != NULL && item->data != NULL && !copying_in_place) {

I'm still not sure if this is the right fix.

For an ANY wrapped in a definite-length ANY, then dest has been preallocated for copying. For an indefinite length constructed string type wrapped in a definite-length string type (of the same type - that's required of BER), then it's also copying. However, if there's a definite-length ANY type wrapping an indefinite-length string type, there's no preallocation - the indefinite length string type needs to allocate its own storage, and the storage for its children.

Comment 20

[Ryan Sleevi]

Attachment: Proposed Fix

Attached is a fix that I believe works, and I've tried to extensively document (inline) why that is. Considering how confusing this whole mess was, I figured it'd make more sense to leave the explanation in code.

Comment 21

[Dana Keeler (she/her) (use needinfo) [:keeler]]

Comment on attachment 8662125 [details] [diff] [review]
Proposed Fix

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

As far as I can tell (given the complicated and unfamiliar nature of this code), I believe this is correct. Also, great write-up.

Comment 22

[Daniel Veditz [:dveditz]]

Use CVE-2015-7182 for this issue

Comment 23

[Ryan Sleevi]

Adding Apple Product Security due to this affecting libsecurity_asn1 ( https://opensource.apple.com/source/Security/Security-57031.40.6/Security/libsecurity_asn1/lib/ )

Comment 24

[Al Billings [:abillings - ex-MoCo]]

Does this affect ESR38?

Comment 25

[Dana Keeler (she/her) (use needinfo) [:keeler]]

(In reply to Al Billings [:abillings] from comment #24)
> Does this affect ESR38?

Yes. This is a long-standing issue.

Comment 28

[Kai Engert [:KaiE:]]

Comment on attachment 8662125 [details] [diff] [review]
Proposed Fix

Landed into NSS trunk.
https://hg.mozilla.org/projects/nss/rev/4dc247276e58

Comment 29

[Kai Engert [:KaiE:]]

I had to land a bustage fix, because the late variable declaration broke the Windows build.
https://hg.mozilla.org/projects/nss/rev/534aca7a5bca

Comment 30

[Kai Engert [:KaiE:]]

Another one :-(
https://hg.mozilla.org/projects/nss/rev/b4feb2cb0ed6

Comment 31

[Kai Engert [:KaiE:]]

Attachment: patch with bustage fixes merged in

Comment 32

[Kai Engert [:KaiE:]]

How should this issue be documented in the future release notes?

Comment 33

[Ryan Sleevi]

I'd lump it in with the others,

Several issues existed within the ASN.1 decoder used by NSS for handling streaming BER data. While the majority of NSS uses a separate, unaffected DER decoder, several public routines also accept BER data, and thus are affected. An attacker that successfully exploited these issues can overflow the heap and may be able to obtain remote code execution.

Comment 34

[Sylvestre Ledru [:Sylvestre]]

We landed these changes, updating the tracking flags accordingly.

Comment 35

[Kai Engert [:KaiE:]]

Marking fixed as of NSS 3.20.1
Release scheduled to be announced on Nov 3.

In addition, the fix has been backported to older branches, and additional releases
  3.19.2.1
and
  3.19.4
will also be announced on Nov 3.

(FYI, the difference between 3.19.2.1 and 3.19.4 are root CA changes, only.)