Closed Bug 492779 (CVE-2009-2463) Opened 15 years ago Closed 15 years ago

PL_Base64Decode integer overflow

Categories

(NSPR :: NSPR, defect)

defect
Not set
minor

Tracking

(Not tracked)

RESOLVED FIXED

People

(Reporter: monarch2020, Assigned: wtc)

Details

(Keywords: fixed1.8.1.24, fixed1.9.0.12, fixed1.9.1, Whiteboard: [sg:critical?] impractical attack? [4.7.5] [mostly fixed in 4.8])

Attachments

(5 files, 2 obsolete files)

User-Agent:       Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.9.0.10) Gecko/2009042316 Firefox/3.0.10 (.NET CLR 3.5.30729)
Build Identifier: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.9.0.10) Gecko/2009042316 Firefox/3.0.10 (.NET CLR 3.5.30729)

PL_Base64Deconde in nsprpub/lib/libc/src/base64.c appears to suffer from an integer overflow issue while determine the size of the dest buffer.

I only spent a small amount of time trying to determine if it was possible to trigger this, but with no success.  I've since discarded it from my list of bugs to investigate but wanted to pass it on.  Since PL_Base64Decode is used in several locations it may be possible for a remote attacker to trigger the overflow. Once the overflow is triggered it would be a rather simple bug to exploit since an attacker can control the exact amount of data to overflow the buffer with by using invalid base64 characters to no op the decoding.

If you feel it is not possible to trigger the integer overflow, then please just fix the code and call it a potential bug. I labeled it as a security bug because someone with more knowledge of your code might see things I do not.

Reproducible: Couldn't Reproduce

Steps to Reproduce:
1. Use one of the many callers to PL_Base64Decode and pass a string large enough to overflow the size of the dest
2.
3.



Most likely would only be exploitable on high end computers.
Assignee: nobody → wtc
Component: Security → NSPR
Product: Firefox → NSPR
QA Contact: firefox → nspr
Version: unspecified → other
The problem is here:

http://bonsai.mozilla.org/cvsblame.cgi?file=mozilla/nsprpub/lib/libc/src/base64.c&rev=3.7&mark=406#404

I'm not sure we can get a 1.4Gb string into there, but there are enough callers that we probably can't rule it out. If we can then we'd have a buffer overwrite when we got to decode() on line 416. We should divide by 4 before the multiplication. (Note: only callers who pass a null dest are vulnerable)

PL_Base64Encode has a similar problem but would require a 3Gb string to trigger the overflow.

http://bonsai.mozilla.org/cvsblame.cgi?file=mozilla/nsprpub/lib/libc/src/base64.c&rev=3.7&mark=158#144

Maybe the real solution is to reject excessively long strings. 640K ought to be enough for anybody.
Status: UNCONFIRMED → NEW
Ever confirmed: true
Whiteboard: [sg:critical?]
The PL_strlen call here is also problematic because PL_strlen
returns PRUint32 rather than size_t:
http://bonsai.mozilla.org/cvsblame.cgi?file=mozilla/nsprpub/lib/libc/src/base64.c&rev=3.7&mark=384-387#404

Georgi Guninski filed bug 445295 on the use of PRUint32 for
buffer and string lengths in NSPR functions before.
In reply to comment 1,
Dan, At one time, the browser had a problem where it was frequently calling
realloc() on 200+MB string buffers.  See bug 400295.  I called for setting 
an upper bound on the size of string buffers, and I proposed 50MB.  That got
ENORMOUS push back, and was never implemented.  Fortunately, after about 6 
months, those absurd reallocs just mysteriously stopped.  

Now, you're proposing 640K.  I reject the notion that it's OK for the browser
to accept 200MB strings, but not acceptable for NSPR to accept 640KB strings.
What's good for the goose is good for the gander.
I was not proposing a literal 640K (Google the phrase).

