Base64 parser issues in multiple projects

This article describes a number of memory safety issues in two base64 decoding and encoding libraries. I found these issues during fuzzing research of the Shift Cryptosecurity BitBox01 and during the resulting disclosure process.

In the second half of the article, I outline general recommendations to developers and describe some challenging aspects of the disclosure process.

Consulting

I’m a freelance Security Consultant and currently available for new projects. If you are looking for assistance to secure your projects or organization, contact me.

Technical background

The well-known base64 binary-to-text encoding scheme is used in many places where data has to be transported over interfaces that were not designed for the full binary “character” range. One example is SSH public key data which is suitable for copy operations into forms and text files.

In the case of the BitBox01, the communication packets with the device are transported in base64 encoded format as payload data of the U2F protocol. The device then has to perform base64 decoding on attacker-controlled data that is received via USB.

The NibbleAndAHalf base64 library is both small (self-contained .h file), written in pure C and among the fastest libraries (see this post and benchmark from 2016), which made it interesting for a number of C projects.

The vulnerabilities in NibbleAndAHalf

During the base64 decode operation, the printable base64 input sequence has to be translated back into the original binary data. However, not all base64 inputs are valid, for example due to missing padding with = characters, and so the decoding function has to reject those to prevent false results or problematic memory behavior.

For the unbase64 function, the initial part of the code looks like this:

