Ed25519 verification sometimes fails

[vanitasvitae]

Hey! While playing with Ed25519, I noticed that some signatures I generate do not verify - while others which were generated the same way do verify successfully (see GOOD_SIG below).

First I thought this was an issue during signature generation, but I was able to successfully verify the same signature using both gopenpgp (via gosop) and rpgp (via rsop), so this is an indicator that the signature is good and that the bug is in the verification code.

I was able to isolate a failing signature (BROKEN_SIG) and step through the verification process (see test case below).

Compared to a "good" signature, in Ed25519.normalizeToNeutralElementVar the return value is false. Digging deeper, it turns out that F.isZeroVar(p.x) returns false, while "good" signatures would return true.

So my suspicion (which I cannot prove because I'm no cryptographer and not deep enough into the maths) is, that there might be a bug in scalarMultStraus128Var, as for "good" sigs, the final values of r.x and r.u would be zeros, while for the "broken" sig they are non-zero values.

What do you think?

Here is a test case:

package org.bouncycastle.openpgp.test;

import org.bouncycastle.bcpg.ArmoredInputStream;
import org.bouncycastle.bcpg.BCPGInputStream;
import org.bouncycastle.openpgp.PGPException;
import org.bouncycastle.openpgp.PGPObjectFactory;
import org.bouncycastle.openpgp.PGPPublicKey;
import org.bouncycastle.openpgp.PGPPublicKeyRing;
import org.bouncycastle.openpgp.PGPSignature;
import org.bouncycastle.openpgp.PGPSignatureList;
import org.bouncycastle.openpgp.bc.BcPGPObjectFactory;
import org.bouncycastle.openpgp.operator.bc.BcPGPContentVerifierBuilderProvider;
import org.bouncycastle.util.test.SimpleTest;

import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.nio.charset.StandardCharsets;

public class BrokenEd25519Test
        extends SimpleTest
{
    private static final String ARMORED_CERT = "-----BEGIN PGP PUBLIC KEY BLOCK-----\n" +
            "\n" +
            "xioGY4d/4xsAAAAg+U2nu0jWCmHlZ3BqZYfQMxmZu52JGggkLq2EVD34laPCsQYf\n" +
            "GwoAAABCBYJjh3/jAwsJBwUVCg4IDAIWAAKbAwIeCSIhBssYbE8GCaaX5NUt+mxy\n" +
            "KwwfHifBilZwj2Ul7Ce62azJBScJAgcCAAAAAK0oIBA+LX0ifsDm185Ecds2v8lw\n" +
            "gyU2kCcUmKfvBXbAf6rhRYWzuQOwEn7E/aLwIwRaLsdry0+VcallHhSu4RN6HWaE\n" +
            "QsiPlR4zxP/TP7mhfVEe7XWPxtnMUMtf15OyA51YBM4qBmOHf+MZAAAAIIaTJINn\n" +
            "+eUBXbki+PSAld2nhJh/LVmFsS+60WyvXkQ1wpsGGBsKAAAALAWCY4d/4wKbDCIh\n" +
            "BssYbE8GCaaX5NUt+mxyKwwfHifBilZwj2Ul7Ce62azJAAAAAAQBIKbpGG2dWTX8\n" +
            "j+VjFM21J0hqWlEg+bdiojWnKfA5AQpWUWtnNwDEM0g12vYxoWM8Y81W+bHBw805\n" +
            "I8kWVkXU6vFOi+HWvv/ira7ofJu16NnoUkhclkUrk0mXubZvyl4GBg==\n" +
            "-----END PGP PUBLIC KEY BLOCK-----";
    private static final String ARMORED_KEY = "-----BEGIN PGP PRIVATE KEY BLOCK-----\n" +
            "\n" +
            "xUsGY4d/4xsAAAAg+U2nu0jWCmHlZ3BqZYfQMxmZu52JGggkLq2EVD34laMAGXKB\n" +
            "exK+cH6NX1hs5hNhIB00TrJmosgv3mg1ditlsLfCsQYfGwoAAABCBYJjh3/jAwsJ\n" +
            "BwUVCg4IDAIWAAKbAwIeCSIhBssYbE8GCaaX5NUt+mxyKwwfHifBilZwj2Ul7Ce6\n" +
            "2azJBScJAgcCAAAAAK0oIBA+LX0ifsDm185Ecds2v8lwgyU2kCcUmKfvBXbAf6rh\n" +
            "RYWzuQOwEn7E/aLwIwRaLsdry0+VcallHhSu4RN6HWaEQsiPlR4zxP/TP7mhfVEe\n" +
            "7XWPxtnMUMtf15OyA51YBMdLBmOHf+MZAAAAIIaTJINn+eUBXbki+PSAld2nhJh/\n" +
            "LVmFsS+60WyvXkQ1AE1gCk95TUR3XFeibg/u/tVY6a//1q0NWC1X+yui3O24wpsG\n" +
            "GBsKAAAALAWCY4d/4wKbDCIhBssYbE8GCaaX5NUt+mxyKwwfHifBilZwj2Ul7Ce6\n" +
            "2azJAAAAAAQBIKbpGG2dWTX8j+VjFM21J0hqWlEg+bdiojWnKfA5AQpWUWtnNwDE\n" +
            "M0g12vYxoWM8Y81W+bHBw805I8kWVkXU6vFOi+HWvv/ira7ofJu16NnoUkhclkUr\n" +
            "k0mXubZvyl4GBg==\n" +
            "-----END PGP PRIVATE KEY BLOCK-----";

    @Override
    public String getName()
    {
        return "BrokenEd25519Test";
    }

    @Override
    public void performTest()
            throws Exception
    {
        verifBroken();
    }

    private void verifBroken()
            throws IOException, PGPException
    {
        String BROKEN_SIG = "-----BEGIN PGP SIGNED MESSAGE-----\n" +
                "\n" +
                "Hello, World!\n" +
                "-----BEGIN PGP SIGNATURE-----\n" +
                "\n" +
                "wpgGARsKAAAAKSKhBssYbE8GCaaX5NUt+mxyKwwfHifBilZwj2Ul7Ce62azJBYJm\n" +
                "xFfKAAAAAPQuILJpX0qXjMN3qawaS8EKE3AuC7DBuPJQf/LuY9IYiFE0f1jvAC9i\n" +
                "p9hDToXarz+XCbEG9RijCHz1YcPcAtdFfW8ZuT0saOyzJsnLW77UGv2PTRCc2ej6\n" +
                "cE+DHVq7TPjKCg==\n" +
                "-----END PGP SIGNATURE-----";
        String GOOD_SIG = "-----BEGIN PGP SIGNED MESSAGE-----\n" +
                "\n" +
                "Hello, World!\n" +
                "-----BEGIN PGP SIGNATURE-----\n" +
                "\n" +
                "wpgGARsKAAAAKSKhBssYbE8GCaaX5NUt+mxyKwwfHifBilZwj2Ul7Ce62azJBYJm\n" +
                "xFnJAAAAAAtFIL6Et0V4w8lNWX/WnVKB/2uvBj/cHC3vJveiA9PHq/cZP1Y82OQl\n" +
                "XrZ3tQHSGKOv0D/9Cv+K9mpBvZUxdZhofOnjMddgUmtw0FPcrSp9OqffyDn/+EKw\n" +
                "mjjo2RCO9vDFDA==\n" +
                "-----END PGP SIGNATURE-----";

        // to deal with the quirks of cleartext signature framework (line endings etc.),
        //  I define the signed plaintext here explicitly instead of extracting it from the message.
        //  I verified though that this is not the source of the error.
        String signedPlaintext = "Hello, World!";

        // parse certificate
        ByteArrayInputStream bIn = new ByteArrayInputStream(ARMORED_CERT.getBytes(StandardCharsets.UTF_8));
        ArmoredInputStream aIn = new ArmoredInputStream(bIn);
        BCPGInputStream pIn = new BCPGInputStream(aIn);
        PGPObjectFactory objFac = new BcPGPObjectFactory(pIn);
        PGPPublicKeyRing certificate = (PGPPublicKeyRing) objFac.nextObject();
        PGPPublicKey signingPubKey = certificate.getPublicKey();

        // parse message
        bIn = new ByteArrayInputStream(BROKEN_SIG.getBytes());
        aIn = new ArmoredInputStream(bIn);
        while (aIn.isClearText())
        {
            // skip over plaintext, see signedPlaintext above
            aIn.read();
        }

        // parse signature
        pIn = new BCPGInputStream(aIn);
        objFac = new BcPGPObjectFactory(pIn);
        PGPSignatureList sigList = (PGPSignatureList) objFac.nextObject();
        isEquals("There MUST be exactly 1 signature.", 1, sigList.size());
        PGPSignature sig = sigList.get(0);

        // Attempt to verify.
        sig.init(new BcPGPContentVerifierBuilderProvider(), signingPubKey);
        sig.update(signedPlaintext.getBytes(StandardCharsets.UTF_8));
        isTrue("Signature MUST verify successfully", sig.verify());
    }

    public static void main(String[] args)
    {
        runTest(new BrokenEd25519Test());
    }
}

[vanitasvitae]

Update: Some thing that's odd to me: I'm only able to produce "bad" signatures if using the Cleartext Signature Framework. If I generate Inline-signatures or detached signatures at the same time, I'd expect "bad" signatures to show up with the same frequency...

[peterdettman]

It's doubtful that there are any issues with the low-level ed25519 signing/verification, but I guess we should first exclude that.

BcImplProvider uses org.bouncycastle.crypto.signers.Ed25519Signer; you could modify Ed25519Signer.Buffer.generateSignature to immediately verify all generated signatures:

synchronized byte[] generateSignature(Ed25519PrivateKeyParameters privateKey)
{
    byte[] signature = new byte[Ed25519PrivateKeyParameters.SIGNATURE_SIZE];
    privateKey.sign(Ed25519.Algorithm.Ed25519, null, buf, 0, count, signature, 0);

    // begin check
    Ed25519PublicKeyParameters publicKey = privateKey.generatePublicKey();
    if (!publicKey.verify(Ed25519.Algorithm.Ed25519, null, buf, 0, count, signature, 0))
    {
        throw new IllegalStateException();
    }
    // end check

    reset();
    return signature;
}

You didn't include the code for (intermittently?) generating "broken signatures", but using the above change during that process should reveal any problems with the low-level verification.

Assuming the low-level is working fine, it will then be a matter of determining which one or more of the input message, signature and/or public key are inconsistent with the signature generation values. Ed25519Signer.Buffer.verifySignature is a convenient place to capture the values that the PGP verification is sending to the low-level implementation, for comparison with what are appearing in Ed25519Signer.Buffer.generateSignature.

[vanitasvitae]

Awesome, I will use your hints to do some more digging! Thanks!

[vanitasvitae]

My bad, I found the issue. I was using the wrong method to update the signature with the salt value. This caused modifications to the salt value in some cases. Dejavu?