Subject: [openpgp] [RFC4880bis PATCH] Clarify CRC-24 C example implementation

From: Daniel Kahn Gillmor <[email-masked]>
Date: Wed, 17 Mar 2021 10:55:08 -0400

The mismatch between the variable in the sample CRC-24 generation code
and the definition of the generator in the paragraph above has been a
source of confusion for over 20 years (see [0] for the first instance
I could find in the wild).  It has also been raised as an explicit
erratum [1].

[0] https://mailarchive.ietf.org/arch/msg/openpgp/F29_03_iISnOS7DF0PUH-tVVKsI/

[1] https://www.rfc-editor.org/errata/eid5491

One option would be to change the CRC24_POLY variable in the code to
exactly match the generator described above.  This allows the `crc24`
accumulator to overflow, which on most architectures has has no
practical functional change, because of the masking step at the end of
the function.

However, allowing the `crc24` accumulator to overflow *might* cause a
problem in some obscure architecture, as (a) `crc24` is defined as
"long", which is typically a signed type, and (b) left-shift behavior
is undefined for overflowing signed values (and also for negative
signed values) [2].

[2] http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf § 6.5.7(4)

So allowing the accumulator to overflow in the sample code seems
ill-advised.  This change clarifies both that the accumulator should
be treated as unsigned, and aligns the variable with the textual
description of the generator.

It follows a suggestion first made by Hal Finney 22 years ago [3].

[3] https://mailarchive.ietf.org/arch/msg/openpgp/UMLreIiKtKzXEnPT5ZbcDDjRQX0/
---
 crypto-refresh.md | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)

diff --git a/crypto-refresh.md b/crypto-refresh.md
index 9fbb6eb..9f57a1a 100644
--- a/crypto-refresh.md
+++ b/crypto-refresh.md
@@ -2116,9 +2116,9 @@ The nonzero initialization can detect more errors than a zero initialization.
 ## An Implementation of the CRC-24 in "C"
 
     #define CRC24_INIT 0xB704CEL
-    #define CRC24_POLY 0x1864CFBL
+    #define CRC24_GENERATOR 0x864CFBL
 
-    typedef long crc24;
+    typedef unsigned long crc24;
     crc24 crc_octets(unsigned char *octets, size_t len)
     {
         crc24 crc = CRC24_INIT;
@@ -2128,7 +2128,7 @@ The nonzero initialization can detect more errors than a zero initialization.
             for (i = 0; i < 8; i++) {
                 crc <<= 1;
                 if (crc & 0x1000000)
-                    crc ^= CRC24_POLY;
+                    crc ^= (CRC24_GENERATOR | 0x1000000L);
             }
         }
         return crc & 0xFFFFFFL;
-- 
2.30.2

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Wed, 17 Mar 2021 11:05:14 -0400

On Wed 2021-03-17 10:55:08 -0400, Daniel Kahn Gillmor wrote:
> source of confusion for over 20 years.

I recorded this proposed minor cleanup as MR 39:
https://gitlab.com/openpgp-wg/rfc4880bis/-/merge_requests/39

        --dkg

---

From: Ángel <[email-masked]>
Date: Thu, 18 Mar 2021 02:33:54 +0100

> https://gitlab.com/openpgp-wg/rfc4880bis/-/merge_requests/39

What about using, instead of the 'long' type, which may mean quite
dfferent things, the uint_least32_t type defined in ISO C 7.18 ?

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Wed, 17 Mar 2021 22:54:19 -0400

> dfferent things, the uint_least32_t type defined in ISO C 7.18 ?

