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 Epid11VerifyBasicSig implementation. 20 */ 21 #include <stdio.h> 22 #include <string.h> 23 #include "epid/common/math/src/bignum-internal.h" 24 #include "epid/common/src/memory.h" 25 #include "epid/verifier/1.1/api.h" 26 #include "epid/verifier/1.1/src/context.h" 27 /// Handle SDK Error with Break 28 #define BREAK_ON_EPID_ERROR(ret) \ 29 if (kEpidNoErr != (ret)) { \ 30 break; \ 31 } 32 33 /// Count of elements in array 34 #define COUNT_OF(A) (sizeof(A) / sizeof((A)[0])) 35 36 /// Convert bit size into 32-bit words 37 #ifndef BITS2BYTES 38 #define BITS2BYTES(n) ((((n) + 7) / 8)) 39 #endif 40 41 /// The EPID11 "sf" value must never be larger than 2**593 42 #define EPID11_SF_MAX_SIZE_BITS (593) 43 44 EpidStatus Epid11VerifyBasicSig(Epid11VerifierCtx const* ctx, 45 Epid11BasicSignature const* sig, 46 void const* msg, size_t msg_len) { 47 EpidStatus res = kEpidNoErr; 48 49 // Epid11 G1 elements 50 EcPoint* T1 = NULL; 51 EcPoint* T2 = NULL; 52 EcPoint* R1 = NULL; 53 EcPoint* R2 = NULL; 54 EcPoint* t1 = NULL; 55 EcPoint* t2 = NULL; 56 57 // Epid11 GT elements 58 FfElement* R4 = NULL; 59 FfElement* t3 = NULL; 60 61 // Epid11 G3 elements 62 EcPoint* B = NULL; 63 EcPoint* K = NULL; 64 EcPoint* R3 = NULL; 65 EcPoint* t5 = NULL; 66 67 BigNum* c_bn = NULL; 68 BigNum* sa_bn = NULL; 69 BigNum* sb_bn = NULL; 70 BigNum* nc_bn = NULL; 71 BigNum* salpha_bn = NULL; 72 BigNum* sbeta_bn = NULL; 73 BigNum* nsx_bn = NULL; 74 BigNum* sf_bn = NULL; 75 BigNum* sf_tick_bn = NULL; 76 BigNum* nc_tick_bn = NULL; 77 BigNum* syalpha_bn = NULL; 78 79 Sha256Digest c_hash = {0}; 80 81 if (!ctx || !sig) return kEpidBadArgErr; 82 if (!msg && (0 != msg_len)) { 83 // if message is non-empty it must have both length and content 84 return kEpidBadArgErr; 85 } 86 if (msg_len > UINT_MAX) return kEpidBadArgErr; 87 if (!ctx->epid11_params || !ctx->pub_key) return kEpidBadArgErr; 88 89 do { 90 bool cmp_result = false; 91 BigNumStr nc_str = {0}; 92 // handy shorthands: 93 EcGroup* G1 = ctx->epid11_params->G1; 94 EcGroup* G3 = ctx->epid11_params->G3; 95 FiniteField* GT = ctx->epid11_params->GT; 96 BigNum* p_bn = ctx->epid11_params->p; 97 BigNum* p_tick_bn = ctx->epid11_params->p_tick; 98 EcPoint* g1 = ctx->epid11_params->g1; 99 EcPoint* g2 = ctx->epid11_params->g2; 100 EcPoint* w = ctx->pub_key->w; 101 Epid11CommitValues commit_values = ctx->commit_values; 102 EcPoint* basename_hash = ctx->basename_hash; 103 104 if (!G1 || !G3 || !GT || !p_bn || !p_tick_bn || !g1 || !g2 || !w) { 105 res = kEpidBadArgErr; 106 BREAK_ON_EPID_ERROR(res); 107 } 108 109 // 1. We use the following variables T1, T2, R1, R2, t1, 110 // t2 (elements of G1), R4, t3 (elements of GT), B, K, R3, 111 // t5 (elements of G3), c, sx, sy, sa, sb, salpha, sbeta, 112 // nc, nc_tick, nsx, syalpha, t4 (256-bit big integers), 113 // nd (80-bit big integer), and sf (600-bit big integer). 114 res = NewEcPoint(G1, &T1); 115 BREAK_ON_EPID_ERROR(res); 116 res = NewEcPoint(G1, &T2); 117 BREAK_ON_EPID_ERROR(res); 118 res = NewEcPoint(G1, &R1); 119 BREAK_ON_EPID_ERROR(res); 120 res = NewEcPoint(G1, &R2); 121 BREAK_ON_EPID_ERROR(res); 122 res = NewEcPoint(G1, &t1); 123 BREAK_ON_EPID_ERROR(res); 124 res = NewEcPoint(G1, &t2); 125 BREAK_ON_EPID_ERROR(res); 126 127 res = NewFfElement(GT, &R4); 128 BREAK_ON_EPID_ERROR(res); 129 res = NewFfElement(GT, &t3); 130 BREAK_ON_EPID_ERROR(res); 131 132 res = NewEcPoint(G3, &B); 133 BREAK_ON_EPID_ERROR(res); 134 res = NewEcPoint(G3, &K); 135 BREAK_ON_EPID_ERROR(res); 136 res = NewEcPoint(G3, &R3); 137 BREAK_ON_EPID_ERROR(res); 138 res = NewEcPoint(G3, &t5); 139 BREAK_ON_EPID_ERROR(res); 140 141 res = NewBigNum(sizeof(FpElemStr), &c_bn); 142 BREAK_ON_EPID_ERROR(res); 143 res = NewBigNum(sizeof(FpElemStr), &sa_bn); 144 BREAK_ON_EPID_ERROR(res); 145 res = NewBigNum(sizeof(FpElemStr), &sb_bn); 146 BREAK_ON_EPID_ERROR(res); 147 res = NewBigNum(sizeof(FpElemStr), &nc_bn); 148 BREAK_ON_EPID_ERROR(res); 149 res = NewBigNum(sizeof(FpElemStr), &salpha_bn); 150 BREAK_ON_EPID_ERROR(res); 151 res = NewBigNum(sizeof(FpElemStr), &sbeta_bn); 152 BREAK_ON_EPID_ERROR(res); 153 res = NewBigNum(sizeof(FpElemStr), &nsx_bn); 154 BREAK_ON_EPID_ERROR(res); 155 res = NewBigNum(sizeof(OctStr600), &sf_bn); 156 BREAK_ON_EPID_ERROR(res); 157 res = NewBigNum(sizeof(OctStr600), &sf_tick_bn); 158 BREAK_ON_EPID_ERROR(res); 159 res = NewBigNum(sizeof(FpElemStr), &nc_tick_bn); 160 BREAK_ON_EPID_ERROR(res); 161 res = NewBigNum(sizeof(FpElemStr) * 2, &syalpha_bn); 162 BREAK_ON_EPID_ERROR(res); 163 164 // Steps 2-6 done in Epid11Create 165 166 // 8. If bsnSize = 0, the verifier verifies G3.inGroup(B) = true. 167 res = ReadEcPoint(G3, &(sig->B), sizeof(sig->B), B); 168 if (kEpidNoErr != res) { 169 if (ctx->basename_len == 0 && kEpidBadArgErr == res) { 170 res = kEpidSigInvalid; 171 } 172 break; 173 } 174 175 // 7. The verifier verifies that G3.isIdentity(B) is false 176 res = EcIsIdentity(G3, B, &cmp_result); 177 BREAK_ON_EPID_ERROR(res); 178 if (cmp_result != false) { 179 res = kEpidSigInvalid; 180 break; 181 } 182 183 // 9. If bsnSize > 0, the verifier verifies B = G3.hash(bsn). 184 if (basename_hash) { 185 res = EcIsEqual(G3, basename_hash, B, &cmp_result); 186 BREAK_ON_EPID_ERROR(res); 187 if (cmp_result != true) { 188 res = kEpidSigInvalid; 189 break; 190 } 191 } 192 // 10. The verifier verifies G3.inGroup(K) = true. 193 res = ReadEcPoint(G3, &(sig->K), sizeof(sig->K), K); 194 if (kEpidNoErr != res) { 195 if (kEpidBadArgErr == res) { 196 res = kEpidSigInvalid; 197 } 198 break; 199 } 200 201 // 11. The verifier verifies G1.inGroup(T1) = true. 202 res = ReadEcPoint(G1, &(sig->T1), sizeof(sig->T1), T1); 203 if (kEpidNoErr != res) { 204 if (kEpidBadArgErr == res) { 205 res = kEpidSigInvalid; 206 } 207 break; 208 } 209 210 // 12. The verifier verifies G1.inGroup(T2) = true. 211 res = ReadEcPoint(G1, &(sig->T2), sizeof(sig->T2), T2); 212 if (kEpidNoErr != res) { 213 if (kEpidBadArgErr == res) { 214 res = kEpidSigInvalid; 215 } 216 break; 217 } 218 219 // 13. The verifier verifies sx, sy, sa, sb, salpha, sbeta in [0, p-1]. 220 if (memcmp(&sig->sx, &ctx->commit_values.p, sizeof(FpElemStr)) >= 0 || 221 memcmp(&sig->sy, &ctx->commit_values.p, sizeof(FpElemStr)) >= 0 || 222 memcmp(&sig->sa, &ctx->commit_values.p, sizeof(FpElemStr)) >= 0 || 223 memcmp(&sig->sb, &ctx->commit_values.p, sizeof(FpElemStr)) >= 0 || 224 memcmp(&sig->salpha, &ctx->commit_values.p, sizeof(FpElemStr)) >= 0 || 225 memcmp(&sig->sbeta, &ctx->commit_values.p, sizeof(FpElemStr)) >= 0) { 226 res = kEpidSigInvalid; 227 break; 228 } 229 230 // 14. The verifier verifies that sf is an (at-most) 593-bit unsigned 231 // integer, in other words, sf < 2**593. 232 233 if (EPID11_SF_MAX_SIZE_BITS <= 234 OctStrBitSize(sig->sf.data, sizeof(sig->sf.data))) { 235 res = kEpidSigInvalid; 236 break; 237 } 238 239 // 15. The verifier computes nc = (-c) mod p. 240 res = ReadBigNum(&(sig->c), sizeof(sig->c), c_bn); 241 BREAK_ON_EPID_ERROR(res); 242 res = BigNumMod(c_bn, p_bn, nc_bn); 243 BREAK_ON_EPID_ERROR(res); 244 // (-c) mod p == p - (c mod p) 245 res = BigNumSub(p_bn, nc_bn, nc_bn); 246 BREAK_ON_EPID_ERROR(res); 247 248 // 16. The verifier computes nc_tick = (-c) mod p_tick. 249 res = BigNumMod(c_bn, p_tick_bn, nc_tick_bn); 250 BREAK_ON_EPID_ERROR(res); 251 res = BigNumSub(p_tick_bn, nc_tick_bn, nc_tick_bn); 252 BREAK_ON_EPID_ERROR(res); 253 254 // 17. The verifier computes nsx = (-sx) mod p. 255 res = ReadBigNum(&(sig->sx), sizeof(sig->sx), nsx_bn); 256 BREAK_ON_EPID_ERROR(res); 257 res = BigNumSub(p_bn, nsx_bn, nsx_bn); 258 BREAK_ON_EPID_ERROR(res); 259 260 // 18. The verifier computes syalpha = (sy + salpha) mod p. 261 res = ReadBigNum(&(sig->salpha), sizeof(sig->salpha), salpha_bn); 262 BREAK_ON_EPID_ERROR(res); 263 res = ReadBigNum(&(sig->sy), sizeof(sig->sy), syalpha_bn); 264 BREAK_ON_EPID_ERROR(res); 265 res = BigNumAdd(salpha_bn, syalpha_bn, syalpha_bn); 266 BREAK_ON_EPID_ERROR(res); 267 res = BigNumMod(syalpha_bn, p_bn, syalpha_bn); 268 BREAK_ON_EPID_ERROR(res); 269 270 // 19. The verifier computes R1 = G1.multiexp(h1, sa, h2, sb, T2, nc). 271 res = ReadBigNum(&sig->sa, sizeof(sig->sa), sa_bn); 272 BREAK_ON_EPID_ERROR(res); 273 res = ReadBigNum(&sig->sb, sizeof(sig->sb), sb_bn); 274 BREAK_ON_EPID_ERROR(res); 275 { 276 EcPoint const* points[3]; 277 BigNum const* exponents[3]; 278 points[0] = ctx->pub_key->h1; 279 points[1] = ctx->pub_key->h2; 280 points[2] = T2; 281 exponents[0] = sa_bn; 282 exponents[1] = sb_bn; 283 exponents[2] = nc_bn; 284 res = EcMultiExpBn(G1, points, exponents, COUNT_OF(points), R1); 285 BREAK_ON_EPID_ERROR(res); 286 } 287 // 20. The verifier computes 288 // R2 = G1.multiexp(h1, salpha, h2, sbeta, T2, nsx). 289 res = ReadBigNum(&sig->sbeta, sizeof(sig->sbeta), sbeta_bn); 290 BREAK_ON_EPID_ERROR(res); 291 { 292 EcPoint const* points[3]; 293 BigNum const* exponents[3]; 294 points[0] = ctx->pub_key->h1; 295 points[1] = ctx->pub_key->h2; 296 points[2] = T2; 297 exponents[0] = salpha_bn; 298 exponents[1] = sbeta_bn; 299 exponents[2] = nsx_bn; 300 res = EcMultiExpBn(G1, points, exponents, COUNT_OF(points), R2); 301 BREAK_ON_EPID_ERROR(res); 302 } 303 // 21. The verifier computes R3 = G3.multiexp(B, sf, K, nc_tick). 304 res = ReadBigNum(&sig->sf, sizeof(sig->sf), sf_tick_bn); 305 BREAK_ON_EPID_ERROR(res); 306 // G3.exp(B, sf) = G3(B, sf mod G3.order) 307 res = BigNumMod(sf_tick_bn, p_tick_bn, sf_tick_bn); 308 BREAK_ON_EPID_ERROR(res); 309 { 310 EcPoint const* points[2]; 311 BigNum const* exponents[2]; 312 points[0] = B; 313 points[1] = K; 314 exponents[0] = sf_tick_bn; 315 exponents[1] = nc_tick_bn; 316 res = EcMultiExpBn(G3, points, exponents, COUNT_OF(points), R3); 317 BREAK_ON_EPID_ERROR(res); 318 } 319 320 // 22. The verifier computes t1 = G1.multiexp(T1, nsx, g1, c). 321 res = BigNumMod(c_bn, p_bn, c_bn); 322 BREAK_ON_EPID_ERROR(res); 323 { 324 EcPoint const* points[2]; 325 BigNum const* exponents[2]; 326 points[0] = T1; 327 points[1] = g1; 328 exponents[0] = nsx_bn; 329 exponents[1] = c_bn; 330 res = EcMultiExpBn(G1, points, exponents, COUNT_OF(points), t1); 331 BREAK_ON_EPID_ERROR(res); 332 } 333 // 23. The verifier computes t2 = G1.exp(T1, nc). 334 res = WriteBigNum(nc_bn, sizeof(nc_str), &nc_str); 335 BREAK_ON_EPID_ERROR(res); 336 res = EcExp(G1, T1, &nc_str, t2); 337 BREAK_ON_EPID_ERROR(res); 338 // 24. The verifier computes R4 = pairing(t1, g2). 339 res = Epid11Pairing(ctx->epid11_params->pairing_state, t1, g2, R4); 340 BREAK_ON_EPID_ERROR(res); 341 // 25. The verifier computes t3 = pairing(t2, w). 342 res = Epid11Pairing(ctx->epid11_params->pairing_state, t2, w, t3); 343 BREAK_ON_EPID_ERROR(res); 344 // 26. The verifier computes R4 = GT.mul(R4, t3). 345 res = FfMul(GT, R4, t3, R4); 346 BREAK_ON_EPID_ERROR(res); 347 // 27. The verifier compute 348 // t3 = GT.multiexp(e12, sf, e22, syalpha, e2w, sa). 349 res = ReadBigNum(&sig->sf, sizeof(sig->sf), sf_bn); 350 BREAK_ON_EPID_ERROR(res); 351 { 352 FfElement const* points[3]; 353 BigNum const* exponents[3]; 354 points[0] = ctx->e12; 355 points[1] = ctx->e22; 356 points[2] = ctx->e2w; 357 exponents[0] = sf_bn; 358 exponents[1] = syalpha_bn; 359 exponents[2] = sa_bn; 360 res = FfMultiExpBn(GT, points, exponents, COUNT_OF(points), t3); 361 BREAK_ON_EPID_ERROR(res); 362 } 363 // 28. The verifier compute R4 = GT.mul(R4, t3). 364 res = FfMul(GT, R4, t3, R4); 365 BREAK_ON_EPID_ERROR(res); 366 // 29. The verifier compute t4 = Hash(p || g1 || g2 || g3 || h1 || h2 || w 367 // || B || K || T1 || T2 || R1 || R2 || R3 || R4). 368 // 30. The verifier verifies c = H(t4 || nd || mSize || m). 369 res = SetCalculatedEpid11CommitValues(&sig->B, &sig->K, &sig->T1, &sig->T2, 370 R1, R2, R3, R4, G1, G3, GT, 371 &commit_values); 372 BREAK_ON_EPID_ERROR(res); 373 res = CalculateEpid11CommitmentHash(&commit_values, msg, (uint32_t)msg_len, 374 &sig->nd, &c_hash); 375 BREAK_ON_EPID_ERROR(res); 376 if (0 != memcmp(&sig->c, &c_hash, sizeof(sig->c))) { 377 res = kEpidSigInvalid; 378 break; 379 } 380 res = kEpidNoErr; 381 } while (0); 382 EpidZeroMemory(&c_hash, sizeof(c_hash)); 383 384 DeleteEcPoint(&T1); 385 DeleteEcPoint(&T2); 386 DeleteEcPoint(&R1); 387 DeleteEcPoint(&R2); 388 DeleteEcPoint(&t1); 389 DeleteEcPoint(&t2); 390 391 DeleteFfElement(&R4); 392 DeleteFfElement(&t3); 393 394 DeleteEcPoint(&B); 395 DeleteEcPoint(&K); 396 DeleteEcPoint(&R3); 397 DeleteEcPoint(&t5); 398 399 DeleteBigNum(&c_bn); 400 DeleteBigNum(&sa_bn); 401 DeleteBigNum(&sb_bn); 402 DeleteBigNum(&nc_bn); 403 DeleteBigNum(&salpha_bn); 404 DeleteBigNum(&sbeta_bn); 405 DeleteBigNum(&nsx_bn); 406 DeleteBigNum(&sf_bn); 407 DeleteBigNum(&sf_tick_bn); 408 DeleteBigNum(&nc_tick_bn); 409 DeleteBigNum(&syalpha_bn); 410 411 return (res); 412 } 413