RFC 9285

The Base45 Data Encoding

📅 published August 2022, from ietf

RFC 9285: The Base45 Data Encoding ✨

okay bestie, this one is RFC 9285, called The Base45 Data Encoding 🦋 It's an Informational doc (so not a Standards Track spec 🙈), published in August 2022, with ISSN 2070-1721. The authors are P. Fältström from Netnod, F. Ljunggren from Kirei, and D.W. van Gulik from Webweaving 💜 It's an IETF product that went through public review and got approved by the IESG 🌸

Abstract

Base45 is an encoding scheme that's built on top of Base64, Base32, and Base16 🍓

Status of This Memo

This doc is not an Internet Standards Track spec. It's just published for informational purposes 💅

It's an IETF product and represents the consensus of the IETF community. It went through public review and got the okay from the Internet Engineering Steering Group (IESG). Not every IESG-approved doc is a candidate for any level of Internet Standard, so see Section 2 of RFC 7841 for that 👑

You can find the current status, any errata, and how to send feedback at https://www.rfc-editor.org/info/rfc9285.

Copyright (c) 2022 IETF Trust and the persons identified as the document authors. All rights reserved 🎀

This doc is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info), as they were in effect on the publication date. Please actually read them, because they explain your rights and restrictions for this doc 🫶 Any Code Components pulled out of this doc have to include Revised BSD License text, as described in Section 4.e of the Trust Legal Provisions. They also come with no warranty, as described in the Revised BSD License 😭

Table of Contents

  • 1. Introduction
  • 2. Conventions Used in This Document
  • 3. Interpretation of Encoded Data
  • 4. The Base45 Encoding
    • 4.1. When to Use and Not Use Base45
    • 4.2. The Alphabet Used in Base45
    • 4.3. Encoding Examples
    • 4.4. Decoding Example
  • 5. IANA Considerations
  • 6. Security Considerations
  • 7. Normative References
  • Acknowledgements
  • Authors' Addresses

1. Introduction ✨

okay so a QR code is how we store text as a little picture 📱 There are a bunch of ways to encode the text in a QR code, like Numeric, Alphanumeric, and Byte mode. Even in Byte mode, though, a typical QR reader assumes the bytes are text in UTF-8 or ISO/IEC 8859-1. So QR codes can't just hold arbitrary binary data directly 💀 That data has to be turned into text first, and then that text gets encoded as a QR code.

Base64, Base32, and Base16 already exist and are described in [RFC4648]. Compared to those, Base45 gives you a more compact QR code encoding, which is a whole mood 🔥

One big difference between Base45 and those others is the key table. Also, the padding with '=' isn't required 🌈

2. Conventions Used in This Document 💜

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" are to be read as described in BCP 14 [RFC2119] [RFC8174], but only when they show up in all capitals, like they do here 🧚

3. Interpretation of Encoded Data 🎀

Encoded data gets interpreted the way [RFC4648] describes, with one exception: a different alphabet is selected 🦋

4. The Base45 Encoding 🌸

QR codes can only store so much binary data. In practice, you have to encode binary data as characters using one of the modes that's already defined for QR codes 👑 The easiest mode to use is Alphanumeric mode (see Section 7.3.4 and Table 2 of [ISO18004]. Unfortunately, Alphanumeric mode uses 45 different characters, which means neither Base32 nor Base64 is a super effective encoding here 😭

Base45 uses a 45-character subset of US-ASCII: the 45 characters you can use in a QR code in Alphanumeric mode (see Section 7.3.4 and Table 2 of [ISO18004]). It encodes 2 bytes in 3 characters, while Base64 encodes 3 bytes in 4 characters 🍓

Let's do the math, bestie 🤓 For encoding, two bytes [a, b] MUST be read as a number n in base 256. That means an unsigned 16-bit integer, where n = (a * 256) + b.

That number n gets converted to base 45 [c, d, e], so that n = c + (d * 45) + (e * 45 * 45). Notice the order of c, d and e: they're picked so that the left-most [c] is the least significant one 🙈

Then c, d, and e get looked up in Table 1 to make a three-character string. Decoding just reverses the whole process ✨

For encoding a single byte [a], it MUST be read as a base 256 number, which is an unsigned 8-bit integer. That integer MUST be converted to base 45 [c d], so that a = c + (45 * d). Then c and d get looked up in Table 1 to make a two-character string 💅

A byte string [a b c d ... x y z] with any content and any length MUST be encoded like this: going from left to right, pairs of bytes MUST be encoded the way described above. If the number of bytes is even, the encoded form is a string whose length is evenly divisible by 3. If the number of bytes is odd, the last (rightmost) byte MUST be encoded on two characters, the way described above 🌈

