Re: [openpgp] on the risks of pubkey codepoint parameterization [was: another suggestion for a way fwd with hybrid sigs]

[Daniel Kahn Gillmor <[e-mail]>]

On Wed 2024-03-06 12:37:45 +0000, Daniel Huigens wrote:
> My only caution would be that, if we commit to only having one code
> point in advance, folks might be tempted to use it for two security
> levels of ML-DSA (if they feel that we need both, which I'm personally
> not sure is the case) by parameterizing the code point, which I would
> prefer not to do.

As soon as you said this, i started thinking "hm, if it came to that,
what would be the best way to parameterize this?"  ha ha, the exact
opposite of what you wanted to happen :P

But i share your instinct that parameterized pubkey codepoints are not a
great idea.  So, i turned my line of inquiry into *why* parameterized
pubkey codepoints seem problematic.  The answers i came up with (in a
personal capacity, not wearing a chair hat) are below.  I hope folks
will critique or correct them!

# Parameterized Pubkey Codepoints in OpenPGP

Many OpenPGP pubkey algorithm codepoints are parameterized.

For example, RSA (pubkey ID 1), ElGamal (16), and DSA (17) can have
arbitrary sizes, up to the size limit of the MPI format.  This can be
seen as a sort of simple size-based parameterization.

ECDSA (19), ECDH (18), and EdDSALegacy (22) are each parameterized
internally by OID, yielding even more potential variation than size,
depending on how the OIDs are characterized.  For example, ECDH with
Curve25519Legacy behaves differently (e.g., has different wire format)
than ECDH with BrainpoolP256r1.

The more recently defined pubkey codepoints (X25519 (25), X448 (26),
Ed25519 (27) and Ed448 (28)) are not parameterized at all.  each
codepoint represents a single, unique algorithm.

# Concerns About Parameterized Pubkeys in OpenPGP

What specifically are the drawbacks to parameterized public key
algorithms in OpenPGP?

## Interoperability/Compatibility

It is difficult to know whether any given implementation fully supports
a parameterized public key algorithm.

For size-based parameterization,
https://tests.sequoia-pgp.org/#RSA_key_sizes demonstrates a wide range
of acceptance/rejection across different implementations.

The OID-based parameterization of ECDH, ECDSA, and EdDSALegacy
codepoints make it impossible to know for certain whether any particular
algorithm or curve is supported.  For example, knowing that my
recipient's implementation can do ECDH doesn't help me at all with
knowing whether any particular curve is supported.

## Cross-algorithm Weak Context

The stream of octets hashed for an OpenPGP signature (see the "Computing
Signatures" section in RFC 4880 and draft-ietf-openpgp-crypto-refresh)
explicitly contains the signature algorithm octet, but does not contain
any parameterization indicator.

If you consider two signing keys from algorithms that have different
algorithm IDs, those keys will never sign the same bytestream, because
there is one octet in the bytestream that identifies the algorithm ID.
But for two keys that share the same algorithm ID, but use actually
different algorithms, to the extent that any cross-algorithm confusion
is possible, the stream of bytes hashed cannot be used to explicitly
differentiate the algorithmic context.

I tried to do a comparable analysis on pubkey encryption, and stumbled a
bit.  When encrypting with PKESK (either v3 or v6), i don't see a way
that the specific pubkey algorithm ID is folded into any stages of the
wrapping of the session key, with the exception of ECDH, which
explicitly puts the ECDH algorithm ID into the KDF function used to
derive the key for AES keywrap.  ECDH also includes the parameterization
itself (by means of the curve OID) in the KDF for the keywrap.
non-parameterized X25519 and X448 differentiate themselves from each
other not by algorithm ID, but by algorithm-specific strings in the HKDF
info parameter.  As a result, I'm not sure whether there are ways to
abuse the missing context in pubkey encryption algorithms.

And, cross-algorithm attacks are themselves pretty arcane.  I don't
think i know of a specific real-world attack.

## Multidimensional Parameterization

In some cases, the parameterization isn't just size or arbitrary OID,
but actual flexible, "choose one from column A, one from column B, and
one from column C" multidimensional parameterization.  For example, the
KDF parameterization of ECDH leaves room to choose a hash function for
the KDF and a symmetric cipher for the KEK.  (as of the crypto-refresh,
this flexibility is deprecated, and specific choices are bound to the
curve OID for v6 encryption-capable ECDH keys)

Multidimensional parameterization is a bad idea because it lets the
generator make mismatched choices (e.g., KDF hash algo SHA2-224 and KEK
symmetric algo AES-256) or bizarre combinations (RIPEMD-160 with
Camellia-256) which might not have sufficiently widespread
support. Furthermore, as the dimensions increase, test suites are
obliged to deal with a combinatorial explosion of options if they want
to confirm full coverage.


What else have i missed in this analysis? What have i gotten wrong?

     --dkg