1 /* Copyright (c) 2020, Google Inc.
2  *
3  * Permission to use, copy, modify, and/or distribute this software for any
4  * purpose with or without fee is hereby granted, provided that the above
5  * copyright notice and this permission notice appear in all copies.
6  *
7  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
8  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
9  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
10  * SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
11  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION
12  * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
13  * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */
14 
15 #include <openssl/trust_token.h>
16 
17 #include <openssl/bn.h>
18 #include <openssl/bytestring.h>
19 #include <openssl/ec.h>
20 #include <openssl/err.h>
21 #include <openssl/mem.h>
22 #include <openssl/nid.h>
23 #include <openssl/rand.h>
24 
25 #include "../ec_extra/internal.h"
26 #include "../fipsmodule/ec/internal.h"
27 
28 #include "internal.h"
29 
30 
31 typedef int (*hash_to_group_func_t)(const EC_GROUP *group, EC_RAW_POINT *out,
32                                     const uint8_t t[TRUST_TOKEN_NONCE_SIZE]);
33 typedef int (*hash_to_scalar_func_t)(const EC_GROUP *group, EC_SCALAR *out,
34                                      uint8_t *buf, size_t len);
35 
36 typedef struct {
37   const EC_GROUP *group;
38 
39   // hash_to_group implements the HashToGroup operation for VOPRFs. It returns
40   // one on success and zero on error.
41   hash_to_group_func_t hash_to_group;
42   // hash_to_scalar implements the HashToScalar operation for VOPRFs. It returns
43   // one on success and zero on error.
44   hash_to_scalar_func_t hash_to_scalar;
45 } VOPRF_METHOD;
46 
47 static const uint8_t kDefaultAdditionalData[32] = {0};
48 
voprf_init_method(VOPRF_METHOD * method,int curve_nid,hash_to_group_func_t hash_to_group,hash_to_scalar_func_t hash_to_scalar)49 static int voprf_init_method(VOPRF_METHOD *method, int curve_nid,
50                              hash_to_group_func_t hash_to_group,
51                              hash_to_scalar_func_t hash_to_scalar) {
52   method->group = EC_GROUP_new_by_curve_name(curve_nid);
53   if (method->group == NULL) {
54     return 0;
55   }
56 
57   method->hash_to_group = hash_to_group;
58   method->hash_to_scalar = hash_to_scalar;
59 
60   return 1;
61 }
62 
cbb_add_point(CBB * out,const EC_GROUP * group,const EC_AFFINE * point)63 static int cbb_add_point(CBB *out, const EC_GROUP *group,
64                          const EC_AFFINE *point) {
65   size_t len =
66       ec_point_to_bytes(group, point, POINT_CONVERSION_UNCOMPRESSED, NULL, 0);
67   if (len == 0) {
68     return 0;
69   }
70 
71   uint8_t *p;
72   return CBB_add_space(out, &p, len) &&
73          ec_point_to_bytes(group, point, POINT_CONVERSION_UNCOMPRESSED, p,
74                            len) == len &&
75          CBB_flush(out);
76 }
77 
cbs_get_point(CBS * cbs,const EC_GROUP * group,EC_AFFINE * out)78 static int cbs_get_point(CBS *cbs, const EC_GROUP *group, EC_AFFINE *out) {
79   CBS child;
80   size_t plen = 1 + 2 * BN_num_bytes(&group->field);
81   if (!CBS_get_bytes(cbs, &child, plen) ||
82       !ec_point_from_uncompressed(group, out, CBS_data(&child),
83                                   CBS_len(&child))) {
84     return 0;
85   }
86   return 1;
87 }
88 
scalar_to_cbb(CBB * out,const EC_GROUP * group,const EC_SCALAR * scalar)89 static int scalar_to_cbb(CBB *out, const EC_GROUP *group,
90                          const EC_SCALAR *scalar) {
91   uint8_t *buf;
92   size_t scalar_len = BN_num_bytes(&group->order);
93   if (!CBB_add_space(out, &buf, scalar_len)) {
94     OPENSSL_PUT_ERROR(TRUST_TOKEN, ERR_R_MALLOC_FAILURE);
95     return 0;
96   }
97   ec_scalar_to_bytes(group, buf, &scalar_len, scalar);
98   return 1;
99 }
100 
scalar_from_cbs(CBS * cbs,const EC_GROUP * group,EC_SCALAR * out)101 static int scalar_from_cbs(CBS *cbs, const EC_GROUP *group, EC_SCALAR *out) {
102   size_t scalar_len = BN_num_bytes(&group->order);
103   CBS tmp;
104   if (!CBS_get_bytes(cbs, &tmp, scalar_len)) {
105     OPENSSL_PUT_ERROR(TRUST_TOKEN, TRUST_TOKEN_R_DECODE_FAILURE);
106     return 0;
107   }
108 
109   ec_scalar_from_bytes(group, out, CBS_data(&tmp), CBS_len(&tmp));
110   return 1;
111 }
112 
voprf_generate_key(const VOPRF_METHOD * method,CBB * out_private,CBB * out_public)113 static int voprf_generate_key(const VOPRF_METHOD *method, CBB *out_private,
114                               CBB *out_public) {
115   const EC_GROUP *group = method->group;
116   EC_RAW_POINT pub;
117   EC_SCALAR priv;
118   EC_AFFINE pub_affine;
119   if (!ec_random_nonzero_scalar(group, &priv, kDefaultAdditionalData) ||
120       !ec_point_mul_scalar_base(group, &pub, &priv) ||
121       !ec_jacobian_to_affine(group, &pub_affine, &pub)) {
122     OPENSSL_PUT_ERROR(TRUST_TOKEN, TRUST_TOKEN_R_KEYGEN_FAILURE);
123     return 0;
124   }
125 
126   if (!scalar_to_cbb(out_private, group, &priv) ||
127       !cbb_add_point(out_public, group, &pub_affine)) {
128     OPENSSL_PUT_ERROR(TRUST_TOKEN, TRUST_TOKEN_R_BUFFER_TOO_SMALL);
129     return 0;
130   }
131 
132   return 1;
133 }
134 
voprf_client_key_from_bytes(const VOPRF_METHOD * method,TRUST_TOKEN_CLIENT_KEY * key,const uint8_t * in,size_t len)135 static int voprf_client_key_from_bytes(const VOPRF_METHOD *method,
136                                        TRUST_TOKEN_CLIENT_KEY *key,
137                                        const uint8_t *in, size_t len) {
138   const EC_GROUP *group = method->group;
139   if (!ec_point_from_uncompressed(group, &key->pubs, in, len)) {
140     OPENSSL_PUT_ERROR(TRUST_TOKEN, TRUST_TOKEN_R_DECODE_FAILURE);
141     return 0;
142   }
143 
144   return 1;
145 }
146 
voprf_issuer_key_from_bytes(const VOPRF_METHOD * method,TRUST_TOKEN_ISSUER_KEY * key,const uint8_t * in,size_t len)147 static int voprf_issuer_key_from_bytes(const VOPRF_METHOD *method,
148                                        TRUST_TOKEN_ISSUER_KEY *key,
149                                        const uint8_t *in, size_t len) {
150   const EC_GROUP *group = method->group;
151   if (!ec_scalar_from_bytes(group, &key->xs, in, len)) {
152     OPENSSL_PUT_ERROR(TRUST_TOKEN, TRUST_TOKEN_R_DECODE_FAILURE);
153     return 0;
154   }
155 
156   // Recompute the public key.
157   EC_RAW_POINT pub;
158   if (!ec_point_mul_scalar_base(group, &pub, &key->xs) ||
159       !ec_jacobian_to_affine(group, &key->pubs, &pub)) {
160     return 0;
161   }
162 
163   return 1;
164 }
165 
STACK_OF(TRUST_TOKEN_PRETOKEN)166 static STACK_OF(TRUST_TOKEN_PRETOKEN) *
167     voprf_blind(const VOPRF_METHOD *method, CBB *cbb, size_t count) {
168   const EC_GROUP *group = method->group;
169   STACK_OF(TRUST_TOKEN_PRETOKEN) *pretokens =
170       sk_TRUST_TOKEN_PRETOKEN_new_null();
171   if (pretokens == NULL) {
172     OPENSSL_PUT_ERROR(TRUST_TOKEN, ERR_R_MALLOC_FAILURE);
173     goto err;
174   }
175 
176   for (size_t i = 0; i < count; i++) {
177     // Insert |pretoken| into |pretokens| early to simplify error-handling.
178     TRUST_TOKEN_PRETOKEN *pretoken =
179         OPENSSL_malloc(sizeof(TRUST_TOKEN_PRETOKEN));
180     if (pretoken == NULL ||
181         !sk_TRUST_TOKEN_PRETOKEN_push(pretokens, pretoken)) {
182       OPENSSL_PUT_ERROR(TRUST_TOKEN, ERR_R_MALLOC_FAILURE);
183       TRUST_TOKEN_PRETOKEN_free(pretoken);
184       goto err;
185     }
186 
187     RAND_bytes(pretoken->t, sizeof(pretoken->t));
188 
189     // We sample r in Montgomery form to simplify inverting.
190     EC_SCALAR r;
191     if (!ec_random_nonzero_scalar(group, &r,
192                                   kDefaultAdditionalData)) {
193       OPENSSL_PUT_ERROR(TRUST_TOKEN, ERR_R_MALLOC_FAILURE);
194       goto err;
195     }
196 
197     // pretoken->r is rinv.
198     ec_scalar_inv0_montgomery(group, &pretoken->r, &r);
199     // Convert both out of Montgomery form.
200     ec_scalar_from_montgomery(group, &r, &r);
201     ec_scalar_from_montgomery(group, &pretoken->r, &pretoken->r);
202 
203     // Tp is the blinded token in the VOPRF protocol.
204     EC_RAW_POINT P, Tp;
205     if (!method->hash_to_group(group, &P, pretoken->t) ||
206         !ec_point_mul_scalar(group, &Tp, &P, &r) ||
207         !ec_jacobian_to_affine(group, &pretoken->Tp, &Tp)) {
208       goto err;
209     }
210 
211     if (!cbb_add_point(cbb, group, &pretoken->Tp)) {
212       goto err;
213     }
214   }
215 
216   return pretokens;
217 
218 err:
219   sk_TRUST_TOKEN_PRETOKEN_pop_free(pretokens, TRUST_TOKEN_PRETOKEN_free);
220   return NULL;
221 }
222 
hash_to_scalar_dleq(const VOPRF_METHOD * method,EC_SCALAR * out,const EC_AFFINE * X,const EC_AFFINE * T,const EC_AFFINE * W,const EC_AFFINE * K0,const EC_AFFINE * K1)223 static int hash_to_scalar_dleq(const VOPRF_METHOD *method, EC_SCALAR *out,
224                                const EC_AFFINE *X, const EC_AFFINE *T,
225                                const EC_AFFINE *W, const EC_AFFINE *K0,
226                                const EC_AFFINE *K1) {
227   static const uint8_t kDLEQLabel[] = "DLEQ";
228 
229   int ok = 0;
230   CBB cbb;
231   CBB_zero(&cbb);
232   uint8_t *buf = NULL;
233   size_t len;
234   if (!CBB_init(&cbb, 0) ||
235       !CBB_add_bytes(&cbb, kDLEQLabel, sizeof(kDLEQLabel)) ||
236       !cbb_add_point(&cbb, method->group, X) ||
237       !cbb_add_point(&cbb, method->group, T) ||
238       !cbb_add_point(&cbb, method->group, W) ||
239       !cbb_add_point(&cbb, method->group, K0) ||
240       !cbb_add_point(&cbb, method->group, K1) ||
241       !CBB_finish(&cbb, &buf, &len) ||
242       !method->hash_to_scalar(method->group, out, buf, len)) {
243     OPENSSL_PUT_ERROR(TRUST_TOKEN, ERR_R_MALLOC_FAILURE);
244     goto err;
245   }
246 
247   ok = 1;
248 
249 err:
250   CBB_cleanup(&cbb);
251   OPENSSL_free(buf);
252   return ok;
253 }
254 
hash_to_scalar_batch(const VOPRF_METHOD * method,EC_SCALAR * out,const CBB * points,size_t index)255 static int hash_to_scalar_batch(const VOPRF_METHOD *method, EC_SCALAR *out,
256                                 const CBB *points, size_t index) {
257   static const uint8_t kDLEQBatchLabel[] = "DLEQ BATCH";
258   if (index > 0xffff) {
259     // The protocol supports only two-byte batches.
260     OPENSSL_PUT_ERROR(TRUST_TOKEN, ERR_R_OVERFLOW);
261     return 0;
262   }
263 
264   int ok = 0;
265   CBB cbb;
266   CBB_zero(&cbb);
267   uint8_t *buf = NULL;
268   size_t len;
269   if (!CBB_init(&cbb, 0) ||
270       !CBB_add_bytes(&cbb, kDLEQBatchLabel, sizeof(kDLEQBatchLabel)) ||
271       !CBB_add_bytes(&cbb, CBB_data(points), CBB_len(points)) ||
272       !CBB_add_u16(&cbb, (uint16_t)index) ||
273       !CBB_finish(&cbb, &buf, &len) ||
274       !method->hash_to_scalar(method->group, out, buf, len)) {
275     OPENSSL_PUT_ERROR(TRUST_TOKEN, ERR_R_MALLOC_FAILURE);
276     goto err;
277   }
278 
279   ok = 1;
280 
281 err:
282   CBB_cleanup(&cbb);
283   OPENSSL_free(buf);
284   return ok;
285 }
286 
dleq_generate(const VOPRF_METHOD * method,CBB * cbb,const TRUST_TOKEN_ISSUER_KEY * priv,const EC_RAW_POINT * T,const EC_RAW_POINT * W)287 static int dleq_generate(const VOPRF_METHOD *method, CBB *cbb,
288                          const TRUST_TOKEN_ISSUER_KEY *priv,
289                          const EC_RAW_POINT *T, const EC_RAW_POINT *W) {
290   const EC_GROUP *group = method->group;
291 
292   enum {
293     idx_T,
294     idx_W,
295     idx_k0,
296     idx_k1,
297     num_idx,
298   };
299   EC_RAW_POINT jacobians[num_idx];
300 
301   // Setup the DLEQ proof.
302   EC_SCALAR r;
303   if (// r <- Zp
304       !ec_random_nonzero_scalar(group, &r, kDefaultAdditionalData) ||
305       // k0;k1 = r*(G;T)
306       !ec_point_mul_scalar_base(group, &jacobians[idx_k0], &r) ||
307       !ec_point_mul_scalar(group, &jacobians[idx_k1], T, &r))  {
308     return 0;
309   }
310 
311   EC_AFFINE affines[num_idx];
312   jacobians[idx_T] = *T;
313   jacobians[idx_W] = *W;
314   if (!ec_jacobian_to_affine_batch(group, affines, jacobians, num_idx)) {
315     return 0;
316   }
317 
318   // Compute c = Hc(...).
319   EC_SCALAR c;
320   if (!hash_to_scalar_dleq(method, &c, &priv->pubs, &affines[idx_T],
321                            &affines[idx_W], &affines[idx_k0],
322                            &affines[idx_k1])) {
323     return 0;
324   }
325 
326 
327   EC_SCALAR c_mont;
328   ec_scalar_to_montgomery(group, &c_mont, &c);
329 
330   // u = r + c*xs
331   EC_SCALAR u;
332   ec_scalar_mul_montgomery(group, &u, &priv->xs, &c_mont);
333   ec_scalar_add(group, &u, &r, &u);
334 
335   // Store DLEQ proof in transcript.
336   if (!scalar_to_cbb(cbb, group, &c) ||
337       !scalar_to_cbb(cbb, group, &u)) {
338     OPENSSL_PUT_ERROR(TRUST_TOKEN, ERR_R_MALLOC_FAILURE);
339     return 0;
340   }
341 
342   return 1;
343 }
344 
mul_public_2(const EC_GROUP * group,EC_RAW_POINT * out,const EC_RAW_POINT * p0,const EC_SCALAR * scalar0,const EC_RAW_POINT * p1,const EC_SCALAR * scalar1)345 static int mul_public_2(const EC_GROUP *group, EC_RAW_POINT *out,
346                         const EC_RAW_POINT *p0, const EC_SCALAR *scalar0,
347                         const EC_RAW_POINT *p1, const EC_SCALAR *scalar1) {
348   EC_RAW_POINT points[2] = {*p0, *p1};
349   EC_SCALAR scalars[2] = {*scalar0, *scalar1};
350   return ec_point_mul_scalar_public_batch(group, out, /*g_scalar=*/NULL, points,
351                                           scalars, 2);
352 }
353 
dleq_verify(const VOPRF_METHOD * method,CBS * cbs,const TRUST_TOKEN_CLIENT_KEY * pub,const EC_RAW_POINT * T,const EC_RAW_POINT * W)354 static int dleq_verify(const VOPRF_METHOD *method, CBS *cbs,
355                        const TRUST_TOKEN_CLIENT_KEY *pub, const EC_RAW_POINT *T,
356                        const EC_RAW_POINT *W) {
357   const EC_GROUP *group = method->group;
358 
359 
360   enum {
361     idx_T,
362     idx_W,
363     idx_k0,
364     idx_k1,
365     num_idx,
366   };
367   EC_RAW_POINT jacobians[num_idx];
368 
369   // Decode the DLEQ proof.
370   EC_SCALAR c, u;
371   if (!scalar_from_cbs(cbs, group, &c) ||
372       !scalar_from_cbs(cbs, group, &u)) {
373     OPENSSL_PUT_ERROR(TRUST_TOKEN, TRUST_TOKEN_R_DECODE_FAILURE);
374     return 0;
375   }
376 
377   // k0;k1 = u*(G;T) - c*(pub;W)
378   EC_RAW_POINT pubs;
379   ec_affine_to_jacobian(group, &pubs, &pub->pubs);
380   EC_SCALAR minus_c;
381   ec_scalar_neg(group, &minus_c, &c);
382   if (!ec_point_mul_scalar_public(group, &jacobians[idx_k0], &u, &pubs,
383                                   &minus_c) ||
384       !mul_public_2(group, &jacobians[idx_k1], T, &u, W, &minus_c)) {
385     return 0;
386   }
387 
388   // Check the DLEQ proof.
389   EC_AFFINE affines[num_idx];
390   jacobians[idx_T] = *T;
391   jacobians[idx_W] = *W;
392   if (!ec_jacobian_to_affine_batch(group, affines, jacobians, num_idx)) {
393     return 0;
394   }
395 
396   // Compute c = Hc(...).
397   EC_SCALAR calculated;
398   if (!hash_to_scalar_dleq(method, &calculated, &pub->pubs, &affines[idx_T],
399                            &affines[idx_W], &affines[idx_k0],
400                            &affines[idx_k1])) {
401     return 0;
402   }
403 
404   // c == calculated
405   if (!ec_scalar_equal_vartime(group, &c, &calculated)) {
406     OPENSSL_PUT_ERROR(TRUST_TOKEN, TRUST_TOKEN_R_INVALID_PROOF);
407     return 0;
408   }
409 
410   return 1;
411 }
412 
voprf_sign(const VOPRF_METHOD * method,const TRUST_TOKEN_ISSUER_KEY * key,CBB * cbb,CBS * cbs,size_t num_requested,size_t num_to_issue)413 static int voprf_sign(const VOPRF_METHOD *method,
414                       const TRUST_TOKEN_ISSUER_KEY *key, CBB *cbb, CBS *cbs,
415                       size_t num_requested, size_t num_to_issue) {
416   const EC_GROUP *group = method->group;
417   if (num_requested < num_to_issue) {
418     OPENSSL_PUT_ERROR(TRUST_TOKEN, ERR_R_INTERNAL_ERROR);
419     return 0;
420   }
421 
422   if (num_to_issue > ((size_t)-1) / sizeof(EC_RAW_POINT) ||
423       num_to_issue > ((size_t)-1) / sizeof(EC_SCALAR)) {
424     OPENSSL_PUT_ERROR(TRUST_TOKEN, ERR_R_OVERFLOW);
425     return 0;
426   }
427 
428   int ret = 0;
429   EC_RAW_POINT *BTs = OPENSSL_malloc(num_to_issue * sizeof(EC_RAW_POINT));
430   EC_RAW_POINT *Zs = OPENSSL_malloc(num_to_issue * sizeof(EC_RAW_POINT));
431   EC_SCALAR *es = OPENSSL_malloc(num_to_issue * sizeof(EC_SCALAR));
432   CBB batch_cbb;
433   CBB_zero(&batch_cbb);
434   if (!BTs ||
435       !Zs ||
436       !es ||
437       !CBB_init(&batch_cbb, 0) ||
438       !cbb_add_point(&batch_cbb, method->group, &key->pubs)) {
439     OPENSSL_PUT_ERROR(TRUST_TOKEN, ERR_R_MALLOC_FAILURE);
440     goto err;
441   }
442 
443   for (size_t i = 0; i < num_to_issue; i++) {
444     EC_AFFINE BT_affine, Z_affine;
445     EC_RAW_POINT BT, Z;
446     if (!cbs_get_point(cbs, group, &BT_affine)) {
447       OPENSSL_PUT_ERROR(TRUST_TOKEN, TRUST_TOKEN_R_DECODE_FAILURE);
448       goto err;
449     }
450     ec_affine_to_jacobian(group, &BT, &BT_affine);
451     if (!ec_point_mul_scalar(group, &Z, &BT, &key->xs) ||
452         !ec_jacobian_to_affine(group, &Z_affine, &Z) ||
453         !cbb_add_point(cbb, group, &Z_affine)) {
454       goto err;
455     }
456 
457     if (!cbb_add_point(&batch_cbb, group, &BT_affine) ||
458         !cbb_add_point(&batch_cbb, group, &Z_affine)) {
459       OPENSSL_PUT_ERROR(TRUST_TOKEN, ERR_R_MALLOC_FAILURE);
460       goto err;
461     }
462     BTs[i] = BT;
463     Zs[i] = Z;
464 
465     if (!CBB_flush(cbb)) {
466       goto err;
467     }
468   }
469 
470   // The DLEQ batching construction is described in appendix B of
471   // https://eprint.iacr.org/2020/072/20200324:214215. Note the additional
472   // computations all act on public inputs.
473   for (size_t i = 0; i < num_to_issue; i++) {
474     if (!hash_to_scalar_batch(method, &es[i], &batch_cbb, i)) {
475       goto err;
476     }
477   }
478 
479   EC_RAW_POINT BT_batch, Z_batch;
480   if (!ec_point_mul_scalar_public_batch(group, &BT_batch,
481                                         /*g_scalar=*/NULL, BTs, es,
482                                         num_to_issue) ||
483       !ec_point_mul_scalar_public_batch(group, &Z_batch,
484                                         /*g_scalar=*/NULL, Zs, es,
485                                         num_to_issue)) {
486     goto err;
487   }
488 
489   CBB proof;
490   if (!CBB_add_u16_length_prefixed(cbb, &proof) ||
491       !dleq_generate(method, &proof, key, &BT_batch, &Z_batch) ||
492       !CBB_flush(cbb)) {
493     goto err;
494   }
495 
496   // Skip over any unused requests.
497   size_t point_len = 1 + 2 * BN_num_bytes(&group->field);
498   if (!CBS_skip(cbs, point_len * (num_requested - num_to_issue))) {
499     OPENSSL_PUT_ERROR(TRUST_TOKEN, TRUST_TOKEN_R_DECODE_FAILURE);
500     goto err;
501   }
502 
503   ret = 1;
504 
505 err:
506   OPENSSL_free(BTs);
507   OPENSSL_free(Zs);
508   OPENSSL_free(es);
509   CBB_cleanup(&batch_cbb);
510   return ret;
511 }
512 
STACK_OF(TRUST_TOKEN)513 static STACK_OF(TRUST_TOKEN) *
514     voprf_unblind(const VOPRF_METHOD *method, const TRUST_TOKEN_CLIENT_KEY *key,
515                   const STACK_OF(TRUST_TOKEN_PRETOKEN) * pretokens, CBS *cbs,
516                   size_t count, uint32_t key_id) {
517   const EC_GROUP *group = method->group;
518   if (count > sk_TRUST_TOKEN_PRETOKEN_num(pretokens)) {
519     OPENSSL_PUT_ERROR(TRUST_TOKEN, TRUST_TOKEN_R_DECODE_FAILURE);
520     return NULL;
521   }
522 
523   int ok = 0;
524   STACK_OF(TRUST_TOKEN) *ret = sk_TRUST_TOKEN_new_null();
525   if (ret == NULL) {
526     OPENSSL_PUT_ERROR(TRUST_TOKEN, ERR_R_MALLOC_FAILURE);
527     return NULL;
528   }
529 
530   if (count > ((size_t)-1) / sizeof(EC_RAW_POINT) ||
531       count > ((size_t)-1) / sizeof(EC_SCALAR)) {
532     OPENSSL_PUT_ERROR(TRUST_TOKEN, ERR_R_OVERFLOW);
533     return 0;
534   }
535   EC_RAW_POINT *BTs = OPENSSL_malloc(count * sizeof(EC_RAW_POINT));
536   EC_RAW_POINT *Zs = OPENSSL_malloc(count * sizeof(EC_RAW_POINT));
537   EC_SCALAR *es = OPENSSL_malloc(count * sizeof(EC_SCALAR));
538   CBB batch_cbb;
539   CBB_zero(&batch_cbb);
540   if (!BTs ||
541       !Zs ||
542       !es ||
543       !CBB_init(&batch_cbb, 0) ||
544       !cbb_add_point(&batch_cbb, method->group, &key->pubs)) {
545     OPENSSL_PUT_ERROR(TRUST_TOKEN, ERR_R_MALLOC_FAILURE);
546     goto err;
547   }
548 
549   for (size_t i = 0; i < count; i++) {
550     const TRUST_TOKEN_PRETOKEN *pretoken =
551         sk_TRUST_TOKEN_PRETOKEN_value(pretokens, i);
552 
553     EC_AFFINE Z_affine;
554     if (!cbs_get_point(cbs, group, &Z_affine)) {
555       OPENSSL_PUT_ERROR(TRUST_TOKEN, TRUST_TOKEN_R_DECODE_FAILURE);
556       goto err;
557     }
558 
559     ec_affine_to_jacobian(group, &BTs[i], &pretoken->Tp);
560     ec_affine_to_jacobian(group, &Zs[i], &Z_affine);
561 
562     if (!cbb_add_point(&batch_cbb, group, &pretoken->Tp) ||
563         !cbb_add_point(&batch_cbb, group, &Z_affine)) {
564       OPENSSL_PUT_ERROR(TRUST_TOKEN, ERR_R_MALLOC_FAILURE);
565       goto err;
566     }
567 
568     // Unblind the token.
569     // pretoken->r is rinv.
570     EC_RAW_POINT N;
571     EC_AFFINE N_affine;
572     if (!ec_point_mul_scalar(group, &N, &Zs[i], &pretoken->r) ||
573         !ec_jacobian_to_affine(group, &N_affine, &N)) {
574       goto err;
575     }
576 
577     // Serialize the token. Include |key_id| to avoid an extra copy in the layer
578     // above.
579     CBB token_cbb;
580     size_t point_len = 1 + 2 * BN_num_bytes(&group->field);
581     if (!CBB_init(&token_cbb, 4 + TRUST_TOKEN_NONCE_SIZE + (2 + point_len)) ||
582         !CBB_add_u32(&token_cbb, key_id) ||
583         !CBB_add_bytes(&token_cbb, pretoken->t, TRUST_TOKEN_NONCE_SIZE) ||
584         !cbb_add_point(&token_cbb, group, &N_affine) ||
585         !CBB_flush(&token_cbb)) {
586       CBB_cleanup(&token_cbb);
587       goto err;
588     }
589 
590     TRUST_TOKEN *token =
591         TRUST_TOKEN_new(CBB_data(&token_cbb), CBB_len(&token_cbb));
592     CBB_cleanup(&token_cbb);
593     if (token == NULL ||
594         !sk_TRUST_TOKEN_push(ret, token)) {
595       OPENSSL_PUT_ERROR(TRUST_TOKEN, ERR_R_MALLOC_FAILURE);
596       TRUST_TOKEN_free(token);
597       goto err;
598     }
599   }
600 
601   // The DLEQ batching construction is described in appendix B of
602   // https://eprint.iacr.org/2020/072/20200324:214215. Note the additional
603   // computations all act on public inputs.
604   for (size_t i = 0; i < count; i++) {
605     if (!hash_to_scalar_batch(method, &es[i], &batch_cbb, i)) {
606       goto err;
607     }
608   }
609 
610   EC_RAW_POINT BT_batch, Z_batch;
611   if (!ec_point_mul_scalar_public_batch(group, &BT_batch,
612                                         /*g_scalar=*/NULL, BTs, es, count) ||
613       !ec_point_mul_scalar_public_batch(group, &Z_batch,
614                                         /*g_scalar=*/NULL, Zs, es, count)) {
615     goto err;
616   }
617 
618   CBS proof;
619   if (!CBS_get_u16_length_prefixed(cbs, &proof) ||
620       !dleq_verify(method, &proof, key, &BT_batch, &Z_batch) ||
621       CBS_len(&proof) != 0) {
622     goto err;
623   }
624 
625   ok = 1;
626 
627 err:
628   OPENSSL_free(BTs);
629   OPENSSL_free(Zs);
630   OPENSSL_free(es);
631   CBB_cleanup(&batch_cbb);
632   if (!ok) {
633     sk_TRUST_TOKEN_pop_free(ret, TRUST_TOKEN_free);
634     ret = NULL;
635   }
636   return ret;
637 }
638 
voprf_read(const VOPRF_METHOD * method,const TRUST_TOKEN_ISSUER_KEY * key,uint8_t out_nonce[TRUST_TOKEN_NONCE_SIZE],const uint8_t * token,size_t token_len)639 static int voprf_read(const VOPRF_METHOD *method,
640                       const TRUST_TOKEN_ISSUER_KEY *key,
641                       uint8_t out_nonce[TRUST_TOKEN_NONCE_SIZE],
642                       const uint8_t *token, size_t token_len) {
643   const EC_GROUP *group = method->group;
644   CBS cbs;
645   CBS_init(&cbs, token, token_len);
646   EC_AFFINE Ws;
647   if (!CBS_copy_bytes(&cbs, out_nonce, TRUST_TOKEN_NONCE_SIZE) ||
648       !cbs_get_point(&cbs, group, &Ws) ||
649       CBS_len(&cbs) != 0) {
650     OPENSSL_PUT_ERROR(TRUST_TOKEN, TRUST_TOKEN_R_INVALID_TOKEN);
651     return 0;
652   }
653 
654 
655   EC_RAW_POINT T;
656   if (!method->hash_to_group(group, &T, out_nonce)) {
657     return 0;
658   }
659 
660   EC_RAW_POINT Ws_calculated;
661   if (!ec_point_mul_scalar(group, &Ws_calculated, &T, &key->xs) ||
662       !ec_affine_jacobian_equal(group, &Ws, &Ws_calculated)) {
663     OPENSSL_PUT_ERROR(TRUST_TOKEN, TRUST_TOKEN_R_BAD_VALIDITY_CHECK);
664     return 0;
665   }
666 
667   return 1;
668 }
669 
670 
671 // VOPRF experiment v2.
672 
voprf_exp2_hash_to_group(const EC_GROUP * group,EC_RAW_POINT * out,const uint8_t t[TRUST_TOKEN_NONCE_SIZE])673 static int voprf_exp2_hash_to_group(const EC_GROUP *group, EC_RAW_POINT *out,
674                                     const uint8_t t[TRUST_TOKEN_NONCE_SIZE]) {
675   const uint8_t kHashTLabel[] = "TrustToken VOPRF Experiment V2 HashToGroup";
676   return ec_hash_to_curve_p384_xmd_sha512_sswu_draft07(
677       group, out, kHashTLabel, sizeof(kHashTLabel), t, TRUST_TOKEN_NONCE_SIZE);
678 }
679 
voprf_exp2_hash_to_scalar(const EC_GROUP * group,EC_SCALAR * out,uint8_t * buf,size_t len)680 static int voprf_exp2_hash_to_scalar(const EC_GROUP *group, EC_SCALAR *out,
681                              uint8_t *buf, size_t len) {
682   const uint8_t kHashCLabel[] = "TrustToken VOPRF Experiment V2 HashToScalar";
683   return ec_hash_to_scalar_p384_xmd_sha512_draft07(
684       group, out, kHashCLabel, sizeof(kHashCLabel), buf, len);
685 }
686 
687 static int voprf_exp2_ok = 0;
688 static VOPRF_METHOD voprf_exp2_method;
689 static CRYPTO_once_t voprf_exp2_method_once = CRYPTO_ONCE_INIT;
690 
voprf_exp2_init_method_impl(void)691 static void voprf_exp2_init_method_impl(void) {
692   voprf_exp2_ok =
693       voprf_init_method(&voprf_exp2_method, NID_secp384r1,
694                         voprf_exp2_hash_to_group, voprf_exp2_hash_to_scalar);
695 }
696 
voprf_exp2_init_method(void)697 static int voprf_exp2_init_method(void) {
698   CRYPTO_once(&voprf_exp2_method_once, voprf_exp2_init_method_impl);
699   if (!voprf_exp2_ok) {
700     OPENSSL_PUT_ERROR(TRUST_TOKEN, ERR_R_INTERNAL_ERROR);
701     return 0;
702   }
703   return 1;
704 }
705 
voprf_exp2_generate_key(CBB * out_private,CBB * out_public)706 int voprf_exp2_generate_key(CBB *out_private, CBB *out_public) {
707   if (!voprf_exp2_init_method()) {
708     return 0;
709   }
710 
711   return voprf_generate_key(&voprf_exp2_method, out_private, out_public);
712 }
713 
voprf_exp2_client_key_from_bytes(TRUST_TOKEN_CLIENT_KEY * key,const uint8_t * in,size_t len)714 int voprf_exp2_client_key_from_bytes(TRUST_TOKEN_CLIENT_KEY *key,
715                                      const uint8_t *in, size_t len) {
716   if (!voprf_exp2_init_method()) {
717     return 0;
718   }
719   return voprf_client_key_from_bytes(&voprf_exp2_method, key, in, len);
720 }
721 
voprf_exp2_issuer_key_from_bytes(TRUST_TOKEN_ISSUER_KEY * key,const uint8_t * in,size_t len)722 int voprf_exp2_issuer_key_from_bytes(TRUST_TOKEN_ISSUER_KEY *key,
723                                      const uint8_t *in, size_t len) {
724   if (!voprf_exp2_init_method()) {
725     return 0;
726   }
727   return voprf_issuer_key_from_bytes(&voprf_exp2_method, key, in, len);
728 }
729 
STACK_OF(TRUST_TOKEN_PRETOKEN)730 STACK_OF(TRUST_TOKEN_PRETOKEN) * voprf_exp2_blind(CBB *cbb, size_t count) {
731   if (!voprf_exp2_init_method()) {
732     return NULL;
733   }
734   return voprf_blind(&voprf_exp2_method, cbb, count);
735 }
736 
voprf_exp2_sign(const TRUST_TOKEN_ISSUER_KEY * key,CBB * cbb,CBS * cbs,size_t num_requested,size_t num_to_issue,uint8_t private_metadata)737 int voprf_exp2_sign(const TRUST_TOKEN_ISSUER_KEY *key, CBB *cbb, CBS *cbs,
738                     size_t num_requested, size_t num_to_issue,
739                     uint8_t private_metadata) {
740   if (!voprf_exp2_init_method() || private_metadata != 0) {
741     return 0;
742   }
743   return voprf_sign(&voprf_exp2_method, key, cbb, cbs, num_requested,
744                     num_to_issue);
745 }
746 
STACK_OF(TRUST_TOKEN)747 STACK_OF(TRUST_TOKEN) *
748     voprf_exp2_unblind(const TRUST_TOKEN_CLIENT_KEY *key,
749                        const STACK_OF(TRUST_TOKEN_PRETOKEN) * pretokens,
750                        CBS *cbs, size_t count, uint32_t key_id) {
751   if (!voprf_exp2_init_method()) {
752     return NULL;
753   }
754   return voprf_unblind(&voprf_exp2_method, key, pretokens, cbs, count,
755                           key_id);
756 }
757 
voprf_exp2_read(const TRUST_TOKEN_ISSUER_KEY * key,uint8_t out_nonce[TRUST_TOKEN_NONCE_SIZE],uint8_t * out_private_metadata,const uint8_t * token,size_t token_len)758 int voprf_exp2_read(const TRUST_TOKEN_ISSUER_KEY *key,
759                     uint8_t out_nonce[TRUST_TOKEN_NONCE_SIZE],
760                     uint8_t *out_private_metadata, const uint8_t *token,
761                     size_t token_len) {
762   if (!voprf_exp2_init_method()) {
763     return 0;
764   }
765   return voprf_read(&voprf_exp2_method, key, out_nonce, token, token_len);
766 }
767