Subject: [secdir] Secdir last call review of draft-faltstrom-base45-10

From: Kyle Rose via Datatracker <[email-masked]>
Date: Mon, 07 Feb 2022 14:26:59 -0800

Reviewer: Kyle Rose
Review result: Has Issues

I have reviewed this document as part of the security directorate's ongoing
effort to review all IETF documents being processed by the IESG.  These
comments were written primarily for the benefit of the security area directors.
 Document editors and WG chairs should treat these comments just like any other
last call comments.

This document has one Issue. Technically, the described protocol is Ready
primarily because it describes an existing encoding standardized in ISO/IEC
18004. That said, I can't really help but ask a few things about this encoding:

* Why 45? (This is probably really a question for the people who designed QR
codes.) 45^3 = 91125 >> 2^16, which means roughly 30% of strings with length
divisible by 3 comprising base45 characters are invalid encodings. * Why is
Space included as a character? This renders the encoding fragile in many string
handling contexts. * Base64 requires padding only to comply with the spec
as-written: a minor modification of the spec (let's call it base64') could lose
the padding and still produce unambiguous encodings of both content and length:
going from 64 to 45 doesn't have anything to do with remedying this. And, by
contrast with base45, 64^4=256^3, which means all strings with length divisible
by 4 comprising base64 characters would be valid base64' encodings.

But the real issue I have with the document (and one that might be technically
unavoidable, depending how ISO/IEC 18004 is worded) is that an actual covert
channel isn't addressed at all: that of the remaining insignificant bits in
encodings of odd-length strings (a problem that would similarly impact base64'
from above for encodings of strings with length mod 3 !≅ 0). Taking the example
from section 4.4, the final chunk ([33 0]) in the example comes from the 16-bit
value 33 (= 33 + 0 * 45). But all that is needed is that 33 ≅ X mod 256 unless
the decoder enforces that encodings of length not divisible by 3 have 16-bit
values < 256. For example, QED8WEJ6 ultimately decodes to the string "ietf!",
or to "ietf!1", or not at all, depending on the behavior of the decoder: ignore
non-zero second octet in odd-length strings (quite likely), render it based on
the available data (unlikely because, if not special-cased, would result in
decoding "ietf!0" in the example from the document), or reject the encoding.
The last option is the only valid thing to do from a security perspective.

Grammar nit: "For example, it MUST the encoded data"

---

From: Robert Sparks <[email-masked]>
Date: Wed, 23 Feb 2022 18:00:31 -0600

Hi Kyle - I read this while working on my Genart review. Some thoughts 
inline.

On 2/7/22 4:26 PM, Kyle Rose via Datatracker wrote:
> divisible by 3 comprising base45 characters are invalid encodings.

If you didn't see the exchange between Carsten et.al. on this point, it 
is compelling.

See https://mailarchive.ietf.org/arch/search/?q=draft-faltstrom-base45

>   * Why is
> handling contexts.
Well, it also requires encoding of buffers that contain nulls, so 
fragility abounds.
> * Base64 requires padding only to comply with the spec
Show your math (or at least reading of the logic in the draft) a bit 
more? It seems dead obvious to me from the draft that any base 45 [c d] 
such that a = c + 45*d > 255 is an invalid encoding. In other words, the 
draft requires the last option. What am I missing?

---

From: Russ Housley <[email-masked]>
Date: Thu, 24 Feb 2022 10:12:33 -0500

> On Feb 23, 2022, at 7:00 PM, Robert Sparks <[email-masked]> wrote:
> 
> Hi Kyle - I read this while working on my Genart review. Some thoughts inline.
> 
> If you didn't see the exchange between Carsten et.al. on this point, it is compelling.
> 
> Well, it also requires encoding of buffers that contain nulls, so fragility abounds.
> Show your math (or at least reading of the logic in the draft) a bit more? It seems dead obvious to me from the draft that any base 45 [c d] such that a = c + 45*d > 255 is an invalid encoding. In other words, the draft requires the last option. What am I missing?

My code throws an error when presented with this example.

Russ

---

From: Kyle Rose <[email-masked]>
Date: Thu, 24 Feb 2022 12:02:07 -0500

> See https://mailarchive.ietf.org/arch/search/?q=draft-faltstrom-base45

Good thread. Given that this encoding is a fait accompli, discussion
of the merits is somewhat moot; that said, it's perhaps useful as a
warning about the questionable level of care put into the design.

> Well, it also requires encoding of buffers that contain nulls, so

"Everything is b0rken, so ¯\_(ツ)_/¯" is not really a good response,
but my point from above also applies here: there's no point in arguing
about it any further. That ship has sailed, the train has left the
station, the horse has left the barn, etc.

> more?

Good catch. Let me show you where I went wrong:

"QED8WEJ6"
[26 14 13 8 32 14 19 6]
[[26 14 13] [8 32 14] [19 6]]
Base45: [ 26981, 29798, 289 ] where:
  26981 = 26+14*45+13*45*45
  29798 = 8 + 32*45 + 14*45*45
  289 = 19 + 6*45
Bytes: [[105 101] [116 102] [1 33]]** where:
  105 = floor(26981 / 256); 101 = 26981 % 256
  116 = floor(29798 / 256); 102 = 29798 % 256
  1 = floor(289 / 256); 33 = 289 % 256

**Note [1 33] rather than [33 1] for the last pair. Which of course
makes this not start with "ietf!", no matter how the decoder behaves.
Apologies for the confusion.

That said, there is still the potential for a limited covert channel
here for some strings. Assume the octet stream you're trying to encode
is of odd length and ends in '\x01' or [1]. The proper encoding of
this is:

Bytes: [1]
Base45: [1]
[[1 0]] where 1 = 1 + 45*0
[1 0]
"10"

What if instead you send "W5"? There's no way to get this string via
proper encoding, but if you decode naively, you get:

"W5"
[32 5]
[[32 5]]
Base45: [ 257 ] where:
  257 = 32 + 5*45
Bytes: [[1 1]] where:
  1 = floor(257/256); 1 = 257 % 256

which is '\x01\x01' if the decoder outputs both bytes, '\x01' if it
outputs only one byte, or results in failure if you do the 257 < 256
check. My point before screwing up the example in my original review
was mainly that simply saying "For decoding a Base45 encoded string
the inverse operations are performed" doesn't, in my judgment,
sufficiently cover this case. FWIW, the decoder I am using properly
rejects "W5", but the issue is not the behavior of any particular
decoding implementation, but rather of making it clear in the
specification that any proper decoder MUST reject such input. I think
the document would be improved by a section explicitly describing
decoding, of which such a check would be a natural part.

Kyle