Subject: Re: [openpgp] Possible ambiguity in description of regular expressions: [^][]

From: Daniel Kahn Gillmor <[email-masked]>
Date: Tue, 05 Jan 2021 10:33:30 -0500

On Sun 2020-12-27 11:57:32 +0100, Neal H. Walfield wrote:
> We need to exclude [^] as well.

good catch!

> Perhaps:
>
> +A range is a non-empty sequence of characters excluding the optional
> leading ^ enclosed in '[]'.

This seems like pretty confusing wording to me, because i can't tell how
to connect "non-empty" with "excluding" and "optional".  Maybe a
concrete example of what we're trying to fix would also help?  something
like:

    In particular, '[]' and '[^]' are not valid ranges.

I'd be happy if folks can exchange wordsmithing ideas on the list here.

But beyond the wordsmithing, if anyone thinks that Neal's interpretation
(or my proposed clarification) is actually wrong or problematic, please
speak up!

      --dkg

---

From: Andrew Gallagher <[email-masked]>
Date: Tue, 5 Jan 2021 17:11:36 +0000

> (or my proposed clarification) is actually wrong or problematic, please

The original proposed change: "A range is a non-empty sequence of 
characters enclosed in []" is clear and (mostly) effective, so IMO 
should be adopted despite the fact that it is insufficient in itself.

Now, consider the remaining corner cases:

[]]	: matches a closing square bracket
[^]]	: matches anything other than a closing square bracket
[[]	: matches an opening square bracket
[^[]	: matches anything other than an opening square bracket
[][]	: matches either square bracket
[^][]	: matches anything other than either square bracket
[^]	: is an incorrectly nested sequence

To tackle the insufficiency, I propose an additional change:

-If the sequence begins with '^', it matches any single character not 
from the rest of the sequence.
+If the sequence begins with '^', it matches any single character not 
from the rest of the sequence, which must then contain at least one 
further character following the '^'.

When read alongside "To include a literal ']' in the sequence, make it 
the first character (following a possible '^')", this should be 
sufficient to cover all corner cases.

(I considered "... the rest of the sequence, which must be non-empty", 
but it is unclear whether "which" refers to "the sequence" or "the rest 
of the sequence")

However...

We should probably also explicitly note how to negate the special 
meaning of '^':

+To include a literal '^', locate it somewhere other than the first 
character of the sequence.

Now, this doesn't cover the (contrived) case where we may want to use a 
literal '^' as the beginning of an ASCII range:

[^-~]

But if absolutely necessary, one could refactor:

[_-~^]

While we're at it, we should also clarify range inclusivity:

-this is shorthand for the full list of ASCII characters between them
+this is shorthand for them and the full list of ASCII characters 
between them

Also, many regex engines support backslash-escaping within a character 
class. Does RFC4880 support this or not? My reading is that it doesn't, 
but it may be worth explicitly clarifying this also (even though 
backslash escaping would be a more elegant solution to [^-~]).

Is there anything to be said for referring out to an external regex 
definition instead of reinventing the wheel? :-)

-- 
Andrew Gallagher

---

From: Ángel <[email-masked]>
Date: Fri, 08 Jan 2021 01:29:36 +0100

> definition instead of reinventing the wheel? :-)

The problem is that there is not a single regex specification. Although
it would be beneficial to be able to change the regex definition in
some minor ways.

On this same topic, I had started the following reply last weekend:

On 2020-12-23 at 22:58 +0100, Neal H. Walfield wrote:
> Wait... that can also be parsed as match anything (2) followed by
> match nothing (1)!
> 
> 
> Perhaps I'm misreading the standard.  I'd appreciate confirmation or
> any help clarifying my mistake.
> 
> Thanks,
> 
> :) Neal

I think it's kinda implicit in the 
> To include a literal ']' in the sequence, make it the first character
> (following a possible '^').

that a range cannot be "[]" or "[^]" since it is specified that in such
case the "]" will be a literal character.

The place-]-at-the-start (along make-'-'-first-or-last) is a well-known 
trick when using old regex flavors which don't support escapes inside
ranges. I would say the whole section makes sense. But there's room for
improvement.

A trickier case would be a regular expression such as:
> Werner Koch (dist.*

This could be taken as a valid regular expression, with the "(" «a
single character with no other significance (matching that character)»,
or a syntax error, since parentheses are 'special' per «An atom is a
regular expression in parentheses». Exactly the same case applies to
"[foo". Although rfc 4880 makes no reference to invalid regular
expressions, I think that's how these should be categorised (another
example would be a regular expression beginning with a quantifier).*

