MOPB-39-2007:PHP str_replace() Memory Allocation Integer Overflow Vulnerability

Summary

When str_replace() is called in a way that a single char is replaced by a long string and the single char occurs very often in the subject this will result in an integer overflow when the size of the memory buffer is calculated. The allocation of a too small buffer will result in a buffer overflow.
Affected versions

Affected are PHP 4 < 4.4.5 and PHP 5 < 5.2.1
Detailed information

When str_replace() is called the code will switch into two different code paths depending of the length of the search string. A single character search string will be handled by a different function, because this was implemented more efficient. However the more efficient method contains the following code that is vulnerable to an integer overflow.

Z_STRLEN_P(result) = len + (char_count * (to_len - 1));
Z_STRVAL_P(result) = target = emalloc(Z_STRLEN_P(result) + 1);
Z_TYPE_P(result) = IS_STRING;

It should be obvious that when char_count and to_len are for example both above 65537 this will result in an integer overflow of the 32 bit length counter and therefore not enough memory is allocated by the emalloc() call. When the replacement is performed this will lead to an overflow of the allocated buffer. To successfully exploit this the target buffer must be allocated infront of the subject so that the overflow will overwrite the subject, so that copying stops before a crash occurs.
Proof of concept, exploit or instructions to reproduce

To test for this vulnerability just try the following piece of code.

<?php

str_replace("A", str_repeat("B", 65535), str_repeat("A", 65538));

?>

This little POC will only crash PHP. A code execution exploit for this vulnerability will be added to the site in the future. So check back soon.
Notes

The described problem was fixed in PHP 4.4.5 and PHP 5.2.1. However the security fix was broken and therefore PHP 4.4.4 and PHP 5.2.1 are vulnerable to an off by one overflow at the same place. Triggered by the replacement of one char with another char.

The newly released update PHP 4.4.6 fixed the off by one, but there is no such fix for PHP 5.2.1 out yet.