ED25519 compatibility

[CodeAndWeb]

Hi,

I used this implementation of ED25519 for signing software updates - which seems to be reasonably well. https://github.com/orlp/ed25519

I now decided to switch to php's ED25519 implementation which uses libsodium for signing. The issue now is that it seems that signing the same message delivers different signatures even so the keys are identical.

I wonder why it is like that. Both algorithms claim to be based on SUPERCOP "ref10" - but why am I not getting them to match?

crypto_sign_verify() and crypto_sign_verify_detached() are only designed to verify signatures computed using crypto_sign() and crypto_sign_detached().

Is there a way to get libsodium to emulate the same behavior as the other implementation? As I said: I am using this to validate software updated by signing new versions of my programs. The implementation is already in the field and I can't take that back. So the only way would be to make PHP behave in the same way.

Does this mean that I have to pad the original input to make the buffer size divisible by 64?

The original NaCl crypto_sign_open() implementation overwrote 64 bytes after the message, whereas the libsodium implementation doesn't write past the end of the message.

When looking at the signing code, it seems that the difference between sodium and the other implementation is that sodium calls

    _crypto_sign_ed25519_clamp(az);

See https://github.com/orlp/ed25519/blob/master/src/sign.c vs https://github.com/jedisct1/libsodium/blob/master/src/libsodium/crypto_sign/ed25519/ref10/sign.c

Is this maybe the reason for the difference?

Best
Andreas

[jedisct1]

This creates a signature using your library and verifies it with libsodium. Works as expected.

int main()
{
    unsigned char seed[32];
    unsigned char sig[64];
    unsigned char pk[32], sk[32];

    ed25519_create_seed(seed);
    ed25519_create_keypair(pk, sk, seed);
    ed25519_sign(sig, (const void *) "test", 4, pk, sk);

    if (sodium_init() != 0) {
        return 1;
    }
    if (crypto_sign_verify_detached(sig, (const void *) "test", 4, pk) != 0) {
        return 1;
    }
    puts("OK");

    return 0;
}

[CodeAndWeb]

Thanks for the reply. I've done some further testing.

It currently looks like the keys generated with the PHP version (based on libsodium) don't work with the C implementation - but it works in the other direction. When creating key pairs in C they work in both implementations.

PHP 8.1.0 (cli) (built: Nov 28 2021 01:44:44) (NTS), HomeBrew, running on macOS.

<?php
$keyPair = sodium_crypto_sign_keypair();  
$private_key = sodium_crypto_sign_secretkey($keyPair);  
$public_key = sodium_crypto_sign_publickey($keyPair);  
$message = "Hello!";  
$signature = sodium_crypto_sign_detached($message, $private_key);  

printf("private:   %s\n", sodium_bin2base64($private_key, SODIUM_BASE64_VARIANT_ORIGINAL));
printf("public:    %s\n", sodium_bin2base64($public_key, SODIUM_BASE64_VARIANT_ORIGINAL));
printf("signature: %s\n", sodium_bin2base64($signature, SODIUM_BASE64_VARIANT_ORIGINAL));

Generates this when signing "Hello!" (6 characters, no terminal 0)

private:   8KN8TVE9GnchuDpbN8j1z8h051EMDo8nHCBaR96ZhS3pUQxA/lRJEZJm7ovc+GPViHkhqHHBaNYf3jylRxxKrg==
public:    6VEMQP5USRGSZu6L3Phj1Yh5IahxwWjWH948pUccSq4=
signature: cSZ21NrgZa7ilNEKh4EAsf5jvjY+ngfU8qWVA7LyexUGcwLZlmd392IhHWaHiPBW7NYlYL+jdfy2BzHpKUWCBQ==

Using the same input and key pair in the C library delivers this signature:

9s8JSZycKCwRYy9EaxCoUYI5rgqDwVh8uzIVqxdWT2BsGvmx5ZYz10hBFhNa/VSBIdD6MgkmeUop0qf7BF2oDg==

So validation fails.

Creating a key pair with the C implementation delivers for example

Public  key: JRfovO8+vEt5p9Afp25ziqxVf9iHeQhkdQfOzsJxWbc=
Private key: MCKcMa5UnKsY1YKKR0sh9UDW49KJQHmS4IsOpJGdoUGeyUz88VIQRu+aK5KY8t9P3Hrgf7GsW9582IrzPNbQlA==

And signing "Hello!" in both cases delivers the signature

02NWOP/tlQHgz+zufmmHW0LMAx8pKWsfsxsp/yunFE8MGJANKkSGWL4x8ImwAyboro+UZ7HsguO39uBOtHvkBQ==

[CodeAndWeb]

Some more investigation... it seems that not the hashing/signing itself is cause of the trouble but the keys.

The C implementation gives me for example this key pair:

private: 0EjxnPbre3Y3263aOnk3nBxMErXqiWbajsL2/5bqulKGn4teieoX1h9PY8FioEv9LXtRjDetx8XHlySSQfv0+g==
public: 0P3cJ4LJtFyo6jwAUdSMXkTrndgEXZDZySusnnTGarw=

Using the private key with the PHP (libsodium) to calculate a public key gives me a completely different key:

public: hp+LXonqF9YfT2PBYqBL/S17UYw3rcfFx5ckkkH79Po=

This means that the private keys don't seem to be compatible. ?!?!

I've now created 100 keys with PHP and C. I am using the binary data and AND/OR each set together to see which bits are set or not.
The mask created from the C implementation and the PHP implementation differ:

OR:
C:   f8ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
php: ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff

AND:
C:   00000000000000000000000000000000000000000000000000000000000000400000000000000000000000000000000000000000000000000000000000000000
php: 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

So some bits in the C implementation are always 0 (byte 0 and 31) whereas they might be set in libsodium. On the other hand, some bits are never 0 in the C implementation (byte 31) but can be 0 in the php implementation.

This corresponds to the setup in crypto_sign_ed25519_seed_keypair in libsodium:

sk[0] &= 248;
sk[31] &= 127;
sk[31] |= 64;

which is practically the same as in the C implementation

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

So libsodium should create the same keys as the C implementation. However the PHP implementation (also using libsodium) does something different.

The keys created in C are a subset of the PHP keys since they contain some bits fixed to 0 or 1. I now wonder why deriving a public key from the private key in php now delivers a different key...

[jedisct1]

The format of the secret key is seed || public_key.

That's what virtually all implementations do, including libsodium. Storing the seed, not its hash, is also what's documented in the RFC.

The library you used appears to return H(seed) as the secret key instead. There's no way to use that with other implementations. At least not without modifying them.

[CodeAndWeb]

That's what virtually all implementations do, including libsodium. Storing the seed, not its hash, is also what's documented in the RFC.

I see - that's the first memmove in your crypto_sign_ed25519_seed_keypair- it overwrites the secret key with the seed. The second appends the public key.

From my observations:

It currently looks like the keys generated with the PHP version (based on libsodium) don't work with the C implementation - but it works in the other direction. When creating key pairs in C they work in both implementations.

So the validation works because the private key is not used for the verification, right?
But signing with PHP doesn't work because the private key is faulty.

Ok - thanks a lot for your time! That really helped me understand the issue. Even so it's sad that there is no solution for my problem :-(

[orlp]

As a counterpoint to this, note that my library is older than libsodium, and predates the mentioned RFC by 4 years. I chose this API because it means I don't have to re-hash the seed on every invocation without a further state struct. If you wish to be compatible with libsodium you have to keep the seed around separately.