1192028 - (CVE-2015-7181) ASan: use-after-poison in sec_asn1d_parse_leaf()

Status: RESOLVED FIXED

(NSS :: Libraries, defect)

Description

[Tyson Smith [:tsmith]]

Attachment: call_stack.txt

Tim shared tools with me from bug 1185033.

Comment 1

[Tyson Smith [:tsmith]]

Attachment: test_case.der

Comment 2

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

Mass cc to get some NSS eyes on these bugs.

Comment 3

[Liz Henry (:lizzard) (relman/hg->git project)]

I'm assuming other versions than 42 would also be affected. Tracking for 43, for now.

Comment 4

[Liz Henry (:lizzard) (relman/hg->git project)]

sworkman or rbarnes can you help find an owner for this bug? Since it's sec-critical, I don't like to see it go assigned to nobody for too long. This bug has the assigned to nobody blues.

Comment 5

[Steve Workman [:sworkman] (INACTIVE)]

Keeler should able to look at this or find someone to look at it when he gets back from PTO next week.

Comment 6

[Tim Taubert [:ttaubert] (inactive)]

Here's some debug output from the ASN.1 parsing routines:

> PLACE = beforeIdentifier, next byte = 0x24, f4400464[0]
> State: tmpl f7168540, kind SEQUENCE duringSequence, expect 0x30 51
>   STATE: tmpl f7168570, kind OCTET_STRING beforeIdentifier, expect 0x04 0
> Found tag 24  CONSTRUCTED OCTET_STRING

Found a constructed octet string...

> PLACE = afterIdentifier, next byte = 0x01, f4400465[0]
> State: tmpl f7168540, kind SEQUENCE duringSequence, expect 0x30 51
>   STATE: tmpl f7168570, kind OCTET_STRING afterIdentifier, expect 0x04 0
> 
> PLACE = beforeLength, next byte = 0x01, f4400465[0]
> State: tmpl f7168540, kind SEQUENCE duringSequence, expect 0x30 51
>   STATE: tmpl f7168570, kind OCTET_STRING beforeLength, expect 0x04 0
> 
> PLACE = afterLength, next byte = 0x24, f4400466[0]
> State: tmpl f7168540, kind SEQUENCE duringSequence, expect 0x30 51
>   STATE: tmpl f7168570, kind OCTET_STRING afterLength, expect 0x04 0
> Found Length 1

... with length 1.

> PLACE = beforeIdentifier, next byte = 0x24, f4400466[0]
> State: tmpl f7168540, kind SEQUENCE duringSequence, expect 0x30 51
>   State: tmpl f7168570, kind OCTET_STRING duringConstructedString, expect 0x04 1
>     STATE: tmpl f6badb60, kind OCTET_STRING  beforeIdentifier, expect 0x04 0
> Found tag 24  CONSTRUCTED OCTET_STRING

Found another constructed string inside it. After parsing the tag we should be done with the parent because of length=1, or maybe throw an error because we'd need the length too. (Seems like the minimum length should be 2 for "0000"?)

> PLACE = afterIdentifier, next byte = 0x80, f4400467[0]
> State: tmpl f7168540, kind SEQUENCE duringSequence, expect 0x30 51
>   State: tmpl f7168570, kind OCTET_STRING duringConstructedString, expect 0x04 1
>     STATE: tmpl f6badb60, kind OCTET_STRING  afterIdentifier, expect 0x04 0
> 
> PLACE = beforeLength, next byte = 0x80, f4400467[0]
> State: tmpl f7168540, kind SEQUENCE duringSequence, expect 0x30 51
>   State: tmpl f7168570, kind OCTET_STRING duringConstructedString, expect 0x04 1
>     STATE: tmpl f6badb60, kind OCTET_STRING  beforeLength, expect 0x04 0
> 
> PLACE = afterLength, next byte = 0x04, f4400468[0]
> State: tmpl f7168540, kind SEQUENCE duringSequence, expect 0x30 51
>   State: tmpl f7168570, kind OCTET_STRING duringConstructedString, expect 0x04 1
>     STATE: tmpl f6badb60, kind OCTET_STRING  afterLength, expect 0x04, indef 0
> Found Length 0 indefinite

