Botan Library: Heap Overflow Bug In `botan_mp_to_hex`

Introduction

In the realm of cryptographic libraries, security and reliability are paramount. Recently, a potential heap overflow vulnerability was identified in the widely-used Botan cryptographic library, specifically within the botan_mp_to_hex function. This article delves into the details of this bug, its implications, and potential solutions, offering insights for developers and users of Botan.

Understanding the Bug: A Deep Dive into botan_mp_to_hex

The botan_mp_to_hex function in Botan is designed to convert a multiple precision integer (MPI) into its hexadecimal string representation. According to the documentation, this function should write exactly botan_mp_num_bytes(mp)*2 + 1 bytes to the output buffer. However, the actual implementation prepends 0x and appends a null byte, leading to a write of botan_mp_num_bytes(mp)*2 + 3 bytes in most cases. This discrepancy is also reflected in the Python binding code, which allocates memory based on this incorrect calculation.

Further analysis reveals two critical edge cases that exacerbate the issue:

1. Negative Numbers: When converting negative numbers, an additional - byte is prepended, increasing the required buffer size to num_bytes*2 + 4.
2. Zero Value: The number 0 is reported to have a size of 0 bytes via botan_mp_num_bytes, but the botan_mp_to_hex function will produce 0x00, which requires 5 bytes including the null terminator.

These edge cases highlight a significant vulnerability: if the allocated buffer is not large enough to accommodate these extra bytes, a heap overflow occurs. A heap overflow can lead to a variety of security issues, including denial of service, arbitrary code execution, and information disclosure. This makes it crucial to address this bug promptly.

Proof of Concept: Demonstrating the Heap Overflow

A proof-of-concept (POC) test case was developed to demonstrate this vulnerability. The test case, written in C++, utilizes the Botan library to convert a negative integer (-0x1234) to its hexadecimal representation. The test case allocates a buffer based on the size calculation used in the Python bindings (nb * 2 + 3), which is insufficient for negative numbers. This leads to a heap overflow when botan_mp_to_hex attempts to write the hexadecimal string to the buffer.

#include <vector>
#include <cstdio>
extern "C" {
#include "/fuzz/install/include/botan-3/botan/ffi.h"
}
int main(){
 botan_mp_t mp = nullptr;
 if(botan_mp_init(&mp) != 0 || mp == nullptr) return 0;
 botan_mp_set_from_int(mp, -0x1234);

 size_t nb = 0;
 if(botan_mp_num_bytes(mp, &nb) != 0) return 0;
 printf("nb: %zu\n", nb);
 size_t out_sz = nb * 2 + 3; // using the requirement specified in Python bindings

 std::vector<char> out(out_sz); // allocates 1 byte
 (void)botan_mp_to_hex(mp, out.data()); // writes 2 bytes ("0" + NUL) -> overflow

 return 0;
}

When compiled and executed, the test case triggers a heap-buffer-overflow error, as reported by AddressSanitizer (ASan). The ASan output clearly shows that the write operation exceeds the allocated buffer size, confirming the vulnerability.

nb: 2
=================================================================
==1==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x502000000037 at pc 0x557371450bb4 bp 0x7fff1b5dc410 sp 0x7fff1b5dbbd0
WRITE of size 8 at 0x502000000037 thread T0
 #0 0x557371450bb3 in __asan_memcpy (/fuzz/test+0xd1bb3) (BuildId: b6590d45e51c2f84fec88160be4c12dc0a98cc85)
 #1 0x5573714959a4 in botan_mp_to_hex (/fuzz/test+0x1169a4) (BuildId: b6590d45e51c2f84fec88160be4c12dc0a98cc85)
 #2 0x557371491af8 in main /fuzz/testcase.cpp:17:9
 #3 0x7f8b6e0b0d8f in __libc_start_call_main csu/../sysdeps/nptl/libc_start_call_main.h:58:16
 #4 0x7f8b6e0b0e3f in __libc_start_main csu/../csu/libc-start.c:392:3
 #5 0x5573713b66d4 in _start (/fuzz/test+0x376d4) (BuildId: b6590d45e51c2f84fec88160be4c12dc0a98cc85)