i'd be fine with either one.  afaict, "unsigned long" is always at least
at least a 32-bit unsigned integer, and is more typical idiomatic C, but
if the WG prefers uint_least32_t i would not object.  (technically the
CRC-24 accumulator just needs 25 bits -- one to test for overflow -- but
we don't need to cut it so fine :P)

  --dkg

---

From: Werner Koch <[email-masked]>
Date: Thu, 18 Mar 2021 09:49:22 +0100

> if the WG prefers uint_least32_t i would not object.  (technically the

This is a protocol, specification and not an implementation description.
Thus this should be considred as Pseudo code.

Anyway, I am in favor of applying Hal Finney's old suggestion (patch 39,
attached).

Salam-Shalom,

   Werner

-- 
Die Gedanken sind frei.  Ausnahmen regelt ein Bundesgesetz.
From 998f55481cd4101eefe45350ded408dbfdd16438 Mon Sep 17 00:00:00 2001
From: Daniel Kahn Gillmor <[email-masked]>
Date: Wed, 17 Mar 2021 09:54:16 -0400
Subject: [PATCH] Clarify CRC-24 C example implementation
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

 
 
-    typedef long crc24;
GitLab

---

From: "brian m. carlson" <[email-masked]>
Date: Thu, 18 Mar 2021 22:38:41 +0000

> dfferent things, the uint_least32_t type defined in ISO C 7.18 ?

My preference here is uint32_t, since as a practical matter all modern
architectures offer that and implement it reasonably efficiently, and it
is much more commonly used.  More recent languages like Rust and Go just
assume everyone has such a type, and in the unlikely event someone uses
a system that doesn't have it, they'll clearly know how to adjust.

However, I'm also fine with uint_least32_t or unsigned long.  The
important thing is that we produce something that is (a) correct so that
it produces the right results, (b) conformant so that compilers don't
break it in the name of better optimizations during undefined behavior,
and (c) as simple and easy to understand as possible.  Any option which
meets those requirements is satisfactory to me.
-- 
brian m. carlson (he/him or they/them)
Houston, Texas, US

---

From: Ángel <[email-masked]>
Date: Fri, 19 Mar 2021 00:08:02 +0100

> (technically the CRC-24 accumulator just needs 25 bits -- one to test
> for overflow -- but we don't need to cut it so fine :P)

I don't think you would find many platforms with a uint_least25_t type. ;-)
I generally prefer explicit sizes when the number of bits matter, but
you are right: a long is more idiomatic. I don't mind either way.

On 2021-03-18 at 09:49 +0100, Werner Koch wrote:
> Anyway, I am in favor of applying Hal Finney's old suggestion (patch
> 39, attached).

As the goal is to provide clear code, that ORed 0x1000000 may still be
a bit surprising (albeit less than when it was included in the
constant). I think it would be clearer to use

                   if (crc & 0x1000000) {
                       crc = (crc ^ CRC24_POLY) & 0xffffff;
                   }

or, following more closely hal's second suggestion:
                   if (crc & 0x1000000) {
                       crc &= 0xffffff; /* Clear bit 25 to avoid overflow */
                       crc ^= CRC24_POLY;
                   }

Best regards

---

From: Ángel <[email-masked]>
Date: Fri, 19 Mar 2021 00:19:15 +0100

Looking at the Radix-64 section, I noticed the phrase
> The checksum with its leading equal sign MAY appear on the first line
> after the base64 encoded data.

I understand it is that way to convey that the checksum may not appear
at all, but it would be better to explicitly say so.

diff --git a/crypto-refresh.md b/crypto-refresh.md
index 9fbb6eb..bb9635b 100644
--- a/crypto-refresh.md
+++ b/crypto-refresh.md
@@ -2100,7 +2100,7 @@ As stated in the introduction, OpenPGP's underlying native representation for ob
 In principle, any printable encoding scheme that met the requirements of the unsafe channel would suffice, since it would 
not change the underlying binary bit streams of the native OpenPGP data structures.
 The OpenPGP standard specifies one such printable encoding scheme to ensure interoperability.
 
-OpenPGP's Radix-64 encoding is composed of two parts: a base64 encoding of the binary data and a checksum.
+OpenPGP's Radix-64 encoding is composed of two parts: a base64 encoding of the binary data and an optional checksum.
 The base64 encoding is identical to the MIME base64 content-transfer-encoding {{RFC2045}}.
 
 The checksum is a 24-bit Cyclic Redundancy Check (CRC) converted to four characters of radix-64 encoding by the same MIME 
base64 transformation, preceded by an equal sign (=).
@@ -2108,7 +2108,7 @@ The CRC is computed by using the generator 0x864CFB and an initialization of 0xB
 The accumulation is done on the data before it is converted to radix-64, rather than on the converted data.
 A sample implementation of this algorithm is in the next section.
 
-The checksum with its leading equal sign MAY appear on the first line after the base64 encoded data.
+If present, the checksum with its leading equal sign SHALL appear on the next line after the base64 encoded data.
 
 Rationale for CRC-24: The size of 24 bits fits evenly into printable base64.
 The nonzero initialization can detect more errors than a zero initialization.

---

From: Werner Koch <[email-masked]>
Date: Fri, 19 Mar 2021 07:54:56 +0100

On Fri, 19 Mar 2021 00:19, Ángel said:

> -OpenPGP's Radix-64 encoding is composed of two parts: a base64
> encoding of the binary data and a checksum.
> +OpenPGP's Radix-64 encoding is composed of two parts: a base64
> encoding of the binary data and an optional checksum.

> +If present, the checksum with its leading equal sign SHALL appear on
> the next line after the base64 encoded data.

Adding "optional" and making the CRC a SHOULD create indeed clarifies
the intention of the RFC.  Thus I am in favor of this change.

Shalom-Salam,

   Werner

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Fri, 19 Mar 2021 13:24:11 -0400

>                        crc &= 0xffffff; /* Clear bit 25 to avoid overflow */

fwiw, i'm fine with either of these.  I note that the change i'd
originally proposed renamed the constant to CRC24_GENERATOR, to align it
with the term in the text ("poly" doesn't appear anywhere in the text,
but "generator" does).

That said, we are pretty clearly in bike-shedding territory here.

I have heard no one advocate for leaving the text unchanged, and i have
heard no one advocate for just silently amending the code to drop bit 25
from the constant.

All of the other variants proposed in this thread seem to have people
expressing various degrees of mild preference, so long as:

 - bit 25 should be cleared during accumulation
 - the accumulator type is explicitly and clearly unsigned
 - the variable definition matches the constant in the text

i observe that the first two points are mutually redundant -- when the
accumulator is unsigned, then overflow doesn't hit undefined behavior,
if i'm reading the C spec correctly.  But it still seems cleaner and
easier to understand if the sample code includes both belt and
suspenders.

<chair hat on>
I think the editors should pick one particular color of bike shed that
satisfies the conditions above and include it in the next revision.
If a member of the WG strongly objects to the revision, we can have more
discussion, but otherwise, i think the WG should focus on more pressing
topics.
</chair hat off>

        --dkg

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Fri, 19 Mar 2021 17:39:58 -0400

>  The nonzero initialization can detect more errors than a zero initialization.

As an implementer and a maintainer, I am in favor of this change.  I
think it makes the draft more accurately represent the state of the
ecosystem, where i suspect implementations are willing to accomodate
an absent CRCs.

As a chair, I note that this does seem to subtly change the semantics of
the document, and therefore I think we need to hear from more people in
the WG about whether this seems correct.  Thanks to Werner for already
weighing in on this.

The other way is to have hard data about what implementations are
willing to accept.  I've opened
https://gitlab.com/sequoia-pgp/openpgp-interoperability-test-suite/-/issues/42
to suggest that the interoperability test suite should have a batch of
consumer tests that demonstrate which implementations can handle a
missing CRC.

If folks are interested in helping out with the test suite, this might
be a relatively easy way to make a contribution.

   --dkg

---

From: Ángel <[email-masked]>
Date: Sat, 20 Mar 2021 03:01:37 +0100

On 2021-03-19 at 13:24 -0400, Daniel Kahn Gillmor wrote:
> originally proposed renamed the constant to CRC24_GENERATOR, to align
> it with the term in the text ("poly" doesn't appear anywhere in the
> text, but "generator" does).

Right. I began from Hal's mail [1] Particularly the second option is
his code just adding the comment. Thus I didn't want to add another
change with the constant rename (something I'm fine with).

Another potential point is if 0xffffff should have been changed to
0xffffffUL, as we are also changing the type to unsigned, but it looks
redundant.

> heard no one advocate for just silently amending the code to drop bit 25

Indeed. Even if discussing which wording might be (slightly) better,
let me explicitly state my support, in that I think all proposed
changes on this thread represent an improvement over the existing text.

Best regards

1- 
https://mailarchive.ietf.org/arch/msg/openpgp/UMLreIiKtKzXEnPT5ZbcDDjRQX0/

---

From: Ángel <[email-masked]>
Date: Thu, 25 Mar 2021 01:07:06 +0100

> the intention of the RFC.  Thus I am in favor of this change.

Note I wasn't placing the later. I only stated that you can only place
the checksum at the end.
I was planning to treat this as a feature request and add a phrase with
such SHOULD, since I agree it's a good idea, but turns out I can't come
out with a better rationale than “it's cheap enough it makes sense to
do it even if not giving much value”.

What is the goal of the armor CRC?
The only good use case I can think of is when a human has been
involved, such as when restoring a key from paper.

On other scenarios, the CRC would either be too weak (e.g. in presence
of an active attacker) or protecting from an error that would already
have been handled at lower layers.
[1] and [2] suggest it was added to avoid modem line noise altering the
messages (which nowadays should be discarded at e.g. TCP).

Without a compelling use case, I don't think it should be a SHOULD.
And finally, we should at least mention why it was once considered
useful.

The original change is available in git mode at
https://gitlab.com/Angel-Gonzalez/rfc4880bis/-/tree/checksum-may-appear

Best regards

1- https://mailarchive.ietf.org/arch/msg/openpgp/3K6tSdebEjQw8K1z1pZkXxyvu-k/
2- https://mailarchive.ietf.org/arch/msg/openpgp/2FmAqP-nJkV08E1qQ4YNO2xR2Pc/