CRYPTO_SIGN(3MONOCYPHER)

3MONOCYPHER

CRYPTO_SIGN(3MONOCYPHER)

NAME

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. The arguments are:

seed: Random seed, freshly generated and used only once. It is automatically wiped by crypto_eddsa_key_pair(). See intro() 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() and then crypto_aead_lock() 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().

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() 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);
}

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