Fix some undefined behaviour in the Curve448 code
[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             || (context_len > 0
67                 && !EVP_DigestUpdate(hashctx, context, context_len)))
68         return C448_FAILURE;
69
70     return C448_SUCCESS;
71 }
72
73 /* In this file because it uses the hash */
74 c448_error_t c448_ed448_convert_private_key_to_x448(
75                             uint8_t x[X448_PRIVATE_BYTES],
76                             const uint8_t ed [EDDSA_448_PRIVATE_BYTES])
77 {
78     /* pass the private key through oneshot_hash function */
79     /* and keep the first X448_PRIVATE_BYTES bytes */
80     return oneshot_hash(x, X448_PRIVATE_BYTES, ed,
81                         EDDSA_448_PRIVATE_BYTES);
82 }
83
84 c448_error_t c448_ed448_derive_public_key(
85                         uint8_t pubkey[EDDSA_448_PUBLIC_BYTES],
86                         const uint8_t privkey[EDDSA_448_PRIVATE_BYTES])
87 {
88     /* only this much used for keygen */
89     uint8_t secret_scalar_ser[EDDSA_448_PRIVATE_BYTES];
90     curve448_scalar_t secret_scalar;
91     unsigned int c;
92     curve448_point_t p;
93
94     if (!oneshot_hash(secret_scalar_ser, sizeof(secret_scalar_ser), privkey,
95                       EDDSA_448_PRIVATE_BYTES))
96         return C448_FAILURE;
97
98     clamp(secret_scalar_ser);
99
100     curve448_scalar_decode_long(secret_scalar, secret_scalar_ser,
101                                 sizeof(secret_scalar_ser));
102
103     /*
104      * Since we are going to mul_by_cofactor during encoding, divide by it
105      * here. However, the EdDSA base point is not the same as the decaf base
106      * point if the sigma isogeny is in use: the EdDSA base point is on
107      * Etwist_d/(1-d) and the decaf base point is on Etwist_d, and when
108      * converted it effectively picks up a factor of 2 from the isogenies.  So
109      * we might start at 2 instead of 1.
110      */
111     for (c = 1; c < C448_EDDSA_ENCODE_RATIO; c <<= 1)
112         curve448_scalar_halve(secret_scalar, secret_scalar);
113
114     curve448_precomputed_scalarmul(p, curve448_precomputed_base, secret_scalar);
115
116     curve448_point_mul_by_ratio_and_encode_like_eddsa(pubkey, p);
117
118     /* Cleanup */
119     curve448_scalar_destroy(secret_scalar);
120     curve448_point_destroy(p);
121     OPENSSL_cleanse(secret_scalar_ser, sizeof(secret_scalar_ser));
122
123     return C448_SUCCESS;
124 }
125
126 c448_error_t c448_ed448_sign(
127                         uint8_t signature[EDDSA_448_SIGNATURE_BYTES],
128                         const uint8_t privkey[EDDSA_448_PRIVATE_BYTES],
129                         const uint8_t pubkey[EDDSA_448_PUBLIC_BYTES],
130                         const uint8_t *message, size_t message_len,
131                         uint8_t prehashed, const uint8_t *context,
132                         size_t context_len)
133 {
134     curve448_scalar_t secret_scalar;
135     EVP_MD_CTX *hashctx = EVP_MD_CTX_new();
136     c448_error_t ret = C448_FAILURE;
137     curve448_scalar_t nonce_scalar;
138     uint8_t nonce_point[EDDSA_448_PUBLIC_BYTES] = { 0 };
139     unsigned int c;
140     curve448_scalar_t challenge_scalar;
141
142     if (hashctx == NULL)
143         return C448_FAILURE;
144
145     {
146         /*
147          * Schedule the secret key, First EDDSA_448_PRIVATE_BYTES is serialised
148          * secret scalar,next EDDSA_448_PRIVATE_BYTES bytes is the seed.
149          */
150         uint8_t expanded[EDDSA_448_PRIVATE_BYTES * 2];
151
152         if (!oneshot_hash(expanded, sizeof(expanded), privkey,
153                           EDDSA_448_PRIVATE_BYTES))
154             goto err;
155         clamp(expanded);
156         curve448_scalar_decode_long(secret_scalar, expanded,
157                                     EDDSA_448_PRIVATE_BYTES);
158
159         /* Hash to create the nonce */
160         if (!hash_init_with_dom(hashctx, prehashed, 0, context, context_len)
161                 || !EVP_DigestUpdate(hashctx,
162                                      expanded + EDDSA_448_PRIVATE_BYTES,
163                                      EDDSA_448_PRIVATE_BYTES)
164                 || (message_len > 0
165                     && !EVP_DigestUpdate(hashctx, message, message_len))) {
166             OPENSSL_cleanse(expanded, sizeof(expanded));
167             goto err;
168         }
169         OPENSSL_cleanse(expanded, sizeof(expanded));
170     }
171
172     /* Decode the nonce */
173     {
174         uint8_t nonce[2 * EDDSA_448_PRIVATE_BYTES];
175
176         if (!EVP_DigestFinalXOF(hashctx, nonce, sizeof(nonce)))
177             goto err;
178         curve448_scalar_decode_long(nonce_scalar, nonce, sizeof(nonce));
179         OPENSSL_cleanse(nonce, sizeof(nonce));
180     }
181
182     {
183         /* Scalarmul to create the nonce-point */
184         curve448_scalar_t nonce_scalar_2;
185         curve448_point_t p;
186
187         curve448_scalar_halve(nonce_scalar_2, nonce_scalar);
188         for (c = 2; c < C448_EDDSA_ENCODE_RATIO; c <<= 1)
189             curve448_scalar_halve(nonce_scalar_2, nonce_scalar_2);
190
191         curve448_precomputed_scalarmul(p, curve448_precomputed_base,
192                                        nonce_scalar_2);
193         curve448_point_mul_by_ratio_and_encode_like_eddsa(nonce_point, p);
194         curve448_point_destroy(p);
195         curve448_scalar_destroy(nonce_scalar_2);
196     }
197
198     {
199         uint8_t challenge[2 * EDDSA_448_PRIVATE_BYTES];
200
201         /* Compute the challenge */
202         if (!hash_init_with_dom(hashctx, prehashed, 0, context, context_len)
203                 || !EVP_DigestUpdate(hashctx, nonce_point, sizeof(nonce_point))
204                 || !EVP_DigestUpdate(hashctx, pubkey, EDDSA_448_PUBLIC_BYTES)
205                 || (message_len > 0
206                     && !EVP_DigestUpdate(hashctx, message, message_len))
207                 || !EVP_DigestFinalXOF(hashctx, challenge, sizeof(challenge)))
208             goto err;
209
210         curve448_scalar_decode_long(challenge_scalar, challenge,
211                                     sizeof(challenge));
212         OPENSSL_cleanse(challenge, sizeof(challenge));
213     }
214
215     curve448_scalar_mul(challenge_scalar, challenge_scalar, secret_scalar);
216     curve448_scalar_add(challenge_scalar, challenge_scalar, nonce_scalar);
217
218     OPENSSL_cleanse(signature, EDDSA_448_SIGNATURE_BYTES);
219     memcpy(signature, nonce_point, sizeof(nonce_point));
220     curve448_scalar_encode(&signature[EDDSA_448_PUBLIC_BYTES],
221                            challenge_scalar);
222
223     curve448_scalar_destroy(secret_scalar);
224     curve448_scalar_destroy(nonce_scalar);
225     curve448_scalar_destroy(challenge_scalar);
226
227     ret = C448_SUCCESS;
228  err:
229     EVP_MD_CTX_free(hashctx);
230     return ret;
231 }
232
233 c448_error_t c448_ed448_sign_prehash(
234                         uint8_t signature[EDDSA_448_SIGNATURE_BYTES],
235                         const uint8_t privkey[EDDSA_448_PRIVATE_BYTES],
236                         const uint8_t pubkey[EDDSA_448_PUBLIC_BYTES],
237                         const uint8_t hash[64], const uint8_t *context,
238                         size_t context_len)
239 {
240     return c448_ed448_sign(signature, privkey, pubkey, hash, 64, 1, context,
241                            context_len);
242 }
243
244 c448_error_t c448_ed448_verify(
245                     const uint8_t signature[EDDSA_448_SIGNATURE_BYTES],
246                     const uint8_t pubkey[EDDSA_448_PUBLIC_BYTES],
247                     const uint8_t *message, size_t message_len,
248                     uint8_t prehashed, const uint8_t *context,
249                     uint8_t context_len)
250 {
251     curve448_point_t pk_point, r_point;
252     c448_error_t error =
253         curve448_point_decode_like_eddsa_and_mul_by_ratio(pk_point, pubkey);
254     curve448_scalar_t challenge_scalar;
255     curve448_scalar_t response_scalar;
256     unsigned int c;
257
258     if (C448_SUCCESS != error)
259         return error;
260
261     error =
262         curve448_point_decode_like_eddsa_and_mul_by_ratio(r_point, signature);
263     if (C448_SUCCESS != error)
264         return error;
265
266     {
267         /* Compute the challenge */
268         EVP_MD_CTX *hashctx = EVP_MD_CTX_new();
269         uint8_t challenge[2 * EDDSA_448_PRIVATE_BYTES];
270
271         if (hashctx == NULL
272                 || !hash_init_with_dom(hashctx, prehashed, 0, context,
273                                        context_len)
274                 || !EVP_DigestUpdate(hashctx, signature, EDDSA_448_PUBLIC_BYTES)
275                 || !EVP_DigestUpdate(hashctx, pubkey, EDDSA_448_PUBLIC_BYTES)
276                 || !EVP_DigestUpdate(hashctx, message, message_len)
277                 || !EVP_DigestFinalXOF(hashctx, challenge, sizeof(challenge))) {
278             EVP_MD_CTX_free(hashctx);
279             return C448_FAILURE;
280         }
281
282         EVP_MD_CTX_free(hashctx);
283         curve448_scalar_decode_long(challenge_scalar, challenge,
284                                     sizeof(challenge));
285         OPENSSL_cleanse(challenge, sizeof(challenge));
286     }
287     curve448_scalar_sub(challenge_scalar, curve448_scalar_zero,
288                         challenge_scalar);
289
290     curve448_scalar_decode_long(response_scalar,
291                                 &signature[EDDSA_448_PUBLIC_BYTES],
292                                 EDDSA_448_PRIVATE_BYTES);
293
294     for (c = 1; c < C448_EDDSA_DECODE_RATIO; c <<= 1)
295         curve448_scalar_add(response_scalar, response_scalar, response_scalar);
296
297     /* pk_point = -c(x(P)) + (cx + k)G = kG */
298     curve448_base_double_scalarmul_non_secret(pk_point,
299                                               response_scalar,
300                                               pk_point, challenge_scalar);
301     return c448_succeed_if(curve448_point_eq(pk_point, r_point));
302 }
303
304 c448_error_t c448_ed448_verify_prehash(
305                     const uint8_t signature[EDDSA_448_SIGNATURE_BYTES],
306                     const uint8_t pubkey[EDDSA_448_PUBLIC_BYTES],
307                     const uint8_t hash[64], const uint8_t *context,
308                     uint8_t context_len)
309 {
310     return c448_ed448_verify(signature, pubkey, hash, 64, 1, context,
311                              context_len);
312 }
313
314 int ED448_sign(uint8_t *out_sig, const uint8_t *message, size_t message_len,
315                const uint8_t public_key[57], const uint8_t private_key[57],
316                const uint8_t *context, size_t context_len)
317 {
318     return c448_ed448_sign(out_sig, private_key, public_key, message,
319                            message_len, 0, context, context_len)
320         == C448_SUCCESS;
321 }
322
323 int ED448_verify(const uint8_t *message, size_t message_len,
324                  const uint8_t signature[114], const uint8_t public_key[57],
325                  const uint8_t *context, size_t context_len)
326 {
327     return c448_ed448_verify(signature, public_key, message, message_len, 0,
328                              context, (uint8_t)context_len) == C448_SUCCESS;
329 }
330
331 int ED448ph_sign(uint8_t *out_sig, const uint8_t hash[64],
332                  const uint8_t public_key[57], const uint8_t private_key[57],
333                  const uint8_t *context, size_t context_len)
334 {
335     return c448_ed448_sign_prehash(out_sig, private_key, public_key, hash,
336                                    context, context_len) == C448_SUCCESS;
337
338 }
339
340 int ED448ph_verify(const uint8_t hash[64], const uint8_t signature[114],
341                    const uint8_t public_key[57], const uint8_t *context,
342                    size_t context_len)
343 {
344     return c448_ed448_verify_prehash(signature, public_key, hash, context,
345                                      (uint8_t)context_len) == C448_SUCCESS;
346 }
347
348 int ED448_public_from_private(uint8_t out_public_key[57],
349                               const uint8_t private_key[57])
350 {
351     return c448_ed448_derive_public_key(out_public_key, private_key)
352         == C448_SUCCESS;
353 }