(In reply to comment #2)
> The PL_strlen call here is also problematic because PL_strlen
> returns PRUint32 rather than size_t:

We're OK as long as we never ship a 64-bit version (note to Nelson: that's a joke, too. 64-bit versions are already available, although not from MoCo)
Flags: wanted1.9.1.x+
Flags: wanted1.9.0.x+
Flags: wanted1.8.1.x+
Flags: wanted1.8.0.x?
Flags: blocking1.9.1?
Flags: blocking1.9.0.12?
Whiteboard: [sg:critical?] → [sg:critical?] impractical attack?
Attached patch Proposed patch (without tests) (obsolete) — Splinter Review
I still need to add tests, but I'd like to get your
opinions on the approach.

I think it'd be better to pick a tighter than necessary
bound, say PR_UINT32_MAX/4 for both Encode and Decode, so
we can easily see no intermediate and final PRUint32 values
will overflow.
Attachment #377433 - Flags: superreview?(nelson)
Attachment #377433 - Flags: review?
Comment on attachment 377433 [details] [diff] [review]
Proposed patch (without tests)

I forgot to note that the magic constant 2147483647 in strlen.c
is PR_INT32_MAX:

http://bonsai.mozilla.org/cvsblame.cgi?file=mozilla/nsprpub/pr/include/prtypes.h&rev=3.41&mark=326#317
Comment on attachment 377433 [details] [diff] [review]
Proposed patch (without tests)

Wan-Teh,  Let's discuss this.

>-        PRUint32 destlen = ((srclen + 2)/3) * 4;
>+        PRUint32 destlen;
>+        /* Ensure all PRUint32 values stay within range. */
>+        if( srclen > (PR_UINT32_MAX/4) * 3  - 2 )

Remove the "- 2".  It's not strictly correct.  

Shouldn't the limit for Encode and the limit for Decode be symmetric?
Do we want to allow the Encoder to encode something that the Decoder 
will refuse to decode?
Since this patch limits Decode src to PR_UINT32_MAX / 3, 
shouldn't it     limit  Encode src to PR_UINT32_MAX / 4 ?

>     if( sizeof(PRUint32) < sizeof(size_t) )
>-        PR_ASSERT(l < 2147483647);
>+    {
>+        PR_ASSERT(l <= PR_INT32_MAX);
>+        if( l > PR_INT32_MAX )
>+            return 0;  /* is this better than calling abort? */
>+    }

Perhaps it should return PR_INT32_MAX in this case?
Comment on attachment 377433 [details] [diff] [review]
Proposed patch (without tests)

>+        /* Ensure all PRUint32 values stay within range. */
>+        if( srclen > (PR_UINT32_MAX/4) * 3  - 2 )

The -2 comes from the +2 in the expression below:

>+        destlen = ((srclen + 2)/3) * 4;

Basically, I start with the condition of overflow:

    ((srclen + 2)/3) * 4 > PR_UINT32_MAX

and solve it for srclen:

    srclen > (PR_UINT32_MAX/4) * 3 - 2

>+        if( srclen > PR_UINT32_MAX / 3 )
>+        {
>+            return (char *)0;
>+        }
>+        destlen = ((srclen * 3) / 4);

For Decode, the PR_UINT32_MAX/3 limit is actually not
necessary.  We can compute destlen in a different way so
that any value of srclen won't result in an overflow:

    PRUint32 rem = srclen % 4;
    destlen = (srclen / 4) * 3 + (rem * 3) / 4;
Wan-Teh, IINM, the objective of this computation
    if( srclen > (PR_UINT32_MAX/4) * 3  - 2 )
is to ensure that no 32-bit overflow will occur in the subsequent computation
    destlen = ((srclen + 2)/3) * 4;

Consider the srclen value 0xBFFFFFFD, which is (PR_UINT32_MAX/4) * 3.
Your comparison disallows it, because it is > (PR_UINT32_MAX/4) * 3 - 2,
yet when plugged into ((srclen + 2)/3) * 4, it yields 0xFFFFFFFC without 
any overflow.
Thanks.  (PR_UINT32_MAX/4) throws away 0.75, so
(PR_UINT32_MAX/4) * 3 throws away 2.25, which makes
the - 2 unnecessary.

I'll change the limit to (PR_UINT32_MAX/4) * 3 for Encode.

