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
Epid11VerifyBasicSig(Epid11VerifierCtx const * ctx,Epid11BasicSignature const * sig,void const * msg,size_t msg_len)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