0x502000000037 is located 0 bytes after 7-byte region [0x502000000030,0x502000000037)
allocated by thread T0 here:
 #0 0x55737148f4ed in operator new(unsigned long) (/fuzz/test+0x1104ed) (BuildId: b6590d45e51c2f84fec88160be4c12dc0a98cc85)
 #1 0x557371492770 in __gnu_cxx::new_allocator<char>::allocate(unsigned long, void const*) /usr/bin/../lib/gcc/x86_64-linux-gnu/11/../../../../include/c++/11/ext/new_allocator.h:127:27
 #2 0x557371492700 in std::allocator_traits<std::allocator<char>>::allocate(std::allocator<char>&, unsigned long) /usr/bin/../lib/gcc/x86_64-linux-gnu/11/../../../../include/c++/11/bits/alloc_traits.h:464:20
 #3 0x5573714926bf in std::_Vector_base<char, std::allocator<char>>::_M_allocate(unsigned long) /usr/bin/../lib/gcc/x86_64-linux-gnu/11/../../../../include/c++/11/bits/stl_vector.h:346:20
 #4 0x5573714924e0 in std::_Vector_base<char, std::allocator<char>>::_M_create_storage(unsigned long) /usr/bin/../lib/gcc/x86_64-linux-gnu/11/../../../../include/c++/11/bits/stl_vector.h:361:33
 #5 0x557371491fe1 in std::_Vector_base<char, std::allocator<char>>::_Vector_base(unsigned long, std::allocator<char> const&) /usr/bin/../lib/gcc/x86_64-linux-gnu/11/../../../../include/c++/11/bits/stl_vector.h:305:9
 #6 0x557371491d08 in std::vector<char, std::allocator<char>>::vector(unsigned long, std::allocator<char> const&) /usr/bin/../lib/gcc/x86_64-linux-gnu/11/../../../../include/c++/11/bits/stl_vector.h:511:9
 #7 0x557371491aa4 in main /fuzz/testcase.cpp:16:21
 #8 0x7f8b6e0b0d8f in __libc_start_call_main csu/../sysdeps/nptl/libc_start_call_main.h:58:16

SUMMARY: AddressSanitizer: heap-buffer-overflow (/fuzz/test+0xd1bb3) (BuildId: b6590d45e51c2f84fec88160be4c12dc0a98cc85) in __asan_memcpy
Shadow bytes around the buggy address:
 0x501ffffffd80: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
 0x501ffffffe00: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
 0x501ffffffe80: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
 0x501fffffff00: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
 0x501fffffff80: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
=>0x502000000000: fa fa 00 fa fa fa[07]fa fa fa fd fa fa fa fa fa
 0x502000000080: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
 0x502000000100: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
 0x502000000180: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
 0x502000000200: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
 0x502000000280: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
Shadow byte legend (one shadow byte represents 8 application bytes):
 Addressable: 00
 Partially addressable: 01 02 03 04 05 06 07
 Heap left redzone: fa
 Freed heap region: fd
 Stack left redzone: f1
 Stack mid redzone: f2
 Stack right redzone: f3
 Stack after return: f5
 Stack use after scope: f8
 Global redzone: f9
 Global init order: f6
 Poisoned by user: f7
 Container overflow: fc
 Array cookie: ac
 Intra object redzone: bb
 ASan internal: fe
 Left alloca redzone: ca
 Right alloca redzone: cb
==1==ABORTING

Proposed Solutions

To address this heap overflow vulnerability, two primary solutions have been suggested:

Option 1: Introducing botan_mp_hex_size

This approach involves creating a dedicated function, botan_mp_hex_size, that accurately calculates the size required for the hexadecimal string representation of an MPI. The botan_mp_to_hex function would then be documented as writing exactly botan_mp_hex_size(mp) bytes. This is the most precise solution, as it ensures that the allocated buffer is always the correct size.

Option 2: Documenting a Safe Threshold

Alternatively, the documentation for botan_mp_to_hex could be updated to state that the function writes up to botan_mp_num_bytes(mb)*2+5 bytes. This threshold is considered safe as it accounts for the extra characters added for negative numbers, the 0x prefix, and the null terminator. While this approach is less precise than Option 1, it provides a practical and straightforward solution.

Impact and Mitigation

The heap overflow vulnerability in botan_mp_to_hex has the potential to impact applications that use Botan for cryptographic operations. Specifically, applications that rely on the documented size calculation (botan_mp_num_bytes(mp)*2 + 1) or the Python binding's calculation (botan_mp_num_bytes(mp)*2 + 3) may be vulnerable.

To mitigate this risk, developers should ensure that they allocate sufficient buffer space when using botan_mp_to_hex. Until a patch is released, the safer approach is to allocate botan_mp_num_bytes(mb)*2+5 bytes, as suggested in Option 2. Alternatively, developers can implement their own size calculation based on the edge cases described above.

Conclusion

The identification of this heap overflow vulnerability in botan_mp_to_hex underscores the importance of rigorous testing and code review in cryptographic libraries. While Botan is a well-regarded library, this incident highlights that even mature codebases can contain subtle bugs. By understanding the nature of this vulnerability and implementing the proposed solutions, developers can ensure the security and reliability of their applications.

This bug was discovered by an autonomous fuzzing system STITCH, demonstrating the power of fuzzing in uncovering potential security vulnerabilities. For more information on heap overflows and their impact, you can visit the OWASP website.