Do you want me to rewrite the calculation of destlen for
Decode so that we don't need to impose a limit?
> Do you want me to rewrite the calculation of destlen ?

Sure.  Let me suggest:

    PRUint32 rem = srclen % 4;
    destlen = 3 * ((srclen / 4) + (rem != 0));
Nelson, the formula you gave in comment 11 is only
an approximation to the original formula.  Since we
store a terminating null byte at index 'destlen':

http://bonsai.mozilla.org/cvsblame.cgi?file=mozilla/nsprpub/lib/libc/src/base64.c&rev=3.7&mark=412#404

I use my formula, which gives the same value as the
original formula.
Attachment #377433 - Attachment is obsolete: true
Attachment #377609 - Flags: superreview?(nelson)
Attachment #377609 - Flags: review?(dveditz)
Attachment #377433 - Flags: superreview?(nelson)
Attachment #377433 - Flags: review?
Of course, for the decoder, destlen is merely an upper bound.  My formula
ensures that it will always be a multiple of 3, which the original formula
did not.  If you think it should always be one more than a multiple of 3,
that's fine with me.

The (rem * 3)/4 forumla seems to assume that, in the presence of a partial 
block of input (less that 4 bytes), the amount of output will be in some way 
proportional to the "remainder" number of bytes of input.  

My formula is based on the observation that base64 encoded input is required 
to be a multiple or 4 bytes long (excluding white space). 
Each block of 4 bytes of input will produce 3 bytes of output, except 
the last block of 4 bytes, which will produce 1, 2 or 3 bytes of output.
The only way that the input can be other than a multiple of 4 and not 
have an error is when whitespace is present in the input.  In that case,
the output will be more than big enough.
Comment on attachment 377609 [details] [diff] [review]
Proposed patch (without tests) v2

r=nelson

I see that our decoder does allow a final partial block, but that
it rounds down, not up, on the number of bytes output.
Attachment #377609 - Flags: superreview?(nelson) → superreview+
Nelson,

I didn't write base64.c, and I am not familiar with Base64.
I don't know the purpose of that terminating null byte, so
I don't want to change the value of destlen.

If we just want an upper bound, we can compute destlen using
  PRUint32 destlen = 3 * ((srclen / 4) + 1);

I'm very confused as to how the caller of PL_Base64Decode
knows the length of the decoded data.  Is that (srclen * 3)/4?

Dan, could you ask a Mozilla developer who's familiar with
Base64 to work with Nelson on this bug?  I won't be able to
spend more time on this.

We should also update the comment in plbase.h with a formula
that doesn't overflow:
http://bonsai.mozilla.org/cvsblame.cgi?file=mozilla/nsprpub/lib/libc/include/plbase64.h&rev=3.5&mark=79#70

That formula (srclen * 3)/4 has been copied to the Mozilla
code I cited in comment 14.  We need to fix the source.
Assignee: wtc → nspr
Wan-Teh, 
I'm sure you didn't write this code.  You would have designed a better 
interface, and probably a different algorithm.  

Prompted by your comment 16, I went back and read through all the code, and 
discovered that this API expects NO whitespace.  It does not detect or skip
over whitespace, and it does not expect or allow the last character of input
to be an end-of-line character.  It allows partial final blocks to be decoded
because it actually strips trailing padding characters.  In other words, it
will decode an input stream from which the caller has stripped trailing 
padding characters.  

Since you're likely to run into Base64 encoding and decoding again, let me
describe it briefly.  Encoding takes binary input, 3 bytes at a time, and
outputs 4 encoded characters for each 3 bytes of input.  Each encoded 
character contains 6 bits from the original binary input.  Output is always
a multiple of 4 bytes and includes no white space.  When the input is not a 
multiple of 3 bytes, it is padded to be a multiple of 3, and then the last 
one or two of the final four bytes of output is replaced with an '=' character, 
one '=' character for each byte of padding added to the input.  By convention, 
white space (including end of line characters) is permitted to be inserted 
into the encoded data on any 4-character boundary (between any two blocks 
of 4 bytes of encoded output).