And since the usage of regular expressions is for trust signatures
packets, 5.2.3.15 should probably state that a regular expression that
is invalid, or the implementation cannot support for whatever reason
e.g. implementations _will_ place a recursion limit), then trust MUST
NOT be extended.

There's a second definition of the Regular Expressions, which is
> The regular expression uses the same syntax as the Henry Spencer's
> "almost public domain" regular expression [REGEX] package.

with
>    [REGEX]          Jeffrey Friedl, "Mastering Regular Expressions,"
>                     O'Reilly, ISBN 0-596-00289-0.

However, someone which turned to that book will find that the latest
edition (14.5 years old 3rd edition, from August 2006), which is the
one readily available, does not describe Henry Spencer regex flavor. It
mentions it as historically relevant, and that Perl 2 used an enhanced
version of that, but it is not described by itself nor included in the
tables comparing different flavors (I guess more details about it might
have been removed in the rewrite that went into the second version).

It is possible to dig out the original code[1] and actually test how it
performs (spoiler: it does reject the above constructs), but one should
not need to rely on how that code works.

If I had to define the message now from new, I would probably define it
as being a POSIX Extended Regular Expressions (ERE)[2] (or a subset of
that). Those are relatively similar to the existing definition, are
well-known and well-defined, and such definition would allow to simply
use existing libraries conforming to that one (including regexec on
a POSIX  libc). An openpgp client shouldn't really need to care much
about creating a regular expression engine. It is a complex part for
the tiny usage it would get.
In fact, the easier way to implement it would probably be to barely
parse the 4880 regex to convert it into an ERE, and then use an
existing facility to execute that.

The main differences are:

Curly brackets { } are special for EREs (used for the range quantifier)
but not for 4880 regex, where they would be literals.

An empty regex alternation (a | at the beginning or end of an ERE, or
of a group inside brackets) is undefined on an ERE. A 4880 regex
supports it with the expected meaning. An equivalent regex using ? can
be used instead.

4880 regex doesn't support collating expressions inside equivalence
sets.

4880 regex allow escaping any character with a backslash. On an ERE you
can only escape special characters, an ordinary character preceded by a
backslash is undefined (and often used for extensions e.g. \w)

Regular expressions are a little-used feature, and the "natural" way to
write them would conform to both of those specifications. It is
unlikely that someone would have restricted a trust value based on the
presence of curly brackets on an User ID (they are legal in the local
part of email addresses, even unquoted, but it would be very rare to
find one). Equally, it would be strange to needlessly escape
characters.
So it _may_ be possible the change the definition without adversely
affecting existing usage. For full compatibility, changing the regex
would need to wait for V5 signatures or, preferably, use a new
subpacket type.

Happy New Year to all!

Ángel González

1- there is a nice copy preserved at  https://github.com/garyhouston/regexp.old,
see https://garyhouston.github.io/regex/
2- https://pubs.opengroup.org/onlinepubs/007908799/xbd/re.html#tag_007_004

---

From: Ángel <[email-masked]>
Date: Fri, 08 Jan 2021 02:42:36 +0100

On 2021-01-08 at 01:29 +0100, Ángel wrote:
> It is unlikely that someone would have restricted a trust value based
> on the presence of curly brackets on an User ID (they are legal in
> the local part of email addresses, even unquoted, but it would be
> very rare to find one). 

I have done a small review on the keyservers for User ID containing
curly brackets.
First, I restricted it to User ID containing email addresses.† Most
curly brackets on user id appear on the display-name of the user-id, as
part of a nick or used as brackets (e.g. "{Corporate Key}", "{RSA
Key}"…).

Someone might want to restrict a signature based on the display name,
such as trusting "John Doe" key for signing any key of someone named
"John Doe" (presumably other keys of himself), thus breaking for
names/nicks restricted in such way that contained "{".

But the real benefit of this feature imho would be for delegating the
trust on a subset of users, based on their email address.

For example, trust on a protonmail "master" openpgp key could (should?)
be qualified for "@protonmail\.(com|ch)>$" to only cover their users.

This reduces a lot the number of user ids with curly braces. There are
a few people that surrounded the email address with curly braces
instead of angle ones, or added a name/comment with those. Such emails
wouldn't be recognised by mail clients, though.

