Ed25519 keys: what's stored in a secret key packet?

[Marco Ricci]

Greetings!

I'm having trouble verifying what exactly an OpenPGP secret key packet
for Ed25519 keys is supposed to contain, i.e. what the fields in the
secret key packet actually represent. I think that the spec [1] (and its
later version [2]), if implemented literally, would cause part of the
information necessary for signing to be lost.

My understanding of Ed25519 is based on Brian Warner's presentation [3]:

  * Ed25519 keys start as a 32-byte seed `k`, which is hashed and
    divided into a left half `LH` and a right half `RH`.

  * `LH` is massaged into a secret scalar `a`, from which the public key
    `A` is derived via EC point multiplication.

  * Ed25519 signatures consist of two encoded EC points `R` and `S`. `R`
    depends solely on `r`, the DSA secret "random" integer (which in
    Ed25519 is deterministically computed from the message `M` and from
    `RH`). `S` is computed from `A`, `a`, `M`, `R` and `r`.

In particular, from my understanding, Ed25519 signatures are
deterministic, and require calculating or storing `RH` to achieve that
goal; consequently, `k` or `RH` must be part of the secret key's wire
format, because calculating `RH` without knowing `k` involves a large
partial hash inversion and is thus cryptographically infeasible. The
bit-fiddling on `LH` also guarantees that `a` is always divisible by 8.

The EdDSA for OpenPGP spec [1] defines the wire format to only contain
"an MPI of an integer representing the secret key, which is a scalar of
the public EC point". This appears to describe the secret scalar `a`.
In contrast, SSH, or more specifically the SSH agent protocol [4],
defines the wire format of Ed25519 keys to contain the seed `k`. It is
unclear to me how OpenPGP would ensure that Ed25519 signatures remain
deterministic -- which I verified that they are -- if neither `k` nor
`RH` is stored in the secret key material. Some testing with sample
Ed25519 keys and GnuPG's `--list-packets` indicates that the range of
possible values for the secret MPI value is actually consistent with
`k`, but not with `a`, because not all sample MPI values were divisible
by 8.

Thus, my question: What exactly does the scalar in an OpenPGP Ed25519
secret key denote? The Ed25519 multiplicative scalar `a` such that the
public key `A` is `a` times the Ed25519 base point? Or the seed `k` such
that `a` and `RH` are derived from `SHA512(k)`?

Thanks, and cheers,
Marco

[1]: https://tools.ietf.org/html/draft-koch-eddsa-for-openpgp-04#section-4
[2]: https://tools.ietf.org/html/draft-ietf-openpgp-rfc4880bis-10#section-5.6.5
[3]: https://blog.mozilla.org/warner/2011/11/29/ed25519-keys/
[4]: https://tools.ietf.org/html/draft-miller-ssh-agent-04#section-4.2.3


_______________________________________________
Gnupg-devel mailing list
[hidden email]
http://lists.gnupg.org/mailman/listinfo/gnupg-devel

[GnuPG - Dev mailing list]

On Fri, 2021-02-12 at 14:12 +0100, Marco Ricci wrote:

> Greetings!
>
> I'm having trouble verifying what exactly an OpenPGP secret key
> packet for Ed25519 keys is supposed to contain, i.e. what the fields
> in the secret key packet actually represent. I think that the spec
> [1] (and its later version [2]), if implemented literally, would
> cause part of the information necessary for signing to be lost.
>
> My understanding of Ed25519 is based on Brian Warner's presentation
> [3]:
>
>   * Ed25519 keys start as a 32-byte seed `k`, which is hashed and
>     divided into a left half `LH` and a right half `RH`.
>
>   * `LH` is massaged into a secret scalar `a`, from which the public
> key
>     `A` is derived via EC point multiplication.
>
>   * Ed25519 signatures consist of two encoded EC points `R` and `S`.
> `R`
>     depends solely on `r`, the DSA secret "random" integer (which in
>     Ed25519 is deterministically computed from the message `M` and
> from
>     `RH`). `S` is computed from `A`, `a`, `M`, `R` and `r`.
>
> In particular, from my understanding, Ed25519 signatures are
> deterministic, and require calculating or storing `RH` to achieve
> that goal; consequently, `k` or `RH` must be part of the secret key's
> wire format, because calculating `RH` without knowing `k` involves a
> large partial hash inversion and is thus cryptographically
> infeasible. The bit-fiddling on `LH` also guarantees that `a` is
> always divisible by 8.

Well 2^3 is the cofactor of the Bernstein curve, yes.