Decoding is the reverse.  Input is taken 4 characters at a time, and converted
into binary output 3 bytes at a time.  For the last 4-character block of input,
The output is reduced by one byte for each '=' in the block.  Thus, assuming
input is a multiple of 4, output length = input length * 0.75 - the number of
trailing '=' characters.  This decoder allows odd length inputs, treating 
missing characters from the final block as '=' characters.  

Anyway, your patch is OK.  SR+!
Nelson, thanks for writing an intro to Base64.  I'll read it
later.

On second thought, I removed my change to PL_strlen from this
patch because returning any value (0 or PR_INT32MAX) less than
the actual string length may result in a buffer overflow if the
caller uses the return value to allocate a buffer and copy the
string to the buffer using strcpy.  I'm afraid that the only
safe things to do are 1) call abort(), or 2) violate the API
contract and store a terminating null byte into the const
string to truncate it to the returned length.

I checked in the patch on the NSPR trunk (NSPR 4.8).

Checking in base64.c;
/cvsroot/mozilla/nsprpub/lib/libc/src/base64.c,v  <--  base64.c
new revision: 3.8; previous revision: 3.7
done
Checking in strlen.c;
/cvsroot/mozilla/nsprpub/lib/libc/src/strlen.c,v  <--  strlen.c
new revision: 3.8; previous revision: 3.7
done
Attachment #377609 - Attachment is obsolete: true
Attachment #377609 - Flags: review?(dveditz)
The remaining work is:

1. update the comments in plbase64.h that instruct the callers
on how to calculate the size of the 'dest' output buffer.

http://bonsai.mozilla.org/cvsblame.cgi?file=mozilla/nsprpub/lib/libc/include/plbase64.h&rev=3.5&mark=53-55#45

http://bonsai.mozilla.org/cvsblame.cgi?file=mozilla/nsprpub/lib/libc/include/plbase64.h&rev=3.5&mark=78-81#70

For PL_Base64Decode, if the 'dest' output buffer size doesn't
need to be exactly (srclen * 3)/4, we can use (srclen/4 + 1) * 3,
which gives an approximate upper bound.  Alternatively we can
do 64-bit arithmetic ((PRUint64)srclen * 3)/4.

Another alternative is to impose a maximum on 'srclen'.
We can use the same maximum for PL_Base64Encode and
PL_Base64Decode for simplicity.

2. do something about PL_strlen.
Wan-Teh - Will we get this fix with NSPR_4_8_RTM in bug 492464?  Does this need to block, independent of that pickup?
Minused, but renom as per comment 20 if we need this independent of bug 492464.
Flags: blocking1.9.1? → blocking1.9.1-
Mozilla gets this fix with NSPR_4_8_RTM.  But Mozilla has similar
problems outside NSPR.  See comment 14.

I can create NSPR_4_7_5_RTM for Firefox 3.0.x if necessary.

I pushed NSPR_4_8_RTM to mozilla-1.9.1 in changeset 9fef988ed375:
http://hg.mozilla.org/releases/mozilla-1.9.1/rev/9fef988ed375