To decode a Base45 string, you do the inverse operations ⭐

4.1. When to Use and Not Use Base45 🦋

If you're storing binary data in a QR code, the suggested move is Alphanumeric mode, which uses 11 bits for 2 characters, as defined in Section 7.3.4 of [ISO18004]. The Extended Channel Interpretation (ECI) mode indicator for this encoding is 0010 🎀

On the other hand, if the data is going over some other transport, you should use a transport encoding that fits that transport instead of Base45 🫶 For example, it's not recommended to encode data in Base45 first and then encode that resulting string in Base64 if you're sending it by email. Instead, you should drop the Base45 encoding and encode the data itself in Base64 💖

4.2. The Alphabet Used in Base45 💜

Alphanumeric mode is defined to use the 45 characters in this alphabet 🧚

+=====+==========+=====+==========+=====+==========+=====+==========+
|Value| Encoding |Value| Encoding |Value| Encoding |Value| Encoding |
+=====+==========+=====+==========+=====+==========+=====+==========+
|   00| 0        |   12| C        |   24| O        |   36| Space    |
+-----+----------+-----+----------+-----+----------+-----+----------+
|   01| 1        |   13| D        |   25| P        |   37| $        |
+-----+----------+-----+----------+-----+----------+-----+----------+
|   02| 2        |   14| E        |   26| Q        |   38| %        |
+-----+----------+-----+----------+-----+----------+-----+----------+
|   03| 3        |   15| F        |   27| R        |   39| *        |
+-----+----------+-----+----------+-----+----------+-----+----------+
|   04| 4        |   16| G        |   28| S        |   40| +        |
+-----+----------+-----+----------+-----+----------+-----+----------+
|   05| 5        |   17| H        |   29| T        |   41| -        |
+-----+----------+-----+----------+-----+----------+-----+----------+
|   06| 6        |   18| I        |   30| U        |   42| .        |
+-----+----------+-----+----------+-----+----------+-----+----------+
|   07| 7        |   19| J        |   31| V        |   43| /        |
+-----+----------+-----+----------+-----+----------+-----+----------+
|   08| 8        |   20| K        |   32| W        |   44| :        |
+-----+----------+-----+----------+-----+----------+-----+----------+
|   09| 9        |   21| L        |   33| X        |     |          |
+-----+----------+-----+----------+-----+----------+-----+----------+
|   10| A        |   22| M        |   34| Y        |     |          |
+-----+----------+-----+----------+-----+----------+-----+----------+
|   11| B        |   23| N        |   35| Z        |     |          |
+-----+----------+-----+----------+-----+----------+-----+----------+

                     Table 1: The Base45 Alphabet

4.3. Encoding Examples 🎀

Okay bestie, even though all these examples look like normal text, Base45 is really an encoding for binary data, where each octet can be any value from 0-255 💅

Encoding example 1:

The string "AB" is the byte sequence [[65 66]]. If we look at all 16 bits, we get 65 * 256 + 66 = 16706. That equals 11 + (11 * 45) + (8 * 45 * 45), so the sequence in base 45 is [11 11 8]. Referring to Table 1, we get the encoded string "BB8" 🦋

+-----------+------------------+
| AB        | Initial string   |
+-----------+------------------+
| [[65 66]] | Decimal value    |
+-----------+------------------+
| [16706]   | Value in base 16 |
+-----------+------------------+
| [11 11 8] | Value in base 45 |
+-----------+------------------+
| BB8       | Encoded string   |
+-----------+------------------+

Table 2: Example 1 in Detail

Encoding example 2:

The string "Hello!!" as ASCII is the byte sequence [[72 101] [108 108] [111 33] [33]]. If we look at this 16 bits at a time, we get [18533 27756 28449 33]. Note the 33 for the last byte. When we look at the values in base 45, we get [[38 6 9] [36 31 13] [9 2 14] [33 0]], where the last byte is represented by two values. The resulting string "%69 VD92EX0" is created by looking up these values in Table 1. Worth noting, it includes a space 🌸

+---------------------------------------+------------------+
| Hello!!                               | Initial string   |
+---------------------------------------+------------------+
| [[72 101] [108 108] [111 33] [33]]    | Decimal value    |
+---------------------------------------+------------------+
| [18533 27756 28449 33]                | Value in base 16 |
+---------------------------------------+------------------+
| [[38 6 9] [36 31 13] [9 2 14] [33 0]] | Value in base 45 |
+---------------------------------------+------------------+
| %69 VD92EX0                           | Encoded string   |
+---------------------------------------+------------------+

Table 3: Example 2 in Detail

Encoding example 3:

