The Base45 Data Encoding • Hacker News Board

Re: The Base45 Data Encoding

#41

Post by Nursie » Fri, Jun 25, 2021, 10:56 AM UTC

lawl wrote: post #26

radicalbyte wrote: post #5

A nice tidbit: this RFC has its roots in the EU Covid Certificate project. The encoding was designed to cut the size of the QR payload (which for DCC is a CBOR - binary encoded - object) :) The smaller the payload, the better and faster the scanning. Which is important for something that is designed to be used during border crossings and the like. We have a number of implementations here: https://github.com/ehn-dcc-d…

Interesting. The swiss system, which is supposedly compatible with the EU uses JSON + base64 [0]. Seems we also use RSA, and from a quick glance the EU seems to take any x509 certificate authority [1]. Does anyone know if there is a reason elliptic curves weren't been mandated, which should cause smaller signatures than RSA and thus a smaller payload? [0] https://github.com/admin-ch/CovidCertificate-Apidoc/#respons..…

>> Does anyone know if there is a reason elliptic curves weren't been mandated

Support still patchy ?

I work in this area (certificates mostly) and find issues every so often with various platforms having gaps in their EC stuff. That said most things can now deal with the base subset and sticking to (say) P-256 would probably be pretty trouble-free. Getting europe-wide agreement on this would likely be hard though, and european standards[0] often have stuff in that's not widely supported, like FRP256v1, which doesn't seem to be in openssl yet, or wasn't last time I looked, let alone more obscure or outdated implementations.

[0] - e.g. https://www.etsi.org/deliver/etsi_ts/119300_119399/119312/01...

Re: The Base45 Data Encoding

#42

Post by upofadown » Fri, Jun 25, 2021, 11:23 AM UTC

Why would this be a RFC? It seems quite specific to QR codes. Nothing specific to the Internet.

Re: The Base45 Data Encoding

#43

Post by lifthrasiir » Fri, Jun 25, 2021, 11:28 AM UTC

mr_mitm wrote: post #40

kristov wrote: post #37

Earlier quoted context omitted.

Having these chars is a pain (particularly space). Manipulating lists of these in files with standard Unix tools will mean having to escape, quote, etc.

I don't understand why they didn't use lower case letters instead of special characters. Does anyone here know?

You can't put lowercase letters in the alphanumeric mode (5.5 bits per character) and need to switch to less efficient byte mode (8 bits per character).

Re: The Base45 Data Encoding

#44

Post by jalk » Fri, Jun 25, 2021, 11:52 AM UTC

lifthrasiir wrote: post #28

pulse7 wrote: post #25

Earlier quoted context omitted.

One could take 10 digits, 26 letters and 5 operands (+ - * / %) for Base41 encoding. 41 * 41 * 41 = 68921 is enough for 2 bytes (65536 combinatons).

/ and % don't play well with URLs. I would take + - * . $ instead.

'+' doesn't play well with URLs

Re: The Base45 Data Encoding

#45

Post by sixothree » Fri, Jun 25, 2021, 11:52 AM UTC

zaxomi wrote: post #32

eventreduce1 wrote: post #3

What are the benefits to base58? Base45 uses chars like backslash. This is super annoying when the encoded string is used in an url.

slash = / backslash = \ They are using slash. And space, which is confusing. Did not see the space in the "Hello!!" example since the space is the last character on the line.

Trailing spaces too?

Re: The Base45 Data Encoding

#46

Post by lifthrasiir » Fri, Jun 25, 2021, 1:41 PM UTC

jalk wrote: post #44

lifthrasiir wrote: post #28

Earlier quoted context omitted.

/ and % don't play well with URLs. I would take + - * . $ instead.

'+' doesn't play well with URLs

Less so than %, for example. It is classified as a sub-delim subset of reserved characters [1], meaning that they won't conflict with the generic URI components syntax and thus are reasonably safe. (* and $ are also included in this set.) You might be worrying that it gets "converted" into %2B but this conversion is not required and fully reversible.

[1] https://datatracker.ietf.org/doc/html/rfc3986#section-2.2

Re: The Base45 Data Encoding

#47

Post by kstenerud » Fri, Jun 25, 2021, 1:45 PM UTC

codeflo wrote: post #9

So instead of extending QR codes, which are inherently binary, to efficiently handle binary payloads, we invent yet another ASCII-based tunneling scheme. Why ever fix any problem when we can just pile workaround upon workaround upon workaround?

Unfortunately, the QR code "binary" mode specification defaults to ISO 8859-1 for the encoding (because it was not originally intended to store actual binary data), and there's also no way to indicate what format is actually encoded. So all decoders of course just assume ISO 8859-1 because they have no way of knowing otherwise.

However, we could in theory get around this by using binary data formats that always begin with an invalid text character (0x80-0x9f). This way, an implementation can know that the data is not ISO 8859-1, and try to decode whatever format it discovers through the beginning byte signature.

I've actually put this into Concise Encoding [1]

[1] https://github.com/kstenerud/concise-encoding/blob/master/cb...

Re: The Base45 Data Encoding

#48

Post by kstenerud » Fri, Jun 25, 2021, 1:48 PM UTC

Unfortunately, the QR code "binary" mode specification defaults to ISO 8859-1 for the encoding (because it was not originally intended to store actual binary data), and there's also no way to indicate what format is actually encoded. So all decoders of course just assume ISO 8859-1 because they have no way of knowing otherwise.

However, we could in theory get around this by using binary data formats that always begin with an invalid text character (such as 0x80-0x9f). This way, an implementation can know that the data is not ISO 8859-1, and try to decode whatever format it discovers through the beginning byte signature.

I've actually put this into Concise Encoding [1]

[1] https://github.com/kstenerud/concise-encoding/blob/master/cb...

Re: The Base45 Data Encoding

#49

Post by thehappypm » Fri, Jun 25, 2021, 6:02 PM UTC

radicalbyte wrote: post #5

A nice tidbit: this RFC has its roots in the EU Covid Certificate project. The encoding was designed to cut the size of the QR payload (which for DCC is a CBOR - binary encoded - object) :) The smaller the payload, the better and faster the scanning. Which is important for something that is designed to be used during border crossings and the like. We have a number of implementations here: https://github.com/ehn-dcc-d…

Honestly feels like premature/unnecessary optimization.

Re: The Base45 Data Encoding

#50

Post by mjevans » Sat, Jun 26, 2021, 1:35 AM UTC

lifthrasiir wrote: post #36

mjevans wrote: post #34

Earlier quoted context omitted.

32 bits raw 33 bits (3 pairs of 11 bits) QR alphanum. In blocks of 4 bytes this encodes as 6 'base45' (QR alphanum) characters, and uses the same lookup table. https://en.wikipedia.org/wiki/QR_code#Encoding The "Alphanumeric character codes" table, at least at a visual glance, is identical to the RFC's lookup table.

The GP is saying that the equal efficiency is possible with using only 41 out of 45 characters, so reducing the symbol set would make base45 (now base41) more useful as a general encoding, not just an encoding for QR codes.

That's a fair point that wasn't made clearly enough. I have two questions though:

1) Is it worth no longer sharing the same lookup table? My supposition is that this wouldn't practically matter in the modern bloated environment anyway, but it's still annoying and might be a source of additional bugs.

2) Which 4 characters would be skipped for what reason?

I'd initially propose not including: non-printing character space (b45[36]), possible variable wildcard dollar-sign (also a currency symbol that might get translated) (b45[37]), html escape and database wildcard percent (b45[38]), then typical wildcard asterisk (star) (b45[39]). Thus the sequence string would be.

b41 = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ+-./:";