Mailing List Archive: gpg --export produces invalid EdDSA output

gpg --export produces invalid EdDSA output - regression

Sep 12, 2023, 8:45 AM

Post #1 of 10 (381 views)

Hello,

GnuPG 2.4.0 produces invalid output when exporting EdDSA key.
Specifically, there is extra padding in the signature. This causes
Sequoia (and maybe others) to reject such key (GnuPG itself accepts it).

The problem does not affect 2.2.40, so this is a regression in some
later version.

This can be reproduced as follows:

wget https://github.com/QubesOS/qubes-qubes-release/raw/main/RPM-GPG-KEY-qubes-4.2-templates-community
mkdir ~/test
gpg --homedir ~/test --import RPM-GPG-KEY-qubes-4.2-templates-community

With 2.2.4:

[user@disp6884 gnupg-2.2.40]$ g10/gpg --homedir ~/test --export |sq packet dump -x
Public-Key Packet, old CTB, 2 header bytes + 51 bytes
Version: 4
Creation time: 2023-03-14 14:35:36 UTC
Pk algo: EdDSA
Pk size: 256 bits
Fingerprint: 8F24D388C9DA21A55D7DBC8F08D08ABE6D5C71B3
KeyID: 08D08ABE6D5C71B3

00000000 98 CTB
00000001 33 length
00000002 04 version
00000003 64 10 86 38 creation_time
00000007 16 pk_algo
00000008 09 curve_len
00000009 2b 06 01 04 01 da 47 curve
00000010 0f 01
00000012 01 07 eddsa_public_len
00000014 40 a8 b6 69 8c 05 70 46 52 b5 2d 5d eddsa_public
00000020 08 e7 71 d8 b9 5f a6 e5 24 5b 33 e5 35 1c 5c 0b
00000030 d9 96 ad bc c7

User ID Packet, old CTB, 2 header bytes + 52 bytes
Value: Qubes OS Release 4.2 Community Templates Signing Key

00000000 b4 CTB
00000001 34 length
00000002 51 75 62 65 73 20 4f 53 20 52 65 6c 65 61 value
00000010 73 65 20 34 2e 32 20 43 6f 6d 6d 75 6e 69 74 79
00000020 20 54 65 6d 70 6c 61 74 65 73 20 53 69 67 6e 69
00000030 6e 67 20 4b 65 79

Signature Packet, old CTB, 2 header bytes + 146 bytes
Version: 4
Type: PositiveCertification
Pk algo: EdDSA
Hash algo: SHA512
Hashed area:
Issuer Fingerprint: 8F24D388C9DA21A55D7DBC8F08D08ABE6D5C71B3
Signature creation time: 2023-03-14 15:17:16 UTC
Key flags: CS
Symmetric algo preferences: AES256, AES192, AES128, TripleDES
AEAD preferences: OCB
Hash preferences: SHA512, SHA384, SHA256, SHA224, SHA1
Compression preferences: Zlib, BZip2, Zip
Features: MDC, AEAD, #2
Keyserver preferences: no modify
Unhashed area:
Issuer: 08D08ABE6D5C71B3
Digest prefix: 1631
Level: 0 (signature over data)

00000000 88 CTB
00000001 92 length
00000002 04 version
00000003 13 type
00000004 16 pk_algo
00000005 0a hash_algo
00000006 00 3b hashed_area_len
00000008 16 subpacket length
00000009 21 subpacket tag
0000000a 04 version
0000000b 8f 24 d3 88 c9 issuer fp
00000010 da 21 a5 5d 7d bc 8f 08 d0 8a be 6d 5c 71 b3
0000001f 05 subpacket length
00000020 02 subpacket tag
00000021 64 10 8f fc sig creation time
00000025 02 subpacket length
00000026 1b subpacket tag
00000027 03 key flags
00000028 05 subpacket length
00000029 0b subpacket tag
0000002a 09 08 07 02 pref sym algos
0000002e 02 subpacket length
0000002f 22 subpacket tag
00000030 02 pref aead algos
00000031 06 subpacket length
00000032 15 subpacket tag
00000033 0a 09 08 0b 02 pref hash algos
00000038 04 subpacket length
00000039 16 subpacket tag
0000003a 02 03 01 pref compression algos
0000003d 02 subpacket length
0000003e 1e subpacket tag
0000003f 07 features
00000040 02 subpacket length
00000041 17 subpacket tag
00000042 80 key server pref
00000043 00 0a unhashed_area_len
00000045 09 subpacket length
00000046 10 subpacket tag
00000047 08 d0 8a be 6d 5c 71 b3 issuer
0000004f 16 digest_prefix1
00000050 31 digest_prefix2
00000051 01 00 eddsa_sig_r_len
00000053 87 ab 4e 3a a8 4b 13 19 7f 39 21 4a ef eddsa_sig_r
00000060 7e 87 10 74 27 82 50 9b 14 54 c3 1c 1f 58 34 09
00000070 b5 2f 27
00000073 00 f8 eddsa_sig_s_len
00000075 b2 c7 d6 0d 3e 23 40 41 fe 8e 9c eddsa_sig_s
00000080 51 28 21 a0 31 b7 ca 55 9c b3 a3 6a 70 d9 ca d0
00000090 c7 bd eb 0f

