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 OpenPGP_signature (235 bytes) Download Attachment |
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. > 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. 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 signature.asc (235 bytes) Download Attachment |
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 OpenPGP_signature (235 bytes) Download Attachment |
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. 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? 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 signature.asc (235 bytes) Download Attachment |
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. 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 OpenPGP_signature (235 bytes) Download Attachment |
Free forum by Nabble | Edit this page |