1 /*############################################################################
2 # Copyright 2016-2017 Intel Corporation
3 #
4 # Licensed under the Apache License, Version 2.0 (the "License");
5 # you may not use this file except in compliance with the License.
6 # You may obtain a copy of the License at
7 #
8 # http://www.apache.org/licenses/LICENSE-2.0
9 #
10 # Unless required by applicable law or agreed to in writing, software
11 # distributed under the License is distributed on an "AS IS" BASIS,
12 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 # See the License for the specific language governing permissions and
14 # limitations under the License.
15 ############################################################################*/
16
17 /*!
18 * \file
19 * \brief Elliptic curve group implementation.
20 */
21
22 #include "epid/common/math/ecgroup.h"
23 #include <string.h>
24 #include "epid/common/1.1/types.h"
25 #include "epid/common/math/hash.h"
26 #include "epid/common/math/src/bignum-internal.h"
27 #include "epid/common/math/src/ecgroup-internal.h"
28 #include "epid/common/math/src/finitefield-internal.h"
29 #include "epid/common/src/endian_convert.h"
30 #include "epid/common/src/memory.h"
31 #include "ext/ipp/include/ippcp.h"
32 #include "ext/ipp/include/ippcpdefs.h"
33
34 /// Handle SDK Error with Break
35 #define BREAK_ON_EPID_ERROR(ret) \
36 if (kEpidNoErr != (ret)) { \
37 break; \
38 } /// Handle Ipp Errors with Break
39 #define BREAK_ON_IPP_ERROR(sts, ret) \
40 { \
41 IppStatus temp_sts = (sts); \
42 if (ippStsNoErr != temp_sts) { \
43 if (ippStsContextMatchErr == temp_sts) { \
44 (ret) = kEpidMathErr; \
45 } else { \
46 (ret) = kEpidBadArgErr; \
47 } \
48 break; \
49 } \
50 }
51
NewEcGroup(FiniteField const * ff,FfElement const * a,FfElement const * b,FfElement const * x,FfElement const * y,BigNum const * order,BigNum const * cofactor,EcGroup ** g)52 EpidStatus NewEcGroup(FiniteField const* ff, FfElement const* a,
53 FfElement const* b, FfElement const* x,
54 FfElement const* y, BigNum const* order,
55 BigNum const* cofactor, EcGroup** g) {
56 EpidStatus result = kEpidNoErr;
57 IppsGFpECState* state = NULL;
58 OctStr scratch_buffer = NULL;
59 EcGroup* grp = NULL;
60 do {
61 IppStatus ipp_status;
62 int stateSize = 0;
63 int scratch_size = 0;
64 IppBNU order_bnu;
65 IppBNU cofactor_bnu;
66 int order_bnu_size;
67 int cofactor_bnu_size;
68 IppsBigNumSGN sgn;
69 // validate input pointers
70 if (!ff || !a || !b || !x || !y || !order || !cofactor || !g) {
71 result = kEpidBadArgErr;
72 break;
73 }
74 if (ff->element_len != a->element_len ||
75 ff->element_len != b->element_len ||
76 ff->element_len != x->element_len ||
77 ff->element_len != y->element_len) {
78 result = kEpidBadArgErr;
79 break;
80 }
81
82 // construct the ECPrimeField
83 ipp_status = ippsGFpECGetSize(ff->ipp_ff, &stateSize);
84 if (ippStsNoErr != ipp_status) {
85 if (ippStsSizeErr == ipp_status) {
86 result = kEpidBadArgErr;
87 } else {
88 result = kEpidMathErr;
89 }
90 break;
91 }
92
93 grp = (EcGroup*)SAFE_ALLOC(sizeof(EcGroup));
94 if (!grp) {
95 result = kEpidMemAllocErr;
96 break;
97 }
98
99 state = (IppsGFpECState*)SAFE_ALLOC(stateSize);
100 if (!state) {
101 result = kEpidMemAllocErr;
102 break;
103 }
104
105 ipp_status = ippsRef_BN(&sgn, &order_bnu_size, &order_bnu, order->ipp_bn);
106 order_bnu_size /= sizeof(CHAR_BIT) * 4;
107 if (ippStsNoErr != ipp_status) {
108 result = kEpidMathErr;
109 break;
110 }
111
112 ipp_status =
113 ippsRef_BN(&sgn, &cofactor_bnu_size, &cofactor_bnu, cofactor->ipp_bn);
114 cofactor_bnu_size /= sizeof(CHAR_BIT) * 4;
115 if (ippStsNoErr != ipp_status) {
116 result = kEpidMathErr;
117 break;
118 }
119
120 ipp_status =
121 ippsGFpECInit(ff->ipp_ff, a->ipp_ff_elem, b->ipp_ff_elem, state);
122 if (ippStsNoErr != ipp_status) {
123 result = kEpidMathErr;
124 break;
125 }
126 ipp_status = ippsGFpECSetSubgroup(x->ipp_ff_elem, y->ipp_ff_elem,
127 order->ipp_bn, cofactor->ipp_bn, state);
128 if (ippStsNoErr != ipp_status) {
129 result = kEpidMathErr;
130 break;
131 }
132
133 // allocate scratch buffer
134 ipp_status = ippsGFpECScratchBufferSize(1, state, &scratch_size);
135 // check return codes
136 if (ippStsNoErr != ipp_status) {
137 // ippStsContextMatchErr not possible since we create the state
138 // in this function
139 result = kEpidMathErr;
140 break;
141 }
142
143 // allocate scratch buffer
144 scratch_buffer = (OctStr)SAFE_ALLOC(scratch_size);
145 if (!scratch_buffer) {
146 result = kEpidMemAllocErr;
147 break;
148 }
149 // Warning: once assigned ground field must never be modified. this was not
150 // made const
151 // to allow the FiniteField structure to be used in context when we want to
152 // modify the parameters.
153 grp->ff = (FiniteField*)ff;
154 grp->ipp_ec = state;
155 grp->scratch_buffer = scratch_buffer;
156 *g = grp;
157 } while (0);
158
159 if (kEpidNoErr != result) {
160 // we had a problem during init, free any allocated memory
161 SAFE_FREE(state);
162 SAFE_FREE(scratch_buffer);
163 SAFE_FREE(grp);
164 }
165 return result;
166 }
167
DeleteEcGroup(EcGroup ** g)168 void DeleteEcGroup(EcGroup** g) {
169 if (!g || !(*g)) {
170 return;
171 }
172 if ((*g)->ipp_ec) {
173 SAFE_FREE((*g)->ipp_ec);
174 (*g)->ipp_ec = NULL;
175 }
176 if ((*g)->scratch_buffer) {
177 SAFE_FREE((*g)->scratch_buffer);
178 (*g)->scratch_buffer = NULL;
179 }
180 SAFE_FREE(*g);
181 *g = NULL;
182 }
183
NewEcPoint(EcGroup const * g,EcPoint ** p)184 EpidStatus NewEcPoint(EcGroup const* g, EcPoint** p) {
185 EpidStatus result = kEpidErr;
186 IppsGFpECPoint* ec_pt_context = NULL;
187 EcPoint* ecpoint = NULL;
188 do {
189 IppStatus sts = ippStsNoErr;
190 int sizeInBytes = 0;
191 // validate inputs
192 if (!g || !p) {
193 result = kEpidBadArgErr;
194 break;
195 } else if (!g->ipp_ec) {
196 result = kEpidBadArgErr;
197 break;
198 }
199 // get size
200 sts = ippsGFpECPointGetSize(g->ipp_ec, &sizeInBytes);
201 if (ippStsContextMatchErr == sts) {
202 result = kEpidBadArgErr;
203 break;
204 } else if (ippStsNoErr != sts) {
205 result = kEpidMathErr;
206 break;
207 }
208 // allocate memory
209 ec_pt_context = (IppsGFpECPoint*)SAFE_ALLOC(sizeInBytes);
210 if (!ec_pt_context) {
211 result = kEpidMemAllocErr;
212 break;
213 }
214 // Initialize
215 sts = ippsGFpECPointInit(NULL, NULL, ec_pt_context, g->ipp_ec);
216 if (ippStsContextMatchErr == sts) {
217 result = kEpidBadArgErr;
218 break;
219 } else if (ippStsNoErr != sts) {
220 result = kEpidMathErr;
221 break;
222 }
223 ecpoint = SAFE_ALLOC(sizeof(EcPoint));
224 if (!ecpoint) {
225 result = kEpidMemAllocErr;
226 break;
227 }
228 if (!g->ff) {
229 result = kEpidBadArgErr;
230 break;
231 }
232 ecpoint->element_len = g->ff->element_len;
233 ecpoint->ipp_ec_pt = ec_pt_context;
234 *p = ecpoint;
235 result = kEpidNoErr;
236 } while (0);
237 if (kEpidNoErr != result) {
238 SAFE_FREE(ec_pt_context);
239 SAFE_FREE(ecpoint);
240 }
241 return result;
242 }
243
DeleteEcPoint(EcPoint ** p)244 void DeleteEcPoint(EcPoint** p) {
245 if (p) {
246 if (*p) {
247 SAFE_FREE((*p)->ipp_ec_pt);
248 }
249 SAFE_FREE(*p);
250 }
251 }
252
253 /// Check and initialize element if it is in elliptic curve group.
254 /*!
255 This is internal function.
256 Takes a value p as input. If p is indeed an element of g, it
257 outputs true, otherwise, it outputs false.
258
259 This is only used to check if input buffer are actually valid
260 elements in group. If p is in g, this fills p and initializes it to
261 internal FfElement format.
262
263 \param[in] g
264 The eliptic curve group in which to perform the check
265 \param[in] p_str
266 Serialized eliptic curve group element to check
267 \param[in] strlen
268 The size of p_str in bytes.
269 \param[out] p
270 Deserialized value of p_str
271 \param[out] in_group
272 Result of the check
273
274 \returns ::EpidStatus
275
276 \see NewEcPoint
277 */
eccontains(EcGroup * g,ConstOctStr p_str,size_t strlen,EcPoint * p,bool * in_group)278 EpidStatus eccontains(EcGroup* g, ConstOctStr p_str, size_t strlen, EcPoint* p,
279 bool* in_group) {
280 EpidStatus result = kEpidErr;
281 IppStatus sts = ippStsNoErr;
282 FiniteField* fp = NULL;
283 FfElement* fp_x = NULL;
284 FfElement* fp_y = NULL;
285 ConstIppOctStr byte_str = (ConstIppOctStr)p_str;
286 IppECResult ec_result = ippECPointIsNotValid;
287 int ipp_half_strlen = (int)strlen / 2;
288
289 if (!g || !p_str || !p || !in_group) {
290 return kEpidBadArgErr;
291 }
292 if (!g->ff || !g->ipp_ec || !p->ipp_ec_pt) {
293 return kEpidBadArgErr;
294 }
295
296 if (INT_MAX < strlen || strlen <= 0 || strlen & 0x1) {
297 return kEpidBadArgErr;
298 }
299
300 do {
301 size_t i = 0;
302 // if the string is all zeros then we take it as point at infinity
303 for (i = 0; i < strlen; i++) {
304 if (0 != byte_str[i]) {
305 break;
306 }
307 }
308 if (i >= strlen) {
309 // p_str is point at infinity! Set it and we are done
310 sts = ippsGFpECSetPointAtInfinity(p->ipp_ec_pt, g->ipp_ec);
311 // check return codes
312 if (ippStsNoErr != sts) {
313 if (ippStsContextMatchErr == sts)
314 result = kEpidBadArgErr;
315 else
316 result = kEpidMathErr;
317 break;
318 }
319 *in_group = true;
320 result = kEpidNoErr;
321 break;
322 }
323 // get finite field
324 fp = g->ff;
325 // create element X
326 result = NewFfElement(fp, &fp_x);
327 if (kEpidNoErr != result) {
328 break;
329 }
330
331 // create element Y
332 result = NewFfElement(fp, &fp_y);
333 if (kEpidNoErr != result) {
334 break;
335 }
336
337 // set element X data
338 result = SetFfElementOctString(byte_str, ipp_half_strlen, fp_x, fp);
339 if (kEpidNoErr != result) {
340 break;
341 }
342
343 // set element Y data
344 result = SetFfElementOctString(byte_str + ipp_half_strlen, ipp_half_strlen,
345 fp_y, fp);
346 if (kEpidNoErr != result) {
347 break;
348 }
349
350 // set point from elements
351 sts = ippsGFpECSetPoint(fp_x->ipp_ff_elem, fp_y->ipp_ff_elem, p->ipp_ec_pt,
352 g->ipp_ec);
353 // check return codes
354 if (ippStsNoErr != sts) {
355 if (ippStsContextMatchErr == sts)
356 result = kEpidBadArgErr;
357 else
358 result = kEpidMathErr;
359 break;
360 }
361
362 // verify the point is actually on the curve
363 sts = ippsGFpECTstPoint(p->ipp_ec_pt, &ec_result, g->ipp_ec);
364 // check return codes
365 if (ippStsNoErr != sts) {
366 if (ippStsContextMatchErr == sts)
367 result = kEpidBadArgErr;
368 else
369 result = kEpidMathErr;
370 break;
371 }
372 *in_group = (ippECValid == ec_result);
373 result = kEpidNoErr;
374 } while (0);
375
376 DeleteFfElement(&fp_x);
377 DeleteFfElement(&fp_y);
378 return result;
379 }
380
ReadEcPoint(EcGroup * g,ConstOctStr p_str,size_t strlen,EcPoint * p)381 EpidStatus ReadEcPoint(EcGroup* g, ConstOctStr p_str, size_t strlen,
382 EcPoint* p) {
383 EpidStatus result;
384 bool in_group = false;
385
386 if (!g || !p_str || !p) {
387 return kEpidBadArgErr;
388 }
389 if (0 == strlen) {
390 return kEpidBadArgErr;
391 }
392
393 result = eccontains(g, p_str, strlen, p, &in_group);
394 if (kEpidNoErr != result) {
395 return result;
396 }
397 if (in_group == false) {
398 IppStatus sts = ippsGFpECPointInit(NULL, NULL, p->ipp_ec_pt, g->ipp_ec);
399 if (ippStsContextMatchErr == sts) {
400 return kEpidBadArgErr;
401 } else if (ippStsNoErr != sts) {
402 return kEpidMathErr;
403 }
404 return kEpidBadArgErr;
405 }
406 return kEpidNoErr;
407 }
408
WriteEcPoint(EcGroup * g,EcPoint const * p,OctStr p_str,size_t strlen)409 EpidStatus WriteEcPoint(EcGroup* g, EcPoint const* p, OctStr p_str,
410 size_t strlen) {
411 EpidStatus result = kEpidErr;
412 FiniteField* fp = NULL;
413 FfElement* fp_x = NULL;
414 FfElement* fp_y = NULL;
415 IppOctStr byte_str = (IppOctStr)p_str;
416 IppStatus sts = ippStsNoErr;
417 int ipp_half_strlen = (int)strlen / 2;
418
419 if (!g || !p || !p_str) {
420 return kEpidBadArgErr;
421 }
422 if (!g->ff || !g->ipp_ec || !p->ipp_ec_pt) {
423 return kEpidBadArgErr;
424 }
425 if (INT_MAX < strlen) {
426 return kEpidBadArgErr;
427 }
428
429 if (INT_MAX < strlen || strlen <= 0 || strlen & 0x1) {
430 return kEpidBadArgErr;
431 }
432
433 do {
434 // get finite field
435 fp = g->ff;
436
437 // create element X
438 result = NewFfElement(fp, &fp_x);
439 if (kEpidNoErr != result) {
440 break;
441 }
442
443 // create element Y
444 result = NewFfElement(fp, &fp_y);
445 if (kEpidNoErr != result) {
446 break;
447 }
448
449 // get elements from point
450 sts = ippsGFpECGetPoint(p->ipp_ec_pt, fp_x->ipp_ff_elem, fp_y->ipp_ff_elem,
451 g->ipp_ec);
452 // check return codes
453 if (ippStsNoErr != sts) {
454 if (ippStsPointAtInfinity == sts) {
455 memset(p_str, 0, strlen);
456 result = kEpidNoErr;
457 } else if (ippStsContextMatchErr == sts || ippStsOutOfRangeErr == sts) {
458 result = kEpidBadArgErr;
459 } else {
460 result = kEpidMathErr;
461 }
462 break;
463 }
464
465 // get element X data
466 sts = ippsGFpGetElementOctString(fp_x->ipp_ff_elem, byte_str,
467 ipp_half_strlen, fp->ipp_ff);
468 // check return codes
469 if (ippStsNoErr != sts) {
470 if (ippStsContextMatchErr == sts)
471 result = kEpidBadArgErr;
472 else
473 result = kEpidMathErr;
474 break;
475 }
476
477 // get element Y data
478 sts = ippsGFpGetElementOctString(fp_y->ipp_ff_elem,
479 byte_str + ipp_half_strlen,
480 ipp_half_strlen, fp->ipp_ff);
481 // check return codes
482 if (ippStsNoErr != sts) {
483 if (ippStsContextMatchErr == sts)
484 result = kEpidBadArgErr;
485 else
486 result = kEpidMathErr;
487 break;
488 }
489 result = kEpidNoErr;
490 } while (0);
491
492 DeleteFfElement(&fp_x);
493 DeleteFfElement(&fp_y);
494
495 return result;
496 }
497
EcMul(EcGroup * g,EcPoint const * a,EcPoint const * b,EcPoint * r)498 EpidStatus EcMul(EcGroup* g, EcPoint const* a, EcPoint const* b, EcPoint* r) {
499 IppStatus sts = ippStsNoErr;
500 if (!g || !a || !b || !r) {
501 return kEpidBadArgErr;
502 } else if (!g->ff || !g->ipp_ec || !a->ipp_ec_pt || !b->ipp_ec_pt ||
503 !r->ipp_ec_pt) {
504 return kEpidBadArgErr;
505 }
506 if (g->ff->element_len != a->element_len ||
507 g->ff->element_len != b->element_len ||
508 g->ff->element_len != r->element_len) {
509 return kEpidBadArgErr;
510 }
511 // Multiplies elliptic curve points
512 sts = ippsGFpECAddPoint(a->ipp_ec_pt, b->ipp_ec_pt, r->ipp_ec_pt, g->ipp_ec);
513 // Check return codes
514 if (ippStsNoErr != sts) {
515 if (ippStsContextMatchErr == sts)
516 return kEpidBadArgErr;
517 else
518 return kEpidMathErr;
519 }
520 return kEpidNoErr;
521 }
522
EcExp(EcGroup * g,EcPoint const * a,BigNumStr const * b,EcPoint * r)523 EpidStatus EcExp(EcGroup* g, EcPoint const* a, BigNumStr const* b, EcPoint* r) {
524 EpidStatus result = kEpidErr;
525 BigNum* b_bn = NULL;
526 do {
527 IppStatus sts = ippStsNoErr;
528
529 // Check required parameters
530 if (!g || !a || !b || !r) {
531 result = kEpidBadArgErr;
532 break;
533 } else if (!g->ff || !g->ipp_ec || !a->ipp_ec_pt || !r->ipp_ec_pt) {
534 result = kEpidBadArgErr;
535 break;
536 }
537 if (g->ff->element_len != a->element_len ||
538 g->ff->element_len != r->element_len) {
539 result = kEpidBadArgErr;
540 break;
541 }
542
543 // Create and initialize big number element for ipp call
544 result = NewBigNum(sizeof(((BigNumStr*)0)->data.data), &b_bn);
545 if (kEpidNoErr != result) break;
546 result = ReadBigNum(b, sizeof(*b), b_bn);
547 if (kEpidNoErr != result) break;
548 sts = ippsGFpECMulPoint(a->ipp_ec_pt, b_bn->ipp_bn, r->ipp_ec_pt, g->ipp_ec,
549 g->scratch_buffer);
550 if (ippStsNoErr != sts) {
551 if (ippStsContextMatchErr == sts || ippStsRangeErr == sts ||
552 ippStsOutOfRangeErr == sts)
553 result = kEpidBadArgErr;
554 else
555 result = kEpidMathErr;
556 break;
557 }
558 result = kEpidNoErr;
559 } while (0);
560 DeleteBigNum(&b_bn);
561 return result;
562 }
563
EcSscmExp(EcGroup * g,EcPoint const * a,BigNumStr const * b,EcPoint * r)564 EpidStatus EcSscmExp(EcGroup* g, EcPoint const* a, BigNumStr const* b,
565 EcPoint* r) {
566 // call EcExp directly because its implementation is side channel
567 // mitigated already
568 return EcExp(g, a, b, r);
569 }
570
EcMultiExp(EcGroup * g,EcPoint const ** a,BigNumStr const ** b,size_t m,EcPoint * r)571 EpidStatus EcMultiExp(EcGroup* g, EcPoint const** a, BigNumStr const** b,
572 size_t m, EcPoint* r) {
573 EpidStatus result = kEpidErr;
574 BigNum* b_bn = NULL;
575 EcPoint* ecp_t = NULL;
576 size_t i = 0;
577 size_t ii = 0;
578
579 if (!g || !a || !b || !r) {
580 return kEpidBadArgErr;
581 }
582 if (!g->ff || !g->ipp_ec || m <= 0) {
583 return kEpidBadArgErr;
584 }
585
586 // Verify that ec points are not NULL
587 for (i = 0; i < m; i++) {
588 if (!a[i]) {
589 return kEpidBadArgErr;
590 }
591 if (!a[i]->ipp_ec_pt) {
592 return kEpidBadArgErr;
593 }
594 if (g->ff->element_len != a[i]->element_len) {
595 return kEpidBadArgErr;
596 }
597 for (ii = 0; ii < i; ii++) {
598 if (a[i]->element_len != a[ii]->element_len) {
599 return kEpidBadArgErr;
600 }
601 }
602 }
603
604 if (g->ff->element_len != r->element_len) {
605 return kEpidBadArgErr;
606 }
607
608 do {
609 IppStatus sts = ippStsNoErr;
610
611 // Create big number element for ipp call
612 result = NewBigNum(sizeof(((BigNumStr*)0)->data.data), &b_bn);
613 if (kEpidNoErr != result) break;
614 // Create temporal EcPoint element
615 result = NewEcPoint(g, &ecp_t);
616 if (kEpidNoErr != result) break;
617
618 for (i = 0; i < m; i++) {
619 // Initialize big number element for ipp call
620 result = ReadBigNum(b[i], sizeof(BigNumStr), b_bn);
621 if (kEpidNoErr != result) break;
622 sts = ippsGFpECMulPoint(a[i]->ipp_ec_pt, b_bn->ipp_bn, ecp_t->ipp_ec_pt,
623 g->ipp_ec, g->scratch_buffer);
624 if (ippStsNoErr != sts) {
625 if (ippStsContextMatchErr == sts || ippStsRangeErr == sts ||
626 ippStsOutOfRangeErr == sts)
627 result = kEpidBadArgErr;
628 else
629 result = kEpidMathErr;
630 break;
631 }
632 if (i == 0) {
633 sts = ippsGFpECCpyPoint(ecp_t->ipp_ec_pt, r->ipp_ec_pt, g->ipp_ec);
634 if (ippStsNoErr != sts) {
635 result = kEpidMathErr;
636 break;
637 }
638 } else {
639 sts = ippsGFpECAddPoint(ecp_t->ipp_ec_pt, r->ipp_ec_pt, r->ipp_ec_pt,
640 g->ipp_ec);
641 if (ippStsNoErr != sts) {
642 result = kEpidMathErr;
643 break;
644 }
645 }
646 }
647 if (kEpidNoErr != result) break;
648
649 result = kEpidNoErr;
650 } while (0);
651 DeleteBigNum(&b_bn);
652 DeleteEcPoint(&ecp_t);
653
654 return result;
655 }
656
EcMultiExpBn(EcGroup * g,EcPoint const ** a,BigNum const ** b,size_t m,EcPoint * r)657 EpidStatus EcMultiExpBn(EcGroup* g, EcPoint const** a, BigNum const** b,
658 size_t m, EcPoint* r) {
659 EpidStatus result = kEpidErr;
660 EcPoint* ecp_t = NULL;
661 size_t i = 0;
662 size_t ii = 0;
663
664 if (!g || !a || !b || !r) {
665 return kEpidBadArgErr;
666 }
667 if (!g->ff || !g->ipp_ec || m <= 0) {
668 return kEpidBadArgErr;
669 }
670
671 // Verify that ec points are not NULL
672 for (i = 0; i < m; i++) {
673 if (!a[i]) {
674 return kEpidBadArgErr;
675 }
676 if (!a[i]->ipp_ec_pt) {
677 return kEpidBadArgErr;
678 }
679 if (!b[i]) {
680 return kEpidBadArgErr;
681 }
682 if (!b[i]->ipp_bn) {
683 return kEpidBadArgErr;
684 }
685
686 if (g->ff->element_len != a[i]->element_len) {
687 return kEpidBadArgErr;
688 }
689 for (ii = 0; ii < i; ii++) {
690 if (a[i]->element_len != a[ii]->element_len) {
691 return kEpidBadArgErr;
692 }
693 }
694 }
695
696 if (g->ff->element_len != r->element_len) {
697 return kEpidBadArgErr;
698 }
699
700 do {
701 IppStatus sts = ippStsNoErr;
702 // Create temporal EcPoint element
703 result = NewEcPoint(g, &ecp_t);
704 if (kEpidNoErr != result) break;
705
706 for (i = 0; i < m; i++) {
707 sts = ippsGFpECMulPoint(a[i]->ipp_ec_pt, b[i]->ipp_bn, ecp_t->ipp_ec_pt,
708 g->ipp_ec, g->scratch_buffer);
709 if (ippStsNoErr != sts) {
710 if (ippStsContextMatchErr == sts || ippStsRangeErr == sts ||
711 ippStsOutOfRangeErr == sts)
712 result = kEpidBadArgErr;
713 else
714 result = kEpidMathErr;
715 break;
716 }
717 if (i == 0) {
718 sts = ippsGFpECCpyPoint(ecp_t->ipp_ec_pt, r->ipp_ec_pt, g->ipp_ec);
719 if (ippStsNoErr != sts) {
720 result = kEpidMathErr;
721 break;
722 }
723 } else {
724 sts = ippsGFpECAddPoint(ecp_t->ipp_ec_pt, r->ipp_ec_pt, r->ipp_ec_pt,
725 g->ipp_ec);
726 if (ippStsNoErr != sts) {
727 result = kEpidMathErr;
728 break;
729 }
730 }
731 }
732 if (kEpidNoErr != result) break;
733
734 result = kEpidNoErr;
735 } while (0);
736 DeleteEcPoint(&ecp_t);
737
738 return result;
739 }
740
EcSscmMultiExp(EcGroup * g,EcPoint const ** a,BigNumStr const ** b,size_t m,EcPoint * r)741 EpidStatus EcSscmMultiExp(EcGroup* g, EcPoint const** a, BigNumStr const** b,
742 size_t m, EcPoint* r) {
743 // call EcMultiExp directly because its implementation is side channel
744 // mitigated already
745 return EcMultiExp(g, a, b, m, r);
746 }
747
EcGetRandom(EcGroup * g,BitSupplier rnd_func,void * rnd_func_param,EcPoint * r)748 EpidStatus EcGetRandom(EcGroup* g, BitSupplier rnd_func, void* rnd_func_param,
749 EcPoint* r) {
750 IppStatus sts = ippStsNoErr;
751 if (!g || !rnd_func || !r) {
752 return kEpidBadArgErr;
753 }
754 if (!g->ff || !g->ipp_ec || !g->scratch_buffer) {
755 return kEpidBadArgErr;
756 }
757
758 if (g->ff->element_len != r->element_len) {
759 return kEpidBadArgErr;
760 }
761
762 sts =
763 ippsGFpECSetPointRandom(r->ipp_ec_pt, g->ipp_ec, (IppBitSupplier)rnd_func,
764 rnd_func_param, g->scratch_buffer);
765 if (ippStsNoErr != sts) {
766 if (ippStsContextMatchErr == sts) {
767 return kEpidBadArgErr;
768 } else {
769 return kEpidMathErr;
770 }
771 }
772 return kEpidNoErr;
773 }
774
EcInGroup(EcGroup * g,ConstOctStr p_str,size_t strlen,bool * in_group)775 EpidStatus EcInGroup(EcGroup* g, ConstOctStr p_str, size_t strlen,
776 bool* in_group) {
777 EpidStatus result = kEpidErr;
778 EcPoint* p = NULL;
779
780 if (!g || !p_str || !in_group) {
781 return kEpidBadArgErr;
782 }
783 if (!g->ff) {
784 return kEpidBadArgErr;
785 }
786 if (0 == strlen) {
787 return kEpidBadArgErr;
788 }
789
790 if (strlen != sizeof(G1ElemStr) && strlen != sizeof(G2ElemStr)) {
791 *in_group = false;
792 return kEpidBadArgErr;
793 } else {
794 if (strlen == sizeof(G1ElemStr)) {
795 // check finitefield.elementlen with strlen
796 // multiply by 2 for x,y and 4 multiply to convert dword to bytes
797 size_t info_elementLen_in_byte = (g->ff->element_len) * 2 * 4;
798 if (info_elementLen_in_byte != strlen) {
799 *in_group = false;
800 return kEpidBadArgErr;
801 }
802 // check Fq basic and ground degree
803 if (g->ff->basic_degree != 1 || g->ff->ground_degree != 1) {
804 *in_group = false;
805 return kEpidBadArgErr;
806 }
807 }
808 if (strlen == sizeof(G2ElemStr)) {
809 // check info.elementlen with strlen
810 // multiply by 2 for x,y and 4 multiply to convert dword to bytes
811 size_t info_elementLen_in_byte = (g->ff->element_len) * 2 * 4;
812 FiniteField* ground_ff = NULL;
813 if (info_elementLen_in_byte != strlen) {
814 *in_group = false;
815 return kEpidBadArgErr;
816 }
817 // check Fq2 basic and ground degree
818 if (g->ff->basic_degree != 2 || g->ff->ground_degree != 2) {
819 *in_group = false;
820 return kEpidBadArgErr;
821 }
822 // check Fq basic and ground degree
823 ground_ff = g->ff->ground_ff;
824 if (ground_ff == NULL) {
825 *in_group = false;
826 return kEpidBadArgErr;
827 }
828
829 if (ground_ff->basic_degree != 1 || ground_ff->ground_degree != 1) {
830 *in_group = false;
831 return kEpidBadArgErr;
832 }
833 }
834 }
835
836 do {
837 result = NewEcPoint(g, &p);
838 if (kEpidNoErr != result) break;
839
840 result = eccontains(g, p_str, strlen, p, in_group);
841 if (kEpidNoErr != result) break;
842
843 result = kEpidNoErr;
844 } while (0);
845
846 DeleteEcPoint(&p);
847
848 return result;
849 }
850
851 /// The number of attempts to hash a message to an element
852 #define EPID_ECHASH_WATCHDOG (50)
853
854 #pragma pack(1)
855 /// 336 bit octet string
856 typedef struct OctStr336 {
857 unsigned char data[336 / CHAR_BIT]; ///< 336 bit data
858 } OctStr336;
859 #pragma pack()
860
861 /*!
862 Returns the first bit and the next 336 bits of str in octet string.
863
864 \param[in] str hash string
865 \param[in] str_len hash string lengh in bytes
866 \param[out] first_bit first bit of str
867 \param[out] t pointer to the first 336 bits of input str after the first bit
868 \param[in] t_len length of t octet string
869
870 \returns ::EpidStatus
871 */
SplitHashBits(ConstOctStr str,size_t str_len,uint32_t * first_bit,OctStr336 * t)872 static EpidStatus SplitHashBits(ConstOctStr str, size_t str_len,
873 uint32_t* first_bit, OctStr336* t) {
874 // this is 336bits /8 bits per byte = 42 bytes
875 OctStr336 next336 = {0};
876 size_t i = 0;
877 ConstIppOctStr data = (ConstIppOctStr)str;
878 if (!str || !first_bit || !t) return kEpidBadArgErr;
879 if (str_len < sizeof(next336) + 1) {
880 // we need at least 337 bits!
881 return kEpidBadArgErr;
882 }
883 for (i = 0; i < sizeof(next336); i++) {
884 // This is not overflowing since str length was assured to
885 // be at least one byte greater than needed for 336 bits. We are
886 // carrying in the first bit of that byte.
887 uint8_t carry = ((data[i + 1] & 0x80) >> 7);
888 next336.data[i] = (((data[i] << 1) & 0xFF) | carry) & 0xFF;
889 }
890 *first_bit = ((data[0] & 0x80) >> 7);
891 *t = next336;
892 return kEpidNoErr;
893 }
894
Epid11EcHash(EcGroup * g,ConstOctStr msg,size_t msg_len,EcPoint * r)895 EpidStatus Epid11EcHash(EcGroup* g, ConstOctStr msg, size_t msg_len,
896 EcPoint* r) {
897 EpidStatus result = kEpidErr;
898
899 #pragma pack(1)
900 struct {
901 uint32_t msg_len;
902 uint8_t msg[1];
903 }* hash_buf = NULL;
904 #pragma pack()
905 size_t hash_buf_size = 0;
906
907 FfElement* a = NULL;
908 FfElement* b = NULL;
909
910 FfElement* rx = NULL;
911 FfElement* t1 = NULL;
912 FfElement* t2 = NULL;
913
914 BigNum* q = NULL;
915 BigNum* t_bn = NULL;
916 BigNum* h_bn = NULL;
917
918 FiniteField* ff = NULL;
919
920 // check parameters
921 if ((!msg && msg_len > 0) || !r || !g) {
922 return kEpidBadArgErr;
923 }
924 if (!g->ff || !g->ipp_ec || !r->ipp_ec_pt) {
925 return kEpidBadArgErr;
926 }
927
928 if (g->ff->element_len != r->element_len) {
929 return kEpidBadArgErr;
930 }
931
932 // mitigate hash_buf_size and msg_len overflow
933 if (INT_MAX - sizeof(uint32_t) < msg_len) {
934 return kEpidBadArgErr;
935 }
936
937 do {
938 IppStatus sts;
939 uint32_t i = 0;
940 uint32_t ip1 = 0;
941 uint32_t high_bit = 0;
942
943 IppsGFpState* ipp_ff = NULL;
944
945 int sqrt_loop_count = 2 * EPID_ECHASH_WATCHDOG;
946 Sha256Digest message_digest[2] = {0};
947 OctStr336 t = {0};
948
949 hash_buf_size = sizeof(*hash_buf) - sizeof(hash_buf->msg) + msg_len;
950 hash_buf = SAFE_ALLOC(hash_buf_size);
951 if (!hash_buf) {
952 result = kEpidMemAllocErr;
953 break;
954 }
955
956 result = NewBigNum(sizeof(BigNumStr), &h_bn);
957 BREAK_ON_EPID_ERROR(result);
958 sts = ippsGFpECGet(&ipp_ff, 0, 0, g->ipp_ec);
959 BREAK_ON_IPP_ERROR(sts, result);
960 sts = ippsGFpECGetSubgroup(&ipp_ff, 0, 0, 0, h_bn->ipp_bn, g->ipp_ec);
961 BREAK_ON_IPP_ERROR(sts, result);
962 ff = g->ff;
963
964 result = NewFfElement(ff, &a);
965 BREAK_ON_EPID_ERROR(result);
966 result = NewFfElement(ff, &b);
967 BREAK_ON_EPID_ERROR(result);
968 result = NewFfElement(ff, &rx);
969 BREAK_ON_EPID_ERROR(result);
970 result = NewFfElement(ff, &t1);
971 BREAK_ON_EPID_ERROR(result);
972 result = NewFfElement(ff, &t2);
973 BREAK_ON_EPID_ERROR(result);
974 result = NewBigNum(sizeof(t), &t_bn);
975 BREAK_ON_EPID_ERROR(result);
976
977 sts = ippsGFpECGet(0, a->ipp_ff_elem, b->ipp_ff_elem, g->ipp_ec);
978 BREAK_ON_IPP_ERROR(sts, result);
979
980 // compute H = hash (i || m) || Hash (i+1 || m) where (i =ipp32u)
981 // copy variable length message to the buffer to hash
982 if (0 != memcpy_S(hash_buf->msg,
983 hash_buf_size - sizeof(*hash_buf) + sizeof(hash_buf->msg),
984 msg, msg_len)) {
985 result = kEpidErr;
986 break;
987 }
988
989 do {
990 result = kEpidErr;
991
992 // set hash (i || m) portion
993 hash_buf->msg_len = ntohl(i);
994 result = Sha256MessageDigest(hash_buf, hash_buf_size, &message_digest[0]);
995 BREAK_ON_EPID_ERROR(result);
996 // set hash (i+1 || m) portion
997 ip1 = i + 1;
998 hash_buf->msg_len = ntohl(ip1);
999 result = Sha256MessageDigest(hash_buf, hash_buf_size, &message_digest[1]);
1000 BREAK_ON_EPID_ERROR(result);
1001 // let b = first bit of H
1002 // t = next 336bits of H (336 = length(q) + slen)
1003 result =
1004 SplitHashBits(message_digest, sizeof(message_digest), &high_bit, &t);
1005 BREAK_ON_EPID_ERROR(result);
1006 result = ReadBigNum(&t, sizeof(t), t_bn);
1007 BREAK_ON_EPID_ERROR(result);
1008 // compute rx = t mod q (aka prime field based on q)
1009 result = InitFfElementFromBn(ff, t_bn, rx);
1010 BREAK_ON_EPID_ERROR(result);
1011
1012 // t1 = (rx^3 + a*rx + b) mod q
1013 result = FfMul(ff, rx, rx, t1);
1014 BREAK_ON_EPID_ERROR(result);
1015 result = FfMul(ff, t1, rx, t1);
1016 BREAK_ON_EPID_ERROR(result);
1017 result = FfMul(ff, a, rx, t2);
1018 BREAK_ON_EPID_ERROR(result);
1019 result = FfAdd(ff, t1, t2, t1);
1020 BREAK_ON_EPID_ERROR(result);
1021 result = FfAdd(ff, t1, b, t1);
1022 BREAK_ON_EPID_ERROR(result);
1023
1024 // t2 = &ff.sqrt(t1)
1025 result = FfSqrt(ff, t1, t2);
1026 if (kEpidMathQuadraticNonResidueError == result) {
1027 // if sqrt fail set i = i+ 2 and repeat from top
1028 i += 2;
1029 continue;
1030 } else if (kEpidNoErr != result) {
1031 result = kEpidErr;
1032 }
1033 break;
1034 } while (--sqrt_loop_count);
1035
1036 BREAK_ON_EPID_ERROR(result);
1037 // reset to fail to catch other errors
1038 result = kEpidErr;
1039
1040 // y[0] = min (t2, q-t2), y[1] = max(t2, q-t2)
1041 if (0 == high_bit) {
1042 // q-t2 = &ff.neg(t2)
1043 result = FfNeg(ff, t2, t2);
1044 BREAK_ON_EPID_ERROR(result);
1045 }
1046
1047 // Ry = y[b]
1048 sts = ippsGFpECSetPoint(rx->ipp_ff_elem, t2->ipp_ff_elem, r->ipp_ec_pt,
1049 g->ipp_ec);
1050 BREAK_ON_IPP_ERROR(sts, result);
1051 // R = E(&ff).exp(R,h)
1052 sts = ippsGFpECMulPoint(r->ipp_ec_pt, h_bn->ipp_bn, r->ipp_ec_pt, g->ipp_ec,
1053 g->scratch_buffer);
1054 BREAK_ON_IPP_ERROR(sts, result);
1055
1056 result = kEpidNoErr;
1057 } while (0);
1058
1059 SAFE_FREE(hash_buf);
1060 DeleteFfElement(&a);
1061 DeleteFfElement(&b);
1062 DeleteFfElement(&rx);
1063 DeleteFfElement(&t1);
1064 DeleteFfElement(&t2);
1065 DeleteBigNum(&h_bn);
1066 DeleteBigNum(&t_bn);
1067 DeleteBigNum(&q);
1068
1069 return result;
1070 }
1071
EcHash(EcGroup * g,ConstOctStr msg,size_t msg_len,HashAlg hash_alg,EcPoint * r,uint32_t * iterations)1072 EpidStatus EcHash(EcGroup* g, ConstOctStr msg, size_t msg_len, HashAlg hash_alg,
1073 EcPoint* r, uint32_t* iterations) {
1074 IppStatus sts = ippStsNoErr;
1075 IppHashAlgId hash_id;
1076 int ipp_msg_len = 0;
1077 Ipp32u ipp_i = 0;
1078 if (!g || (!msg && msg_len > 0) || !r) {
1079 return kEpidBadArgErr;
1080 } else if (!g->ff || !g->ipp_ec || !r->ipp_ec_pt) {
1081 return kEpidBadArgErr;
1082 }
1083 // because we use ipp function with message length parameter
1084 // defined as "int" we need to verify that input length
1085 // do not exceed INT_MAX to avoid overflow
1086 if (msg_len > INT_MAX) {
1087 return kEpidBadArgErr;
1088 }
1089 ipp_msg_len = (int)msg_len;
1090 if (kSha256 == hash_alg) {
1091 hash_id = ippHashAlg_SHA256;
1092 } else if (kSha384 == hash_alg) {
1093 hash_id = ippHashAlg_SHA384;
1094 } else if (kSha512 == hash_alg) {
1095 hash_id = ippHashAlg_SHA512;
1096 } else if (kSha512_256 == hash_alg) {
1097 hash_id = ippHashAlg_SHA512_256;
1098 } else {
1099 return kEpidHashAlgorithmNotSupported;
1100 }
1101
1102 if (g->ff->element_len != r->element_len) {
1103 return kEpidBadArgErr;
1104 }
1105
1106 do {
1107 sts = ippsGFpECSetPointHash(ipp_i, msg, ipp_msg_len, r->ipp_ec_pt,
1108 g->ipp_ec, hash_id, g->scratch_buffer);
1109 } while (ippStsQuadraticNonResidueErr == sts &&
1110 ipp_i++ < EPID_ECHASH_WATCHDOG);
1111
1112 if (iterations) {
1113 *iterations = (uint32_t)ipp_i;
1114 }
1115
1116 if (ippStsContextMatchErr == sts || ippStsBadArgErr == sts ||
1117 ippStsLengthErr == sts) {
1118 return kEpidBadArgErr;
1119 }
1120 if (ippStsNoErr != sts) {
1121 return kEpidMathErr;
1122 }
1123
1124 return kEpidNoErr;
1125 }
1126
EcMakePoint(EcGroup * g,FfElement const * x,EcPoint * r)1127 EpidStatus EcMakePoint(EcGroup* g, FfElement const* x, EcPoint* r) {
1128 IppStatus sts = ippStsNoErr;
1129 if (!g || !x || !r) {
1130 return kEpidBadArgErr;
1131 }
1132 if (!g->ff || !g->ipp_ec || !x->ipp_ff_elem || !r->ipp_ec_pt) {
1133 return kEpidBadArgErr;
1134 }
1135
1136 if (g->ff->element_len != x->element_len ||
1137 g->ff->element_len != r->element_len) {
1138 return kEpidBadArgErr;
1139 }
1140 sts = ippsGFpECMakePoint(x->ipp_ff_elem, r->ipp_ec_pt, g->ipp_ec);
1141 if (ippStsNoErr != sts) {
1142 if (ippStsContextMatchErr == sts || ippStsQuadraticNonResidueErr == sts ||
1143 ippStsBadArgErr == sts)
1144 return kEpidBadArgErr;
1145 else
1146 return kEpidMathErr;
1147 }
1148 return kEpidNoErr;
1149 }
1150
EcInverse(EcGroup * g,EcPoint const * p,EcPoint * r)1151 EpidStatus EcInverse(EcGroup* g, EcPoint const* p, EcPoint* r) {
1152 IppStatus sts = ippStsNoErr;
1153 if (!g || !p || !r) {
1154 return kEpidBadArgErr;
1155 } else if (!g->ff || !g->ipp_ec || !p->ipp_ec_pt || !r->ipp_ec_pt) {
1156 return kEpidBadArgErr;
1157 }
1158
1159 if (g->ff->element_len != p->element_len ||
1160 g->ff->element_len != r->element_len) {
1161 return kEpidBadArgErr;
1162 }
1163 // Inverses elliptic curve point
1164 sts = ippsGFpECNegPoint(p->ipp_ec_pt, r->ipp_ec_pt, g->ipp_ec);
1165 // Check return codes
1166 if (ippStsNoErr != sts) {
1167 if (ippStsContextMatchErr == sts)
1168 return kEpidBadArgErr;
1169 else
1170 return kEpidMathErr;
1171 }
1172 return kEpidNoErr;
1173 }
1174
EcIsEqual(EcGroup * g,EcPoint const * a,EcPoint const * b,bool * is_equal)1175 EpidStatus EcIsEqual(EcGroup* g, EcPoint const* a, EcPoint const* b,
1176 bool* is_equal) {
1177 IppStatus sts;
1178 IppECResult result;
1179
1180 if (!g || !a || !b || !is_equal) {
1181 return kEpidBadArgErr;
1182 }
1183 if (!g->ff || !g->ipp_ec || !a->ipp_ec_pt || !b->ipp_ec_pt) {
1184 return kEpidBadArgErr;
1185 }
1186 if (g->ff->element_len != a->element_len ||
1187 g->ff->element_len != b->element_len) {
1188 return kEpidBadArgErr;
1189 }
1190
1191 sts = ippsGFpECCmpPoint(a->ipp_ec_pt, b->ipp_ec_pt, &result, g->ipp_ec);
1192 if (ippStsNoErr != sts) {
1193 if (ippStsContextMatchErr == sts) {
1194 return kEpidBadArgErr;
1195 } else {
1196 return kEpidMathErr;
1197 }
1198 }
1199 *is_equal = ippECPointIsEqual == result;
1200
1201 return kEpidNoErr;
1202 }
1203
EcIsIdentity(EcGroup * g,EcPoint const * p,bool * is_identity)1204 EpidStatus EcIsIdentity(EcGroup* g, EcPoint const* p, bool* is_identity) {
1205 IppStatus sts;
1206 IppECResult result;
1207
1208 if (!g || !p || !is_identity) {
1209 return kEpidBadArgErr;
1210 }
1211 if (!g->ff || !g->ipp_ec || !p->ipp_ec_pt) {
1212 return kEpidBadArgErr;
1213 }
1214 if (g->ff->element_len != p->element_len) {
1215 return kEpidBadArgErr;
1216 }
1217
1218 sts = ippsGFpECTstPoint(p->ipp_ec_pt, &result, g->ipp_ec);
1219 if (ippStsNoErr != sts) {
1220 if (ippStsContextMatchErr == sts) {
1221 return kEpidBadArgErr;
1222 } else {
1223 return kEpidMathErr;
1224 }
1225 }
1226 sts = ippsGFpECTstPointInSubgroup(p->ipp_ec_pt, &result, g->ipp_ec,
1227 g->scratch_buffer);
1228 if (ippStsNoErr != sts) {
1229 if (ippStsContextMatchErr == sts) {
1230 return kEpidBadArgErr;
1231 } else {
1232 return kEpidMathErr;
1233 }
1234 }
1235 *is_identity = ippECPointIsAtInfinite == result;
1236
1237 return kEpidNoErr;
1238 }
1239