We happily continue parsing the length.

> PLACE = beforeIdentifier, next byte = 0x04, f4400468[0]
> State: tmpl f7168540, kind SEQUENCE duringSequence, expect 0x30 51
>   State: tmpl f7168570, kind OCTET_STRING duringConstructedString, expect 0x04 1
>     State: tmpl f6badb60, kind OCTET_STRING  duringConstructedString, expect 0x04, indef 0
>       STATE: tmpl f6badb60, kind OCTET_STRING  beforeIdentifier, expect 0x04 0
> Found tag 04  OCTET_STRING

And another tag inside that new octet string.

> PLACE = afterIdentifier, next byte = 0x18, f4400469[0]
> State: tmpl f7168540, kind SEQUENCE duringSequence, expect 0x30 51
>   State: tmpl f7168570, kind OCTET_STRING duringConstructedString, expect 0x04 1
>     State: tmpl f6badb60, kind OCTET_STRING  duringConstructedString, expect 0x04, indef 0
>       STATE: tmpl f6badb60, kind OCTET_STRING  afterIdentifier, expect 0x04 0
> 
> PLACE = beforeLength, next byte = 0x18, f4400469[0]
> State: tmpl f7168540, kind SEQUENCE duringSequence, expect 0x30 51
>   State: tmpl f7168570, kind OCTET_STRING duringConstructedString, expect 0x04 1
>     State: tmpl f6badb60, kind OCTET_STRING  duringConstructedString, expect 0x04, indef 0
>       STATE: tmpl f6badb60, kind OCTET_STRING  beforeLength, expect 0x04 0
> 
> PLACE = afterLength, next byte = 0x00, f440046a[0]
> State: tmpl f7168540, kind SEQUENCE duringSequence, expect 0x30 51
>   State: tmpl f7168570, kind OCTET_STRING duringConstructedString, expect 0x04 1
>     State: tmpl f6badb60, kind OCTET_STRING  duringConstructedString, expect 0x04, indef 0
>       STATE: tmpl f6badb60, kind OCTET_STRING  afterLength, expect 0x04 0
> Found Length 24

And another length.

> PLACE = duringLeaf, next byte = 0x00, f440046a[0]
> State: tmpl f7168540, kind SEQUENCE duringSequence, expect 0x30 51
>   State: tmpl f7168570, kind OCTET_STRING duringConstructedString, expect 0x04 1
>     State: tmpl f6badb60, kind OCTET_STRING  duringConstructedString, expect 0x04, indef 0
>       STATE: tmpl f6badb60, kind OCTET_STRING  duringLeaf, expect 0x04 24

That's the point at which ASan crashes.

Comment 7

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

I think this is a result of a buggy constructed encoding implementation. Some background on ASN.1:

An OCTET STRING (tag 04) can be encoded as a constructed value, in which the concatenation of the substrings is the value of the overall string. For example:

24 0c                 [OCTET STRING | CONSTRUCTED] [length is 12 bytes]
   04 04 01 23 45 67    [OCTET STRING] [length is 4 bytes] [value is 01 23 45 67]
   04 04 89 ab cd ef    [OCTET STRING] [length is 4 bytes] [value is 89 ab cd ef]

