Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Base-122 – A space efficient alternative to base-64

blog.kevinalbs.com

Post reply on HN
Print view View original

11–20 of 71 posts

Re: Base-122 – A space efficient alternative to base-64

#11

Post by dom0 »

theoh wrote: post #6
CiPHPerCoder wrote: post #4

My problem with base-122 is simply that it's not an even power of 2. It's very easy to write a cache-timing-safe version of base{16,32,64} encoding for use in encoding/decoding cryptographic keys in configuration files. To wit: https://github.com/paragonie/constant_time_encoding Base-122? Not sure if it's even possible.

A number system can have any natural number as radix, so why not? https://en.m.wikipedia.org/wiki/Radix From the posted article: "This leaves us with 122 legal one-byte UTF-8 characters to use" Seems legit to me.

> It's very easy to write a cache-timing-safe version of base{16,32,64} encoding ...

> Base-122? Not sure if it's even possible.

Parent is clearly referring to his previous statement, not that Base-122 itself is not possible.

Re: Base-122 – A space efficient alternative to base-64

#12

Post by krschultz »

sikosmurf wrote: post #10
zihotki wrote: post #3

tldr, no revolution, base64+gzip still far better than base122+gzip. But the article worth reading.

Aren't there security concerns using gzip and HTTPS? Could this be a space efficient alternative when gzip is disabled?

I would be interested to learn more about those concerns. My "default" setup these days is HTTPS & gzip everything, but I can't say I've read any white papers on the security implications of that.

Re: Base-122 – A space efficient alternative to base-64

#13

Post by theoh »

dom0 wrote: post #11
theoh wrote: post #6

Earlier quoted context omitted.

A number system can have any natural number as radix, so why not? https://en.m.wikipedia.org/wiki/Radix From the posted article: "This leaves us with 122 legal one-byte UTF-8 characters to use" Seems legit to me.

> It's very easy to write a cache-timing-safe version of base{16,32,64} encoding ... > Base-122? Not sure if it's even possible. Parent is clearly referring to his previous statement, not that Base-122 itself is not possible.

Not obvious to me at all.

Re: Base-122 – A space efficient alternative to base-64

#14

Post by beagle3 »

deckar01 wrote: post #7
CiPHPerCoder wrote: post #4

My problem with base-122 is simply that it's not an even power of 2. It's very easy to write a cache-timing-safe version of base{16,32,64} encoding for use in encoding/decoding cryptographic keys in configuration files. To wit: https://github.com/paragonie/constant_time_encoding Base-122? Not sure if it's even possible.

I think you are focusing on the wrong number. Each byte of base64 produces 6 bits of data, so the boundary aligns at 32 bits. LCM(6,8) = (6•8)/2 Each byte of base122 produces 7 bits of data, so the byte boundary aligns at 56 bits. LCM(7,8) = (7•8)/1 Edit: Due to the variable length encoding, there is no guarantee of byte alignment.

If it was base 128 it Would have produced 7 bits. But as it is 122 it produces 6.8 bits, hence a problem.

Re: Base-122 – A space efficient alternative to base-64

#15

Post by zrm »

krschultz wrote: post #12
sikosmurf wrote: post #10

Earlier quoted context omitted.

Aren't there security concerns using gzip and HTTPS? Could this be a space efficient alternative when gzip is disabled?

I would be interested to learn more about those concerns. My "default" setup these days is HTTPS & gzip everything, but I can't say I've read any white papers on the security implications of that.

If the attacker knows or controls any part of the data then the compressed size leaks information about the unknown data because the compressed size will be smaller if the known data shares bytes with the unknown data.

Re: Base-122 – A space efficient alternative to base-64

#17

Post by deckar01 »

beagle3 wrote: post #14
deckar01 wrote: post #7

Earlier quoted context omitted.

I think you are focusing on the wrong number. Each byte of base64 produces 6 bits of data, so the boundary aligns at 32 bits. LCM(6,8) = (6•8)/2 Each byte of base122 produces 7 bits of data, so the byte boundary aligns at 56 bits. LCM(7,8) = (7•8)/1 Edit: Due to the variable length encoding, there is no guarantee of byte alignment.

If it was base 128 it Would have produced 7 bits. But as it is 122 it produces 6.8 bits, hence a problem.

> This uses one-byte characters encode seven bits and two-byte characters to encode fourteen bits. Hence this attains the goal of encoding seven bits per byte, i.e. the 8 : 7 inflation ratio.

The magic is in the 2 byte encoding 110sss1x 10xxxxxx.

There are really 890 characters used in this encoding, so it should be called base890.

((2^7)-6)+((6•2)•(2^6))=890

Re: Base-122 – A space efficient alternative to base-64

#18

Post by bunderbunder »

NelsonMinar wrote: post #9
poizan42 wrote: post #5

A lot of people have experimented with a lot of different ways of encoding binary data as printable text. Wikipedia has a list of different encoding schemes[0]. The most efficient one is yEnc[1]. Still the simplest ones such as base64 or good old hex may actually work better once compression comes into the picture. [0]: https://en.wikipedia.org/wiki/Binary-to-text_encoding [1]: https://en.wikipedia.org/wiki/YEnc

It's crucial to evaluate encoding space usage in the context of compression. For instance gzip(base16(data)) is often smaller than gzip(base64(data)) for practical data. Even though base64 is more efficient than base16, it breaks up data across byte boundaries which then makes gzip significantly less efficient.

When would you gzip encoded data instead of encoding gzipped data? Doesn't gzip after encoding defeat the whole idea of encoding the data in a format that won't get mangled by systems that expect to be handling text?

Re: Base-122 – A space efficient alternative to base-64

#19

Post by [deleted] »

bunderbunder wrote: post #18
NelsonMinar wrote: post #9

Earlier quoted context omitted.

It's crucial to evaluate encoding space usage in the context of compression. For instance gzip(base16(data)) is often smaller than gzip(base64(data)) for practical data. Even though base64 is more efficient than base16, it breaks up data across byte boundaries which then makes gzip significantly less efficient.

When would you gzip encoded data instead of encoding gzipped data? Doesn't gzip after encoding defeat the whole idea of encoding the data in a format that won't get mangled by systems that expect to be handling text?

[deleted]

Re: Base-122 – A space efficient alternative to base-64

#20

Post by dleslie »

bunderbunder wrote: post #18
NelsonMinar wrote: post #9

Earlier quoted context omitted.

It's crucial to evaluate encoding space usage in the context of compression. For instance gzip(base16(data)) is often smaller than gzip(base64(data)) for practical data. Even though base64 is more efficient than base16, it breaks up data across byte boundaries which then makes gzip significantly less efficient.

When would you gzip encoded data instead of encoding gzipped data? Doesn't gzip after encoding defeat the whole idea of encoding the data in a format that won't get mangled by systems that expect to be handling text?

When serving gzip-compressed pages to browsers that support it.
Post reply on HN