Re: [openpgp] EdDSA problem and possible change about ECC

[Justus Winter <[e-mail]>]

Hello,
On Tue, Oct 29, 2019 at 3:10 AM, NIIBE Yutaka <[e-mail]> wrote:
> While I examined GnuPG and libgcrypt for that, I realized that there 
> are
> some discrepancy/inconsistency and possible interoperability issues
> among OpenPGP implementations.

Interoperability between implementations with regarad to EdDSA seems to 
be good:

https://tests.sequoia-pgp.org/#Detached_Sign-Verify_roundtrip_with_key__Alice_

Though I agree that OpenPGP's MPI encoding has been a source of bugs. I 
just discovered this exact issue in dkgpg this week:

https://savannah.nongnu.org/bugs/index.php?57135

> (2) Removal of zeros in MPI handling in EdDSA
> 
>   While the native EdDSA octet string for secret is defined as
>   fixed-size, it is defined as an MPI (big-endian) in OpenPGP.
> 
>   While the native EdDSA EC point representation is defined as
>   fixed-size little-endian, it is defined as an MPI in OpenPGP.
> 
>   While the native EdDSA integer representation is defined as 
> fixed-size
>   little-endian, it is defined as an MPI (big-endian) in OpenPGP.
> 
>   Because of this,
> 
>   * In EdDSA secret key, the zeros (least significant bytes) in native
>     representation of the secret are removed to compose an MPI.
> 
>   * In EdDSA signature, the zeros (least significant bytes) in native
>     representation of an EC point R are removed to compose an MPI.
> 
>   * In EdDSA signature, the zeros (least significant bytes) in native
>     representation of an integer S are removed to compose an MPI.
> 
> (3) Recovery of zeros in MPI handling in EdDSA
> 
>   To compensate the problem (2), it does special handling to recover
>   zeros when it receives an EdDSA secret/signature in OpenPGP format.

I agree with your analysis.

> While we should keep support of zero-removed EdDSA secret/signature, I
> think that it's good to modify GnuPG so that it won't generate 
> possibly
> problematic EdDSA secret/signature any more.

I wrote a test to see how various OpenPGP implementations react to MPIs 
that are not in canonical form (i.e. malformed MPIs) for S, or 
0x40-padded R, and only GnuPG and PGPy accept zero-padded S:

https://tests.sequoia-pgp.org/#EdDSA_signature_encodings

Therefore, I'm afraid that changing what implementations emit now will 
introduce incompatibilities with existing implementations.


Cheers,
Justus