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 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 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 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 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 */ 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 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 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 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 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 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 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 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 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 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 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 */ 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 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 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 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 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 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 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
