Hello,

There is an out-of-bounds write that is likely exploitable while performing Huffman decoding of Fax images.
The technical details are as follows.

Type: integer underflow produces out of bounds heap/etc write

Platform: 32-bit

Details:

 390 MagickExport MagickPassFail HuffmanDecodeImage(Image *image)
 391 {
 392 const HuffmanTable
 393 *entry;
 394
 [...]
 412
 413 long
 414 count,
 415 y;
 416
 [...]
 420 register long
 421 i,
 422 x;
 423
 [...]
 462 InitializeHashTable(mw_hash,TWTable,MWHashA,MWHashB);
 463 InitializeHashTable(mw_hash,MWTable,MWHashA,MWHashB);
 464 InitializeHashTable(mw_hash,EXTable,MWHashA,MWHashB);
 465 InitializeHashTable(mb_hash,TBTable,MBHashA,MBHashB);
 466 InitializeHashTable(mb_hash,MBTable,MBHashA,MBHashB);
 467 InitializeHashTable(mb_hash,EXTable,MBHashA,MBHashB);

Basic initialization; of specific note are that the variables ‘x’ and ‘count’ are signed. On a 64-bit
platform, assuming GCC or similar, it is 8 bytes in length and of course 4 bytes in length on 32-bit. There
is nothing inherently restricting this to 32-bit other than practicalities of the file size as there is a
need to have backing data to trigger the vulnerability. On 64-bit platforms this equates to a file size that
exceeds the default maximums, whereas on 32-bit the attached Proof-of-Concept out-of-bounds write trigger
only requires a file of a few megabytes-- which to my understanding can be reduced by wrapping the file in
compression.

Additionally, the Huffman hash tables have code lengths that range between 0 and 2560.

495 color=True;
496 code=0;
497 count=0;
498 length=0;
499 runlength=0;
500 x=0;
501 for ( ; ; )
502 {
503 if (byte == EOF)
504 break;
505 if (x >= (long) image->columns)
506 {
507 while (runlength < 11)
508 InputBit(bit);
509 do { InputBit(bit); } while (bit == 0);
510 break;
511 }
512 bail=False;
513 do
514 {
515 if (runlength < 11)
516 InputBit(bit)
517 else
518 {
519 InputBit(bit);
520 if (bit)
521 {
522 null_lines++;
523 if (x != 0)
524 null_lines=0;
525 bail=True;
526 break;
527 }
528 }
529 code=(code << 1)+bit;
530 length++;
531 } while (code <= 0);
532 if (bail)
533 break;
534 if (length > 13)
535 {
536 while (runlength < 11)
537 InputBit(bit);
538 do
539 {
540 InputBit(bit);
541 } while (bit == 0);
542 break;
543 }
544 if (color)
545 {
546 if (length < 4)
547 continue;
548 entry=mw_hash[((length+MWHashA)*(code+MWHashB)) % HashSize];
549 }
550 else
551 {
552 if (length < 2)
553 continue;
554 entry=mb_hash[((length+MBHashA)*(code+MBHashB)) % HashSize];
555 }
556 if (!entry)
557 continue;
558 if ((entry->length != length) || (entry->code != code))
559 continue;

In the above code, we enter an unbounded for() loop at line 501, which terminates upon file EOF or other
abnormal condition. lines 513-531 unpack a huffman encoded pixel one bit at a time. Once the first binary 1
is encountered, the loop will always terminate until the total length of the code exceeds 13 or a
corresponding entry in the huffman tables are found at lines 548 or 554.

In other words, we unpack the pixels and look them up in the huffman tables. Once we encounter a one, we
terminate the loop and attempt to look up the symbol in the corresponding tables matching the symbol length
and the symbol code. If we don’t find a match, then we restart the loop and unpack another bit. This
continues until a symbol is found or a sequence of 11 or more zeros or 13 or more bits is encountered.

 560 switch (entry->id)
 561 {
 562 case TWId:
 563 case TBId:
 564 {
 565 count+=entry->count;
 566 if ((x+count) > (long) image->columns)
 567 count=(long) image->columns-x;
 568 if (count > 0)
 569 {
 570 if (color)
 571 {
 572 x+=count;
 573 count=0;
 574 }
 575 else
 576 for ( ; count > 0; count--)
 577 scanline[x++]=1;
 578 }
 579 color=!color;
 580 break;
 581 }
 582 case MWId:
 583 case MBId:
 584 case EXId:
 585 {
 586 count+=entry->count;
 587 break;
 588 }

When a symbol is found, we enter a jump table dependant upon the symbol type. The crux of the problem exists
in this section. The bounds check at line 566: “if ((x+count) > (long) image->columns)” is insufficient due
to the variables being signed, thus it becomes possible to:
1 Iterate across TWId or TBId symbols incrementing the value of x such that x is non-zero but less than
image->columns
2 Provide repeated instance of MWid, MBId or EXId symbols to iteratively work the “count” variable into a
value close to but not exceeding INT_MAX
3 Provide another TWId or TBId symbol causing an additive overflow at line 566.
4 Depending upon the state of the variable ‘color’, this will either result in:
⋅⋅4 The x variable becoming negative yielding an invalid offset at line 577; or
⋅⋅4 Resulting in an invalid value of count which exceeds the image->columns and thus bounding of scanline,
resulting in an out-of-bounds write at lines 577 and 578

 592 code=0;
 593 length=0;
 594 }
 [...]

Proof-of-Concept:

Attached is a simple C++ program that when build (make; assuming g++ is in your path) and run will output a
file ‘poc.fax’ that can then be supplied to any code path that causes
ReadImage()->ReadFAXImage()->HuffmanDecodeImage() to be executed. It works the ‘x’ variable up to a value of
64, then the count variable up to INT_MAX - 64, then provides one of the symbols with a count length of 0 to
make x negative and then fetches a symbol that results in the out-of-bounds write.

Vendor Response

Justin,

This problem (and a number of other issues observed in compress.c) are
addressed by Mercurial changeset 16131:95abc2b694ce.

Thank you very much for your detailed report.

Bob

Impact

Exploitability:

At first blush, this appears to be a wild out-of-bounds write with relatively little control. However, the
check at line 568 allows us a finer grained control over circumstances. Notably, it becomes possible to skip
over uncontrolled writes and toggle the color variable, the user can then supply additional MWId, MBId or
EXId symbols, causing the value of count to become non-negative, which in tandem with the color toggle
allows arbitrary modification of the x variable which in turn allows for a finer controlled write. The only
bounding is the maximum file size to be processed with each iteration taking approximately 1.3 megabytes of
huffman codes which can be compressed and should compress down nicely.

In other words, you can set the value of x, then increment count into a negative value and toggle the color
variable back then increment count until its value is sane/positive again, and then re-enter the TWId/TBId
section thereby modifying the x variable again, then increment count into a negative and toggle color again
and overall repeat. This would ultimately allow writes as fine grained as a single byte immediately after or
immediately before the scanline buffer and within a certain range outside of that bounding. As this is heap
memory, it is thought to readily lend itself to exploitability.

Finally, because this would allow for the modification of heap metadata, e.g. block sizes and similar,
because both the encoded and decoded data is user controlled without any real constraints and because all
code paths will trigger a free condition, exploitibility seems more a matter of academic interest than a
legitimate question.

The specifics of this can be begrudingly worked out if required.