With 2.4.0:

[user@disp6884 gnupg-2.4.0]$ g10/gpg --homedir ~/test --export |sq packet dump -x
Public-Key Packet, old CTB, 2 header bytes + 51 bytes
Version: 4
Creation time: 2023-03-14 14:35:36 UTC
Pk algo: EdDSA
Pk size: 256 bits
Fingerprint: 8F24D388C9DA21A55D7DBC8F08D08ABE6D5C71B3
KeyID: 08D08ABE6D5C71B3

00000000 98 CTB
00000001 33 length
00000002 04 version
00000003 64 10 86 38 creation_time
00000007 16 pk_algo
00000008 09 curve_len
00000009 2b 06 01 04 01 da 47 curve
00000010 0f 01
00000012 01 07 eddsa_public_len
00000014 40 a8 b6 69 8c 05 70 46 52 b5 2d 5d eddsa_public
00000020 08 e7 71 d8 b9 5f a6 e5 24 5b 33 e5 35 1c 5c 0b
00000030 d9 96 ad bc c7

User ID Packet, old CTB, 2 header bytes + 52 bytes
Value: Qubes OS Release 4.2 Community Templates Signing Key

00000000 b4 CTB
00000001 34 length
00000002 51 75 62 65 73 20 4f 53 20 52 65 6c 65 61 value
00000010 73 65 20 34 2e 32 20 43 6f 6d 6d 75 6e 69 74 79
00000020 20 54 65 6d 70 6c 61 74 65 73 20 53 69 67 6e 69
00000030 6e 67 20 4b 65 79

Unknown or Unsupported Packet, old CTB, 2 header bytes + 147 bytes
Tag: Signature Packet
Error: Malformed MPI: leading bit is not set: expected bit 8 to be set in 0 (0)