There are three instances where curlies appear on the domain part, in
order to cover multiple domains:
<{chongo,noll}@{toad,sgi}.com>        
<dz@{pd.dialnet,rd.relcom}.msk.su>
<colinp@{jolt.mpx,nms.otc}.com.au>

And then exactly twelve email addresses with the character '{' in the
local part:

<[email-masked]>³
<[email-masked]>¹
<[email-masked]>²
<[email-masked]>⁵
<[email-masked]>⁶
<[email-masked]>⁷
<[email-masked]>⁴
<[email-masked]>²
<lunam2{dhwtowers/towers2/[email-masked]>³
<[email-masked]>⁸
<[email-masked]>⁵
<[email-masked]>²

Of which only one of them works.

† This basically lets us ignore "bad" user IDs such as html pages. I
also filtered out from the analysis some garbage-looking user ids.

¹ E-mail accepted
² NXDOMAIN
³ No MX/A record
⁴ No MX record and no SMTP server reachable on A record
⁵ Recipient address rejected: User unknown in virtual mailbox table
⁶ 550 User unknown. (#5.1.1)
⁷ 550 5.4.1 Recipient address rejected: Access denied. AS(201806281)
⁸ 550 Requested action not taken: mailbox unavailable

---

From: Andrew Gallagher <[email-masked]>
Date: Fri, 8 Jan 2021 16:55:02 +0000

> find one). Equally, it would be strange to needlessly escape

It strikes me that regexes are an overengineered solution to a narrow 
use case, and that a simple *? globbing language would be more than 
sufficient. Is anything more complex than <*@*.example.com> required in 
the real world?

-- 
Andrew Gallagher

---

From: Ángel <[email-masked]>
Date: Sat, 09 Jan 2021 01:08:10 +0100

On 2021-01-08 at 16:55 +0000, Andrew Gallagher wrote:
> It strikes me that regexes are an overengineered solution to a
> narrow use case, and that a simple *? globbing language would be more
> than sufficient. Is anything more complex than <*@*.example.com>
> required in the real world?

That's a good point. It indeed looks as overengineered, but I'm not
aware of the dicussion that led to that being included.

I would probably include {} alternatives, to cover multiple tlds, so
resusing my previous example, that could be expressed as:
 "*@protonmail.{com,ch}>"

but I don't think that is required if the same can be expressed with
multiple subpackets.
Note that currently it isn't specified what happens if multiple Regular
Expression subpackets are present.
> Only signatures by the target key on User IDs that match the regular
> expression in the body of this packet have trust extended by the
> trust Signature subpacket.

If I made a signature with by TWO Regular Expressions
"[email-masked]>$" and "Andrew.*", would that cover user ids matching
ANY of them, or only those matched by BOTH?

If a new "Globbing expression" subpacket was added, allowing user ids
covering any of them would be a simple solution (and probably cleaner
as well) to not require that {}

Another fine point would be if * should expand across dots or,
following the same rulesprecedent as SSL certificates not expand
through several labels (see rfc6125 section-6.4.3 rule 2)

Finally, another point to consider would be whether to match only the
email address portion. Yes, User ID could contain something else, but
this delegation of partial trust only seem useful when combined with a
hierarchical structure, such as those to be found on the email address
part. It seems rare to require a matching on the display name part.
And allowing that would greatly decrease its security. Basically a
wildcard not on the left-most side could be bypassed by including the
required characters on the display name.

Best regards

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Sat, 09 Jan 2021 08:42:01 -0500

> required characters on the display name.

This stuff is very rarely used in the wild, and to the extent that it
is, it's used as a hierarchical match on the domain side of an e-mail
address, as found in the user ID (which itself is not typically treated
as a true RFC 2822 name-addr, despite the text in the spec, see
id:[email-masked] and related discussion).

Seems like the right way to address the most common (though still
uncommon) use case is to make a new explicit subpacket that is just
about handling a DNS suffix; to clearly define the interaction between
multiple subpackets; and to deprecate the regex for that particular use
case. (maybe deprecate the regex subpacket in general, as i've not seen
any other legit use, and there are clearly gaps in the spec for it)

That work is not really in-scope given our current charter, but if
someone wants to write something like that down in a more formal way, i
can imagine it being something for the WG to take on after we finish the
cryptographic refresh and consider re-chartering.

              --dkg

---

From: Ángel <[email-masked]>
Date: Sat, 09 Jan 2021 23:49:36 +0100

On 2021-01-09 at 08:42 -0500, Daniel Kahn Gillmor wrote:
> > Finally, another point to consider would be whether to match only
> > the email address portion. Yes, User ID could contain something
> > else, but this delegation of partial trust only seem useful when
> > combined with a hierarchical structure, such as those to be found
> > on the email address part. It seems rare to require a matching on
> > the display name part. And allowing that would greatly decrease its
> > security. Basically a wildcard not on the left-most side could be
> > bypassed by including the required characters on the display name.
> 
> address, as found in the user ID (which itself is not typically
> treated as a true RFC 2822 name-addr, despite the text in the spec,
> see id:[email-masked] and related discussion).

(Hint for future references: that's the “User ID conventions (it's not
really a RFC2822 name-addr)” thread.)