> The EdDSA for OpenPGP spec [1] defines the wire format to only
> contain "an MPI of an integer representing the secret key, which is a
> scalar of the public EC point". This appears to describe the secret
> scalar `a`. In contrast, SSH, or more specifically the SSH agent
> protocol [4], defines the wire format of Ed25519 keys to contain the
> seed `k`. It is unclear to me how OpenPGP would ensure that Ed25519
> signatures remain deterministic -- which I verified that they are --
> if neither `k` nor `RH` is stored in the secret key material. Some
> testing with sample Ed25519 keys and GnuPG's `--list-packets`
> indicates that the range of possible values for the secret MPI value
> is actually consistent with `k`, but not with `a`, because not all
> sample MPI values were divisible by 8.

Firstly the EdDSA signature algorithm uses a private bit string K in
the computation r = H(KM).  Traditionally K is the high part of the
hash of the private key (i.e. LH in your description above) to avoid
having to rely on random numbers but the algorithm works equally well
if K is simply a random number.  As long as K remains unknown to anyone
except the signer, the signature is secure and will verify correctly.

> Thus, my question: What exactly does the scalar in an OpenPGP Ed25519
> secret key denote? The Ed25519 multiplicative scalar `a` such that
> the public key `A` is `a` times the Ed25519 base point? Or the seed
> `k` such that `a` and `RH` are derived from `SHA512(k)`?

Is your problem with what the standard says or what gnupg actually
does?  Because what it does is store the encrypted s-expression of the
private key in the key file exactly as libgcrypt supplies it and
libgcrypt makes d one of the parameters of this s-expression.  d is
what you call k above: the random 32 bit number.  libgcrypt correctly
calculates the public key from the lower 32 bytes of the hash of k
(i.e. RH above).  See ecc-eddsa.c:_gcry_ecc_eddsa_genkey().

James


_______________________________________________
Gnupg-devel mailing list
[hidden email]
http://lists.gnupg.org/mailman/listinfo/gnupg-devel

[Marco Ricci]

Greetings!

Thus spoke James Bottomley:
>> The bit-fiddling on `LH` also guarantees that `a` is
>> always divisible by 8.
>
> Well 2^3 is the cofactor of the Bernstein curve, yes.

I'm aware. I wanted to stress that `a` has range restrictions, and thus
has a characteristic bit pattern when serialized as an OpenPGP MPI.

> Firstly the EdDSA signature algorithm uses a private bit string K in
> the computation r = H(KM).  Traditionally K is the high part of the
> hash of the private key (i.e. LH in your description above) to avoid
> having to rely on random numbers but the algorithm works equally well
> if K is simply a random number.  As long as K remains unknown to anyone
> except the signer, the signature is secure and will verify correctly.

I'm aware, as well. I believe though that the normative EdDSA version is
to use the `r = H(KM)` calculation. I see no indication in the EdDSA for
OpenPGP spec that a non-standard version of determining `r` is used.

> Is your problem with what the standard says or what gnupg actually
> does?  Because what it does is store the encrypted s-expression of the
> private key in the key file exactly as libgcrypt supplies it and
> libgcrypt makes d one of the parameters of this s-expression.  d is
> what you call k above: the random 32 bit number.

The former, sort of. But this actually answers my question. Thanks.
I couldn't sensibly determine what libgcrypt's output is and whether
GnuPG transforms it or not before encoding it as an OpenPGP secret key
packet. (I couldn't find any documentation on the s-expression shape,
nor could I get GnuPG to actually emit the s-expression, so I gathered
that to get my answer I'd have to write my own C program to interface
libgcrypt, which I don't feel confident enough to attempt yet with my
current level of familiarity with libgcrypt.) Knowing that libgcrypt
yields the `d`/`k` value and that it ends up in the secret key packet
clears my doubts on what those secret key packets really contain.

But then the spec and GnuPG's behavior differ, no? And one of them
should be fixed -- presumably the spec, because it's still a draft, and
because IMO the current practice is saner than the spec. Should I file
a proper report against the spec then?

Regards,
Marco


_______________________________________________
Gnupg-devel mailing list
[hidden email]
http://lists.gnupg.org/mailman/listinfo/gnupg-devel

[GnuPG - Dev mailing list]

On Sun, 2021-02-14 at 11:07 +0100, Marco Ricci wrote:

> Greetings!
>
> Thus spoke James Bottomley:
> > > The bit-fiddling on `LH` also guarantees that `a` is
> > > always divisible by 8.
> >
> > Well 2^3 is the cofactor of the Bernstein curve, yes.
>
> I'm aware. I wanted to stress that `a` has range restrictions, and
> thus has a characteristic bit pattern when serialized as an OpenPGP
> MPI.
>
> > Firstly the EdDSA signature algorithm uses a private bit string K
> > in the computation r = H(KM).  Traditionally K is the high part of
> > the hash of the private key (i.e. LH in your description above) to
> > avoid having to rely on random numbers but the algorithm works
> > equally well if K is simply a random number.  As long as K remains
> > unknown to anyone except the signer, the signature is secure and
> > will verify correctly.
>
> I'm aware, as well. I believe though that the normative EdDSA version
> is to use the `r = H(KM)` calculation. I see no indication in the
> EdDSA for OpenPGP spec that a non-standard version of determining `r`
> is used.

libgcrypt uses K = LH

The relevant code is ecc-eddsa.c:_gcry_ecc_eddsa_sign

The only slight deviation gnupg does for elliptic curves is that it
uses RFC6979 deterministic signatures for ECDSA.

> > Is your problem with what the standard says or what gnupg actually
> > does?  Because what it does is store the encrypted s-expression of
> > the private key in the key file exactly as libgcrypt supplies it
> > and libgcrypt makes d one of the parameters of this s-
> > expression.  d is what you call k above: the random 32 bit number.
>
> The former, sort of. But this actually answers my question. Thanks.
> I couldn't sensibly determine what libgcrypt's output is and whether
> GnuPG transforms it or not before encoding it as an OpenPGP secret
> key packet. (I couldn't find any documentation on the s-expression
> shape, nor could I get GnuPG to actually emit the s-expression, so I
> gathered that to get my answer I'd have to write my own C program to
> interface libgcrypt, which I don't feel confident enough to attempt
> yet with my current level of familiarity with libgcrypt.) Knowing
> that libgcrypt yields the `d`/`k` value and that it ends up in the
> secret key packet clears my doubts on what those secret key packets
> really contain.
>
> But then the spec and GnuPG's behavior differ, no? And one of them
> should be fixed -- presumably the spec, because it's still a draft,
> and because IMO the current practice is saner than the spec. Should I
> file a proper report against the spec then?

Well, it's not really relevant any more:  The spec is documenting the
secring keypacket format, which isn't used by current gnupg (it started
switching to the encrypted s-expression format in 2017).  The current
format is documented in agent/keyformat.txt

James


_______________________________________________
Gnupg-devel mailing list
[hidden email]
http://lists.gnupg.org/mailman/listinfo/gnupg-devel

[Marco Ricci]

Greetings!

Thus spoke James Bottomley:

>> I'm aware, as well. I believe though that the normative EdDSA version
>> is to use the `r = H(KM)` calculation. I see no indication in the
>> EdDSA for OpenPGP spec that a non-standard version of determining `r`
>> is used.
>
> libgcrypt uses K = LH
>
> The relevant code is ecc-eddsa.c:_gcry_ecc_eddsa_sign
>
> The only slight deviation gnupg does for elliptic curves is that it
> uses RFC6979 deterministic signatures for ECDSA.

The latter is good to know, thanks.

I believe you on the former -- it looks plausible, given the libgcrypt
code -- but I gave up trying to actually verify it. I find libgcrypt's
code rather too opaque and confusing for me to follow. (But then I've
touched libgcrypt for all of 10mins, I'm not too familiar with its
coding style (names, data structures, etc.), and this kind of low-level
C code isn't really my forte anyway.)

>> But then the spec and GnuPG's behavior differ, no? And one of them
>> should be fixed -- presumably the spec, because it's still a draft,
>> and because IMO the current practice is saner than the spec. Should I
>> file a proper report against the spec then?
>
> Well, it's not really relevant any more:  The spec is documenting the
> secring keypacket format, which isn't used by current gnupg (it started
> switching to the encrypted s-expression format in 2017).

Inasfar as GnuPG alone is concerned, maybe, but what about file exchange
of secret keys between different OpenPGP implementations, say GnuPG and
Thunderbird/RNP? My reason for worrying about secret key contents in the
first place is because I ultimately want to share Ed25519 key material
between OpenPGP and (Open)SSH, and perhaps other systems. And the most
future-proof way of doing that is to attempt converting the "standard"
key formats of the respective systems into one another. That use case
would definitely benefit from a corrected spec.

> The current format is documented in agent/keyformat.txt

I'm starting to feel like I'm not doing my homework properly. Thanks
again for the pointer, I'll give the v2.3+ text-based private key format
a try.

Regards,
Marco



_______________________________________________
Gnupg-devel mailing list
[hidden email]
http://lists.gnupg.org/mailman/listinfo/gnupg-devel