The string "base-45" as ASCII is the byte sequence [[98 97] [115 101] [45 52] [53]]. If we look at this two bytes at a time, we get [25185 29541 11572 53]. Note the 53 for the last byte. When we look at the values in base 45, we get [[30 19 12] [21 26 14] [7 32 5] [8 1]], where the last byte is represented by two values. Referring to Table 1, we get the encoded string "UJCLQE7W581" ✨

+----------------------------------------+------------------+
| base-45                                | Initial string   |
+----------------------------------------+------------------+
| [[98 97] [115 101] [45 52] [53]]       | Decimal value    |
+----------------------------------------+------------------+
| [25185 29541 11572 53]                 | Value in base 16 |
+----------------------------------------+------------------+
| [[30 19 12] [21 26 14] [7 32 5] [8 1]] | Value in base 45 |
+----------------------------------------+------------------+
| UJCLQE7W581                            | Encoded string   |
+----------------------------------------+------------------+

Table 4: Example 3 in Detail

4.4. Decoding Example 🔁

Decoding example 1:

The string "QED8WEX0" represents, when looked up in Table 1, the values [26 14 13 8 32 14 33 0]. We arrange the numbers in chunks of three, except for the last one which can be two numbers, and get [[26 14 13] [8 32 14] [33 0]]. In base 45, we get [26981 29798 33], where the bytes are [[105 101] [116 102] [33]]. If we look at the ASCII values, we get the string "ietf!" 👑

+-------------------------------+------------------------+
| QED8WEX0                      | Initial string         |
+-------------------------------+------------------------+
| [26 14 13 8 32 14 33 0]       | Looked up values       |
+-------------------------------+------------------------+
| [[26 14 13] [8 32 14] [33 0]] | Groups of three        |
+-------------------------------+------------------------+
| [26981 29798 33]              | Interpreted as base 45 |
+-------------------------------+------------------------+
| [[105 101] [116 102] [33]]    | Values in base 8       |
+-------------------------------+------------------------+
| ietf!                         | Decoded string         |
+-------------------------------+------------------------+

Table 5: Example 4 in Detail

5. IANA Considerations 🌈

Good news, no IANA chores here 🙌 This document has no IANA actions.

6. Security Considerations 💀

Okay, this section is super important, so pay attention 😭 When implementing encoding and decoding, you have to be very careful so that buffer overflow or similar issues do not occur. That of course includes the calculations in base 45 and the lookup in the table of characters (Table 1). A decoder must also be robust regarding input, including proper handling of any octet value 0-255, including the NUL character (ASCII 0).

Base64 and some other encodings pad the string so the encoding starts with an aligned number of characters, while Base45 specifically avoids padding. Because of this, special care has to be taken when an odd number of octets is to be encoded. Similarly, care must be taken if the number of characters to decode is not evenly divisible by 3.

Base encodings use a specific, reduced alphabet to encode binary data. Non-alphabet characters could exist within base-encoded data, caused by data corruption or by design. Non-alphabet characters can be exploited as a "covert channel", where non-protocol data is sent for nefarious purposes. Non-alphabet characters might also be sent in order to exploit implementation errors leading to, for example, buffer overflow attacks.

Implementations MUST reject any input that is not a valid encoding. For example, it MUST reject the input (encoded data) if it contains characters outside the base alphabet (in Table 1) when interpreting base-encoded data.

Even though a Base45-encoded string contains only characters from the alphabet in Table 1, cases like the following have to be considered. The string "FGW" represents 65535 (FFFF in base 16), which is a valid encoding of 16 bits. A slightly different encoded string of the same length, "GGW", would represent 65536 (10000 in base 16), which is represented by more than 16 bits. Implementations MUST also reject the encoded data if it contains a triplet of characters that, when decoded, results in an unsigned integer that is greater than 65535 (FFFF in base 16).

It's worth noting that the resulting string after encoding to Base45 might include non-URL-safe characters. So if the URL including the Base45-encoded data has to be URL-safe, you have to use percent-encoding 🔗

7. Normative References 📚

Acknowledgements 🫶

The authors thank Mark Adler, Anders Ahl, Alan Barrett, Sam Spens Clason, Alfred Fiedler, Tomas Harreveld, Erik Hellman, Joakim Jardenberg, Michael Joost, Erik Kline, Christian Landgren, Anders Lowinger, Mans Nilsson, Jakob Schlyter, Peter Teufl, and Gaby Whitehead for the feedback. Also, everyone who has been working with Base64 over a long period of years and has proven the implementations are stable 💖

Authors' Addresses 💌

  • Patrik Fältström, Netnod, Email: paf@netnod.se
  • Fredrik Ljunggren, Kirei, Email: fredrik@kirei.se
  • Dirk-Willem van Gulik, Webweaving, Email: dirkx@webweaving.org
📦 where this page comes from