The Base64 Encoder Has A Fixed Point

Francisco Mota, 06 Feb 2013

Yesterday, the following tweet showed up on my stream, with no explanation.

Curious about my suddenly mysterious friend, and his mysterious message -- at least, I assumed there was a message -- I tried a few things and failed to solve his riddle.

But eventually I got it. I opened up Python, and typed this:

>>> import base64

>>> s = 'Vm0wd2QyUXlVWGxWV0d4V1YwZDRWMVl3WkRSV01Wb

>>> base64.b64decode(s)

>>> base64.b64encode(s)

This is interesting. When you run s through a base64 encoder, you get s ... and a bit more. We can even go further:

>>> base64.b64encode(_)

>>> base64.b64encode(_)

>>> base64.b64encode(_)

Every time we encode, we get the same string back with a few changes at the end1. This isn't on purpose, this is a purely accidental consequence of base64's design. There was never any point where the designer of base64 decided "Let there be a long string s that is a prefix to its own representation in base64!"

Better yet, we can start from a different string, and encode it in base64 repeatedly, and we'll get closer and closer to s above:

>>> base64.b64encode('lol')

>>> base64.b64encode(_)

>>> base64.b64encode(_)

>>> base64.b64encode(_)

>>> base64.b64encode(_)

>>> base64.b64encode(_)

>>> base64.b64encode(_)

>>> base64.b64encode(_)

>>> base64.b64encode(_)

>>> base64.b64encode(_)

>>> base64.b64encode(_)

At this point, the first 8 characters are exactly like s, and there is a lot of similarity in the rest. If we keep going, the number of matching characters goes up.

It seems we have found a fixed point. A fixed point of a function $f$ is some value $x$ such that $x = f(x).$ If we repeat the base64 encoding process over and over again, starting at any point, we get closer and closer to the fixed point of base64, which is some infinite string that begins with s.

It didn't have to be like this. There are many, many encodings without a fixed point. There are encodings where the idea of a fixed point doesn't even make sense, such as an encoding from one data type to a different data type. So why does base64 appear to have a fixed point?

To answer this question, let us look at the design of base64. At its most high-level, base64 has two phases:

  1. It takes a sequence of bytes (that is, digits in base 256), and interprets them as a sequence of digits in base 64, using four digits for every three bytes.

  2. It encodes the base 64 digits as a sequence of bytes, using one byte for every digit.

To explain the first phase, you need 8 bits to represent a byte, but a digit in base 64 only represents 6 bits. So in phase 1, base64 looks at 3 bytes at a time, and maps them to 4 corresponding base 64 digits. 3 bytes = 24 bits = 4 digits.

Then in the second phase, base64 makes these digits human readable. In doing so, it represents the 6 bit digits as 8 bit bytes, which is fine, if a little wasteful. So what was originally three bytes in the input becomes four bytes in the output.

In more formal notation, we have a mapping $\mathrm{base64} : [ 256 ]^* \to [ 256 ]^*$ which is actually just a map $\mathrm{phase1} : [ 256 ]^3 \to [ 64 ]^4$ that is applied on all 3-character pieces of the string, followed by a map $\mathrm{phase2} : [ 64 ] \to [ 256 ]$ that is applied to all of the digits.

For the ensuing discussion, we'll call the 3 character prefix of a string its head.

Let us look at what happens to the head of any string that is repeatedly encoded. We'll call the string $s$. There are $256^3$ possible heads for $s$.

Now we encode it, and we have another string $s'$, which has about 33% more characters than $s$. However, there are only $64^3$ possible heads for $s'$, because of the translation that is being done between base 64 and base 256. To be precise, the head of $s'$ lost 6 bits of information contained in the head of $s$ -- those bits can be found in the fourth character of $s'$.

We encode it again, this time forming $s''$. Regardless of the details of $\mathrm{phase1}$ and $\mathrm{phase2}$, I can guarantee that the head of $s''$ has lost at least 4 bits of information that were still in the head of $s'$. That is, the head of $s''$ has lost 10 bits of information compared to the head of $s$.

We could keep going, getting into the nitty gritty about how the bits of information are lost gradually, by looking at the transformation of the characters one by one. But I'm going to stop right there and give you the big picture.

What matters is that the number of possible prefixes of $s$ decreases as you repeatedly encode it. This means that as strings are repeatedly encoded, their prefixes become more and more similar. Over time, the prefixes of all strings converge onto prefixes of the fixed point.

The take-away here is that base64 is an eventually contracting map, and therefore must have a fixed point2. An eventually contracting map is a function that brings two values closer to each other on repeated application3. Every eventually contracting map over a complete metric space has a unique fixed point.

This is related to principle of metric coinduction [Kozen, Ruozzi, 2009], which states that any property that is preserved on an eventually contracting map must be true about its fixed point, if it is true anywhere in the space. In this case, we are using metric coinduction to construct the fixed point of base64. That's how we know its prefixes, because the prefixes are preserved over base64.

So what was p4bl0's original message?

I think it was something like "Look! Base64 preserves this prefix!"

EDIT 07 Feb 2013: In a fantastic comment, redditor moor-GAYZ shows how base64's fixed point is much more coincidental than my handwavey "bit loss" explanation implies. In particular, rearranging the digit table of the base64 encoding results in encodings with zero, one, two, or three fixed points. See moor-GAYZ's code and table here. So the existence of a unique fixed point is dependent on the details of $\mathrm{phase1}$ and $\mathrm{phase2}$.

  1. And about 33% more characters each time.

  2. This is more or less true. It shows that base64 has a fixed point if it worked on a complete metric space. The space of finite strings is not a complete metric space, but if we allow infinite strings of characters (streams), then base64 definitely has a fixed point.

  3. A contracting map is a function that brings two values closer to each other immediately, without requiring repeated application.