This would result in an OCTET STRING with value 01 23 45 67 89 ab cd ef.
(This is from http://luca.ntop.org/Teaching/Appunti/asn1.html section 5.10).

NSS' implementation appears to allocate memory based on the length in the outer tag, recurse into the substrings, and copy the decoded substrings into the allocated memory. Obviously, care must be taken to not overflow that memory, and it appears that the simple case is handled. An input like:

24 01                 [length is 1 byte]
   04 04 01 23 45 67
   04 04 89 ab cd ef

is properly detected as invalid and the allocated memory isn't overflowed. However, if this is combined with an indefinite encoding (where the length is denoted as 80 and a terminating 00 00 is appended) and another layer of substring nesting, memory is overflowed:

24 01                     [length is 1 byte]
   24 80                  [OCTET STRING | CONSTRUCTED] [indefinite length]
      04 04 01 23 45 67
      04 04 89 ab cd ef
   00 00                  [end indefinite length]

ASAN detects this as a use-after-poison, but it looks like that's just an artifact of how the ASN.1 decoder uses memory arenas. On non-ASAN builds, with large enough substrings, this can overflow the entire arena, meaning this is actually a heap overflow bug that can be triggered from content.

Comment 8

[Tim Taubert [:ttaubert] (inactive)]

DER doesn't support indefinite length encoding, so when calling PK11_ImportDERPrivateKeyInfoAndReturnKey() that should probably be respected?

OTOH, should we simply bail out if we detect an indefinite length encoding in a definite length container? That seems like it would never produce valid BER format, right?

Comment 9

[Tim Taubert [:ttaubert] (inactive)]

(In reply to Tim Taubert [:ttaubert] from comment #8)
> OTOH, should we simply bail out if we detect an indefinite length encoding
> in a definite length container? That seems like it would never produce valid
> BER format, right?

I mean, it obviously *can* produce valid BER format if the substring has the right length but it still seems to not make a lot of sense to support that.

Comment 10

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

(In reply to Tim Taubert [:ttaubert] from comment #8)
> DER doesn't support indefinite length encoding, so when calling
> PK11_ImportDERPrivateKeyInfoAndReturnKey() that should probably be respected?

Ideally we would have a way of telling the parser that we really are expecting DER and not BER, but I'm not aware of a way to do that with the libraries currently available in NSS. Plus I imagine there would be compatibility concerns with doing that.

Comment 11

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

Attachment: 1192028-constructed.diff

I came up with this solution by looking at where the code enforced the similar case of nested strings but without the indefinite length component and extending it to work in this case as well. I don't have a high degree of confidence in it, but let me know what you think.

Comment 12

[Ryan Sleevi]

Comment on attachment 8658876 [details] [diff] [review]
1192028-constructed.diff

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

I'm setting r-, but I believe this is moving towards the correct solution, and is similar to what I've been looking at for handling this case.

There are two root issues here:
- An indefinite length encoded element within a definite length scope (either from the outermost scope of the invocation, or from a nested scope due to reading a definite length element) should be constrained to the most immediate definite length scope.
- The content length of a definite length element should be constrained to the most immediate definite length scope.

Your patch combines both of these, by virtue of walking the entire scope tree and comparing all definite lengths, but we should be able to short-circuit the moment we encounter a definite length ancestor - and we should ensure the topmost state is a definite length ancestor by virtue of the SECItem length of the input.

There's also the question of allocation - this check happens after allocation happens. I'm having trouble convincing myself that won't result in errors as well.

But I do think we're at the most sensitive part of the code, and that most of the bugs will collapse once we fix this point.

Comment 13

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

Attachment: patch v2

Thanks for the review, Ryan. This version is more comprehensive and I believe addresses the two issues in a more clear way. I'm also not sure how memory allocation interacts with this, but I suspect that will involve a separate fix to how indefinite lengths are handled (e.g. in bug 1202868).

Comment 14

[Ryan Sleevi]

Comment on attachment 8659616 [details] [diff] [review]
patch v2

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

::: lib/util/secasn1d.c
@@ +1023,5 @@
> +    }
> +    /* If parent is null, state is the outermost state or the outermost state
> +     * uses indefinite length. In that case, there's nothing external to
> +     * constrain this element. */
> +    if (parent && consumed + state->contents_length > parent->pending) {

Thinking aloud: For each of the indefinite length encodings (on line 1021), we *also* need the EOC octets (2 bytes). Should we factor this in when evaluating the cost?

Do you have a write-up of how we get in the wedged state here? That is, the state transitions? Because my fear is that if we don't account for the EOC, we can still end up in a bad state, but I don't think it's appropriate to account for the EOC here (maybe it is the only appropriate place to put it?)

The recursive call (like as used by sec_asn1d_reuse_encoding) is one option - but it seems way more work to try to get that right.

Should we be factoring that in on line 1021?

On an integer correctness issue, it does seem that this could exploit pathological overflow, by creating a large series of indefinite length encoded items. Since SEC_ASN1DecoderUpdate supports streaming BER, it seems like this 'might' be exploited by doing an object which is an indefinite length constructed string made up of an indef length constructed string (and so on and so on), past ULONG_MAX. That may seem like a lot of memory, but if you combined with gzip and chunked encoding, you could stream chunks at a time efficiently. It's unclear whether or not this represents a viable attack surface, but the mitigation here in this change would be to do some checking of sizes before addition.

I'd be curious whether or not my paranoia of overflow is reasonable. It's entirely possible it isn't (when considering the overall quality/security of this function).

Comment 15

[Ritu Kothari (:ritu) (Inactive, please n-i to RyanVM, jcristau, or pascal)]

Too late to take a fix in 41.

Comment 16

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

Attachment: patch v3

Thanks for the review.

(In reply to Ryan Sleevi from comment #14)
> Thinking aloud: For each of the indefinite length encodings (on line 1021),
> we *also* need the EOC octets (2 bytes). Should we factor this in when
> evaluating the cost?

I suppose so, yes - otherwise I think we could "successfully" decode encodings with incorrect lengths in the tags.

> On an integer correctness issue, it does seem that this could exploit
> pathological overflow

Good catch - I think it would be possible (particularly if you had a number of nested indefinite length elements and then a definite length element that was very large). To avoid this, I re-worked things so that instead of adding up the constrained lengths and then comparing to what the constraining context says the length should be, we find that constraining length and repeatedly subtract off the sub-lengths while checking that the remaining length is positive.

Comment 17

[Daniel Veditz [:dveditz]]

Use CVE-2015-7181 for this issue

Comment 18

[Sylvestre Ledru [:Sylvestre]]

It is likely that we will have to do a new 41 with this fix.

Comment 19

[Ryan Sleevi]

Comment on attachment 8661879 [details] [diff] [review]
patch v3

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

::: lib/util/secasn1d.c
@@ +1089,5 @@
> +                                                     top_context)) {
> +                return;
> +            }
> +            parent = sec_asn1d_get_enclosing_construct(parent);
> +        }

So, it took me a bit longer than desired to try to parse this. I'm wondering whether this can be simplified to the following form:

if (parent) {
  unsigned long constraining_length = parent->pending;
  if (!sec_asnd1_check_and_subtract_length(&constraining_length, parent->consumed, state->top)) {
    return;
  }
  parent = state;
  do {
    if (!sec_asn1d_check_and_subtract_length(&constraining_length, parent->consumed, state->top)) ||
        /* If state->indefinite is true, parent->content_length is zero and this is a no-op. */
        !sec_asn1d_check_and_subtract_length(&constraining_length, parent->content_length, state->top)) ||
        /* If state->indefinite is true, then ensure there is enough space for an EOC tag of 2 bytes. */
        (state->indefinite && !sec_asnd1_check_and_subtract_length(&constraining_length, 2, state->top))) {
      /* This element is larger than its enclosing element, which is invalid */
      return;
    }
  } while ((parent = sec_asnd1_get_enclosing_construct(parent)) && parent->indefinite);
}

