• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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