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