This reduces the number of early returns to 2, which I think makes it easier to read, and it coalesces the conditionals. It also makes the treatment of state (which may be definite or indefinite) use the same logic as the treatment of the enclosing parents (which will always be indefinite), which I think makes things easier.

I didn't think the temporary "top_context" added much value for readability.

The other thing is that I think this check needs to be moved to line 969. We shouldn't allocate theTemplate->size if we know the length is invalid. We can safely move line 1004-1008 of the original to before the allocation without any change in side effects.

Comment 20

[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 21

[Julien Pierre]

David,

(In reply to David Keeler [:keeler] (use needinfo?) from comment #10)
> Ideally we would have a way of telling the parser that we really are
> expecting DER and not BER, but I'm not aware of a way to do that with the
> libraries currently available in NSS. Plus I imagine there would be
> compatibility concerns with doing that.

There is another ASN.1 parser which I wrote, and only supports DER. It is called the QuickDER decoder.
Look at lib/util/quickder.c and SEC_QuickDERDecodeItem .

However, we have to be careful to call it only in places where we truly only ever expect DER . While I would expect this to be OK in a function called PK11_ImportDERPrivateKeyInfoAndReturnKey , I would still check its callers in NSS and make sure there aren't any possible use cases for indefinite length encoding.

Comment 22

[Ryan Sleevi]

Julien: I CC'd you on Bug 1205140 for that discussion, which includes that recommendation :)

Comment 23

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

(In reply to Ryan Sleevi from comment #19)
> So, it took me a bit longer than desired to try to parse this. I'm wondering
> whether this can be simplified to the following form:

Yes, that looks equivalent, except:

>   unsigned long constraining_length = parent->pending;
>   if (!sec_asnd1_check_and_subtract_length(&constraining_length, parent->consumed, state->top)) {
>     return;
>   }

Unless I'm misunderstanding, what the most immediate definite enclosing element has already consumed shouldn't count against the pending data for it, since that's already been accounted for. Here's an example to illustrate:

24 0c             <= this is parent (i.e. the most immediate definite enclosing element)
   04 02 aa bb
   24 80
      04 02 cc dd <= when reading this substring, parent->pending is 8 and parent->consumed is 6.
   00 00

In any case, new patch coming soon. Also, does NSS have a recommended maximum line length?

Comment 24

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

Attachment: patch v4

Comment 25

[Ryan Sleevi]

(In reply to David Keeler [:keeler] (use needinfo?) from comment #23)
> (In reply to Ryan Sleevi from comment #19)
> > So, it took me a bit longer than desired to try to parse this. I'm wondering
> > whether this can be simplified to the following form:
> 
> Yes, that looks equivalent, except:
> 
> >   unsigned long constraining_length = parent->pending;
> >   if (!sec_asnd1_check_and_subtract_length(&constraining_length, parent->consumed, state->top)) {
> >     return;
> >   }
> 

You're right, the math was off there. I wrote it thinking of parent->content_length, but that doesn't align with ->consumed, since parent->consumed would include the Tag & Length consumption, which wouldn't be reflected in parent->content_length.

We can drop the accounting for parent->consumed, which further simplifies the checks.

> In any case, new patch coming soon. Also, does NSS have a recommended
> maximum line length?

It varies based on component. libpkix was very liberal, but much of the rest of NSS goes for 80.

Comment 26

[Ryan Sleevi]

Comment on attachment 8664363 [details] [diff] [review]
patch v4

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

R+, with mostly comment and naming nits. I've made some suggestions, but feel free to reject or reword them.

::: lib/util/secasn1d.c
@@ +960,5 @@
> + * decoding error in the given SEC_ASN1DecoderContext, and returns PR_FALSE.
> + */
> +static PRBool
> +sec_asn1d_check_and_subtract_length (unsigned long *constraining_length,
> +                                     unsigned long to_subtract,

NIT: It seems like in the context of this function, it may make more sense to rename "constraining_length" to "remaining" and "to_subtract" as "consumed"

@@ +961,5 @@
> + */
> +static PRBool
> +sec_asn1d_check_and_subtract_length (unsigned long *constraining_length,
> +                                     unsigned long to_subtract,
> +                                     SEC_ASN1DecoderContext *top_context)

STYLE NIT: This variable is named cx in other functions.

@@ +1006,5 @@
> +     *   2. Repeat the search while subtracting the lengths necessary to
> +     *      contain the elements constrained by that scope. If a length to
> +     *      subtract ever exceeds the remaining length indicated by that scope,
> +     *      the encoding is bad.
> +     */

I guess I still struggle with the wording here of this comment. The first two sentences don't feel very natural for me, as it suggests there's some difference between definite and indefinite length handling, but really, we're talking about the same thing - constraining the child to the parent.

/**
 * The maximum length for a child element should be constrained to the length
 * remaining in the first definite length element in the ancestor stack. If there
 * is no definite length element in the ancestor stack, there's nothing to
 * constrain the length of the child, so there's no further processing necessary.
 *
 * It's necessary to walk the ancestor stack, because it's possible to have
 * definite length children that are part of an indefinite length element, which is
 * itself part of an indefinite length element, and which is ultimately part of a
 * definite length element. A simple example of this would be the handling of
 * constructed OCTET STRINGs in BER encoding.
 *
 * This algorithm finds the first definite length element in the ancestor stack, if
 * any, and if so, ensures that the length of the child element is consistent with
 * the number of bytes remaining in the constraining ancestor element (that is, after
 * accounting for any other sibling elements that may have been read).
 *
 * It's slightly complicated by the need to account both for integer underflow and
 * overflow, as well as ensure that for indefinite length encodings, there's also enough
 * space for the End-of-Contents (EOC) octets (Tag = 0x00, Length = 0x00, or two bytes).
 */

 /* Determine the maximum length available for this element by finding the first definite
  * length ancestor, if any. */
 sec_asn1d_state *parent = ...;
 ...

 /* If parent is null, state is either the outermost state / at the top of the stack, or
  * the outermost state uses indefinite length encoding. In these cases, there's nothing
  * external to constrain this element, so there's nothing to check. */
 if (parent) {

@@ +1015,5 @@
> +    /* If parent is null, state is the outermost state or the outermost state
> +     * uses indefinite length. In that case, there's nothing external to
> +     * constrain this element. */
> +    if (parent) {
> +        unsigned long constraining_length = parent->pending;

Could call this "remaining"

Comment 27

[Ryan Sleevi]

reminder to hold off committing until coordinating releases :)

Comment 28

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

Attachment: patch v4.1

Thanks, Ryan. I went ahead and used your documentation, since it was more clear. I also used 80 characters as a line limit, which made things slightly less readable, but I did the best I could.

Comment 31

[Kai Engert (:KaiE:)]

Attachment: v.4.1 with merge conflict resolved

Note that the reviewed patch doesn't apply cleanly to NSS trunk.
There's a difference in the context (the printf statement just before the second block is different).

This is the merged patch.

Comment 34

[Kai Engert (:KaiE:)]

Comment on attachment 8668423 [details] [diff] [review]
v.4.1 with merge conflict resolved

Landed into NSS trunk.
https://hg.mozilla.org/projects/nss/rev/8ac7f47eecbb

Comment 35

[Kai Engert (:KaiE:)]

Windows bustage fix, variable declarations must go first.
https://hg.mozilla.org/projects/nss/rev/25cb033147fd

Comment 36

[Kai Engert (:KaiE:)]

Attachment: patch with bustage fixes merged in

Comment 37

[Kai Engert (:KaiE:)]

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

Comment 38

[Ryan Sleevi]

I'd lump this 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 39

[Sylvestre Ledru [:Sylvestre]]

I think we fixed this issue in 42, 43 & 44. Updating the tracking flags.

Comment 40

[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.)