CRYPTO_SIGN(3MONOCYPHER)

CRYPTO_SIGN(3MONOCYPHER) | 3MONOCYPHER | CRYPTO_SIGN(3MONOCYPHER)

# NAME

`crypto_eddsa_sign`, `crypto_eddsa_check`, `crypto_eddsa_key_pair`, `crypto_eddsa_to_x25519`, `crypto_eddsa_trim_scalar`, `crypto_eddsa_reduce`, `crypto_eddsa_mul_add`, `crypto_eddsa_scalarbase`, `crypto_eddsa_check_equation` — public key signatures

# SYNOPSIS

`#include <monocypher.h>`

void
`crypto_eddsa_sign`(uint8_t signature[64], const uint8_t secret_key[64], const uint8_t *message, size_t message_size);

int
`crypto_eddsa_check`(const uint8_t signature[64], const uint8_t public_key[32], const uint8_t *message, size_t message_size);

void
`crypto_eddsa_key_pair`(uint8_t secret_key[64], uint8_t public_key[32], uint8_t seed[32]);

void
`crypto_eddsa_to_x25519`(uint8_t x25519[32], const uint8_t eddsa[32]);

void
`crypto_eddsa_trim_scalar`(uint8_t out[32], const uint8_t in[32]);

void
`crypto_eddsa_reduce`(uint8_t reduced[32], const uint8_t expanded[64]);

void
`crypto_eddsa_mul_add`(uint8_t r[32], const uint8_t a[32], const uint8_t b[32], const uint8_t c[32]);

void
`crypto_eddsa_scalarbase`(uint8_t point[32], const uint8_t scalar[32]);

int
`crypto_eddsa_check_equation`(const uint8_t Rs[64], const uint8_t A[32], const uint8_t h[32]);

# DESCRIPTION

## High level API

`crypto_eddsa_sign`() and `crypto_eddsa_check`() provide EdDSA public key signatures and verification. `crypto_eddsa_key_pair`() computes the private and public keys from a random seed. They use BLAKE2b as the underlying hash, which allows monocypher to be more compact, but is not compatible with Ed25519. If you need Ed25519 compatibility, use crypto_ed25519_sign(3monocypher) instead. The arguments are:

seed
  Random seed, freshly generated and used only once. It is automatically wiped by `crypto_eddsa_key_pair`(). See intro(3monocypher) about random number generation (use your operating system's random number generator).
signature
  The signature.
secret_key
  A secret key generated by `crypto_eddsa_key_pair`(), known only to you. Internally the secret key is made up of the seed and the public key. They are bundled together to avoid misuse, and should be treated as a unit.
public_key
  The associated public key, known to everyone.
message
  The message to sign.
message_size
  Length of message, in bytes.

signature and message may overlap.

`crypto_eddsa_sign`() signs a message with secret_key.

`crypto_eddsa_check`() checks that a given signature is genuine. Meaning, only someone who had the private key could have signed the message. It does not run in constant time. It does not have to in most threat models because nothing is secret: everyone knows the public key, and the signature and message are rarely secret. If the message needs to be secret, use a key exchange protocol involving crypto_x25519(3monocypher) and then crypto_aead_lock(3monocypher) instead.

## Conversion to X25519

`crypto_eddsa_to_x25519`() Converts and EdDSA public key to an X25519 public key. Note that it ignores the sign of the x coordinate of the EdDSA input. The inverse operation is provided by crypto_x25519_to_eddsa(3monocypher).

## Low-level building blocks

`crypto_eddsa_trim_scalar`(), `crypto_eddsa_reduce`(), `crypto_eddsa_mul_add`(), `crypto_eddsa_scalarbase`(), and `crypto_eddsa_check_equation`() provide low-level functionality to implement specialised APIs and variants of EdDSA. Monocypher uses them to implement all high-level EdDSA and Ed25519 functions.

These functions are dangerous, using them directly allows many kinds of catastrophic misuse. The following descriptions are kept concise and technical on purpose. If you do not understand them, do not not use those functions.

`crypto_eddsa_trim_scalar`() reads a 256-bit number represented in little-endian, and outputs the same number modified as follows: the 3 least significant bits are cleared; the most significant bit is cleared; and the second most significant bit is set.

`crypto_eddsa_reduce`() reads a 512-bit number represented in little-endian, and outputs the same number reduced modulo the prime order of Curve25519.

`crypto_eddsa_mul_add`() reads three 256-bit numbers represented in little-endian, and outputs a × b + c, reduced modulo the prime order of Curve25519.

`crypto_eddsa_scalarbase`() reads a 256-bit number represented in little-endian, and outputs the result of the scalar multiplication between that number and the twisted Edwards base point of Curve25519. The output uses the same compressed representation as regular EdDSA public keys: the most significant bit represents the sign of the x coordinate (1 if it is odd, 0 if it is even), and the 255 other bits represent the y coordinate in little-endian.

`crypto_eddsa_check_equation`() reads a signature Rs, a public_key A, and hash h, then checks the following:

- A and R are both on the curve.
- s is below the prime order of Curve25519.
- [8×s]B = [8]R + [8×h]A

It then returns 0 if all checks hold, -1 otherwise. Note that A and R are allowed to have low order, and their encoding is allowed to be non-canonical. This function does not run in constant time, do not use it with secret inputs.

# RETURN VALUES

## High level API

`crypto_eddsa_key_pair`() and `crypto_eddsa_sign`() return nothing.

`crypto_eddsa_check`() returns 0 for legitimate signatures and -1 for forgeries.

## Conversion to X25519

`crypto_eddsa_to_x25519`() returns nothing.

## Low-level building blocks

`crypto_eddsa_trim_scalar`(), `crypto_eddsa_reduce`(), `crypto_eddsa_mul_add`(), and `crypto_eddsa_scalarbase`() return nothing.

`crypto_eddsa_check_equation`() returns 0 for legitimate signatures and -1 for forgeries.

# EXAMPLES

The following examples assume the existence of `arc4random_buf`(), which fills the given buffer with cryptographically secure random bytes. If `arc4random_buf`() does not exist on your system, see intro(3monocypher) for advice about how to generate cryptographically secure random bytes.

Generate a key pair:

    uint8_t seed[32]; /* Random seed         */
    uint8_t sk  [64]; /* secret key          */
    uint8_t pk  [32]; /* Matching public key */
    arc4random_buf(seed, 32);
    crypto_eddsa_key_pair(sk, pk, seed);
    /* Wipe the secret key if it is no longer needed */
    /* The seed is wiped automatically               */
    crypto_wipe(sk, 32);

Sign a message:

    uint8_t       sk       [64]; /* Secret key from above          */
    const uint8_t message  [11] = "Lorem ipsu"; /* Message to sign */
    uint8_t       signature[64];
    crypto_eddsa_sign(signature, sk, message, 10);
    /* Wipe the secret key if it is no longer needed */
    crypto_wipe(sk, 32);

Check the above:

    const uint8_t pk       [32]; /* Their public key              */
    const uint8_t message  [11] = "Lorem ipsu"; /* Signed message */
    const uint8_t signature[64]; /* Signature to check            */
    if (crypto_eddsa_check(signature, pk, message, 10)) {
    	/* Message is corrupted, do not trust it */
    } else {
    	/* Message is genuine */
    }

Implement XEdDSA (signatures with X25519 keys normally used for key exchange) with the low-level building blocks

    #include <monocypher.h>
    #include <monocypher-ed25519.h>
    #include <string.h>

    void xed25519_sign(uint8_t signature[64],
                       const uint8_t secret_key[32],
                       const uint8_t random[64],
                       const uint8_t *message, size_t message_size)
    {
    	static const uint8_t zero   [32] = {0};
    	static const uint8_t minus_1[32] = {
    		0xec, 0xd3, 0xf5, 0x5c, 0x1a, 0x63, 0x12, 0x58,
    		0xd6, 0x9c, 0xf7, 0xa2, 0xde, 0xf9, 0xde, 0x14,
    		0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    		0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x10,
    	};
    	static const uint8_t prefix[32] = {
    		0xfe, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
    		0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
    		0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
    		0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
    	};

    	/* Key pair (a, A) */
    	uint8_t A[32];  /* XEdDSA public key  */
    	uint8_t a[32];  /* XEdDSA private key */
    	crypto_eddsa_trim_scalar(a, secret_key);
    	crypto_eddsa_scalarbase(A, a);
    	int is_negative = A[31] & 0x80; /* Retrieve sign bit */
    	A[31] &= 0x7f;                  /* Clear sign bit    */
    	if (is_negative) {
    		/* a = -a */
    		crypto_eddsa_mul_add(a, a, minus_1, zero);
    	}

    	/* Secret nonce r */
    	uint8_t r[64];
    	crypto_sha512_ctx ctx;
    	crypto_sha512_init  (&ctx);
    	crypto_sha512_update(&ctx, prefix , 32);
    	crypto_sha512_update(&ctx, a      , 32);
    	crypto_sha512_update(&ctx, message, message_size);
    	crypto_sha512_update(&ctx, random , 64);
    	crypto_sha512_final (&ctx, r);
    	crypto_eddsa_reduce(r, r);

    	/* First half of the signature R */
    	uint8_t R[32];
    	crypto_eddsa_scalarbase(R, r);

    	/* hash(R || A || M) */
    	uint8_t H[64];
    	crypto_sha512_init  (&ctx);
    	crypto_sha512_update(&ctx, R      , 32);
    	crypto_sha512_update(&ctx, A      , 32);
    	crypto_sha512_update(&ctx, message, message_size);
    	crypto_sha512_final (&ctx, H);
    	crypto_eddsa_reduce(H, H);

    	/* Signature */
    	memcpy(signature, R, 32);
    	crypto_eddsa_mul_add(signature + 32, a, H, r);

    	/* Wipe secrets (A, R, and H are not secret) */
    	crypto_wipe(a, 32);
    	crypto_wipe(r, 32);
    }

    int xed25519_verify(const uint8_t signature[64],
                        const uint8_t public_key[32],
                        const uint8_t *message, size_t message_size)
    {
    	/* Convert X25519 key to EdDSA */
    	uint8_t A[32];
    	crypto_x25519_to_eddsa(A, public_key);

    	/* hash(R || A || M) */
    	uint8_t H[64];
    	crypto_sha512_ctx ctx;
    	crypto_sha512_init  (&ctx);
    	crypto_sha512_update(&ctx, signature, 32);
    	crypto_sha512_update(&ctx, A        , 32);
    	crypto_sha512_update(&ctx, message  , message_size);
    	crypto_sha512_final (&ctx, H);
    	crypto_eddsa_reduce(H, H);

    	/* Check signature */
    	return crypto_eddsa_check_equation(signature, A, H);
    }

# SEE ALSO

crypto_blake2b(3monocypher), crypto_x25519(3monocypher), crypto_aead_lock(3monocypher), intro(3monocypher)

# STANDARDS

`crypto_eddsa_sign`(), `crypto_eddsa_check`(), and `crypto_eddsa_key_pair`() implement PureEdDSA with Curve25519 and BLAKE2b, as described in RFC 8032. This is the same as Ed25519, with BLAKE2b instead of SHA-512.

`crypto_eddsa_trim_scalar`(), `crypto_eddsa_reduce`(), `crypto_eddsa_mul_add`(), `crypto_eddsa_scalarbase`(), and `crypto_eddsa_check_equation`() can be used to implement any Curve25519 based EdDSA variant, including Ed25519 and Ed25519ph.

# HISTORY

The `crypto_sign`(), `crypto_check`(), and `crypto_sign_public_key`() functions appeared in Monocypher 0.2.

Starting with Monocypher 2.0.5, modified signatures abusing the inherent signature malleability property of EdDSA now cause a non-zero return value of `crypto_check`(); in prior versions, such signatures would be accepted.

A critical security vulnerability that caused all-zero signatures to be accepted was introduced in Monocypher 0.3; it was fixed in Monocypher 1.1.1 and 2.0.4.

In Monocypher 4.0.0 `crypto_eddsa_trim_scalar`(), `crypto_eddsa_reduce`(), `crypto_eddsa_mul_add`(), `crypto_eddsa_scalarbase`(), and `crypto_eddsa_check_equation`() were added, and the incremental and custom hash API removed. The main interface was also reworked to avoid misuse, and `crypto_eddsa_key_pair`() replaced `crypto_sign_public_key`().

# CAVEATS

Monocypher does not perform any input validation. Any deviation from the specified input and output length ranges results in undefined behaviour. Make sure your inputs are correct.

# SECURITY CONSIDERATIONS

## Signature malleability

Signature malleability is the ability of an attacker to produce a valid signature with knowledge of only an existing signature and the public key. Monocypher prevents that by checking the encoding of the signature, and guarantees that generating new signatures requires the private key.

On the other hand, EdDSA signatures are not unique like cryptographic hashes. The signing procedure is deterministic by specification and `crypto_eddsa_sign`() follows this specification. However, someone with the private key can generate arbitrarily many valid, canonical, and different signatures of the same message. Because of this, never assume that signatures are unique.

## Fault injection and power analysis

Fault injection (also known as glitching) and power analysis may be used to manipulate the resulting signature and recover the secret key in some cases. This requires hardware access. We can try to mitigate this attack by prefixing all hashes a random data block, in a construction similar to Ed25519ctx. Note that there may still be other power-related side channels (such as if the CPU leaks information when an operation overflows a register) that must be considered.

February 25, 2023 | Debian