[CVE-2021-45960] A large number of prefixed XML attributes on a single tag can crash libexpat (troublesome left shifts by >=29 bits in function storeAtts)

[hartwork]

Back in 2015, Tyson Smith (@tysmith) reported invalid left shifts at 5 places in libexpat to Mozilla. 3 of these bad shifts had also been reported by Dingbao Xie (@xiedingbao), and been fixed in commit 2106ee4 and release 2.2.0 in 2016; this ticket is meant to explain my evaluation of those 2 remaining bad shifts, as a reference, for anyone interested, and to allow review and correction as needed.

For short, there is security issue in libexpat that affects even the oldest releases, >=1.95.7 at least (commit b288698). Probably not one to panic about.

The related code in function storeAtts in lib/xmlparse.c is this:

int nsAttsSize = (int)1 << parser->m_nsAttsPower;
[..]
nsAttsSize = (int)1 << parser->m_nsAttsPower;
[..]
temp = (NS_ATT *)REALLOC(parser, parser->m_nsAtts,
                         nsAttsSize * sizeof(NS_ATT));

It should be noted that:

• The related code is triggered by XML documents that contain tags with prefixed attributes (e.g. <r xmlns:a="[..]" a:a123="[..]" [..] />.
• The (int) cast doesn't do anything, 1 is int by default.
• A left shift on signed int by >=31 bits is undefined behavior for sizeof(int)==4.
• For the multiplication in nsAttsSize * sizeof(NS_ATT):
  • sizeof returns a size_t, unsigned and larger or equal to int in size, depending on machine architecture.
  • signed nsAttsSize is promoted to unsigned(!) size_t in context of that multiplication.
• The value of m_nsAttsPower is derived from the number of prefixed attributes in the tag. If we include the namespace declaration attribute in that number, the math is atts_power := int(math.log2(atts_count - 1)) + 2 (thinking Python). So to see m_nsAttsPower value 29 in memory, we need 2^(29-2)+1 prefixed XML attributes.

From here on, behavior of the code depends on the machine architecture, in particular the sizes of types int and size_t; so we get different behavior on e.g. 32bit x86 than on 64bit amd64. In detail:

                  |  x86 (32bit int and size_t)        |  amd64 (32bit int, 64bit size_t)
------------------+------------------------------------+---------------------------------
m_nsAttsPower 29  |  (size_t)(1 << 29) * (4+4+4)       |  (size_t)(1 << 29) * (8+8+8)
                  |  => 2_147_483_648, mult overflow   |  >= 12_884_901_888
                  |  => allocating too few bytes       |  => mallocs okay or returns NULL
                  |                                    |
m_nsAttsPower 30  |  (size_t)(1 << 30) * (4+4+4)       |  (size_t)(1 << 30) * (8+8+8)
                  |  => 0, mult overflow               |  => 25_769_803_776
                  |  => realloc acts as free           |  => mallocs okay or returns NULL
                  |                                    |
m_nsAttsPower 31  |  (size_t)(1 << 31) * (4+4+4)       |  (size_t)(1 << 31) * (8+8+8)
                  |  => undefined behavior             |  => undefined behavior
                  |                                    |

To summarize the problem,

• m_nsAttsPower<=28 is fine on both platforms.
• m_nsAttsPower==29 will allocate too few bytes on 32bit, fine on 64bit.
• m_nsAttsPower==30 makes realloc act like free on 32bit, fine on 64bit.
• m_nsAttsPower>=31 is undefined behavior is denial of service (or more) on both platforms.

The fix will have these parts:

• First, detect and prevent left shifts by sizeof(int) * 8 - 1 or more bits.
• Second, detect and prevent integer overflow on nsAttsSize * sizeof(NS_ATT).
• (Third, turn int into unsigned int to make the code more clear, close the door to undefined behavior, and allow even 1u << 31.)

A pull request and likely a CVE are upcoming, and there will be a soon release 2.4.3.

Because thy payload to trigger the vulnerability is in the gigabytes, remote exploitability will hopefully be stopped by upload limits in most setups, before even getting to libexpat. Even when generating attribute names using the base58 scheme for short non-overlapping names, an XML file with e.g. 2^29+1 attributes on a single tag is ~6.5 GiB in size.
I have a Python >=3.6 script to create XML files like that online at https://gist.github.com/hartwork/ccad94d00c4193e05ab57de70021e6ee.

Best, Sebastian

[hartwork]

CVE requested from Mitre just now.

[carnil]

CVE-2021-45960 appears to have been assigned.

[hartwork]

@carnil, yes Mitre mailed CVE-2021-45960 to me only a minute ago.

[carnil]

@hartwork ah alright, I noticed by chance looking some minutes ago in the CVE feed from MITRE :) (for updating CVE informations in downstream Debian)