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

[James Bottomley]

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

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 228 bytes
Desc: This is a digitally signed message part
URL: <https://lists.gnupg.org/pipermail/gnupg-devel/attachments/20210213/b3fac89c/attachment.sig>