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.

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.

polsofol

The C++ library written by polsofol 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 Polsofol 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 Polsofol 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

product source fixed version notes
upstream library Github ?  
Shift Cryptosecurity BitBox01 Github v7.0.4 via patch  
open62541 Github patch unbase64() unreachable in default runtime settings
Neonius open62541 fork Github ? see open62541
Qunar QChat IOS Github unclear developers: “unbase64 is never used”
keygen.sh example code Github ?  
Couchbase Labs example code Github patch  
picobounce Github patch  
Open License Manager Github ? no reaction
clandmark Github ? no reaction

Relevant products for polfosol library

product source fixed version notes
upstream library Github ?  
open62541 Github v.1.0.1 via patches unbase64() path unreachable in default settings
ntop libebpfflow Github unclear, 1, 2  
polycube Github ?  
painlessMesh Gitlab, Github ? no reaction
blinker-iot Github ? no reaction, see painlessMesh
openexrid Github ? no reaction

References:

NibbleAndAHalf timeline

Date info
2019-10-20 Disclosure to Shift Cryptosecurity
2019-10-21 Additional info sent to Shift Cryptosecurity
2019-10-22 Additional info sent to Shift Cryptosecurity
2019-10-22 Shift Cryptosecurity acknowledges the report
2019-10-31 Shift Cryptosecurity agrees to contacting library author William Sherif
2019-11-03 Initial contact with William Sherif
2019-11-04 Acknowledgement from Neonius
2019-11-05 Initial contact with open62541 developers
2019-11-06 Feedback from Qunar
2019-11-07 Phone conference with open62541 developers
2019-11-07 Attempt to reach Open License Manager developer
2019-11-07 Feedback from picobounce developer
2019-11-08 Attempt to contact clandmark developer
2019-11-19 Phone conference with Shift Cryptosecurity
2019-11-21 Acknowledgement from keygen.sh
2019-11-24 Acknowledgement from Couchbase Labs
2019-11-25 Fix for Couchbase Labs
2019-12-29 In-person discussion with Shift Cryptosecurity developer
2020-01-16 BitBox01 fix firmware v.7.0.4 is released

Polsofol timeline

Date info
2019-11-05 Initial contact with open62541 developers
2019-11-07 Phone conference with open62541 developers
2019-11-07 Attempt to contact polsofol
2019-11-19 Attempt to contact polycube developers
2019-11-21 Initial contact with polycube
2019-11-21 Attempt to contact painlessMesh developer
2019-11-21 Attempt to contact blinker-iot developer
2019-11-21 Attempt to contact openexrid developers

Bug bounty

Shift Cryptosecurity has announced that they will provide a bug bounty for this issue.