00000000 88 CTB
00000001 93 length
00000002 04 version
00000003 13 type
00000004 16 pk_algo
00000005 0a hash_algo
00000006 00 3b hashed_area_len
00000008 16 subpacket length
00000009 21 subpacket tag
0000000a 04 version
0000000b 8f 24 d3 88 c9 issuer fp
00000010 da 21 a5 5d 7d bc 8f 08 d0 8a be 6d 5c 71 b3
0000001f 05 subpacket length
00000020 02 subpacket tag
00000021 64 10 8f fc sig creation time
00000025 02 subpacket length
00000026 1b subpacket tag
00000027 03 key flags
00000028 05 subpacket length
00000029 0b subpacket tag
0000002a 09 08 07 02 pref sym algos
0000002e 02 subpacket length
0000002f 22 subpacket tag
00000030 02 pref aead algos
00000031 06 subpacket length
00000032 15 subpacket tag
00000033 0a 09 08 0b 02 pref hash algos
00000038 04 subpacket length
00000039 16 subpacket tag
0000003a 02 03 01 pref compression algos
0000003d 02 subpacket length
0000003e 1e subpacket tag
0000003f 07 features
00000040 02 subpacket length
00000041 17 subpacket tag
00000042 80 key server pref
00000043 00 0a unhashed_area_len
00000045 09 subpacket length
00000046 10 subpacket tag
00000047 08 d0 8a be 6d 5c 71 b3 issuer
0000004f 16 digest_prefix1
00000050 31 digest_prefix2
00000051 01 00 eddsa_sig_r_len
00000053 87 ab 4e 3a a8 4b 13 19 7f 39 21 4a ef eddsa_sig_r
00000060 7e 87 10 74 27 82 50 9b 14 54 c3 1c 1f 58 34 09
00000070 b5 2f 27
00000073 01 00 00 b2 c7 d6 0d 3e 23 40 41 fe 8e .......>#@A..
00000080 9c 51 28 21 a0 31 b7 ca 55 9c b3 a3 6a 70 d9 ca .Q(!.1..U...jp..
00000090 d0 c7 bd eb 0f .....

Some more details about similar/related issues can be found at:
https://gitlab.com/sequoia-pgp/sequoia/-/issues/1053
https://github.com/rpm-software-management/dnf/issues/1974

--
Best Regards,
Marek Marczykowski-Górecki
Invisible Things Lab

Re: gpg --export produces invalid EdDSA output - regression [ In reply to ]

gnupg-devel at gnupg

Sep 14, 2023, 5:11 AM

Post #2 of 10 (379 views)

Permalink

Hi!

The issue you mention has been discussed in length and Gniibe actually
took over my place in the "crypto-refresh" design team to help clarify
the interpretation of the MPI (which they unfortunatley ignored). MPIs
in OpenPGP are signed and thus may need a zero prefix byte because
negative numbers are nowhere used. The solution is to specify a new
type (SOS) at least in certain parts of the protocol. This must of
course be done in a backward compatible way given that ed25519 is in use
since 2014.

GnuPG 2.2 is older and and does not yet use the SOS which is the reason
for the different encodings you see. In short, there is no bug but
implementations need to follow this advice

1. OpenPGP implementations should implement:

Recovery of leading zero octets for Ed25519 key handling (secret
part) and Ed25519 signature

2. OpenPGP implementations are expected to accept:

Malformed MPI (with leading zero octet(s)), which is valid in SOS
For secret part of Ed25519/Curve25519/X448/Ed448 key and for
signature value S.

(see https://dev.gnupg.org/T4954)

Salam-Shalom,

Werner

--
The pioneers of a warless world are the youth that
refuse military service. - A. Einstein

Re: gpg --export produces invalid EdDSA output - regression [ In reply to ]

marmarek at invisiblethingslab

Sep 14, 2023, 5:34 AM

Post #3 of 10 (379 views)

Permalink

On Thu, Sep 14, 2023 at 02:11:52PM +0200, Werner Koch wrote:
> Hi!

Hi!

Thanks for the answer!

> The issue you mention has been discussed in length and Gniibe actually
> took over my place in the "crypto-refresh" design team to help clarify
> the interpretation of the MPI (which they unfortunatley ignored). MPIs
> in OpenPGP are signed and thus may need a zero prefix byte because
> negative numbers are nowhere used.

Hmm, but the RFC seems to specify it as unsigned, not signed:
https://datatracker.ietf.org/doc/html/rfc4880#section-3.2

Multiprecision integers (also called MPIs) are unsigned integers used
to hold large integers such as the ones used in cryptographic
calculations.

...

Additional rules:

The size of an MPI is ((MPI.length + 7) / 8) + 2 octets.

The length field of an MPI describes the length starting from its
most significant non-zero bit. Thus, the MPI [00 02 01] is not
formed correctly. It should be [00 01 01].

> The solution is to specify a new
> type (SOS) at least in certain parts of the protocol. This must of
> course be done in a backward compatible way given that ed25519 is in use
> since 2014.

Given the above, I'm not sure if that's really necessary. But even if it
is, it isn't "backward compatible" change, since standard
respecting-compliant implementation is expected to treat leading zeroes
as malformed.

> GnuPG 2.2 is older and and does not yet use the SOS which is the reason
> for the different encodings you see. In short, there is no bug but
> implementations need to follow this advice
>
> 1. OpenPGP implementations should implement:
>
> Recovery of leading zero octets for Ed25519 key handling (secret
> part) and Ed25519 signature
>
> 2. OpenPGP implementations are expected to accept:
>
> Malformed MPI (with leading zero octet(s)), which is valid in SOS
> For secret part of Ed25519/Curve25519/X448/Ed448 key and for
> signature value S.

My reading of the above is rather "an OpenPGP implementation that wants
to be compatible with GnuPG should also accept MPI that is not compliant
with the OpenPGP specification"... Have I missed some part of the spec?
Is this new "SOS" type described in some specification?

> (see https://dev.gnupg.org/T4954)

--
Best Regards,
Marek Marczykowski-Górecki
Invisible Things Lab

Re: gpg --export produces invalid EdDSA output - regression [ In reply to ]

gnupg-devel at gnupg

Sep 14, 2023, 6:49 AM

Post #4 of 10 (379 views)

Permalink

On Thu, 14 Sep 2023 14:34, Marek Marczykowski-Górecki said:

> Hmm, but the RFC seems to specify it as unsigned, not signed:

Sure - mail edit error on my part.

> Given the above, I'm not sure if that's really necessary. But even if it
> is, it isn't "backward compatible" change, since standard
> respecting-compliant implementation is expected to treat leading zeroes
> as malformed.

The problem here is that this is not a number. The MPI requirement has
been ignored since the introduction of RFC-6637 (ECC for OpenPGP) in
PGP, GnuPG and other implementation with support for ECC.

> My reading of the above is rather "an OpenPGP implementation that wants
> to be compatible with GnuPG should also accept MPI that is not compliant
> with the OpenPGP specification"... Have I missed some part of the spec?

A specification and the actual practise almost always differ. Even if
the author of RFC-6637 also did the implementation for PGP and GnuPG.
It is a specification bug and newer implementations need to cope with
the reality.

> Is this new "SOS" type described in some specification?

See

>> (see https://dev.gnupg.org/T4954)

and of course the code.

Shalom-Salam,

Werner

--
The pioneers of a warless world are the youth that
refuse military service. - A. Einstein

Re: gpg --export produces invalid EdDSA output - regression [ In reply to ]

marmarek at invisiblethingslab

Sep 14, 2023, 7:10 AM

Post #5 of 10 (379 views)

Permalink

On Thu, Sep 14, 2023 at 03:49:47PM +0200, Werner Koch wrote:
> On Thu, 14 Sep 2023 14:34, Marek Marczykowski-Górecki said:
>
> > Hmm, but the RFC seems to specify it as unsigned, not signed:
>
> Sure - mail edit error on my part.
>
> > Given the above, I'm not sure if that's really necessary. But even if it
> > is, it isn't "backward compatible" change, since standard
> > respecting-compliant implementation is expected to treat leading zeroes
> > as malformed.
>
> The problem here is that this is not a number. The MPI requirement has
> been ignored since the introduction of RFC-6637 (ECC for OpenPGP) in
> PGP, GnuPG and other implementation with support for ECC.

But GnuPG 2.2 did produced standard-compliant output, it stopped doing
so only later, no? So, where it was "ignored" that prompted changing
what output is produced?

In the discussion I see that SSH uses signed numbers there, but I don't
see how it's relevant for `gpg --export` which deals with OpenPGP
format, not SSH format.

> > My reading of the above is rather "an OpenPGP implementation that wants
> > to be compatible with GnuPG should also accept MPI that is not compliant
> > with the OpenPGP specification"... Have I missed some part of the spec?
>
> A specification and the actual practise almost always differ. Even if
> the author of RFC-6637 also did the implementation for PGP and GnuPG.
> It is a specification bug and newer implementations need to cope with
> the reality.

While it may be desirable to have _optional_ workarounds for some
misbehaving implementation, IMO the goal should be to converge at the
specified behavior. The change we are discussing here "forces" already
compliant implementations to diverge from the spec, which is step
backward. And I'm not surprised that some projects refuse to go into
that direction...

If there is a need for this padding to workaround some bug in another
implementation (can you name specific software and version when it's
actually required?), maybe make it configurable with a switch?

> > Is this new "SOS" type described in some specification?
>
> See
>
> >> (see https://dev.gnupg.org/T4954)
>
> and of course the code.

Well, issue tracker of a specific implementation is not really
specification that others should follow when implementing an IETF
standard...

--
Best Regards,
Marek Marczykowski-Górecki
Invisible Things Lab

Re: gpg --export produces invalid EdDSA output - regression [ In reply to ]

gnupg-devel at gnupg

Sep 14, 2023, 4:56 PM

Post #6 of 10 (379 views)

Permalink

Marek Marczykowski-G?recki <marmarek@invisiblethingslab.com> writes:

>In the discussion I see that SSH uses signed numbers there, but I don't see
>how it's relevant for `gpg --export` which deals with OpenPGP format, not SSH
>format.

A data point from the ASN.1 world, they also use signed integers and in 100.0%
of all cases where the sign bit is set (at least in crypto usage) it's an
encoding error, not an attempt to encode a negative number. So all
implementations treat the values as unsigned no matter what they're actually
supposed to be.

Which has in turn led to a tolerance of new implementations that get the
encoding wrong, but that's another issue. However, if the whole world treats
your values as unsigned anyway then it seems a bit risky to break the encoding
to accommodate something that doesn't exist.

Peter.

_______________________________________________
Gnupg-devel mailing list
Gnupg-devel@gnupg.org
https://lists.gnupg.org/mailman/listinfo/gnupg-devel

Re: gpg --export produces invalid EdDSA output - regression [ In reply to ]

gnupg-devel at gnupg

Sep 15, 2023, 1:35 AM

Post #7 of 10 (379 views)

Permalink

On Thu, 14 Sep 2023 16:10, Marek Marczykowski-Górecki said:

> misbehaving implementation, IMO the goal should be to converge at the
> specified behavior. The change we are discussing here "forces" already

The question is just which specification. GnuPG was the first to
implement ed25519 and then cross-tested this with RNP. Other
implementions showed up only later and thus need to follow existing
praxis. That we decided to change our implementations in a
compatible(!) way had practical reasons for better inperoperability
between other protocols and hardware implementations. The folks from
the other implementation knew about that (after all they used to be
employed for working GnuPG).

> Well, issue tracker of a specific implementation is not really
> specification that others should follow when implementing an IETF
> standard...

The only specification/standard here is RFC6637 (ECC for OpenPGP) which
states:

This document only defines the uncompressed point format. The point
is encoded in the Multiprecision Integer (MPI) format [RFC4880]. The
content of the MPI is the following:

B = 04 || x || y

[...]
This encoding is compatible with the definition given in [SEC1].

If other conversion methods are defined in the future, a compliant
application MUST NOT use a new format when in doubt that any
recipient can support it. Consider, for example, that while both the
public key and the per-recipient ECDH data structure, respectively
defined in Sections 9 and 10, contain an encoded point field, the
format changes to the field in Section 10 only affect a given
recipient of a given message.

For ed25519 we needed another conversion methods.

Shalom-Salam,

Werner

--
The pioneers of a warless world are the youth that
refuse military service. - A. Einstein

Re: gpg --export produces invalid EdDSA output - regression [ In reply to ]

gnupg-devel at gnupg

Sep 15, 2023, 2:38 AM

Post #8 of 10 (379 views)

Permalink

Hey Werner and list,

On 15.09.23 10:35, Werner Koch via Gnupg-devel wrote:
> The question is just which specification. GnuPG was the first to
> implement ed25519 and then cross-tested this with RNP.

You say "cross-testing" here to convey rigor, can you give some more
insight on how exactly the cross-testing was performed? Did these tests
produce any artifacts or documentation available to other developers?

Cheers

- V

_______________________________________________
Gnupg-devel mailing list
Gnupg-devel@gnupg.org
https://lists.gnupg.org/mailman/listinfo/gnupg-devel

Re: gpg --export produces invalid EdDSA output - regression [ In reply to ]

heiko at schaefer

Sep 17, 2023, 1:57 AM

Post #9 of 10 (379 views)

Permalink

Hello Werner, list,

On 9/15/23 10:35, Werner Koch via Gnupg-devel wrote:
> That we decided to change our implementations in a
> compatible(!) way had practical reasons for better inperoperability
> between other protocols and hardware implementations.

I'd be very interested to learn more about this. Could you point me to a
resource where I can read more about what those interoperability issues
were?

Thanks and regards,
:) Heiko

_______________________________________________
Gnupg-devel mailing list
Gnupg-devel@gnupg.org
https://lists.gnupg.org/mailman/listinfo/gnupg-devel

Mailing List Archive

Attached Files:

Attached Files:

Attached Files:

Attached Files:

Attached Files:

Attached Files: