How can I fix mismatched base64 encodings of ids between systems when there is padding

user_1248889 0
Viewed 18

My app communicates with a third-party service that uses base64 encoding on their identifiers. I want to replicate their identifier encoding scheme to communicate with their system, but I'm getting mismatched identifies when the string has to be padded.

Our system is built on php. Using php's base64_encode() on a string that ends with '2~' that needs to be padded results in 'Mn4='. However, their system instead results in 'Mn5'. Both of these string are parsed by php's base64_decode() back into '2~'. I understand that some systems strip the trailing = but the 4 turns into a 5 as well.

In order to figure it out, I tried manually to convert the string to base64, based on wikipedia's Base64 examples:

  • First, convert the characters into octals:
    • '2~' would become 00110010 01111110
  • Now take those and convert group into sextets:
    • It would become 001100 100111 1110.
  • "When the last input group contains only two octets, all 16 bits will be captured in the first three Base64 digits (18 bits); the two least significant bits of the last content-bearing 6-bit block will turn out to be zero, and discarded on decoding"
    • It would become 001100 100111 111000
  • Then convert into ascii using the Base64 table
    • It would become M n 4
  • Then add the zero padding with =
    • It would become Mn4=

So where did the 5 come from? The 111000 sextet would have to be 111001 instead. Those bits are discarded on decode, which normally isn't a problem, but since they are storing/using the base64 as identifiers, this is causing mismatches in my system.

Is there any known implementation that does right padding with non-zeros? I didn't see any listed on Wikipedia's variant list. Can I replicate this behavior in php without rewriting base64_encode in php from scratch?

base64
1 Answers

I never figured out what system they were using. Perhaps they are rolling their own base64_encode. But I did figure out how to convert the standard to a non-standard padding.

In the case that base64 needs to pad 1 character, the last sextet comprises of the lower nibble of the last character, and a two bit padding:

const base64chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
const padChar = '=';
function padOne(lastChar) {
    const lowerNibble = lastChar.charCodeAt(0) & 0b1111;
    const padding = 0b00;
    const sextet = lowerNibble << 2 | padding;
    return base64chars[sextet] + padChar;
}

padOne('~'); // '4='

This creates a repeating padding for the ascii table. The padding will end with: AEIMQUYcgkosw048 followed by =. We can implement padTwo by changing the lowerNibble to half a nibble (a crumb?), and doubling the padding size. This pattern is similar to the first, but only consists of AQgw plus two equal signs: ==

To see the results I'm seeing, change the padding from 0b00 to 0b01 and the padChar to empty string. Then the pattern shifts to: BFJNRVZdhlptx159. After scanning my DB of their identifiers, I confirmed all their base64 padding uses 0b01 instead. Strangely enough, their two pad uses 0b0000, so that remains unaltered, other than dropping the ==.

So, to convert from standard-padding to non-standard padding, we can use the string translate function in php:

function base64_encode_nonstandard_padding(string $toEncode): string {
    return strtr(base64_encode($toEncode), [
        // One Pad
        'A=' => 'B', 'E=' => 'F', 'I=' => 'J', 'M=' => 'N',
        'Q=' => 'R', 'U=' => 'V', 'Y=' => 'Z', 'c=' => 'd',
        'g=' => 'h', 'k=' => 'l', 'o=' => 'p', 's=' => 't',
        'w=' => 'x', '0=' => '1', '4=' => '5', '8=' => '9',

        // Two pad
        'A==' => 'A', 'Q==' => 'Q', 'g==' => 'g', 'w==' => 'w'
    ]);
}
user_12488890
Related