ed25519 expanded private key support

[msmuenchen]

There are implementations of ed25519 such as Tor or orlp-ed25519 (which is used by MeshCore) which export and import private keys in expanded-hash format.

Unfortunately, neither java.security's implementation of ed25519 nor Bouncycastle seem to support using such a key to do signatures at the moment, and apparently there's (at least) two different implementations both using 64 bytes.

Would it be possible to implement support for this format in Bouncycastle to allow key interchange with applications not using the seed?

[roy-basmacier]

Hello @msmuenchen,

The 64-byte (scalar, prefix) form isn't a standard. RFC 8032, PKCS#8 (RFC 8410), and JWK (RFC 8037) all define the Ed25519 private key as the 32-byte seed. The expanded form is an internal artifact of ref10 style signing that a few libraries (Tor, orlp-ed25519) expose as a serializable type, but it isn't specified anywhere as a wire format. It's also easily confused with libsodium's 64-byte secret key, which is seed || pubkey rather than an expanded key (same byte count, different layout). This would also prevent re-exporting in any standard form.

Curious what the scope is and which system you're trying to talk to where the seed is unavailable?

[msmuenchen]

The scope is Meshcore - I am trying to re-implement that in Java. Unfortunately they were using orlp in their initial implementation and haven't yet migrated to Arduinolibs Crypto (which uses standard format seed) and only save the 64-bit extended hash private key and public key on the hardware's config storage, so no way to get the seed back. They are in the process of moving the crypto to Arduinolibs but it will take a few months at the very least, and I need to be backwards-compatible in my implementation.

It seems that your code in private static void implSign(Digest d, byte[] h, byte[] s, byte[] pk, int pkOff, byte[] ctx, byte phflag, byte[] m, int mOff, int mLen, byte[] sig, int sigOff) matches orlp-ed25519's sign.c, so what I'll do first is make a fork of BC ed25519, implement a sign_orlp function that calls into implSign and then submit it here for review.

That should also allow creating a sign_libsodium function that accepts the format of libsodium.

[msmuenchen]

@roy-basmacier I finished creating my wrapper function - it creates signatures that are compatible with meshcore. It's in my repository at commit 3c2d38584841b19f84d5bbaa3f25d1812f9e1329 if you want to take a look.

Should I file my own PR to add this, or do you want to do so? I'm fine with either.

import org.bouncycastle.crypto.Digest;

import java.lang.reflect.InvocationTargetException;
import java.lang.reflect.Method;

/**
 * Wrapper class for Ed25519 cryptography from BouncyCastle
 * We need to use a private-limited method as MC uses extended-hash private key format
 * Will be removed if upstream issue <a href="https://github.com/bcgit/bc-java/issues/2302">2302</a> succeeds
 */
public class Ed25519 extends org.bouncycastle.math.ec.rfc8032.Ed25519 {
    protected static Method implSignMethod;
    protected static Method createDigestMethod;
    protected static Method scalarMultBaseEncodedMethod;

    static {
        //private static void implSign(Digest d, byte[] h, byte[] s, byte[] pk, int pkOff, byte[] ctx, byte phflag, byte[] m,
        //        int mOff, int mLen, byte[] sig, int sigOff)
        try {
            //load the private method
            implSignMethod = org.bouncycastle.math.ec.rfc8032.Ed25519.class.getDeclaredMethod(
                    "implSign",
                    Digest.class, //d
                    byte[].class, //h
                    byte[].class, //s
                    byte[].class, //pk
                    int.class, //pkOff
                    byte[].class, //ctx
                    byte.class, //phflag
                    byte[].class, //m
                    int.class, //mOff
                    int.class, //mLen
                    byte[].class, //sig
                    int.class //sigOff
            );
            implSignMethod.setAccessible(true);
            createDigestMethod = org.bouncycastle.math.ec.rfc8032.Ed25519.class.getDeclaredMethod(
                    "createDigest"
            );
            createDigestMethod.setAccessible(true);
            scalarMultBaseEncodedMethod = org.bouncycastle.math.ec.rfc8032.Ed25519.class.getDeclaredMethod(
                    "scalarMultBaseEncoded",
                    byte[].class, //k
                    byte[].class, //r
                    int.class //rOff
            );
            scalarMultBaseEncodedMethod.setAccessible(true);
        } catch (NoSuchMethodException e) {
            throw new RuntimeException(e);
        }
    }

    /**
     * Sign a message using orlp-ed25519 style private keys
     * <p>
     * Applications using orlp-ed25519 style private keys (like MeshCore) do not store their seed after deriving the
     * private/public keypair and instead store it in a || RH format.
     * </p>
     *
     * @param signature  buffer to write the signature to, 64 bytes {@link org.bouncycastle.math.ec.rfc8032.Ed25519.SIGNATURE_SIZE}
     * @param message    message buffer
     * @param publicKey  orlp-style public key (32 bytes) {@link org.bouncycastle.math.ec.rfc8032.Ed25519.PUBLIC_KEY_SIZE}
     * @param privateKey orlp-style private key (64 bytes)
     * @see <a href="https://github.com/orlp/ed25519/blob/master/src/sign.c">orlp-ed25519 implementation</a>
     * @see <a href="https://blog.mozilla.org/warner/2011/11/29/ed25519-keys/">Brian Warner on ed25519 key formats</a>
     */
    public static void sign_orlp(byte[] signature, byte[] message, byte[] publicKey, byte[] privateKey) {
        try {
            Digest d = (Digest) createDigestMethod.invoke(null);
            //h = LH || RH (corresponding to sha512(seed))
            //orlp-style private key goes further: it already has LH pruned
            byte[] h = new byte[64];
            //h gets mutated by implSign, so copy the buffer to avoid silent corruption
            System.arraycopy(privateKey, 0, h, 0, 64);

            //s = pruned scalar, 32 bytes
            //orlp-style private keys are already assumed to be pruned
            byte[] s = new byte[32];
            //copy the buffer to avoid silent corruption
            System.arraycopy(privateKey, 0, s, 0, 32);

            //orlp-style public key
            byte[] pk = publicKey;
            int pkOff = 0;

            //set to null to avoid the extraneous (compared to orlp ed25519_sign) dom2 code path
            byte[] ctx = null;
            byte phflag = 0x00;

            // message
            byte[] m = message;
            int mOff = 0;
            int mLen = message.length;

            //signature (destination) buffer
            byte[] sig = signature;
            int sigOff = 0;

            implSignMethod.invoke(null, d, h, s, pk, pkOff, ctx, phflag, m, mOff, mLen, sig, sigOff);
        } catch (IllegalAccessException | InvocationTargetException e) {
            throw new RuntimeException(e);
        }
    }

    /**
     * Sign a message using orlp-ed25519 style private keys
     * <p>
     * Applications using orlp-ed25519 style private keys (like MeshCore) do not store their seed after deriving the
     * private/public keypair and instead store it in a || RH format.
     * </p>
     * <p>This overload derives the public key on demand from the private key.</p>
     *
     * @param signature  buffer to write the signature to, 64 bytes {@link org.bouncycastle.math.ec.rfc8032.Ed25519.SIGNATURE_SIZE}
     * @param message    message buffer
     * @param privateKey orlp-style private key (64 bytes)
     * @see <a href="https://github.com/orlp/ed25519/blob/master/src/sign.c">orlp-ed25519 implementation</a>
     * @see <a href="https://blog.mozilla.org/warner/2011/11/29/ed25519-keys/">Brian Warner on ed25519 key formats</a>
     * @see <a href="https://github.com/orlp/ed25519/pull/17/changes">orlp-ed25519 PR describing derivation of public key</a>
     */
    public static void sign_orlp(byte[] signature, byte[] message, byte[] privateKey) {
        try {
            // orlp private keys are a || RH, so a can be simply extracted
            byte[] a = new byte[32];
            System.arraycopy(privateKey, 0, a, 0, 32);

            // derive public key
            byte[] pk = derive_pubkey_orlp(privateKey);
            int pkOff = 0;
            scalarMultBaseEncodedMethod.invoke(null, a, pk, pkOff);

            sign_orlp(signature, message, pk, privateKey);
        } catch (IllegalAccessException | InvocationTargetException e) {
            throw new RuntimeException(e);
        }
    }


    /**
     * Derive public key from orlp-ed25519 style private keys
     * <p>
     * Applications using orlp-ed25519 style private keys (like MeshCore) do not store their seed after deriving the
     * private/public keypair and instead store it in a || RH format.
     * </p>
     *
     * @param privateKey orlp-style private key (64 bytes)
     * @see <a href="https://blog.mozilla.org/warner/2011/11/29/ed25519-keys/">Brian Warner on ed25519 key formats</a>
     * @see <a href="https://github.com/orlp/ed25519/pull/17/changes">orlp-ed25519 PR describing derivation of public key</a>
     */
    public static byte[] derive_pubkey_orlp(byte[] privateKey) {
        try {
            // orlp private keys are a || RH, so a can be simply extracted
            byte[] a = new byte[32];
            System.arraycopy(privateKey, 0, a, 0, 32);

            // derive public key
            // public key (A) = multiply (a)
            byte[] pk = new byte[32];
            int pkOff = 0;
            scalarMultBaseEncodedMethod.invoke(null, a, pk, pkOff);

            return pk;
        } catch (IllegalAccessException | InvocationTargetException e) {
            throw new RuntimeException(e);
        }
    }
}

[msmuenchen]

@roy-basmacier one more question while I'm at it: what is the BC equivalent of ed25519_key_exchange? Based on orlp mentioning montgomery conversion, I assume it's X25519?