Disallow Ed448 signature malleability
[openssl.git] / crypto / ec / curve448 / eddsa.c
1 /*
2  * Copyright 2017-2018 The OpenSSL Project Authors. All Rights Reserved.
3  * Copyright 2015-2016 Cryptography Research, Inc.
4  *
5  * Licensed under the OpenSSL license (the "License").  You may not use
6  * this file except in compliance with the License.  You can obtain a copy
7  * in the file LICENSE in the source distribution or at
8  * https://www.openssl.org/source/license.html
9  *
10  * Originally written by Mike Hamburg
11  */
12 #include <string.h>
13 #include <openssl/crypto.h>
14 #include <openssl/evp.h>
15 #include "curve448_lcl.h"
16 #include "word.h"
17 #include "ed448.h"
18 #include "internal/numbers.h"
19
20 #define COFACTOR 4
21
22 static c448_error_t oneshot_hash(uint8_t *out, size_t outlen,
23                                  const uint8_t *in, size_t inlen)
24 {
25     EVP_MD_CTX *hashctx = EVP_MD_CTX_new();
26
27     if (hashctx == NULL)
28         return C448_FAILURE;
29
30     if (!EVP_DigestInit_ex(hashctx, EVP_shake256(), NULL)
31             || !EVP_DigestUpdate(hashctx, in, inlen)
32             || !EVP_DigestFinalXOF(hashctx, out, outlen)) {
33         EVP_MD_CTX_free(hashctx);
34         return C448_FAILURE;
35     }
36
37     EVP_MD_CTX_free(hashctx);
38     return C448_SUCCESS;
39 }
40
41 static void clamp(uint8_t secret_scalar_ser[EDDSA_448_PRIVATE_BYTES])
42 {
43     secret_scalar_ser[0] &= -COFACTOR;
44     secret_scalar_ser[EDDSA_448_PRIVATE_BYTES - 1] = 0;
45     secret_scalar_ser[EDDSA_448_PRIVATE_BYTES - 2] |= 0x80;
46 }
47
48 static c448_error_t hash_init_with_dom(EVP_MD_CTX *hashctx, uint8_t prehashed,
49                                        uint8_t for_prehash,
50                                        const uint8_t *context,
51                                        size_t context_len)
52 {
53     const char *dom_s = "SigEd448";
54     uint8_t dom[2];
55
56     if (context_len > UINT8_MAX)
57         return C448_FAILURE;
58
59     dom[0] = (uint8_t)(2 - (prehashed == 0 ? 1 : 0)
60                        - (for_prehash == 0 ? 1 : 0));
61     dom[1] = (uint8_t)context_len;
62
63     if (!EVP_DigestInit_ex(hashctx, EVP_shake256(), NULL)
64             || !EVP_DigestUpdate(hashctx, dom_s, strlen(dom_s))
65             || !EVP_DigestUpdate(hashctx, dom, sizeof(dom))
66             || !EVP_DigestUpdate(hashctx, context, context_len))
67         return C448_FAILURE;
68
69     return C448_SUCCESS;
70 }
71
72 /* In this file because it uses the hash */
73 c448_error_t c448_ed448_convert_private_key_to_x448(
74                             uint8_t x[X448_PRIVATE_BYTES],
75                             const uint8_t ed [EDDSA_448_PRIVATE_BYTES])
76 {
77     /* pass the private key through oneshot_hash function */
78     /* and keep the first X448_PRIVATE_BYTES bytes */
79     return oneshot_hash(x, X448_PRIVATE_BYTES, ed,
80                         EDDSA_448_PRIVATE_BYTES);
81 }
82
83 c448_error_t c448_ed448_derive_public_key(
84                         uint8_t pubkey[EDDSA_448_PUBLIC_BYTES],
85                         const uint8_t privkey[EDDSA_448_PRIVATE_BYTES])
86 {
87     /* only this much used for keygen */
88     uint8_t secret_scalar_ser[EDDSA_448_PRIVATE_BYTES];
89     curve448_scalar_t secret_scalar;
90     unsigned int c;
91     curve448_point_t p;
92
93     if (!oneshot_hash(secret_scalar_ser, sizeof(secret_scalar_ser), privkey,
94                       EDDSA_448_PRIVATE_BYTES))
95         return C448_FAILURE;
96
97     clamp(secret_scalar_ser);
98
99     curve448_scalar_decode_long(secret_scalar, secret_scalar_ser,
100                                 sizeof(secret_scalar_ser));
101
102     /*
103      * Since we are going to mul_by_cofactor during encoding, divide by it
104      * here. However, the EdDSA base point is not the same as the decaf base
105      * point if the sigma isogeny is in use: the EdDSA base point is on
106      * Etwist_d/(1-d) and the decaf base point is on Etwist_d, and when
107      * converted it effectively picks up a factor of 2 from the isogenies.  So
108      * we might start at 2 instead of 1.
109      */
110     for (c = 1; c < C448_EDDSA_ENCODE_RATIO; c <<= 1)
111         curve448_scalar_halve(secret_scalar, secret_scalar);
112
113     curve448_precomputed_scalarmul(p, curve448_precomputed_base, secret_scalar);
114
115     curve448_point_mul_by_ratio_and_encode_like_eddsa(pubkey, p);
116
117     /* Cleanup */
118     curve448_scalar_destroy(secret_scalar);
119     curve448_point_destroy(p);
120     OPENSSL_cleanse(secret_scalar_ser, sizeof(secret_scalar_ser));
121
122     return C448_SUCCESS;
123 }
124
125 c448_error_t c448_ed448_sign(
126                         uint8_t signature[EDDSA_448_SIGNATURE_BYTES],
127                         const uint8_t privkey[EDDSA_448_PRIVATE_BYTES],
128                         const uint8_t pubkey[EDDSA_448_PUBLIC_BYTES],
129                         const uint8_t *message, size_t message_len,
130                         uint8_t prehashed, const uint8_t *context,
131                         size_t context_len)
132 {
133     curve448_scalar_t secret_scalar;
134     EVP_MD_CTX *hashctx = EVP_MD_CTX_new();
135     c448_error_t ret = C448_FAILURE;
136     curve448_scalar_t nonce_scalar;
137     uint8_t nonce_point[EDDSA_448_PUBLIC_BYTES] = { 0 };
138     unsigned int c;
139     curve448_scalar_t challenge_scalar;
140
141     if (hashctx == NULL)
142         return C448_FAILURE;
143
144     {
145         /*
146          * Schedule the secret key, First EDDSA_448_PRIVATE_BYTES is serialised
147          * secret scalar,next EDDSA_448_PRIVATE_BYTES bytes is the seed.
148          */
149         uint8_t expanded[EDDSA_448_PRIVATE_BYTES * 2];
150
151         if (!oneshot_hash(expanded, sizeof(expanded), privkey,
152                           EDDSA_448_PRIVATE_BYTES))
153             goto err;
154         clamp(expanded);
155         curve448_scalar_decode_long(secret_scalar, expanded,
156                                     EDDSA_448_PRIVATE_BYTES);
157
158         /* Hash to create the nonce */
159         if (!hash_init_with_dom(hashctx, prehashed, 0, context, context_len)
160                 || !EVP_DigestUpdate(hashctx,
161                                      expanded + EDDSA_448_PRIVATE_BYTES,
162                                      EDDSA_448_PRIVATE_BYTES)
163                 || !EVP_DigestUpdate(hashctx, message, message_len)) {
164             OPENSSL_cleanse(expanded, sizeof(expanded));
165             goto err;
166         }
167         OPENSSL_cleanse(expanded, sizeof(expanded));
168     }
169
170     /* Decode the nonce */
171     {
172         uint8_t nonce[2 * EDDSA_448_PRIVATE_BYTES];
173
174         if (!EVP_DigestFinalXOF(hashctx, nonce, sizeof(nonce)))
175             goto err;
176         curve448_scalar_decode_long(nonce_scalar, nonce, sizeof(nonce));
177         OPENSSL_cleanse(nonce, sizeof(nonce));
178     }
179
180     {
181         /* Scalarmul to create the nonce-point */
182         curve448_scalar_t nonce_scalar_2;
183         curve448_point_t p;
184
185         curve448_scalar_halve(nonce_scalar_2, nonce_scalar);
186         for (c = 2; c < C448_EDDSA_ENCODE_RATIO; c <<= 1)
187             curve448_scalar_halve(nonce_scalar_2, nonce_scalar_2);
188
189         curve448_precomputed_scalarmul(p, curve448_precomputed_base,
190                                        nonce_scalar_2);
191         curve448_point_mul_by_ratio_and_encode_like_eddsa(nonce_point, p);
192         curve448_point_destroy(p);
193         curve448_scalar_destroy(nonce_scalar_2);
194     }
195
196     {
197         uint8_t challenge[2 * EDDSA_448_PRIVATE_BYTES];
198
199         /* Compute the challenge */
200         if (!hash_init_with_dom(hashctx, prehashed, 0, context, context_len)
201                 || !EVP_DigestUpdate(hashctx, nonce_point, sizeof(nonce_point))
202                 || !EVP_DigestUpdate(hashctx, pubkey, EDDSA_448_PUBLIC_BYTES)
203                 || !EVP_DigestUpdate(hashctx, message, message_len)
204                 || !EVP_DigestFinalXOF(hashctx, challenge, sizeof(challenge)))
205             goto err;
206
207         curve448_scalar_decode_long(challenge_scalar, challenge,
208                                     sizeof(challenge));
209         OPENSSL_cleanse(challenge, sizeof(challenge));
210     }
211
212     curve448_scalar_mul(challenge_scalar, challenge_scalar, secret_scalar);
213     curve448_scalar_add(challenge_scalar, challenge_scalar, nonce_scalar);
214
215     OPENSSL_cleanse(signature, EDDSA_448_SIGNATURE_BYTES);
216     memcpy(signature, nonce_point, sizeof(nonce_point));
217     curve448_scalar_encode(&signature[EDDSA_448_PUBLIC_BYTES],
218                            challenge_scalar);
219
220     curve448_scalar_destroy(secret_scalar);
221     curve448_scalar_destroy(nonce_scalar);
222     curve448_scalar_destroy(challenge_scalar);
223
224     ret = C448_SUCCESS;
225  err:
226     EVP_MD_CTX_free(hashctx);
227     return ret;
228 }
229
230 c448_error_t c448_ed448_sign_prehash(
231                         uint8_t signature[EDDSA_448_SIGNATURE_BYTES],
232                         const uint8_t privkey[EDDSA_448_PRIVATE_BYTES],
233                         const uint8_t pubkey[EDDSA_448_PUBLIC_BYTES],
234                         const uint8_t hash[64], const uint8_t *context,
235                         size_t context_len)
236 {
237     return c448_ed448_sign(signature, privkey, pubkey, hash, 64, 1, context,
238                            context_len);
239 }
240
241 c448_error_t c448_ed448_verify(
242                     const uint8_t signature[EDDSA_448_SIGNATURE_BYTES],
243                     const uint8_t pubkey[EDDSA_448_PUBLIC_BYTES],
244                     const uint8_t *message, size_t message_len,
245                     uint8_t prehashed, const uint8_t *context,
246                     uint8_t context_len)
247 {
248     curve448_point_t pk_point, r_point;
249     c448_error_t error;
250     curve448_scalar_t challenge_scalar;
251     curve448_scalar_t response_scalar;
252     /* Order in little endian format */
253     static const uint8_t order[] = {
254         0xF3, 0x44, 0x58, 0xAB, 0x92, 0xC2, 0x78, 0x23, 0x55, 0x8F, 0xC5, 0x8D,
255         0x72, 0xC2, 0x6C, 0x21, 0x90, 0x36, 0xD6, 0xAE, 0x49, 0xDB, 0x4E, 0xC4,
256         0xE9, 0x23, 0xCA, 0x7C, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
257         0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
258         0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0x3F, 0x00
259     };
260     int i;
261
262     /*
263      * Check that s (second 57 bytes of the sig) is less than the order. Both
264      * s and the order are in little-endian format. This can be done in
265      * variable time, since if this is not the case the signature if publicly
266      * invalid.
267      */
268     for (i = EDDSA_448_PUBLIC_BYTES - 1; i >= 0; i--) {
269         if (signature[i + EDDSA_448_PUBLIC_BYTES] > order[i])
270             return C448_FAILURE;
271         if (signature[i + EDDSA_448_PUBLIC_BYTES] < order[i])
272             break;
273     }
274     if (i < 0)
275         return C448_FAILURE;
276
277     error =
278         curve448_point_decode_like_eddsa_and_mul_by_ratio(pk_point, pubkey);
279
280     if (C448_SUCCESS != error)
281         return error;
282
283     error =
284         curve448_point_decode_like_eddsa_and_mul_by_ratio(r_point, signature);
285     if (C448_SUCCESS != error)
286         return error;
287
288     {
289         /* Compute the challenge */
290         EVP_MD_CTX *hashctx = EVP_MD_CTX_new();
291         uint8_t challenge[2 * EDDSA_448_PRIVATE_BYTES];
292
293         if (hashctx == NULL
294                 || !hash_init_with_dom(hashctx, prehashed, 0, context,
295                                        context_len)
296                 || !EVP_DigestUpdate(hashctx, signature, EDDSA_448_PUBLIC_BYTES)
297                 || !EVP_DigestUpdate(hashctx, pubkey, EDDSA_448_PUBLIC_BYTES)
298                 || !EVP_DigestUpdate(hashctx, message, message_len)
299                 || !EVP_DigestFinalXOF(hashctx, challenge, sizeof(challenge))) {
300             EVP_MD_CTX_free(hashctx);
301             return C448_FAILURE;
302         }
303
304         EVP_MD_CTX_free(hashctx);
305         curve448_scalar_decode_long(challenge_scalar, challenge,
306                                     sizeof(challenge));
307         OPENSSL_cleanse(challenge, sizeof(challenge));
308     }
309     curve448_scalar_sub(challenge_scalar, curve448_scalar_zero,
310                         challenge_scalar);
311
312     curve448_scalar_decode_long(response_scalar,
313                                 &signature[EDDSA_448_PUBLIC_BYTES],
314                                 EDDSA_448_PRIVATE_BYTES);
315
316     /* pk_point = -c(x(P)) + (cx + k)G = kG */
317     curve448_base_double_scalarmul_non_secret(pk_point,
318                                               response_scalar,
319                                               pk_point, challenge_scalar);
320     return c448_succeed_if(curve448_point_eq(pk_point, r_point));
321 }
322
323 c448_error_t c448_ed448_verify_prehash(
324                     const uint8_t signature[EDDSA_448_SIGNATURE_BYTES],
325                     const uint8_t pubkey[EDDSA_448_PUBLIC_BYTES],
326                     const uint8_t hash[64], const uint8_t *context,
327                     uint8_t context_len)
328 {
329     return c448_ed448_verify(signature, pubkey, hash, 64, 1, context,
330                              context_len);
331 }
332
333 int ED448_sign(uint8_t *out_sig, const uint8_t *message, size_t message_len,
334                const uint8_t public_key[57], const uint8_t private_key[57],
335                const uint8_t *context, size_t context_len)
336 {
337     return c448_ed448_sign(out_sig, private_key, public_key, message,
338                            message_len, 0, context, context_len)
339         == C448_SUCCESS;
340 }
341
342 int ED448_verify(const uint8_t *message, size_t message_len,
343                  const uint8_t signature[114], const uint8_t public_key[57],
344                  const uint8_t *context, size_t context_len)
345 {
346     return c448_ed448_verify(signature, public_key, message, message_len, 0,
347                              context, (uint8_t)context_len) == C448_SUCCESS;
348 }
349
350 int ED448ph_sign(uint8_t *out_sig, const uint8_t hash[64],
351                  const uint8_t public_key[57], const uint8_t private_key[57],
352                  const uint8_t *context, size_t context_len)
353 {
354     return c448_ed448_sign_prehash(out_sig, private_key, public_key, hash,
355                                    context, context_len) == C448_SUCCESS;
356
357 }
358
359 int ED448ph_verify(const uint8_t hash[64], const uint8_t signature[114],
360                    const uint8_t public_key[57], const uint8_t *context,
361                    size_t context_len)
362 {
363     return c448_ed448_verify_prehash(signature, public_key, hash, context,
364                                      (uint8_t)context_len) == C448_SUCCESS;
365 }
366
367 int ED448_public_from_private(uint8_t out_public_key[57],
368                               const uint8_t private_key[57])
369 {
370     return c448_ed448_derive_public_key(out_public_key, private_key)
371         == C448_SUCCESS;
372 }