I pushed NSPR_4_8_RTM to mozilla-central in changeset 48dd4339ea86:
http://hg.mozilla.org/mozilla-central/rev/48dd4339ea86
Keywords: fixed1.9.1
Whiteboard: [sg:critical?] impractical attack? → [sg:critical?] impractical attack? [consider for 4.7.5]
Target Milestone: --- → 4.8
(In reply to comment #22)
> I can create NSPR_4_7_5_RTM for Firefox 3.0.x if necessary.

I think we'd like that in the next week or two. Any idea what other fixes it will have?
Add comments to plbase64.h to explain how to avoid
PRUint32 overflow when calculating destination buffer
sizes.

Call strlen instead of PL_strlen so we can detect
size_t to PRUint32 truncations.

Change PL_Base64Decode to use the exact same formula
documented in the header.
Attachment #378633 - Flags: review?(nelson)
I can't think of any value that PL_strlen can return
safely when the string's length overflows PRUint32.
So I manually expanded the PR_ASSERT macro to ensure
that we also call abort() (via PR_Assert) when that
happens.

Here is the definition of PR_ASSERT for your reference:
http://bonsai.mozilla.org/cvsblame.cgi?file=mozilla/nsprpub/pr/include/prlog.h&rev=3.16&mark=237-238,245#234

PR_Assert calls abort:
http://bonsai.mozilla.org/cvsblame.cgi?file=mozilla/nsprpub/pr/src/io/prlog.c&rev=3.50&mark=551,563#551
Attachment #378634 - Flags: review?(nelson)
Comment on attachment 378633 [details] [diff] [review]
Add comments, call strlen instead of PL_strlen (checked in)


>-#include "plstr.h" /* for PL_strlen */
>+#include <string.h> /* for strlen */

>-        srclen = PL_strlen(src);
>+        size_t len = strlen(src);

Why?
Ignore comment 27.  I see.  uint->size_t.
Attachment #378633 - Flags: review?(nelson) → review+
Attachment #378634 - Flags: review?(nelson) → review+
Comment on attachment 378634 [details] [diff] [review]
Call abort() if PL_strlen overflows (checked in)

I predict bugs will be filed about the crashes this causes.
Flags: blocking1.9.0.12?
Flags: blocking1.9.0.12+
Flags: blocking1.8.1.next?
Comment on attachment 378634 [details] [diff] [review]
Call abort() if PL_strlen overflows (checked in)

I checked in this patch on the NSPR trunk (NSPR 4.8.1).

Checking in strlen.c;
/cvsroot/mozilla/nsprpub/lib/libc/src/strlen.c,v  <--  strlen.c
new revision: 3.9; previous revision: 3.8
done
Attachment #378634 - Attachment description: Call abort() if PL_strlen overflows → Call abort() if PL_strlen overflows (checked in)
Comment on attachment 378633 [details] [diff] [review]
Add comments, call strlen instead of PL_strlen (checked in)

I checked in this patch on the NSPR trunk (NSPR 4.8.1).

Checking in plbase64.h;
/cvsroot/mozilla/nsprpub/lib/libc/include/plbase64.h,v  <--  plbase64.h
new revision: 3.6; previous revision: 3.5
done
Checking in base64.c;
/cvsroot/mozilla/nsprpub/lib/libc/src/base64.c,v  <--  base64.c
new revision: 3.9; previous revision: 3.8
done
Attachment #378633 - Attachment description: Add comments, call strlen instead of PL_strlen → Add comments, call strlen instead of PL_strlen (checked in)
Status: NEW → RESOLVED
Closed: 15 years ago
Resolution: --- → FIXED
Whiteboard: [sg:critical?] impractical attack? [consider for 4.7.5] → [sg:critical?] impractical attack? [consider for 4.7.5] [mostly fixed in 4.8]
Target Milestone: 4.8 → 4.8.1
Thank you for your efforts. It was great to watch an open source community in action.
Assignee: nspr → wtc
I backported the patches (attachment 377692 [details] [diff] [review], attachment 378633 [details] [diff] [review], and
attachment 378634 [details] [diff] [review]) to the NSPR_4_7_BRANCH for NSPR 4.7.5.

Checking in include/plbase64.h;
/cvsroot/mozilla/nsprpub/lib/libc/include/plbase64.h,v  <--  plbase64.h
new revision: 3.5.86.1; previous revision: 3.5
done
Checking in src/base64.c;
/cvsroot/mozilla/nsprpub/lib/libc/src/base64.c,v  <--  base64.c
new revision: 3.7.86.1; previous revision: 3.7
done
Checking in src/strlen.c;
/cvsroot/mozilla/nsprpub/lib/libc/src/strlen.c,v  <--  strlen.c
new revision: 3.7.86.1; previous revision: 3.7
done
Whiteboard: [sg:critical?] impractical attack? [consider for 4.7.5] [mostly fixed in 4.8] → [sg:critical?] impractical attack? [4.7.5] [mostly fixed in 4.8]
I updated the NSPR checkout tag on the Mozilla trunk from NSPR_4_7_3_RTM to
NSPR_4_7_5_RTM for Mozilla 1.9.0.12.

Checking in client.mk;
/cvsroot/mozilla/client.mk,v  <--  client.mk
new revision: 1.392; previous revision: 1.391
done
Keywords: fixed1.9.0.12
As printed on the to of the tinderbox page... "Bugs must have approval1.9.0.12+ from the 1.9.0-branch triage team". Is there a reason this landed without approval? Branch patches have always needed approval.
I got your email on June 8 titled "Please work on your 1.9.0.12 blockers!",
which is why I prepared the NSPR 4.7.5 release for Mozilla last Saturday.
(See also comment 23.)  From my past experience working on Mozilla, I thought
blocking1.9.0.12+ is equivalent to approval1.9.0.12+.  Sorry.

Do you want me to back out my checkin?
Comment on attachment 383092 [details] [diff] [review]
Upgrade NSPR to NSPR_4_7_5_RTM for Mozilla 1.9.0.12

Requesting approval1.9.0.12 to follow the process properly.

I prepared attachment 383295 [details] [diff] [review] if you want to look at the diffs.

All of these fixes have been tested on the Mozilla trunk for a
long time (at least six weeks).

Bug fixes in NSPR 4.7.4:

- bug 370766, bug 478687: 64 bit MAC OS X support
- bug 385583: NSPR makes incorrect assumptions about jmp_buf
              on ARM EABI systems
- bug 439144: Fix strict aliasing issues in prdtoa.c for gcc 4.4.
- bug 461502: Build NSPR shared libraries with the -Bdirect
              linker flag on Solaris.
- bug 465435: Add a comment to explain the check against
              FD_SETSIZE in _PR_MD_PR_POLL.
- bug 465629: Fix the comments about PR_EnumerateAddrInfo and
              PR_GetCanonNameFromAddrInfo
- bug 467951: Build NSPR on NetBSD with pthreads by default
- bug 469508: In prlink.c, errStrBuf is not thread-safe.
- bug 469744: Implement PR_OpenSemaphore for Mac OS X.
- bug 470528: NetBSD patches for mozilla/nsprpub/pr/include/md/_netbsd.{cfg,h}
- bug 473413: Build problem with spaces in path names
- bug 480740: When compiled by VC 2005, PR_ParseTimeString may
              crash on out-of-range time strings.

Bug fixes in NSPR 4.7.5:

- bug 489231: 64 bit MAC OS X support (LL_MAXUINT, etc.)
- bug 491205: NSPR provides incorrect declarations for big-endian
              ARM/Linux systems
- bug 492170: Crash or data corruption in NSPR's TransmitFile and
              SendFile on HPUX
- bug 492779: PL_Base64Decode integer overflow
Attachment #383092 - Flags: approval1.9.0.12?
Comment on attachment 383092 [details] [diff] [review]
Upgrade NSPR to NSPR_4_7_5_RTM for Mozilla 1.9.0.12

Approved for 1.9.0.12, a=dveditz for release-drivers
Attachment #383092 - Flags: approval1.9.0.12? → approval1.9.0.12+
I assume based on comments here that there is no way to trigger this flaw for verification purposes for 1.9.0.12.
This bug was assigned a CVE? The security announcement makes it sound
like you guys were able to actually find a way to trigger it. I know
I'm not privy to this information just because I reported, just curious.

http://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2009-2463
http://www.mozilla.org/security/announce/2009/mfsa2009-34.html
(In reply to comment #40)
Al: yes, I'm afraid that you need to verify this fix
by checking the source code for 1.9.0.12.  I didn't
try to find a way to trigger this flaw.  I have verified
my fix by copying the relevant code to a standalone
test program and checking that we detect integer
overflows caused by big 'srclen' values.  I started
with 'srclen' rather than calling strlen on a huge
'src' string.
Flags: blocking1.8.1.next? → blocking1.8.1.next+
MOZILLA_1_8_BRANCH has been upgraded to nspr 4.7.6 which contains the fix for this bug.
Keywords: fixed1.8.1.24
Alias: CVE-2009-2463
Group: core-security
You need to log in before you can comment on or make changes to this bug.

Attachment

General

Creator:
Created:
Updated:
Size: