From afa925b680ff5a18c1e5f922219fb766fb891c69 Mon Sep 17 00:00:00 2001 From: Loup Vaillant Date: Sun, 19 Feb 2023 18:22:07 +0100 Subject: [PATCH] Document how to implement XEdDSA This serves two purposes: 1. Providing a real use case for the low-level API. 2. Confirming that Monocypher does support XEdDSA. Closes ##227 --- doc/crypto_eddsa_sign.3monocypher | 218 ++++++++++++++++++++++-------- 1 file changed, 164 insertions(+), 54 deletions(-) diff --git a/doc/crypto_eddsa_sign.3monocypher b/doc/crypto_eddsa_sign.3monocypher index d8ba699..a1c0a3c 100644 --- a/doc/crypto_eddsa_sign.3monocypher +++ b/doc/crypto_eddsa_sign.3monocypher @@ -50,7 +50,7 @@ .\" with this software. If not, see .\" .\" -.Dd July 9, 2022 +.Dd February 19, 2023 .Dt CRYPTO_SIGN 3MONOCYPHER .Os .Sh NAME @@ -120,6 +120,7 @@ .Fa "const uint8_t h[32]" .Fc .Sh DESCRIPTION +.Ss High level API .Fn crypto_eddsa_sign and .Fn crypto_eddsa_check @@ -180,58 +181,7 @@ and then .Xr crypto_aead_lock 3monocypher instead. .Pp -.Sh RETURN VALUES -.Fn crypto_eddsa_key_pair -and -.Fn crypto_eddsa_sign -return nothing. -.Pp -.Fn crypto_eddsa_check -returns 0 for legitimate messages and -1 for forgeries. -.Sh EXAMPLES -The following examples assume the existence of -.Fn arc4random_buf , -which fills the given buffer with cryptographically secure random bytes. -If -.Fn arc4random_buf -does not exist on your system, see -.Xr intro 3monocypher -for advice about how to generate cryptographically secure random bytes. -.Pp -Generate a key pair: -.Bd -literal -offset indent -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); -.Ed -.Pp -Sign a message: -.Bd -literal -offset indent -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); -.Ed -.Pp -Check the above: -.Bd -literal -offset indent -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 */ -} -.Ed -.Sh CONVERSIONS to X25519 +.Ss Conversion to X25519 .Fn crypto_eddsa_to_x25519 Converts and EdDSA public key to an X25519 public key. Note that it ignores the sign of the @@ -239,7 +189,7 @@ Note that it ignores the sign of the coordinate of the EdDSA input. The inverse operation is provided by .Xr crypto_x25519_to_eddsa 3monocypher . -.Sh LOW LEVEL BUILDING BLOCKS +.Ss Low-level building blocks .Fn crypto_eddsa_trim_scalar , .Fn crypto_eddsa_reduce , .Fn crypto_eddsa_mul_add , @@ -323,6 +273,166 @@ are allowed to have low order, and their encoding is allowed to be non-canonical. .Sy This function does not run in constant time , do not use it with secret inputs. +.Sh RETURN VALUES +.Ss High level API +.Fn crypto_eddsa_key_pair +and +.Fn crypto_eddsa_sign +return nothing. +.Pp +.Fn crypto_eddsa_check +returns 0 for legitimate signatures and -1 for forgeries. +.Ss Conversion to X25519 +.Fn crypto_eddsa_to_x25519 +returns nothing. +.Ss Low-level building blocks +.Fn crypto_eddsa_trim_scalar , +.Fn crypto_eddsa_reduce , +.Fn crypto_eddsa_mul_add , +and +.Fn crypto_eddsa_scalarbase +return nothing. +.Pp +.Fn crypto_eddsa_check_equation +returns 0 for legitimate signatures and -1 for forgeries. +.Sh EXAMPLES +The following examples assume the existence of +.Fn arc4random_buf , +which fills the given buffer with cryptographically secure random bytes. +If +.Fn arc4random_buf +does not exist on your system, see +.Xr intro 3monocypher +for advice about how to generate cryptographically secure random bytes. +.Pp +Generate a key pair: +.Bd -literal -offset indent +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); +.Ed +.Pp +Sign a message: +.Bd -literal -offset indent +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); +.Ed +.Pp +Check the above: +.Bd -literal -offset indent +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 */ +} +.Ed +.Pp +Implement XEdDSA +(signatures with X25519 keys normally used for key exchange) +with the low-level building blocks +.Bd -literal -offset indent +#include +#include +#include + +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); +} +.Ed .Sh SEE ALSO .Xr crypto_blake2b 3monocypher , .Xr crypto_x25519 3monocypher , -- 2.47.3