64-byte expanded secret key support

[johndbritton]

Is it possible to use a 64 byte signing key with this library? I have a key generated from https://github.com/sparkle-project/ed25519 and I need to verify signatures using ruby.

[tarcieri]

Use SigningKey.from_keypair

[johndbritton]

This doesn't work for me, it's not a 64 byte keypair, it's a 64 byte signing key only.

Looking through the code it looks like it should be possible to use it according to

ed25519/ext/ed25519_ref10/ed25519_ref10.h

Line 6 in 2448332

#define SECRETKEYBYTES 64

but

ed25519/lib/ed25519.rb

Line 13 in 2448332

KEY_SIZE = 32

restricts to 32 bytes.

I'm using this with https://github.com/sparkle-project/ed25519#usage, which generated our keypair. The signing key is 64 bytes and I'd like to be able to make compatible signatures and verify signatures with Ruby.

I understand if this isn't supported (looks like it) but wonder if it could be supported and what would need to change to get it to work.

[tarcieri]

You'll have to be a little more specific about what you mean by "64 byte signing key only."

Can you describe what you want in terms of this taxonomy of Ed25519 keys:
https://blog.mozilla.org/warner/2011/11/29/ed25519-keys/

It sounds like you might want the original legacy NaCl 20110221 format i.e. a || RH. That is definitely unsupported in current releases, but could potentially be added.

[johndbritton]

You'll have to be a little more specific about what you mean by "64 byte signing key only."

It looks like the library I'm using is following ref10, but stores the private key after hashing rather than providing the seed: orlp/ed25519#10 (comment)

Thanks for your help figuring out the issue.

[tarcieri]

That looks like the a || RH format. More generally what you're referring to is sometimes described as an "expanded secret key" (EDIT: updated the issue title to reflect this).

There are some specific reasons why that format is somewhat problematic, especially for keys supplied directly by users, which is why the "seed"-based API was introduced in ref10 (the blog post I linked goes into some of the tradeoffs).

Namely the "edwards25519" elliptic curve has a somewhat unusual property called a "cofactor" which has to do with the order of the curve group (i.e. number of points which satisfy the curve equation) not being prime. This can potentially lead to something called small subgroup attacks, which have occurred in practice with the "edwards25519" elliptic curve (although not necessarily in conjunction with the "Ed25519" signature algorithm).

In the ref10 implementation of the Ed25519 signature algorithm this is solved by "clamping", another name for "set/clear bits" step in the diagram above. Per this comment, this is how it's implemented (which is general across both Ed25519 and X25519):

orlp/ed25519#10 (comment)

    private_key[0] &= 248;
    private_key[31] &= 63;
    private_key[31] |= 64;

If we do want to support this, the scalar portion of the expanded secret key needs to be "re-clamped", which is to say it's safer to process an "expanded secret key" as LH || RH in the diagram above, performing the "clamping" on any provided LH input to derive a.

All that said, this crate has two backends (CRuby and JRuby), neither of which have direct support for either the LH || RH or a || RH forms of an "expanded secret key". Both instead work off of the "keypair" format internally (seed || A), computing the following on demand:

LH || RH = SHA512(k)
a = clamp(LH)

Changing the internal key format used by both backends is possible, but a fairly significant amount of work for what is effectively a non-standard key format.

[johndbritton]

@tarcieri Really appreciate the detailed explanation.

More generally what you're referring to is sometimes described as an "expanded secret key"

From the article

If you care more about the speed of operations than storage space, you’d want to store the expanded versions. Or, you might want to store as little information as possible, and accept the performance penalty of re-deriving things when necessary. Different implementations choose different tradeoffs.

I spent a good part of my afternoon hacking on this and came to the conclusion that it's not possible for me to use the key that I have with this library because it's an expanded key and I don't have a record of the seed that was used to generate it. If I somehow could obtain the seed (which I think is impossible at this point), I could use that with this library.

Is that logically correct?

I went down the path of regenerating a new key pair using this library and it works fine for me with the new key pair, the problem is many users already have the old public key and will use that to verify my signature and I don't have an easy way to cause them to update the public key they are presently storing.

Changing the internal key format used by both backends is possible, but a fairly significant amount of work for what is effectively a non-standard key format.

It would seem to me that it should be possible to use almost all of the same implementation and just skip the derivation step when an expanded key is provided.

Would you be open to such a contribution? If so, could you give a bit of direction on what you'd expect the API to look like?

[tarcieri]

it's an expanded key and I don't have a record of the seed that was used to generate it. If I somehow could obtain the seed (which I think is impossible at this point), I could use that with this library.

Is that logically correct?

Yes, the backend implementations this crate uses always expand the "seed" value immediately prior to use. This is a deliberately one-way operation (SHA-512) so there's no way to reverse it other than a brute force search.

To work with an "expanded secret key" both the C and Java backends would need to be modified to support expanded secret keys.

It would seem to me that it should be possible to use almost all of the same implementation and just skip the derivation step when an expanded key is provided.

Would you be open to such a contribution?

Yes, but you'll need to be prepared to modify both C and Java code. It won't be trivial, but I'm open to it.

If so, could you give a bit of direction on what you'd expect the API to look like?

Both backends presently compute the "expanded secret key" on-the-fly whenever signing is performed. So what you'd be implementing would be a new class for representing the expanded secret key and computing it from SigningKey.

More concretely, I'd suggest adding a class like SigningKeyExpanded or ExpandedSigningKey, and then modifying both the C and Java backends to use it.

To keep things simple and as close to the current code as possible, I'd suggest that ExpandedSigningKey contains the raw output of SHA512(seed). That is to say, don't try to do the bit-twiddling / "clamping" in advance since both backends already do that on the fly, and if you screw up and accidentally pass an "unclamped" value where a "clamped" one is expected, it could be a potential security vulnerability. "Clamping" is a cheap bit-twiddling operation, so it's easily done on-the-fly.

From there, you just need to remove the SHA-512 operation the backends are currently performing and have them operate on the SigningKeyExpanded/ExpandedSigningKey directly. You can also implement the conversion from SigningKey to the expanded key in pure Ruby using Digest::SHA512.

[johndbritton]

Yes, but you'll need to be prepared to modify both C and Java code. It won't be trivial, but I'm open to it.

I'm going to give it a go on just the C implementation first as I have zero experience with Java or JRuby. If I manage to get the C implementation to work, I'll attempt Java after that.

[johndbritton]

I spent a bunch of time working on this. I feel like I understand the algorithm and this library a lot better now, but I wasn't able to actually implement what we want because I'm pretty rusty with C.

Separately, I was able to find a way to seamlessly replace my public keys so I've gone ahead and generated new keys with this library and saved the seed.

Ultimately, it seems like this isn't as necessary as I thought it was for me, but if you want the feature and can give me a bit more guidance I'd be happy to work on it some more.

[tarcieri]

Unless you're particularly interested in the feature, this library is otherwise "complete" and in maintenance mode only, so I'd prefer not rocking the boat with invasive changes unless they're strongly desired.

[johndbritton]

@tarcieri Makes sense, it's not necessary for me anymore. Even though we didn't get this added, you've been a huge help.

Here's my resolution johndbritton/teleport#84