unsigned char* unbase64( const char* ascii, int len, int *flen )
{
  const unsigned char *safeAsciiPtr = (const unsigned char*)ascii ;
  unsigned char *bin ;
  int cb=0;
  int charNo;
  int pad = 0 ;

  if( len < 2 ) { // 2 accesses below would be OOB.
    // catch empty string, return NULL as result.
    puts( "ERROR: You passed an invalid base64 string (too short). You get NULL back." ) ;
    *flen=0;
    return 0 ;
  }
  if( safeAsciiPtr[ len-1 ]=='=' )  ++pad ;
  if( safeAsciiPtr[ len-2 ]=='=' )  ++pad ;

base64.h

Basically, the code only rejects the len < 2 case. This is insufficient since there are input sequences with len >= 2 that are invalid.

After this check, the library computes the required size of the output buffer and tries to allocate it:

  *flen = 3*len/4 - pad ;
  bin = (unsigned char*)malloc( *flen ) ;
  if( !bin )
  {
    puts( "ERROR: unbase64 could not allocate enough memory." ) ;
    puts( "I must stop because I could not get enough" ) ;
    return 0;
  }

base64.h

The bin pointer is checked against NULL as a failure condition, otherwise the program continues.

Due to the insufficient input validation explained previously, this code has a number of problems, which are described in the next sections.

Malloc() issues

Consider the base64 input sequence == which leads to:

• len is 2
• pad is 2

The output buffer length is then computed as -1 via *flen = 3*len/4 - pad, which is clearly not a meaningful size. Since malloc() takes the length as an unsigned int (size_t), this -1 is translated to the largest size_t value via an unsigned integer overflow. The code issues a very large memory request for ~18 Exabyte of data:

==4634==ERROR: AddressSanitizer: requested allocation size 0xffffffffffffffff [...]
 exceeds maximum supported size of 0x10000000000

In theory, this could cause a denial of service depending on the malloc implementation. I have seen no crashes in practice and assume most implementations reject this.

Similarly, consider the base64 input sequence a= which leads to:

• len is 2
• pad is 1

The output buffer length is then computed as 0 via *flen = 3*len/4 - pad, so the code is requesting 0 bytes of data via malloc(0). Contrary to what one expects, malloc actually serves a valid return pointer to an 1-byte memory region for this request (at least under x86_64) and the if( !bin ) exception does not trigger, which means the program continues to operate on this data.

Generally speaking, invalid base64 sequences of a certain length let the program allocate the wrong output buffer size.

Out of bounds reads + writes

Due to the previously described validation and memory allocation issues, many of the implicit assumptions of the base64 parsing steps regarding the valid memory positions do not hold.

Read example:

==4935==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x602000000272 [...]
READ of size 1 at 0x602000000272 thread T0

This is caused by

int C=unb64[safeAsciiPtr[charNo+2]];

base64.h

Write example:

==5047==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x602000001311 [...]
WRITE of size 1 at 0x602000001311 thread T0

This is caused by

bin[cb++] = (B<<4) | (C>>2) ;

base64.h

To an attacker, the out of bounds writes are likely more interesting since they have the potential to change some program flow somewhere depending on the adjacent memory on the heap. The out of bounds reads may disclose memory contents (which can also be serious for a hardware wallet), but the leaked data needs to be processed and returned by the device in some way for the attacker to read it, which does not appear to be the case here.

As far as I can see, the memory writes are local and target the bytes directly behind the allocated buffer on the heap.

Fix

Shift Cryptosecurity has used the following fix that performs stricter input validation by adding a length check, which is simpler than expected:

-    if ( len < 2 ) { // 2 accesses below would be OOB.
+    if ((len <= 0) || (len % 4 != 0)) { // 2 accesses below would be OOB.

base64.c

I received no information about this fix prior to the public patch in January 2020. (Also, I don’t vouch for this patch, but so far holds up to fuzzing)

Existing countermeasures and mitigating factors

As far as I’m aware, none of the “regular” low-level error detection mechanisms on the microcontroller or desktop system are helping here.

On the BitBox01, triggering the parsing issues increments an error counter that locks the device after ~15 attempts unless it is reset with valid communication (that requires the PIN). Depending on the attack scenario, this limits the attacker to about a dozen malformed base64 packets.

Vulnerabilities in other base64 libraries

During the disclosure process, I looked briefly at other self-contained base64 library implementations.

polfosol

The C++ library written by polfosol also does not correctly validate the base64 data before processing, which leads to memory issues in at least three code positions:

runtime error: addition of unsigned offset to 0x602000000070 overflowed to 0x60200000006f
==5454==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x60200000006f [...]
READ of size 1 at [...]

This is caused by

pad2 = pad1 && (len % 4 > 2 || p[len - 2] != '=');

base64.hh

==5749==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x602000003e55 [...]
READ of size 1 at 0x602000003e55 thread T0

This is caused by

int n = B64index[p[last]] << 18 | B64index[p[last + 1]] << 12;

base64.hh

==5554==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x6020000002b2 [...]
READ of size 1 at 0x6020000002b2 thread T0

This is caused by

str[j] = n >> 8 | B64index[p[last + 2]] >> 2;

base64.hh

Wikibooks.org

This C implementation decoder does appear to contain errors as well:

runtime error: index -33 out of bounds for type 'const unsigned char [256]'

This happens at unsigned char c = d[*in++];

Recommendation for developers

• writing secure parsers in C is hard, even for experienced developers
• assume that unless a parser was extensively fuzzed or audited, it is not safe when exposed to arbitrary inputs
• if your product relies on parsing external input (USB, network), it’s your obligation to make the processing safe
• age, popularity and speed of a third party component is not an indication for its security status
• list a dedicated security contact email address with PGP key in your README.md or SECURITY.md for confidential reports
• think in advance about how you can receive news of library updates from the upstream source
• if in doubt, ask the upstream project for their maintenance status / security goals / ..
• if you find issues in third party components, inform at least the upstream author(s)

Coordinated disclosure

The disclosure process for this topic was complex, time consuming and overall not very satisfying.

Main disclosure

I found and responsibly disclosed the NibbleAndAHalf issue to Shift Cryptosecurity in October 2019.

Since the issue was located in third-party parsing code (similar to the bech32 issue), I began looking for other open source projects that could be affected. After checking with Shift Cryptosecurity, I reached out to the NibbleAndAHalf library author William Sherif and notified him of the issue.
Unfortunately, he indicated that

• the library is only meant for educational purposes
• security issues are out of scope of his maintenance
• he has no time to look into the issue or assist with issue coordination

Therefore, I continued to inform the relevant projects independently.

One of the first projects I contacted was the open62541 project, an open source C implementation of a complex “industry 4.0” communication system. Unlike most other projects, it was actively fuzzed through Google oss-fuzz and had already switched away from the NibbleAndAHalf library to the Polfosol library after detecting unspecified issues. After speaking with the open62541 developers I learned that the library memory issues were already publicly documented via oss-fuzz (1, 2, 3) since August 2019.

On bug severity assessments

Over the disclosure process, Shift Cryptosecurity was sending mixed signals with regards to the importance of this issue for their BitBox01 and the internal priority of a fix, at times stating that this was not a security issue. In the end, they released a patched firmware after ~89 days via version 7.0.4.

Their well-written blog post (published during the disclosure) presents their security assessment strategy and relevant considerations in detail. This is certainly a good step for a vendor but was of limited practical use on the researcher side since they only communicated the relevant assessments ~2 months into the disclosure process after most of the effort was done (see the timeline).

Their essential calculation Severity = impact * scalability clearly depends heavily on the individual assessment of the impact and scalability ratings.

1. The issue had the highest scalability classification in their system as a remote attack on a locked device, which they acknowledged in November. Scalability is closely linked with the attack vector - in this case, the affected component is always exposed on an USB interface level and reachable via software. This technical situation is easy to agree on.

2. However, giving a fair and balanced assessment of the impact rating can be quite difficult. If obvious negative effects can be shown on the device, the case is clear. But how to rate memory corruption cases that depend on complex factors (here: contents of the heap) and where no exploit is known at the moment, but practical issues have not been ruled out either?

Proving that a specific local security problem will not - under any circumstances - cause larger issues is hard, particularly if a number of factors like different memory layouts, undefined behavior or additional security issues are involved.

Shift Cryptosecurity acknowledge this general problem in their blog post, referencing my previous disclosure with them about information disclosure via U2F:

Since many vulnerabilities have aspects that make them “special” as highlighted by the questions in the previous section, we reserve the right to deviate from these rules in our bug bounty program at our sole discretion. Furthermore, it is often not clear what the impact of a potential vulnerability is, especially in the case of memory issues such as leaking some bytes.

In my opinion, it is not the sole responsibility of the security researcher to invest time into the lengthy impact assessment of a memory corruption issue. This is important since the analysis can take dozens of hours without any guarantee of a result.

If the practical impact of a weakness is difficult to determine for both the vendor and researcher, the estimated impact rating should be a compromise between the plausible and the demonstrated impact, not the lowest impact (-> no security consequence). Similarly, CVEs are often extended with “or possibly execute arbitrary code” and given higher CVSS scores where it is appropriate.

Also, while it is very beneficial to have well-defined high-level security goals (seed exposure, loss of funds, …), the integrity and confidentiality of the device memory are clearly low-level goals that also need to hold as necessary preconditions for this.

This topic is particularly frustrating since issue severity is the only factor for Shift Cryptosecurity’s bug bounty valuation. In this particular case, they decided on a low bounty valuation (possibly the lowest tier in this issue class).

To be fair, there were a number of complicating factors involved during this disclosure: other product launches of their company, end-of-sales for the BitBox01, other high-profile security disclosures, staff changes, […]. However, none of this was under my influence. Overall, after my second disclosure to them, I still think that they can improve in terms of transparency towards researchers for their security assessments as well as for their planned bug bounties during the disclosure phase.

Polfosol library disclosure

Due to open62541’s usage, I began looking into the Polfosol library in November 2019 and quickly found memory issues as well (as previously described).

Unfortunately, the open62541 developers immediately made the issues public (via a PR) only a few hours after I notified them. This interfered with a regular coordinated disclosure process. As they explained in a phone conference on the next day, the standard runtime configuration of their project did not expose the issue, but they didn’t think of other projects - for which they’ve apologized.

Although I’ve contacted a number of projects, few have decided to patch their library issues and some have not replied at all after ~2 months.

Product overview

Relevant products for NibbleAndAHalf library

Relevant products for polfosol library

References:

• libFuzzer harness via open62541
  
  

NibbleAndAHalf timeline

Polfosol timeline

Bug bounty

Shift Cryptosecurity has provided a bug bounty for this issue in May 2020.