Yes. I am aware of that packet not exactly being a formal name-addr.
The mention "User ID could contain something else" was trying to convey
that there could be completely unstructured User ID packets but in
order for this to be useful you would need to be dealing with "common"
ones.

Looking again at that thread, I would recommend including some plain
text examples (non-normative, perhaps) on how User ID would be expected
to look like at your MR
https://gitlab.com/openpgp-wg/rfc4880bis/-/merge_r
equests/23/diffs?commit_id=a300afb3aebd1f5645dd3fbdcf14a420c5bc2090
(does gitlab support creating a merge request of a merge request?)

Realistically, there are some things that can only be achieved with
"structured User ID", and rfc4480bis should probably have some more
focus on that.
Particularly, if there is an uid has an email address associated, it is
crucial that all clients find the same one.

> about handling a DNS suffix; to clearly define the interaction
> between multiple subpackets; and to deprecate the regex for that
> particular use case. (maybe deprecate the regex subpacket in general,
> as i've not seen any other legit use, and there are clearly gaps in
> the spec for it)

I would probably consider that subpacket over en email address,
although it would be very rare for one of them not to begin with "*@"

> someone wants to write something like that down in a more formal way,
> i can imagine it being something for the WG to take on after we
> finish the cryptographic refresh and consider re-chartering.
> 
>               --dkg

Are you thinking on a separate RFC or as an amendment that could be
combined later into the same document?

Best regards

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Sun, 10 Jan 2021 09:08:37 -0500

> "structured User ID", and rfc4480bis should probably have some more

Given our charter, i'm not convinced that any of this (including my
merge request, mentioned above) is in scope for the intended
cryptographic refresh of RFC 4880, so i dont think it belongs ultimately
in rfc4880bis.

> combined later into the same document?

I think this would be a separate draft, which the WG isn't currently
chartered to adopt.  Assuming that we can effectively complete the
cryptographic refresh, though, it seems reasonable to think that the WG
would recharter to adopt and publish clarifications/improvements like
this one.

      --dkg

---

From: Ángel <[email-masked]>
Date: Sun, 10 Jan 2021 22:37:03 +0100

On 2021-01-10 at 09:08 -0500, Daniel Kahn Gillmor wrote:
> cryptographic refresh of RFC 4880, so i dont think it belongs
> ultimately in rfc4880bis.

Adding a new subpacket filter format is clearly out of scope of the
current charter. Let's call it "rfc4880tris material". :-)
Maybe, if rechartered before the publication, some low-hanging changes
completely uncontroversial might be included in the document. We could
all be shouting each other much earlier as that, as well. Or only very
difficultly reaching a consensus for rfc 4880 bis. It's too early in
the process. ¯\_(ツ)_/¯

However, I do think the User ID clarifications would be in scope, as
"addressing issues that have been identified by the 
community since the working group was originally closed."

Not that your merge request really changes existing convention. It only
documents it. In fact, I think it should additionally state that user
"SHOULD NOT be larger than XYZ", or at least warn about the attacks
with a note that an implementation "MAY choose to implement a maximum
Usuer ID size" (or even packet size, basically [1])

Best regards

Ángel

1- 
https://tools.ietf.org/html/draft-dkg-openpgp-abuse-resistant-keystore-04#section-4.1

---

From: Wiktor Kwapisiewicz <[email-masked]>
Date: Tue, 12 Jan 2021 10:48:10 +0100

Hi Ángel,

> as well) to not require that {}

If a new subpacket was added I think it'd make sense to store the entire 
expression in a binary (tree) form. This way parsing would be more 
consistent across implementations.

Using regexps invites implementers to just reuse whatever regexp library 
their language has thus inviting incompatibilities.

Of course this is not of highest priority but having a binary packet 
encoding that stores a regexp string that should be parsed with a 
different parser looks like a design issue with the protocol.

Kind regards,
Wiktor