src/secretsharing/gnunet-service-secretsharing.c

   1 /*
   2      This file is part of GNUnet.
   3      Copyright (C) 2013 GNUnet e.V.
   4
   5      GNUnet is free software: you can redistribute it and/or modify it
   6      under the terms of the GNU Affero General Public License as published
   7      by the Free Software Foundation, either version 3 of the License,
   8      or (at your option) any later version.
   9
  10      GNUnet is distributed in the hope that it will be useful, but
  11      WITHOUT ANY WARRANTY; without even the implied warranty of
  12      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13      Affero General Public License for more details.
  14
  15      You should have received a copy of the GNU Affero General Public License
  16      along with this program.  If not, see <http://www.gnu.org/licenses/>.
  17
  18      SPDX-License-Identifier: AGPL3.0-or-later
  19  */
  20
  21 /**
  22  * @file secretsharing/gnunet-service-secretsharing.c
  23  * @brief secret sharing service
  24  * @author Florian Dold
  25  */
  26 #include "platform.h"
  27 #include "gnunet_util_lib.h"
  28 #include "gnunet_time_lib.h"
  29 #include "gnunet_signatures.h"
  30 #include "gnunet_consensus_service.h"
  31 #include "secretsharing.h"
  32 #include "secretsharing_protocol.h"
  33 #include <gcrypt.h>
  34
  35
  36 #define EXTRA_CHECKS 1
  37
  38
  39 /**
  40  * Info about a peer in a key generation session.
  41  */
  42 struct KeygenPeerInfo {
  43   /**
  44    * Peer identity of the peer.
  45    */
  46   struct GNUNET_PeerIdentity peer;
  47
  48   /**
  49    * The peer's paillier public key.
  50    * Freshly generated for each keygen session.
  51    */
  52   struct GNUNET_CRYPTO_PaillierPublicKey paillier_public_key;
  53
  54   /**
  55    * The peer's commitment to its presecret.
  56    */
  57   gcry_mpi_t presecret_commitment;
  58
  59   /**
  60    * Commitment to the preshare that is
  61    * intended for our peer.
  62    */
  63   gcry_mpi_t preshare_commitment;
  64
  65   /**
  66    * Sigma (exponentiated share) for this peer.
  67    */
  68   gcry_mpi_t sigma;
  69
  70   /**
  71    * Did we successfully receive the round1 element
  72    * of the peer?
  73    */
  74   int round1_valid;
  75
  76   /**
  77    * Did we successfully receive the round2 element
  78    * of the peer?
  79    */
  80   int round2_valid;
  81 };
  82
  83
  84 /**
  85  * Information about a peer in a decrypt session.
  86  */
  87 struct DecryptPeerInfo {
  88   /**
  89    * Identity of the peer.
  90    */
  91   struct GNUNET_PeerIdentity peer;
  92
  93   /**
  94    * Original index in the key generation round.
  95    * Necessary for computing the lagrange coefficients.
  96    */
  97   unsigned int original_index;
  98
  99   /**
 100    * Set to the partial decryption of
 101    * this peer, or NULL if we did not
 102    * receive a partial decryption from this
 103    * peer or the zero knowledge proof failed.
 104    */
 105   gcry_mpi_t partial_decryption;
 106 };
 107
 108
 109 /**
 110  * State we keep per client.
 111  */
 112 struct ClientState;
 113
 114
 115 /**
 116  * Session to establish a threshold-shared secret.
 117  */
 118 struct KeygenSession {
 119   /**
 120    * Current consensus, used for both DKG rounds.
 121    */
 122   struct GNUNET_CONSENSUS_Handle *consensus;
 123
 124   /**
 125    * Which client is this for?
 126    */
 127   struct ClientState *cs;
 128
 129   /**
 130    * Randomly generated coefficients of the polynomial for sharing our
 131    * pre-secret, where 'preshares[0]' is our pre-secret.  Contains 'threshold'
 132    * elements, thus represents a polynomial of degree 'threshold-1', which can
 133    * be interpolated with 'threshold' data points.
 134    *
 135    * The pre-secret-shares 'i=1,...,num_peers' are given by evaluating this
 136    * polyomial at 'i' for share i.
 137    */
 138   gcry_mpi_t *presecret_polynomial;
 139
 140   /**
 141    * Minimum number of shares required to restore the secret.
 142    * Also the number of coefficients for the polynomial representing
 143    * the sharing.  Obviously, the polynomial then has degree threshold-1.
 144    */
 145   unsigned int threshold;
 146
 147   /**
 148    * Total number of peers.
 149    */
 150   unsigned int num_peers;
 151
 152   /**
 153    * Index of the local peer.
 154    */
 155   unsigned int local_peer;
 156
 157   /**
 158    * Information about all participating peers.
 159    * Array of size 'num_peers'.
 160    */
 161   struct KeygenPeerInfo *info;
 162
 163   /**
 164    * List of all peers involved in the secret sharing session.
 165    */
 166   struct GNUNET_PeerIdentity *peers;
 167
 168   /**
 169    * Identifier for this session.
 170    */
 171   struct GNUNET_HashCode session_id;
 172
 173   /**
 174    * Paillier private key of our peer.
 175    */
 176   struct GNUNET_CRYPTO_PaillierPrivateKey paillier_private_key;
 177
 178   /**
 179    * When would we like the key to be established?
 180    */
 181   struct GNUNET_TIME_Absolute deadline;
 182
 183   /**
 184    * When does the DKG start?  Necessary to compute fractions of the
 185    * operation's desired time interval.
 186    */
 187   struct GNUNET_TIME_Absolute start_time;
 188
 189   /**
 190    * Index of the local peer in the ordered list
 191    * of peers in the session.
 192    */
 193   unsigned int local_peer_idx;
 194
 195   /**
 196    * Share of our peer.  Once preshares from other peers are received, they
 197    * will be added to 'my'share.
 198    */
 199   gcry_mpi_t my_share;
 200
 201   /**
 202    * Public key, will be updated when a round2 element arrives.
 203    */
 204   gcry_mpi_t public_key;
 205 };
 206
 207
 208 /**
 209  * Session to cooperatively decrypt a value.
 210  */
 211 struct DecryptSession {
 212   /**
 213    * Handle to the consensus over partial decryptions.
 214    */
 215   struct GNUNET_CONSENSUS_Handle *consensus;
 216
 217   /**
 218    * Which client is this for?
 219    */
 220   struct ClientState *cs;
 221
 222   /**
 223    * When should we start communicating for decryption?
 224    */
 225   struct GNUNET_TIME_Absolute start;
 226
 227   /**
 228    * When would we like the ciphertext to be
 229    * decrypted?
 230    */
 231   struct GNUNET_TIME_Absolute deadline;
 232
 233   /**
 234    * Ciphertext we want to decrypt.
 235    */
 236   struct GNUNET_SECRETSHARING_Ciphertext ciphertext;
 237
 238   /**
 239    * Share of the local peer.
 240    * Containts other important information, such as
 241    * the list of other peers.
 242    */
 243   struct GNUNET_SECRETSHARING_Share *share;
 244
 245   /**
 246    * State information about other peers.
 247    */
 248   struct DecryptPeerInfo *info;
 249 };
 250
 251
 252 /**
 253  * State we keep per client.
 254  */
 255 struct ClientState {
 256   /**
 257    * Decrypt session of the client, if any.
 258    */
 259   struct DecryptSession *decrypt_session;
 260
 261   /**
 262    * Keygen session of the client, if any.
 263    */
 264   struct KeygenSession *keygen_session;
 265
 266   /**
 267    * Client this is about.
 268    */
 269   struct GNUNET_SERVICE_Client *client;
 270
 271   /**
 272    * MQ to talk to @a client.
 273    */
 274   struct GNUNET_MQ_Handle *mq;
 275 };
 276
 277
 278 /**
 279  * The ElGamal prime field order as libgcrypt mpi.
 280  * Initialized in #init_crypto_constants.
 281  */
 282 static gcry_mpi_t elgamal_q;
 283
 284 /**
 285  * Modulus of the prime field used for ElGamal.
 286  * Initialized in #init_crypto_constants.
 287  */
 288 static gcry_mpi_t elgamal_p;
 289
 290 /**
 291  * Generator for prime field of order 'elgamal_q'.
 292  * Initialized in #init_crypto_constants.
 293  */
 294 static gcry_mpi_t elgamal_g;
 295
 296 /**
 297  * Peer that runs this service.
 298  */
 299 static struct GNUNET_PeerIdentity my_peer;
 300
 301 /**
 302  * Peer that runs this service.
 303  */
 304 static struct GNUNET_CRYPTO_EddsaPrivateKey *my_peer_private_key;
 305
 306 /**
 307  * Configuration of this service.
 308  */
 309 static const struct GNUNET_CONFIGURATION_Handle *cfg;
 310
 311
 312 /**
 313  * Get the peer info belonging to a peer identity in a keygen session.
 314  *
 315  * @param ks The keygen session.
 316  * @param peer The peer identity.
 317  * @return The Keygen peer info, or NULL if the peer could not be found.
 318  */
 319 static struct KeygenPeerInfo *
 320 get_keygen_peer_info(const struct KeygenSession *ks,
 321                      const struct GNUNET_PeerIdentity *peer)
 322 {
 323   unsigned int i;
 324
 325   for (i = 0; i < ks->num_peers; i++)
 326     if (0 == GNUNET_memcmp(peer, &ks->info[i].peer))
 327       return &ks->info[i];
 328   return NULL;
 329 }
 330
 331
 332 /**
 333  * Get the peer info belonging to a peer identity in a decrypt session.
 334  *
 335  * @param ds The decrypt session.
 336  * @param peer The peer identity.
 337  * @return The decrypt peer info, or NULL if the peer could not be found.
 338  */
 339 static struct DecryptPeerInfo *
 340 get_decrypt_peer_info(const struct DecryptSession *ds,
 341                       const struct GNUNET_PeerIdentity *peer)
 342 {
 343   unsigned int i;
 344
 345   for (i = 0; i < ds->share->num_peers; i++)
 346     if (0 == GNUNET_memcmp(peer, &ds->info[i].peer))
 347       return &ds->info[i];
 348   return NULL;
 349 }
 350
 351
 352 /**
 353  * Interpolate between two points in time.
 354  *
 355  * @param start start time
 356  * @param end end time
 357  * @param num numerator of the scale factor
 358  * @param denum denumerator of the scale factor
 359  */
 360 static struct GNUNET_TIME_Absolute
 361 time_between(struct GNUNET_TIME_Absolute start,
 362              struct GNUNET_TIME_Absolute end,
 363              int num, int denum)
 364 {
 365   struct GNUNET_TIME_Absolute result;
 366   uint64_t diff;
 367
 368   GNUNET_assert(start.abs_value_us <= end.abs_value_us);
 369   diff = end.abs_value_us - start.abs_value_us;
 370   result.abs_value_us = start.abs_value_us + ((diff * num) / denum);
 371
 372   return result;
 373 }
 374
 375
 376 /**
 377  * Compare two peer identities.  Indended to be used with qsort or bsearch.
 378  *
 379  * @param p1 Some peer identity.
 380  * @param p2 Some peer identity.
 381  * @return 1 if p1 > p2, -1 if p1 < p2 and 0 if p1 == p2.
 382  */
 383 static int
 384 peer_id_cmp(const void *p1, const void *p2)
 385 {
 386   return memcmp(p1,
 387                 p2,
 388                 sizeof(struct GNUNET_PeerIdentity));
 389 }
 390
 391
 392 /**
 393  * Get the index of a peer in an array of peers
 394  *
 395  * @param haystack Array of peers.
 396  * @param n Size of @a haystack.
 397  * @param needle Peer to find
 398  * @return Index of @a needle in @a haystack, or -1 if peer
 399  *         is not in the list.
 400  */
 401 static int
 402 peer_find(const struct GNUNET_PeerIdentity *haystack, unsigned int n,
 403           const struct GNUNET_PeerIdentity *needle)
 404 {
 405   unsigned int i;
 406
 407   for (i = 0; i < n; i++)
 408     if (0 == GNUNET_memcmp(&haystack[i],
 409                            needle))
 410       return i;
 411   return -1;
 412 }
 413
 414
 415 /**
 416  * Normalize the given list of peers, by including the local peer
 417  * (if it is missing) and sorting the peers by their identity.
 418  *
 419  * @param listed Peers in the unnormalized list.
 420  * @param num_listed Peers in the un-normalized list.
 421  * @param[out] num_normalized Number of peers in the normalized list.
 422  * @param[out] my_peer_idx Index of the local peer in the normalized list.
 423  * @return Normalized list, must be free'd by the caller.
 424  */
 425 static struct GNUNET_PeerIdentity *
 426 normalize_peers(struct GNUNET_PeerIdentity *listed,
 427                 unsigned int num_listed,
 428                 unsigned int *num_normalized,
 429                 unsigned int *my_peer_idx)
 430 {
 431   unsigned int local_peer_in_list;
 432   /* number of peers in the normalized list */
 433   unsigned int n;
 434   struct GNUNET_PeerIdentity *normalized;
 435
 436   local_peer_in_list = GNUNET_YES;
 437   n = num_listed;
 438   if (peer_find(listed, num_listed, &my_peer) < 0)
 439     {
 440       local_peer_in_list = GNUNET_NO;
 441       n += 1;
 442     }
 443
 444   normalized = GNUNET_new_array(n,
 445                                 struct GNUNET_PeerIdentity);
 446
 447   if (GNUNET_NO == local_peer_in_list)
 448     normalized[n - 1] = my_peer;
 449
 450   GNUNET_memcpy(normalized,
 451                 listed,
 452                 num_listed * sizeof(struct GNUNET_PeerIdentity));
 453   qsort(normalized,
 454         n,
 455         sizeof(struct GNUNET_PeerIdentity),
 456         &peer_id_cmp);
 457
 458   if (NULL != my_peer_idx)
 459     *my_peer_idx = peer_find(normalized, n, &my_peer);
 460   if (NULL != num_normalized)
 461     *num_normalized = n;
 462
 463   return normalized;
 464 }
 465
 466
 467 /**
 468  * Get a the j-th lagrange coefficient for a set of indices.
 469  *
 470  * @param[out] coeff the lagrange coefficient
 471  * @param j lagrange coefficient we want to compute
 472  * @param indices indices
 473  * @param num number of indices in @a indices
 474  */
 475 static void
 476 compute_lagrange_coefficient(gcry_mpi_t coeff, unsigned int j,
 477                              unsigned int *indices,
 478                              unsigned int num)
 479 {
 480   unsigned int i;
 481   /* numerator */
 482   gcry_mpi_t n;
 483   /* denominator */
 484   gcry_mpi_t d;
 485   /* temp value for l-j */
 486   gcry_mpi_t tmp;
 487
 488   GNUNET_assert(0 != coeff);
 489
 490   GNUNET_assert(0 != (n = gcry_mpi_new(0)));
 491   GNUNET_assert(0 != (d = gcry_mpi_new(0)));
 492   GNUNET_assert(0 != (tmp = gcry_mpi_new(0)));
 493
 494   gcry_mpi_set_ui(n, 1);
 495   gcry_mpi_set_ui(d, 1);
 496
 497   for (i = 0; i < num; i++)
 498     {
 499       unsigned int l = indices[i];
 500       if (l == j)
 501         continue;
 502       gcry_mpi_mul_ui(n, n, l + 1);
 503       // d <- d * (l-j)
 504       gcry_mpi_set_ui(tmp, l + 1);
 505       gcry_mpi_sub_ui(tmp, tmp, j + 1);
 506       gcry_mpi_mul(d, d, tmp);
 507     }
 508
 509   // gcry_mpi_invm does not like negative numbers ...
 510   gcry_mpi_mod(d, d, elgamal_q);
 511
 512   GNUNET_assert(gcry_mpi_cmp_ui(d, 0) > 0);
 513
 514   // now we do the actual division, with everything mod q, as we
 515   // are not operating on elements from <g>, but on exponents
 516   GNUNET_assert(0 != gcry_mpi_invm(d, d, elgamal_q));
 517
 518   gcry_mpi_mulm(coeff, n, d, elgamal_q);
 519
 520   gcry_mpi_release(n);
 521   gcry_mpi_release(d);
 522   gcry_mpi_release(tmp);
 523 }
 524
 525
 526 /**
 527  * Destroy a decrypt session, removing it from
 528  * the linked list of decrypt sessions.
 529  *
 530  * @param ds decrypt session to destroy
 531  */
 532 static void
 533 decrypt_session_destroy(struct DecryptSession *ds)
 534 {
 535   GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
 536              "destroying decrypt session\n");
 537   if (NULL != ds->cs)
 538     {
 539       ds->cs->decrypt_session = NULL;
 540       ds->cs = NULL;
 541     }
 542   if (NULL != ds->consensus)
 543     {
 544       GNUNET_CONSENSUS_destroy(ds->consensus);
 545       ds->consensus = NULL;
 546     }
 547
 548   if (NULL != ds->info)
 549     {
 550       for (unsigned int i = 0; i < ds->share->num_peers; i++)
 551         {
 552           if (NULL != ds->info[i].partial_decryption)
 553             {
 554               gcry_mpi_release(ds->info[i].partial_decryption);
 555               ds->info[i].partial_decryption = NULL;
 556             }
 557         }
 558       GNUNET_free(ds->info);
 559       ds->info = NULL;
 560     }
 561   if (NULL != ds->share)
 562     {
 563       GNUNET_SECRETSHARING_share_destroy(ds->share);
 564       ds->share = NULL;
 565     }
 566
 567   GNUNET_free(ds);
 568 }
 569
 570
 571 static void
 572 keygen_info_destroy(struct KeygenPeerInfo *info)
 573 {
 574   if (NULL != info->sigma)
 575     {
 576       gcry_mpi_release(info->sigma);
 577       info->sigma = NULL;
 578     }
 579   if (NULL != info->presecret_commitment)
 580     {
 581       gcry_mpi_release(info->presecret_commitment);
 582       info->presecret_commitment = NULL;
 583     }
 584   if (NULL != info->preshare_commitment)
 585     {
 586       gcry_mpi_release(info->preshare_commitment);
 587       info->preshare_commitment = NULL;
 588     }
 589 }
 590
 591
 592 static void
 593 keygen_session_destroy(struct KeygenSession *ks)
 594 {
 595   GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
 596              "destroying keygen session\n");
 597
 598   if (NULL != ks->cs)
 599     {
 600       ks->cs->keygen_session = NULL;
 601       ks->cs = NULL;
 602     }
 603   if (NULL != ks->info)
 604     {
 605       for (unsigned int i = 0; i < ks->num_peers; i++)
 606         keygen_info_destroy(&ks->info[i]);
 607       GNUNET_free(ks->info);
 608       ks->info = NULL;
 609     }
 610
 611   if (NULL != ks->consensus)
 612     {
 613       GNUNET_CONSENSUS_destroy(ks->consensus);
 614       ks->consensus = NULL;
 615     }
 616
 617   if (NULL != ks->presecret_polynomial)
 618     {
 619       for (unsigned int i = 0; i < ks->threshold; i++)
 620         {
 621           GNUNET_assert(NULL != ks->presecret_polynomial[i]);
 622           gcry_mpi_release(ks->presecret_polynomial[i]);
 623           ks->presecret_polynomial[i] = NULL;
 624         }
 625       GNUNET_free(ks->presecret_polynomial);
 626       ks->presecret_polynomial = NULL;
 627     }
 628   if (NULL != ks->my_share)
 629     {
 630       gcry_mpi_release(ks->my_share);
 631       ks->my_share = NULL;
 632     }
 633   if (NULL != ks->public_key)
 634     {
 635       gcry_mpi_release(ks->public_key);
 636       ks->public_key = NULL;
 637     }
 638   if (NULL != ks->peers)
 639     {
 640       GNUNET_free(ks->peers);
 641       ks->peers = NULL;
 642     }
 643   GNUNET_free(ks);
 644 }
 645
 646
 647 /**
 648  * Task run during shutdown.
 649  *
 650  * @param cls unused
 651  * @param tc unused
 652  */
 653 static void
 654 cleanup_task(void *cls)
 655 {
 656   /* Nothing to do! */
 657 }
 658
 659
 660
 661 /**
 662  * Generate the random coefficients of our pre-secret polynomial
 663  *
 664  * @param ks the session
 665  */
 666 static void
 667 generate_presecret_polynomial(struct KeygenSession *ks)
 668 {
 669   int i;
 670   gcry_mpi_t v;
 671
 672   GNUNET_assert(NULL == ks->presecret_polynomial);
 673   ks->presecret_polynomial = GNUNET_new_array(ks->threshold,
 674                                               gcry_mpi_t);
 675   for (i = 0; i < ks->threshold; i++)
 676     {
 677       v = ks->presecret_polynomial[i] = gcry_mpi_new(GNUNET_SECRETSHARING_ELGAMAL_BITS);
 678       GNUNET_assert(NULL != v);
 679       // Randomize v such that 0 < v < elgamal_q.
 680       // The '- 1' is necessary as bitlength(q) = bitlength(p) - 1.
 681       do
 682         {
 683           gcry_mpi_randomize(v, GNUNET_SECRETSHARING_ELGAMAL_BITS - 1, GCRY_WEAK_RANDOM);
 684         }
 685       while ((gcry_mpi_cmp_ui(v, 0) == 0) || (gcry_mpi_cmp(v, elgamal_q) >= 0));
 686     }
 687 }
 688
 689
 690 /**
 691  * Consensus element handler for round one.
 692  * We should get one ephemeral key for each peer.
 693  *
 694  * @param cls Closure (keygen session).
 695  * @param element The element from consensus, or
 696  *                NULL if consensus failed.
 697  */
 698 static void
 699 keygen_round1_new_element(void *cls,
 700                           const struct GNUNET_SET_Element *element)
 701 {
 702   const struct GNUNET_SECRETSHARING_KeygenCommitData *d;
 703   struct KeygenSession *ks = cls;
 704   struct KeygenPeerInfo *info;
 705
 706   if (NULL == element)
 707     {
 708       GNUNET_log(GNUNET_ERROR_TYPE_WARNING, "round1 consensus failed\n");
 709       return;
 710     }
 711
 712   /* elements have fixed size */
 713   if (element->size != sizeof(struct GNUNET_SECRETSHARING_KeygenCommitData))
 714     {
 715       GNUNET_log(GNUNET_ERROR_TYPE_WARNING,
 716                  "keygen commit data with wrong size (%u) in consensus, %u expected\n",
 717                  (unsigned int)element->size,
 718                  (unsigned int)sizeof(struct GNUNET_SECRETSHARING_KeygenCommitData));
 719       return;
 720     }
 721
 722   GNUNET_log(GNUNET_ERROR_TYPE_INFO, "got round1 element\n");
 723
 724   d = element->data;
 725   info = get_keygen_peer_info(ks, &d->peer);
 726
 727   if (NULL == info)
 728     {
 729       GNUNET_log(GNUNET_ERROR_TYPE_WARNING, "keygen commit data with wrong peer identity (%s) in consensus\n",
 730                  GNUNET_i2s(&d->peer));
 731       return;
 732     }
 733
 734   /* Check that the right amount of data has been signed. */
 735   if (d->purpose.size !=
 736       htonl(element->size - offsetof(struct GNUNET_SECRETSHARING_KeygenCommitData, purpose)))
 737     {
 738       GNUNET_log(GNUNET_ERROR_TYPE_WARNING, "keygen commit data with wrong signature purpose size in consensus\n");
 739       return;
 740     }
 741
 742   if (GNUNET_OK != GNUNET_CRYPTO_eddsa_verify(GNUNET_SIGNATURE_PURPOSE_SECRETSHARING_DKG1,
 743                                               &d->purpose, &d->signature, &d->peer.public_key))
 744     {
 745       GNUNET_log(GNUNET_ERROR_TYPE_WARNING, "keygen commit data with invalid signature in consensus\n");
 746       return;
 747     }
 748   info->paillier_public_key = d->pubkey;
 749   GNUNET_CRYPTO_mpi_scan_unsigned(&info->presecret_commitment, &d->commitment, 512 / 8);
 750   info->round1_valid = GNUNET_YES;
 751 }
 752
 753
 754 /**
 755  * Evaluate the polynomial with coefficients @a coeff at @a x.
 756  * The i-th element in @a coeff corresponds to the coefficient of x^i.
 757  *
 758  * @param[out] z result of the evaluation
 759  * @param coeff array of coefficients
 760  * @param num_coeff number of coefficients
 761  * @param x where to evaluate the polynomial
 762  * @param m what group are we operating in?
 763  */
 764 static void
 765 horner_eval(gcry_mpi_t z, gcry_mpi_t *coeff, unsigned int num_coeff, gcry_mpi_t x, gcry_mpi_t m)
 766 {
 767   unsigned int i;
 768
 769   gcry_mpi_set_ui(z, 0);
 770   for (i = 0; i < num_coeff; i++)
 771     {
 772       // z <- zx + c
 773       gcry_mpi_mul(z, z, x);
 774       gcry_mpi_addm(z, z, coeff[num_coeff - i - 1], m);
 775     }
 776 }
 777
 778
 779 static void
 780 keygen_round2_conclude(void *cls)
 781 {
 782   struct KeygenSession *ks = cls;
 783   struct GNUNET_SECRETSHARING_SecretReadyMessage *m;
 784   struct GNUNET_MQ_Envelope *ev;
 785   size_t share_size;
 786   unsigned int i;
 787   unsigned int j;
 788   struct GNUNET_SECRETSHARING_Share *share;
 789
 790   GNUNET_log(GNUNET_ERROR_TYPE_INFO, "round2 conclude\n");
 791
 792   GNUNET_CONSENSUS_destroy(ks->consensus);
 793   ks->consensus = NULL;
 794
 795   share = GNUNET_new(struct GNUNET_SECRETSHARING_Share);
 796
 797   share->num_peers = 0;
 798
 799   for (i = 0; i < ks->num_peers; i++)
 800     if (GNUNET_YES == ks->info[i].round2_valid)
 801       share->num_peers++;
 802
 803   share->peers = GNUNET_new_array(share->num_peers,
 804                                   struct GNUNET_PeerIdentity);
 805   share->sigmas =
 806     GNUNET_new_array(share->num_peers,
 807                      struct GNUNET_SECRETSHARING_FieldElement);
 808   share->original_indices = GNUNET_new_array(share->num_peers,
 809                                              uint16_t);
 810
 811   /* maybe we're not even in the list of peers? */
 812   share->my_peer = share->num_peers;
 813
 814   j = 0; /* running index of valid peers */
 815   for (i = 0; i < ks->num_peers; i++)
 816     {
 817       if (GNUNET_YES == ks->info[i].round2_valid)
 818         {
 819           share->peers[j] = ks->info[i].peer;
 820           GNUNET_CRYPTO_mpi_print_unsigned(&share->sigmas[j],
 821                                            GNUNET_SECRETSHARING_ELGAMAL_BITS / 8,
 822                                            ks->info[i].sigma);
 823           share->original_indices[i] = j;
 824           if (0 == GNUNET_memcmp(&share->peers[i], &my_peer))
 825             share->my_peer = j;
 826           j += 1;
 827         }
 828     }
 829
 830   if (share->my_peer == share->num_peers)
 831     {
 832       GNUNET_log(GNUNET_ERROR_TYPE_INFO, "P%u: peer identity not in share\n", ks->local_peer_idx);
 833     }
 834
 835   GNUNET_CRYPTO_mpi_print_unsigned(&share->my_share, GNUNET_SECRETSHARING_ELGAMAL_BITS / 8,
 836                                    ks->my_share);
 837   GNUNET_CRYPTO_mpi_print_unsigned(&share->public_key, GNUNET_SECRETSHARING_ELGAMAL_BITS / 8,
 838                                    ks->public_key);
 839
 840   GNUNET_log(GNUNET_ERROR_TYPE_INFO, "keygen completed with %u peers\n", share->num_peers);
 841
 842   /* Write the share. If 0 peers completed the dkg, an empty
 843    * share will be sent. */
 844
 845   GNUNET_assert(GNUNET_OK == GNUNET_SECRETSHARING_share_write(share, NULL, 0, &share_size));
 846
 847   GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "writing share of size %u\n",
 848              (unsigned int)share_size);
 849
 850   ev = GNUNET_MQ_msg_extra(m, share_size,
 851                            GNUNET_MESSAGE_TYPE_SECRETSHARING_CLIENT_SECRET_READY);
 852
 853   GNUNET_assert(GNUNET_OK == GNUNET_SECRETSHARING_share_write(share, &m[1], share_size, NULL));
 854
 855   GNUNET_SECRETSHARING_share_destroy(share);
 856   share = NULL;
 857
 858   GNUNET_MQ_send(ks->cs->mq,
 859                  ev);
 860 }
 861
 862
 863
 864 static void
 865 restore_fair(const struct GNUNET_CRYPTO_PaillierPublicKey *ppub,
 866              const struct GNUNET_SECRETSHARING_FairEncryption *fe,
 867              gcry_mpi_t x, gcry_mpi_t xres)
 868 {
 869   gcry_mpi_t a_1;
 870   gcry_mpi_t a_2;
 871   gcry_mpi_t b_1;
 872   gcry_mpi_t b_2;
 873   gcry_mpi_t big_a;
 874   gcry_mpi_t big_b;
 875   gcry_mpi_t big_t;
 876   gcry_mpi_t n;
 877   gcry_mpi_t t_1;
 878   gcry_mpi_t t_2;
 879   gcry_mpi_t t;
 880   gcry_mpi_t r;
 881   gcry_mpi_t v;
 882
 883
 884   GNUNET_assert(NULL != (n = gcry_mpi_new(0)));
 885   GNUNET_assert(NULL != (t = gcry_mpi_new(0)));
 886   GNUNET_assert(NULL != (t_1 = gcry_mpi_new(0)));
 887   GNUNET_assert(NULL != (t_2 = gcry_mpi_new(0)));
 888   GNUNET_assert(NULL != (r = gcry_mpi_new(0)));
 889   GNUNET_assert(NULL != (big_t = gcry_mpi_new(0)));
 890   GNUNET_assert(NULL != (v = gcry_mpi_new(0)));
 891   GNUNET_assert(NULL != (big_a = gcry_mpi_new(0)));
 892   GNUNET_assert(NULL != (big_b = gcry_mpi_new(0)));
 893
 894   // a = (N,0)^T
 895   GNUNET_CRYPTO_mpi_scan_unsigned(&a_1,
 896                                   ppub,
 897                                   sizeof(struct GNUNET_CRYPTO_PaillierPublicKey));
 898   GNUNET_assert(NULL != (a_2 = gcry_mpi_new(0)));
 899   gcry_mpi_set_ui(a_2, 0);
 900   // b = (x,1)^T
 901   GNUNET_assert(NULL != (b_1 = gcry_mpi_new(0)));
 902   gcry_mpi_set(b_1, x);
 903   GNUNET_assert(NULL != (b_2 = gcry_mpi_new(0)));
 904   gcry_mpi_set_ui(b_2, 1);
 905
 906   // A = a DOT a
 907   gcry_mpi_mul(t, a_1, a_1);
 908   gcry_mpi_mul(big_a, a_2, a_2);
 909   gcry_mpi_add(big_a, big_a, t);
 910
 911   // B = b DOT b
 912   gcry_mpi_mul(t, b_1, b_1);
 913   gcry_mpi_mul(big_b, b_2, b_2);
 914   gcry_mpi_add(big_b, big_b, t);
 915
 916   while (1)
 917     {
 918       // n = a DOT b
 919       gcry_mpi_mul(t, a_1, b_1);
 920       gcry_mpi_mul(n, a_2, b_2);
 921       gcry_mpi_add(n, n, t);
 922
 923       // r = nearest(n/B)
 924       gcry_mpi_div(r, NULL, n, big_b, 0);
 925
 926       // T := A - 2rn + rrB
 927       gcry_mpi_mul(v, r, n);
 928       gcry_mpi_mul_ui(v, v, 2);
 929       gcry_mpi_sub(big_t, big_a, v);
 930       gcry_mpi_mul(v, r, r);
 931       gcry_mpi_mul(v, v, big_b);
 932       gcry_mpi_add(big_t, big_t, v);
 933
 934       if (gcry_mpi_cmp(big_t, big_b) >= 0)
 935         {
 936           break;
 937         }
 938
 939       // t = a - rb
 940       gcry_mpi_mul(v, r, b_1);
 941       gcry_mpi_sub(t_1, a_1, v);
 942       gcry_mpi_mul(v, r, b_2);
 943       gcry_mpi_sub(t_2, a_2, v);
 944
 945       // a = b
 946       gcry_mpi_set(a_1, b_1);
 947       gcry_mpi_set(a_2, b_2);
 948       // b = t
 949       gcry_mpi_set(b_1, t_1);
 950       gcry_mpi_set(b_2, t_2);
 951
 952       gcry_mpi_set(big_a, big_b);
 953       gcry_mpi_set(big_b, big_t);
 954     }
 955
 956   gcry_mpi_set(xres, b_2);
 957   gcry_mpi_invm(xres, xres, elgamal_q);
 958   gcry_mpi_mulm(xres, xres, b_1, elgamal_q);
 959
 960   gcry_mpi_release(a_1);
 961   gcry_mpi_release(a_2);
 962   gcry_mpi_release(b_1);
 963   gcry_mpi_release(b_2);
 964   gcry_mpi_release(big_a);
 965   gcry_mpi_release(big_b);
 966   gcry_mpi_release(big_t);
 967   gcry_mpi_release(n);
 968   gcry_mpi_release(t_1);
 969   gcry_mpi_release(t_2);
 970   gcry_mpi_release(t);
 971   gcry_mpi_release(r);
 972   gcry_mpi_release(v);
 973 }
 974
 975
 976 static void
 977 get_fair_encryption_challenge(const struct GNUNET_SECRETSHARING_FairEncryption *fe,
 978                               gcry_mpi_t *e)
 979 {
 980   struct {
 981     struct GNUNET_CRYPTO_PaillierCiphertext c;
 982     char h[GNUNET_SECRETSHARING_ELGAMAL_BITS / 8];
 983     char t1[GNUNET_SECRETSHARING_ELGAMAL_BITS / 8];
 984     char t2[GNUNET_CRYPTO_PAILLIER_BITS * 2 / 8];
 985   } hash_data;
 986   struct GNUNET_HashCode e_hash;
 987
 988   memset(&hash_data,
 989          0,
 990          sizeof(hash_data));
 991   GNUNET_memcpy(&hash_data.c, &fe->c, sizeof(struct GNUNET_CRYPTO_PaillierCiphertext));
 992   GNUNET_memcpy(&hash_data.h, &fe->h, GNUNET_SECRETSHARING_ELGAMAL_BITS / 8);
 993   GNUNET_memcpy(&hash_data.t1, &fe->t1, GNUNET_SECRETSHARING_ELGAMAL_BITS / 8);
 994   GNUNET_memcpy(&hash_data.t2, &fe->t2, GNUNET_CRYPTO_PAILLIER_BITS * 2 / 8);
 995   GNUNET_CRYPTO_hash(&hash_data,
 996                      sizeof(hash_data),
 997                      &e_hash);
 998   /* This allocates "e" */
 999   GNUNET_CRYPTO_mpi_scan_unsigned(e,
1000                                   &e_hash,
1001                                   sizeof(struct GNUNET_HashCode));
1002   gcry_mpi_mod(*e, *e, elgamal_q);
1003 }
1004
1005
1006 static int
1007 verify_fair(const struct GNUNET_CRYPTO_PaillierPublicKey *ppub,
1008             const struct GNUNET_SECRETSHARING_FairEncryption *fe)
1009 {
1010   gcry_mpi_t n;
1011   gcry_mpi_t n_sq;
1012   gcry_mpi_t z;
1013   gcry_mpi_t t1;
1014   gcry_mpi_t t2;
1015   gcry_mpi_t e;
1016   gcry_mpi_t w;
1017   gcry_mpi_t tmp1;
1018   gcry_mpi_t tmp2;
1019   gcry_mpi_t y;
1020   gcry_mpi_t big_y;
1021   int res;
1022
1023   GNUNET_assert(NULL != (n_sq = gcry_mpi_new(0)));
1024   GNUNET_assert(NULL != (tmp1 = gcry_mpi_new(0)));
1025   GNUNET_assert(NULL != (tmp2 = gcry_mpi_new(0)));
1026
1027   get_fair_encryption_challenge(fe,
1028                                 &e /* this allocates e */);
1029
1030   GNUNET_CRYPTO_mpi_scan_unsigned(&n,
1031                                   ppub,
1032                                   sizeof(struct GNUNET_CRYPTO_PaillierPublicKey));
1033   GNUNET_CRYPTO_mpi_scan_unsigned(&t1, fe->t1, GNUNET_CRYPTO_PAILLIER_BITS / 8);
1034   GNUNET_CRYPTO_mpi_scan_unsigned(&z, fe->z, GNUNET_SECRETSHARING_ELGAMAL_BITS / 8);
1035   GNUNET_CRYPTO_mpi_scan_unsigned(&y, fe->h, GNUNET_SECRETSHARING_ELGAMAL_BITS / 8);
1036   GNUNET_CRYPTO_mpi_scan_unsigned(&w, fe->w, GNUNET_CRYPTO_PAILLIER_BITS / 8);
1037   GNUNET_CRYPTO_mpi_scan_unsigned(&big_y, fe->c.bits, GNUNET_CRYPTO_PAILLIER_BITS * 2 / 8);
1038   GNUNET_CRYPTO_mpi_scan_unsigned(&t2, fe->t2, GNUNET_CRYPTO_PAILLIER_BITS * 2 / 8);
1039   gcry_mpi_mul(n_sq, n, n);
1040
1041   // tmp1 = g^z
1042   gcry_mpi_powm(tmp1, elgamal_g, z, elgamal_p);
1043   // tmp2 = y^{-e}
1044   gcry_mpi_powm(tmp1, y, e, elgamal_p);
1045   gcry_mpi_invm(tmp1, tmp1, elgamal_p);
1046   // tmp1 = tmp1 * tmp2
1047   gcry_mpi_mulm(tmp1, tmp1, tmp2, elgamal_p);
1048
1049   if (0 == gcry_mpi_cmp(t1, tmp1))
1050     {
1051       GNUNET_log(GNUNET_ERROR_TYPE_ERROR, "fair encryption invalid (t1)\n");
1052       res = GNUNET_NO;
1053       goto cleanup;
1054     }
1055
1056   gcry_mpi_powm(big_y, big_y, e, n_sq);
1057   gcry_mpi_invm(big_y, big_y, n_sq);
1058
1059   gcry_mpi_add_ui(tmp1, n, 1);
1060   gcry_mpi_powm(tmp1, tmp1, z, n_sq);
1061
1062   gcry_mpi_powm(tmp2, w, n, n_sq);
1063
1064   gcry_mpi_mulm(tmp1, tmp1, tmp2, n_sq);
1065   gcry_mpi_mulm(tmp1, tmp1, big_y, n_sq);
1066
1067
1068   if (0 == gcry_mpi_cmp(t2, tmp1))
1069     {
1070       GNUNET_log(GNUNET_ERROR_TYPE_ERROR, "fair encryption invalid (t2)\n");
1071       res = GNUNET_NO;
1072       goto cleanup;
1073     }
1074
1075   res = GNUNET_YES;
1076
1077 cleanup:
1078
1079   gcry_mpi_release(n);
1080   gcry_mpi_release(n_sq);
1081   gcry_mpi_release(z);
1082   gcry_mpi_release(t1);
1083   gcry_mpi_release(t2);
1084   gcry_mpi_release(e);
1085   gcry_mpi_release(w);
1086   gcry_mpi_release(tmp1);
1087   gcry_mpi_release(tmp2);
1088   gcry_mpi_release(y);
1089   gcry_mpi_release(big_y);
1090   return res;
1091 }
1092
1093
1094 /**
1095  * Create a fair Paillier encryption of then given ciphertext.
1096  *
1097  * @param v the ciphertext
1098  * @param[out] fe the fair encryption
1099  */
1100 static void
1101 encrypt_fair(gcry_mpi_t v,
1102              const struct GNUNET_CRYPTO_PaillierPublicKey *ppub,
1103              struct GNUNET_SECRETSHARING_FairEncryption *fe)
1104 {
1105   gcry_mpi_t r;
1106   gcry_mpi_t s;
1107   gcry_mpi_t t1;
1108   gcry_mpi_t t2;
1109   gcry_mpi_t z;
1110   gcry_mpi_t w;
1111   gcry_mpi_t n;
1112   gcry_mpi_t e;
1113   gcry_mpi_t n_sq;
1114   gcry_mpi_t u;
1115   gcry_mpi_t Y;
1116   gcry_mpi_t G;
1117   gcry_mpi_t h;
1118
1119   GNUNET_assert(NULL != (r = gcry_mpi_new(0)));
1120   GNUNET_assert(NULL != (s = gcry_mpi_new(0)));
1121   GNUNET_assert(NULL != (t1 = gcry_mpi_new(0)));
1122   GNUNET_assert(NULL != (t2 = gcry_mpi_new(0)));
1123   GNUNET_assert(NULL != (z = gcry_mpi_new(0)));
1124   GNUNET_assert(NULL != (w = gcry_mpi_new(0)));
1125   GNUNET_assert(NULL != (n_sq = gcry_mpi_new(0)));
1126   GNUNET_assert(NULL != (u = gcry_mpi_new(0)));
1127   GNUNET_assert(NULL != (Y = gcry_mpi_new(0)));
1128   GNUNET_assert(NULL != (G = gcry_mpi_new(0)));
1129   GNUNET_assert(NULL != (h = gcry_mpi_new(0)));
1130
1131   GNUNET_CRYPTO_mpi_scan_unsigned(&n,
1132                                   ppub,
1133                                   sizeof(struct GNUNET_CRYPTO_PaillierPublicKey));
1134   gcry_mpi_mul(n_sq, n, n);
1135   gcry_mpi_add_ui(G, n, 1);
1136
1137   do
1138     {
1139       gcry_mpi_randomize(u, GNUNET_CRYPTO_PAILLIER_BITS, GCRY_WEAK_RANDOM);
1140     }
1141   while (gcry_mpi_cmp(u, n) >= 0);
1142
1143   gcry_mpi_powm(t1, G, v, n_sq);
1144   gcry_mpi_powm(t2, u, n, n_sq);
1145   gcry_mpi_mulm(Y, t1, t2, n_sq);
1146
1147   GNUNET_CRYPTO_mpi_print_unsigned(fe->c.bits,
1148                                    sizeof fe->c.bits,
1149                                    Y);
1150
1151
1152   gcry_mpi_randomize(r, 2048, GCRY_WEAK_RANDOM);
1153   do
1154     {
1155       gcry_mpi_randomize(s, GNUNET_CRYPTO_PAILLIER_BITS, GCRY_WEAK_RANDOM);
1156     }
1157   while (gcry_mpi_cmp(s, n) >= 0);
1158
1159   // compute t1
1160   gcry_mpi_mulm(t1, elgamal_g, r, elgamal_p);
1161   // compute t2 (use z and w as temp)
1162   gcry_mpi_powm(z, G, r, n_sq);
1163   gcry_mpi_powm(w, s, n, n_sq);
1164   gcry_mpi_mulm(t2, z, w, n_sq);
1165
1166
1167   gcry_mpi_powm(h, elgamal_g, v, elgamal_p);
1168
1169   GNUNET_CRYPTO_mpi_print_unsigned(fe->h,
1170                                    GNUNET_SECRETSHARING_ELGAMAL_BITS / 8,
1171                                    h);
1172
1173   GNUNET_CRYPTO_mpi_print_unsigned(fe->t1,
1174                                    GNUNET_SECRETSHARING_ELGAMAL_BITS / 8,
1175                                    t1);
1176
1177   GNUNET_CRYPTO_mpi_print_unsigned(fe->t2,
1178                                    GNUNET_CRYPTO_PAILLIER_BITS * 2 / 8,
1179                                    t2);
1180
1181   get_fair_encryption_challenge(fe,
1182                                 &e /* This allocates "e" */);
1183
1184   // compute z
1185   gcry_mpi_mul(z, e, v);
1186   gcry_mpi_addm(z, z, r, elgamal_q);
1187   // compute w
1188   gcry_mpi_powm(w, u, e, n);
1189   gcry_mpi_mulm(w, w, s, n);
1190
1191   GNUNET_CRYPTO_mpi_print_unsigned(fe->z,
1192                                    GNUNET_SECRETSHARING_ELGAMAL_BITS / 8,
1193                                    z);
1194
1195   GNUNET_CRYPTO_mpi_print_unsigned(fe->w,
1196                                    GNUNET_CRYPTO_PAILLIER_BITS / 8,
1197                                    w);
1198
1199   gcry_mpi_release(n);
1200   gcry_mpi_release(r);
1201   gcry_mpi_release(s);
1202   gcry_mpi_release(t1);
1203   gcry_mpi_release(t2);
1204   gcry_mpi_release(z);
1205   gcry_mpi_release(w);
1206   gcry_mpi_release(e);
1207   gcry_mpi_release(n_sq);
1208   gcry_mpi_release(u);
1209   gcry_mpi_release(Y);
1210   gcry_mpi_release(G);
1211   gcry_mpi_release(h);
1212 }
1213
1214
1215 /**
1216  * Insert round 2 element in the consensus, consisting of
1217  * (1) The exponentiated pre-share polynomial coefficients A_{i,l}=g^{a_{i,l}}
1218  * (2) The exponentiated pre-shares y_{i,j}=g^{s_{i,j}}
1219  * (3) The encrypted pre-shares Y_{i,j}
1220  * (4) The zero knowledge proof for fairness of
1221  *     the encryption
1222  *
1223  * @param ks session to use
1224  */
1225 static void
1226 insert_round2_element(struct KeygenSession *ks)
1227 {
1228   struct GNUNET_SET_Element *element;
1229   struct GNUNET_SECRETSHARING_KeygenRevealData *d;
1230   unsigned char *pos;
1231   unsigned char *last_pos;
1232   size_t element_size;
1233   unsigned int i;
1234   gcry_mpi_t idx;
1235   gcry_mpi_t v;
1236
1237   GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "P%u: Inserting round2 element\n",
1238              ks->local_peer_idx);
1239
1240   GNUNET_assert(NULL != (v = gcry_mpi_new(GNUNET_SECRETSHARING_ELGAMAL_BITS)));
1241   GNUNET_assert(NULL != (idx = gcry_mpi_new(GNUNET_SECRETSHARING_ELGAMAL_BITS)));
1242
1243   element_size = (sizeof(struct GNUNET_SECRETSHARING_KeygenRevealData) +
1244                   sizeof(struct GNUNET_SECRETSHARING_FairEncryption) * ks->num_peers +
1245                   GNUNET_SECRETSHARING_ELGAMAL_BITS / 8 * ks->threshold);
1246
1247   element = GNUNET_malloc(sizeof(struct GNUNET_SET_Element) + element_size);
1248   element->size = element_size;
1249   element->data = (void *)&element[1];
1250
1251   d = (void *)element->data;
1252   d->peer = my_peer;
1253
1254   // start inserting vector elements
1255   // after the fixed part of the element's data
1256   pos = (void *)&d[1];
1257   last_pos = pos + element_size;
1258
1259   GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "P%u: computed exp preshares\n",
1260              ks->local_peer_idx);
1261
1262   // encrypted pre-shares
1263   // and fair encryption proof
1264   {
1265     for (i = 0; i < ks->num_peers; i++)
1266       {
1267         ptrdiff_t remaining = last_pos - pos;
1268         struct GNUNET_SECRETSHARING_FairEncryption *fe = (void *)pos;
1269
1270         GNUNET_assert(remaining > 0);
1271         memset(fe, 0, sizeof *fe);
1272         if (GNUNET_YES == ks->info[i].round1_valid)
1273           {
1274             gcry_mpi_set_ui(idx, i + 1);
1275             // evaluate the polynomial
1276             horner_eval(v, ks->presecret_polynomial, ks->threshold, idx, elgamal_q);
1277             // encrypt the result
1278             encrypt_fair(v, &ks->info[i].paillier_public_key, fe);
1279           }
1280         pos += sizeof *fe;
1281       }
1282   }
1283
1284   GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "P%u: computed enc preshares\n",
1285              ks->local_peer_idx);
1286
1287   // exponentiated coefficients
1288   for (i = 0; i < ks->threshold; i++)
1289     {
1290       ptrdiff_t remaining = last_pos - pos;
1291       GNUNET_assert(remaining > 0);
1292       gcry_mpi_powm(v, elgamal_g, ks->presecret_polynomial[i], elgamal_p);
1293       GNUNET_CRYPTO_mpi_print_unsigned(pos, GNUNET_SECRETSHARING_ELGAMAL_BITS / 8, v);
1294       pos += GNUNET_SECRETSHARING_ELGAMAL_BITS / 8;
1295     }
1296
1297   GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "P%u: computed exp coefficients\n",
1298              ks->local_peer_idx);
1299
1300
1301   d->purpose.size = htonl(element_size - offsetof(struct GNUNET_SECRETSHARING_KeygenRevealData, purpose));
1302   d->purpose.purpose = htonl(GNUNET_SIGNATURE_PURPOSE_SECRETSHARING_DKG2);
1303   GNUNET_assert(GNUNET_OK ==
1304                 GNUNET_CRYPTO_eddsa_sign(my_peer_private_key,
1305                                          &d->purpose,
1306                                          &d->signature));
1307
1308   GNUNET_CONSENSUS_insert(ks->consensus, element, NULL, NULL);
1309   GNUNET_free(element);  /* FIXME: maybe stack-allocate instead? */
1310
1311   gcry_mpi_release(v);
1312   gcry_mpi_release(idx);
1313 }
1314
1315
1316 static gcry_mpi_t
1317 keygen_reveal_get_exp_coeff(struct KeygenSession *ks,
1318                             const struct GNUNET_SECRETSHARING_KeygenRevealData *d,
1319                             unsigned int idx)
1320 {
1321   unsigned char *pos;
1322   gcry_mpi_t exp_coeff;
1323
1324   GNUNET_assert(idx < ks->threshold);
1325
1326   pos = (void *)&d[1];
1327   // skip encrypted pre-shares
1328   pos += sizeof(struct GNUNET_SECRETSHARING_FairEncryption) * ks->num_peers;
1329   // skip exp. coeffs we are not interested in
1330   pos += GNUNET_SECRETSHARING_ELGAMAL_BITS / 8 * idx;
1331   // the first exponentiated coefficient is the public key share
1332   GNUNET_CRYPTO_mpi_scan_unsigned(&exp_coeff, pos, GNUNET_SECRETSHARING_ELGAMAL_BITS / 8);
1333   return exp_coeff;
1334 }
1335
1336
1337 static struct GNUNET_SECRETSHARING_FairEncryption *
1338 keygen_reveal_get_enc_preshare(struct KeygenSession *ks,
1339                                const struct GNUNET_SECRETSHARING_KeygenRevealData *d,
1340                                unsigned int idx)
1341 {
1342   unsigned char *pos;
1343
1344   GNUNET_assert(idx < ks->num_peers);
1345
1346   pos = (void *)&d[1];
1347   // skip encrypted pre-shares we're not interested in
1348   pos += sizeof(struct GNUNET_SECRETSHARING_FairEncryption) * idx;
1349   return (struct GNUNET_SECRETSHARING_FairEncryption *)pos;
1350 }
1351
1352
1353 static gcry_mpi_t
1354 keygen_reveal_get_exp_preshare(struct KeygenSession *ks,
1355                                const struct GNUNET_SECRETSHARING_KeygenRevealData *d,
1356                                unsigned int idx)
1357 {
1358   gcry_mpi_t exp_preshare;
1359   struct GNUNET_SECRETSHARING_FairEncryption *fe;
1360
1361   GNUNET_assert(idx < ks->num_peers);
1362   fe = keygen_reveal_get_enc_preshare(ks, d, idx);
1363   GNUNET_CRYPTO_mpi_scan_unsigned(&exp_preshare, fe->h, GNUNET_SECRETSHARING_ELGAMAL_BITS / 8);
1364   return exp_preshare;
1365 }
1366
1367
1368 static void
1369 keygen_round2_new_element(void *cls,
1370                           const struct GNUNET_SET_Element *element)
1371 {
1372   struct KeygenSession *ks = cls;
1373   const struct GNUNET_SECRETSHARING_KeygenRevealData *d;
1374   struct KeygenPeerInfo *info;
1375   size_t expected_element_size;
1376   unsigned int j;
1377   int cmp_result;
1378   gcry_mpi_t tmp;
1379   gcry_mpi_t public_key_share;
1380   gcry_mpi_t preshare;
1381
1382   if (NULL == element)
1383     {
1384       GNUNET_log(GNUNET_ERROR_TYPE_WARNING, "round2 consensus failed\n");
1385       return;
1386     }
1387
1388   expected_element_size = (sizeof(struct GNUNET_SECRETSHARING_KeygenRevealData) +
1389                            sizeof(struct GNUNET_SECRETSHARING_FairEncryption) * ks->num_peers +
1390                            GNUNET_SECRETSHARING_ELGAMAL_BITS / 8 * ks->threshold);
1391
1392   if (element->size != expected_element_size)
1393     {
1394       GNUNET_log(GNUNET_ERROR_TYPE_WARNING,
1395                  "keygen round2 data with wrong size (%u) in consensus, %u expected\n",
1396                  (unsigned int)element->size,
1397                  (unsigned int)expected_element_size);
1398       return;
1399     }
1400
1401   d = (const void *)element->data;
1402
1403   info = get_keygen_peer_info(ks, &d->peer);
1404
1405   if (NULL == info)
1406     {
1407       GNUNET_log(GNUNET_ERROR_TYPE_WARNING, "keygen commit data with wrong peer identity (%s) in consensus\n",
1408                  GNUNET_i2s(&d->peer));
1409       return;
1410     }
1411
1412   if (GNUNET_NO == info->round1_valid)
1413     {
1414       GNUNET_log(GNUNET_ERROR_TYPE_WARNING,
1415                  "ignoring round2 element from peer with invalid round1 element (%s)\n",
1416                  GNUNET_i2s(&d->peer));
1417       return;
1418     }
1419
1420   if (GNUNET_YES == info->round2_valid)
1421     {
1422       GNUNET_log(GNUNET_ERROR_TYPE_WARNING,
1423                  "ignoring duplicate round2 element (%s)\n",
1424                  GNUNET_i2s(&d->peer));
1425       return;
1426     }
1427
1428   GNUNET_log(GNUNET_ERROR_TYPE_INFO, "got round2 element\n");
1429
1430   if (ntohl(d->purpose.size) !=
1431       element->size - offsetof(struct GNUNET_SECRETSHARING_KeygenRevealData, purpose))
1432     {
1433       GNUNET_log(GNUNET_ERROR_TYPE_WARNING, "keygen reveal data with wrong signature purpose size in consensus\n");
1434       return;
1435     }
1436
1437   if (GNUNET_OK != GNUNET_CRYPTO_eddsa_verify(GNUNET_SIGNATURE_PURPOSE_SECRETSHARING_DKG2,
1438                                               &d->purpose, &d->signature, &d->peer.public_key))
1439     {
1440       GNUNET_log(GNUNET_ERROR_TYPE_WARNING, "keygen reveal data with invalid signature in consensus\n");
1441       return;
1442     }
1443
1444   public_key_share = keygen_reveal_get_exp_coeff(ks, d, 0);
1445   info->preshare_commitment = keygen_reveal_get_exp_preshare(ks, d, ks->local_peer_idx);
1446
1447   if (NULL == ks->public_key)
1448     {
1449       GNUNET_assert(NULL != (ks->public_key = gcry_mpi_new(0)));
1450       gcry_mpi_set_ui(ks->public_key, 1);
1451     }
1452   gcry_mpi_mulm(ks->public_key, ks->public_key, public_key_share, elgamal_p);
1453
1454   gcry_mpi_release(public_key_share);
1455   public_key_share = NULL;
1456
1457   {
1458     struct GNUNET_SECRETSHARING_FairEncryption *fe = keygen_reveal_get_enc_preshare(ks, d, ks->local_peer_idx);
1459     GNUNET_assert(NULL != (preshare = gcry_mpi_new(0)));
1460     GNUNET_CRYPTO_paillier_decrypt(&ks->paillier_private_key,
1461                                    &ks->info[ks->local_peer_idx].paillier_public_key,
1462                                    &fe->c,
1463                                    preshare);
1464
1465     // FIXME: not doing the restoration is less expensive
1466     restore_fair(&ks->info[ks->local_peer_idx].paillier_public_key,
1467                  fe,
1468                  preshare,
1469                  preshare);
1470   }
1471
1472   GNUNET_assert(NULL != (tmp = gcry_mpi_new(0)));
1473   gcry_mpi_powm(tmp, elgamal_g, preshare, elgamal_p);
1474
1475   cmp_result = gcry_mpi_cmp(tmp, info->preshare_commitment);
1476   gcry_mpi_release(tmp);
1477   tmp = NULL;
1478   if (0 != cmp_result)
1479     {
1480       GNUNET_log(GNUNET_ERROR_TYPE_WARNING, "P%u: Got invalid presecret from P%u\n",
1481                  (unsigned int)ks->local_peer_idx, (unsigned int)(info - ks->info));
1482       return;
1483     }
1484
1485   if (NULL == ks->my_share)
1486     {
1487       GNUNET_assert(NULL != (ks->my_share = gcry_mpi_new(0)));
1488     }
1489   gcry_mpi_addm(ks->my_share, ks->my_share, preshare, elgamal_q);
1490
1491   for (j = 0; j < ks->num_peers; j++)
1492     {
1493       gcry_mpi_t presigma;
1494       if (NULL == ks->info[j].sigma)
1495         {
1496           GNUNET_assert(NULL != (ks->info[j].sigma = gcry_mpi_new(0)));
1497           gcry_mpi_set_ui(ks->info[j].sigma, 1);
1498         }
1499       presigma = keygen_reveal_get_exp_preshare(ks, d, j);
1500       gcry_mpi_mulm(ks->info[j].sigma, ks->info[j].sigma, presigma, elgamal_p);
1501       gcry_mpi_release(presigma);
1502     }
1503
1504   gcry_mpi_t prod;
1505   GNUNET_assert(NULL != (prod = gcry_mpi_new(0)));
1506   gcry_mpi_t j_to_k;
1507   GNUNET_assert(NULL != (j_to_k = gcry_mpi_new(0)));
1508   // validate that the polynomial sharing matches the additive sharing
1509   for (j = 0; j < ks->num_peers; j++)
1510     {
1511       unsigned int k;
1512       int cmp_result;
1513       gcry_mpi_t exp_preshare;
1514       gcry_mpi_set_ui(prod, 1);
1515       for (k = 0; k < ks->threshold; k++)
1516         {
1517           // Using pow(double,double) is a bit sketchy.
1518           // We count players from 1, but shares from 0.
1519           gcry_mpi_t tmp;
1520           gcry_mpi_set_ui(j_to_k, (unsigned int)pow(j + 1, k));
1521           tmp = keygen_reveal_get_exp_coeff(ks, d, k);
1522           gcry_mpi_powm(tmp, tmp, j_to_k, elgamal_p);
1523           gcry_mpi_mulm(prod, prod, tmp, elgamal_p);
1524           gcry_mpi_release(tmp);
1525         }
1526       exp_preshare = keygen_reveal_get_exp_preshare(ks, d, j);
1527       gcry_mpi_mod(exp_preshare, exp_preshare, elgamal_p);
1528       cmp_result = gcry_mpi_cmp(prod, exp_preshare);
1529       gcry_mpi_release(exp_preshare);
1530       exp_preshare = NULL;
1531       if (0 != cmp_result)
1532         {
1533           GNUNET_log(GNUNET_ERROR_TYPE_WARNING, "P%u: reveal data from P%u incorrect\n",
1534                      ks->local_peer_idx, j);
1535           /* no need for further verification, round2 stays invalid ... */
1536           return;
1537         }
1538     }
1539
1540   // TODO: verify proof of fair encryption (once implemented)
1541   for (j = 0; j < ks->num_peers; j++)
1542     {
1543       struct GNUNET_SECRETSHARING_FairEncryption *fe = keygen_reveal_get_enc_preshare(ks, d, j);
1544       if (GNUNET_YES != verify_fair(&ks->info[j].paillier_public_key, fe))
1545         {
1546           GNUNET_log(GNUNET_ERROR_TYPE_WARNING, "P%u: reveal data from P%u incorrect (fair encryption)\n",
1547                      ks->local_peer_idx, j);
1548           return;
1549         }
1550     }
1551
1552   info->round2_valid = GNUNET_YES;
1553
1554   gcry_mpi_release(preshare);
1555   gcry_mpi_release(prod);
1556   gcry_mpi_release(j_to_k);
1557 }
1558
1559
1560 /**
1561  * Called when the first consensus round has concluded.
1562  * Will initiate the second round.
1563  *
1564  * @param cls closure
1565  */
1566 static void
1567 keygen_round1_conclude(void *cls)
1568 {
1569   struct KeygenSession *ks = cls;
1570
1571   GNUNET_CONSENSUS_destroy(ks->consensus);
1572
1573   ks->consensus = GNUNET_CONSENSUS_create(cfg, ks->num_peers, ks->peers, &ks->session_id,
1574                                           time_between(ks->start_time, ks->deadline, 1, 2),
1575                                           ks->deadline,
1576                                           keygen_round2_new_element, ks);
1577
1578   insert_round2_element(ks);
1579
1580   GNUNET_CONSENSUS_conclude(ks->consensus,
1581                             keygen_round2_conclude,
1582                             ks);
1583 }
1584
1585
1586 /**
1587  * Insert the ephemeral key and the presecret commitment
1588  * of this peer in the consensus of the given session.
1589  *
1590  * @param ks session to use
1591  */
1592 static void
1593 insert_round1_element(struct KeygenSession *ks)
1594 {
1595   struct GNUNET_SET_Element *element;
1596   struct GNUNET_SECRETSHARING_KeygenCommitData *d;
1597   // g^a_{i,0}
1598   gcry_mpi_t v;
1599   // big-endian representation of 'v'
1600   unsigned char v_data[GNUNET_SECRETSHARING_ELGAMAL_BITS / 8];
1601
1602   element = GNUNET_malloc(sizeof *element + sizeof *d);
1603   d = (void *)&element[1];
1604   element->data = d;
1605   element->size = sizeof *d;
1606
1607   d->peer = my_peer;
1608
1609   GNUNET_assert(0 != (v = gcry_mpi_new(GNUNET_SECRETSHARING_ELGAMAL_BITS)));
1610
1611   gcry_mpi_powm(v, elgamal_g, ks->presecret_polynomial[0], elgamal_p);
1612
1613   GNUNET_CRYPTO_mpi_print_unsigned(v_data, GNUNET_SECRETSHARING_ELGAMAL_BITS / 8, v);
1614
1615   GNUNET_CRYPTO_hash(v_data, GNUNET_SECRETSHARING_ELGAMAL_BITS / 8, &d->commitment);
1616
1617   d->pubkey = ks->info[ks->local_peer_idx].paillier_public_key;
1618
1619   d->purpose.size = htonl((sizeof *d) - offsetof(struct GNUNET_SECRETSHARING_KeygenCommitData, purpose));
1620   d->purpose.purpose = htonl(GNUNET_SIGNATURE_PURPOSE_SECRETSHARING_DKG1);
1621   GNUNET_assert(GNUNET_OK ==
1622                 GNUNET_CRYPTO_eddsa_sign(my_peer_private_key,
1623                                          &d->purpose,
1624                                          &d->signature));
1625
1626   GNUNET_CONSENSUS_insert(ks->consensus, element, NULL, NULL);
1627
1628   gcry_mpi_release(v);
1629   GNUNET_free(element);
1630 }
1631
1632
1633 /**
1634  * Check that @a msg is well-formed.
1635  *
1636  * @param cls identification of the client
1637  * @param msg the actual message
1638  * @return #GNUNET_OK if @a msg is well-formed
1639  */
1640 static int
1641 check_client_keygen(void *cls,
1642                     const struct GNUNET_SECRETSHARING_CreateMessage *msg)
1643 {
1644   unsigned int num_peers = ntohs(msg->num_peers);
1645
1646   if (ntohs(msg->header.size) - sizeof(*msg) !=
1647       num_peers * sizeof(struct GNUNET_PeerIdentity))
1648     {
1649       GNUNET_break(0);
1650       return GNUNET_SYSERR;
1651     }
1652   return GNUNET_OK;
1653 }
1654
1655
1656 /**
1657  * Functions with this signature are called whenever a message is
1658  * received.
1659  *
1660  * @param cls identification of the client
1661  * @param msg the actual message
1662  */
1663 static void
1664 handle_client_keygen(void *cls,
1665                      const struct GNUNET_SECRETSHARING_CreateMessage *msg)
1666 {
1667   struct ClientState *cs = cls;
1668   struct KeygenSession *ks;
1669
1670   GNUNET_log(GNUNET_ERROR_TYPE_INFO,
1671              "client requested key generation\n");
1672   if (NULL != cs->keygen_session)
1673     {
1674       GNUNET_break(0);
1675       GNUNET_SERVICE_client_drop(cs->client);
1676       return;
1677     }
1678   ks = GNUNET_new(struct KeygenSession);
1679   ks->cs = cs;
1680   cs->keygen_session = ks;
1681   ks->deadline = GNUNET_TIME_absolute_ntoh(msg->deadline);
1682   ks->threshold = ntohs(msg->threshold);
1683   ks->num_peers = ntohs(msg->num_peers);
1684
1685   ks->peers = normalize_peers((struct GNUNET_PeerIdentity *)&msg[1],
1686                               ks->num_peers,
1687                               &ks->num_peers,
1688                               &ks->local_peer_idx);
1689
1690
1691   GNUNET_log(GNUNET_ERROR_TYPE_INFO,
1692              "first round of consensus with %u peers\n",
1693              ks->num_peers);
1694   ks->consensus = GNUNET_CONSENSUS_create(cfg,
1695                                           ks->num_peers,
1696                                           ks->peers,
1697                                           &msg->session_id,
1698                                           GNUNET_TIME_absolute_ntoh(msg->start),
1699                                           GNUNET_TIME_absolute_ntoh(msg->deadline),
1700                                           keygen_round1_new_element,
1701                                           ks);
1702
1703   ks->info = GNUNET_new_array(ks->num_peers,
1704                               struct KeygenPeerInfo);
1705
1706   for (unsigned int i = 0; i < ks->num_peers; i++)
1707     ks->info[i].peer = ks->peers[i];
1708
1709   GNUNET_CRYPTO_paillier_create(&ks->info[ks->local_peer_idx].paillier_public_key,
1710                                 &ks->paillier_private_key);
1711
1712   GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
1713              "P%u: Generated paillier key pair\n",
1714              ks->local_peer_idx);
1715   generate_presecret_polynomial(ks);
1716   GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
1717              "P%u: Generated presecret polynomial\n",
1718              ks->local_peer_idx);
1719   insert_round1_element(ks);
1720   GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
1721              "P%u: Concluding for round 1\n",
1722              ks->local_peer_idx);
1723   GNUNET_CONSENSUS_conclude(ks->consensus,
1724                             keygen_round1_conclude,
1725                             ks);
1726   GNUNET_SERVICE_client_continue(cs->client);
1727   GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
1728              "P%u: Waiting for round 1 elements ...\n",
1729              ks->local_peer_idx);
1730 }
1731
1732
1733 /**
1734  * Called when the partial decryption consensus concludes.
1735  */
1736 static void
1737 decrypt_conclude(void *cls)
1738 {
1739   struct DecryptSession *ds = cls;
1740   struct GNUNET_SECRETSHARING_DecryptResponseMessage *msg;
1741   struct GNUNET_MQ_Envelope *ev;
1742   gcry_mpi_t lagrange;
1743   gcry_mpi_t m;
1744   gcry_mpi_t tmp;
1745   gcry_mpi_t c_2;
1746   gcry_mpi_t prod;
1747   unsigned int *indices;
1748   unsigned int num;
1749   unsigned int i;
1750   unsigned int j;
1751
1752   GNUNET_CONSENSUS_destroy(ds->consensus);
1753   ds->consensus = NULL;
1754
1755   GNUNET_assert(0 != (lagrange = gcry_mpi_new(0)));
1756   GNUNET_assert(0 != (m = gcry_mpi_new(0)));
1757   GNUNET_assert(0 != (tmp = gcry_mpi_new(0)));
1758   GNUNET_assert(0 != (prod = gcry_mpi_new(0)));
1759
1760   num = 0;
1761   for (i = 0; i < ds->share->num_peers; i++)
1762     if (NULL != ds->info[i].partial_decryption)
1763       num++;
1764
1765   indices = GNUNET_new_array(num,
1766                              unsigned int);
1767   j = 0;
1768   for (i = 0; i < ds->share->num_peers; i++)
1769     if (NULL != ds->info[i].partial_decryption)
1770       indices[j++] = ds->info[i].original_index;
1771
1772   GNUNET_log(GNUNET_ERROR_TYPE_INFO,
1773              "P%u: decrypt conclude, with %u peers\n",
1774              ds->share->my_peer,
1775              num);
1776
1777   gcry_mpi_set_ui(prod, 1);
1778   for (i = 0; i < num; i++)
1779     {
1780       GNUNET_log(GNUNET_ERROR_TYPE_INFO,
1781                  "P%u: index of %u: %u\n",
1782                  ds->share->my_peer, i, indices[i]);
1783       compute_lagrange_coefficient(lagrange, indices[i], indices, num);
1784       // w_i^{\lambda_i}
1785       gcry_mpi_powm(tmp, ds->info[indices[i]].partial_decryption, lagrange, elgamal_p);
1786
1787       // product of all exponentiated partiel decryptions ...
1788       gcry_mpi_mulm(prod, prod, tmp, elgamal_p);
1789     }
1790
1791   GNUNET_CRYPTO_mpi_scan_unsigned(&c_2, ds->ciphertext.c2_bits, GNUNET_SECRETSHARING_ELGAMAL_BITS / 8);
1792
1793   GNUNET_assert(0 != gcry_mpi_invm(prod, prod, elgamal_p));
1794   gcry_mpi_mulm(m, c_2, prod, elgamal_p);
1795   ev = GNUNET_MQ_msg(msg, GNUNET_MESSAGE_TYPE_SECRETSHARING_CLIENT_DECRYPT_DONE);
1796   GNUNET_CRYPTO_mpi_print_unsigned(&msg->plaintext, GNUNET_SECRETSHARING_ELGAMAL_BITS / 8, m);
1797   msg->success = htonl(1);
1798   GNUNET_MQ_send(ds->cs->mq,
1799                  ev);
1800
1801   GNUNET_log(GNUNET_ERROR_TYPE_INFO, "sent decrypt done to client\n");
1802
1803   GNUNET_free(indices);
1804
1805   gcry_mpi_release(lagrange);
1806   gcry_mpi_release(m);
1807   gcry_mpi_release(tmp);
1808   gcry_mpi_release(prod);
1809   gcry_mpi_release(c_2);
1810
1811   // FIXME: what if not enough peers participated?
1812 }
1813
1814
1815 /**
1816  * Get a string representation of an MPI.
1817  * The caller must free the returned string.
1818  *
1819  * @param mpi mpi to convert to a string
1820  * @return string representation of @a mpi, must be free'd by the caller
1821  */
1822 static char *
1823 mpi_to_str(gcry_mpi_t mpi)
1824 {
1825   unsigned char *buf;
1826
1827   GNUNET_assert(0 == gcry_mpi_aprint(GCRYMPI_FMT_HEX, &buf, NULL, mpi));
1828   return (char *)buf;
1829 }
1830
1831
1832 /**
1833  * Called when a new partial decryption arrives.
1834  */
1835 static void
1836 decrypt_new_element(void *cls,
1837                     const struct GNUNET_SET_Element *element)
1838 {
1839   struct DecryptSession *session = cls;
1840   const struct GNUNET_SECRETSHARING_DecryptData *d;
1841   struct DecryptPeerInfo *info;
1842   struct GNUNET_HashCode challenge_hash;
1843
1844   /* nizk response */
1845   gcry_mpi_t r;
1846   /* nizk challenge */
1847   gcry_mpi_t challenge;
1848   /* nizk commit1, g^\beta */
1849   gcry_mpi_t commit1;
1850   /* nizk commit2, c_1^\beta */
1851   gcry_mpi_t commit2;
1852   /* homomorphic commitment to the peer's share,
1853    * public key share */
1854   gcry_mpi_t sigma;
1855   /* partial decryption we received */
1856   gcry_mpi_t w;
1857   /* ciphertext component #1 */
1858   gcry_mpi_t c1;
1859   /* temporary variable (for comparision) #1 */
1860   gcry_mpi_t tmp1;
1861   /* temporary variable (for comparision) #2 */
1862   gcry_mpi_t tmp2;
1863
1864   if (NULL == element)
1865     {
1866       GNUNET_log(GNUNET_ERROR_TYPE_ERROR, "decryption failed\n");
1867       /* FIXME: destroy */
1868       return;
1869     }
1870
1871   if (element->size != sizeof *d)
1872     {
1873       GNUNET_log(GNUNET_ERROR_TYPE_ERROR, "element of wrong size in decrypt consensus\n");
1874       return;
1875     }
1876
1877   d = element->data;
1878
1879   info = get_decrypt_peer_info(session, &d->peer);
1880
1881   if (NULL == info)
1882     {
1883       GNUNET_log(GNUNET_ERROR_TYPE_ERROR, "decrypt element from invalid peer (%s)\n",
1884                  GNUNET_i2s(&d->peer));
1885       return;
1886     }
1887
1888   if (NULL != info->partial_decryption)
1889     {
1890       GNUNET_log(GNUNET_ERROR_TYPE_ERROR, "decrypt element duplicate\n");
1891       return;
1892     }
1893
1894   if (0 != GNUNET_memcmp(&d->ciphertext, &session->ciphertext))
1895     {
1896       GNUNET_log(GNUNET_ERROR_TYPE_WARNING, "P%u: got decrypt element with non-matching ciphertext from P%u\n",
1897                  (unsigned int)session->share->my_peer, (unsigned int)(info - session->info));
1898
1899       return;
1900     }
1901
1902
1903   GNUNET_CRYPTO_hash(offsetof(struct GNUNET_SECRETSHARING_DecryptData, ciphertext) + (char *)d,
1904                      offsetof(struct GNUNET_SECRETSHARING_DecryptData, nizk_response) -
1905                      offsetof(struct GNUNET_SECRETSHARING_DecryptData, ciphertext),
1906                      &challenge_hash);
1907
1908   GNUNET_CRYPTO_mpi_scan_unsigned(&challenge, &challenge_hash,
1909                                   sizeof(struct GNUNET_HashCode));
1910
1911   GNUNET_CRYPTO_mpi_scan_unsigned(&sigma, &session->share->sigmas[info - session->info],
1912                                   sizeof(struct GNUNET_SECRETSHARING_FieldElement));
1913
1914   GNUNET_CRYPTO_mpi_scan_unsigned(&c1, session->ciphertext.c1_bits,
1915                                   sizeof(struct GNUNET_SECRETSHARING_FieldElement));
1916
1917   GNUNET_CRYPTO_mpi_scan_unsigned(&commit1, &d->nizk_commit1,
1918                                   sizeof(struct GNUNET_SECRETSHARING_FieldElement));
1919
1920   GNUNET_CRYPTO_mpi_scan_unsigned(&commit2, &d->nizk_commit2,
1921                                   sizeof(struct GNUNET_SECRETSHARING_FieldElement));
1922
1923   GNUNET_CRYPTO_mpi_scan_unsigned(&r, &d->nizk_response,
1924                                   sizeof(struct GNUNET_SECRETSHARING_FieldElement));
1925
1926   GNUNET_CRYPTO_mpi_scan_unsigned(&w, &d->partial_decryption,
1927                                   sizeof(struct GNUNET_SECRETSHARING_FieldElement));
1928
1929   GNUNET_assert(NULL != (tmp1 = gcry_mpi_new(0)));
1930   GNUNET_assert(NULL != (tmp2 = gcry_mpi_new(0)));
1931
1932   // tmp1 = g^r
1933   gcry_mpi_powm(tmp1, elgamal_g, r, elgamal_p);
1934
1935   // tmp2 = g^\beta * \sigma^challenge
1936   gcry_mpi_powm(tmp2, sigma, challenge, elgamal_p);
1937   gcry_mpi_mulm(tmp2, tmp2, commit1, elgamal_p);
1938
1939   if (0 != gcry_mpi_cmp(tmp1, tmp2))
1940     {
1941       char *tmp1_str;
1942       char *tmp2_str;
1943
1944       tmp1_str = mpi_to_str(tmp1);
1945       tmp2_str = mpi_to_str(tmp2);
1946       GNUNET_log(GNUNET_ERROR_TYPE_WARNING,
1947                  "P%u: Received invalid partial decryption from P%u (eqn 1), expected %s got %s\n",
1948                  session->share->my_peer,
1949                  (unsigned int)(info - session->info),
1950                  tmp1_str,
1951                  tmp2_str);
1952       GNUNET_free(tmp1_str);
1953       GNUNET_free(tmp2_str);
1954       goto cleanup;
1955     }
1956
1957
1958   gcry_mpi_powm(tmp1, c1, r, elgamal_p);
1959
1960   gcry_mpi_powm(tmp2, w, challenge, elgamal_p);
1961   gcry_mpi_mulm(tmp2, tmp2, commit2, elgamal_p);
1962
1963
1964   if (0 != gcry_mpi_cmp(tmp1, tmp2))
1965     {
1966       GNUNET_log(GNUNET_ERROR_TYPE_WARNING,
1967                  "P%u: Received invalid partial decryption from P%u (eqn 2)\n",
1968                  session->share->my_peer,
1969                  (unsigned int)(info - session->info));
1970       goto cleanup;
1971     }
1972
1973
1974   GNUNET_CRYPTO_mpi_scan_unsigned(&info->partial_decryption, &d->partial_decryption,
1975                                   GNUNET_SECRETSHARING_ELGAMAL_BITS / 8);
1976 cleanup:
1977   gcry_mpi_release(tmp1);
1978   gcry_mpi_release(tmp2);
1979   gcry_mpi_release(sigma);
1980   gcry_mpi_release(commit1);
1981   gcry_mpi_release(commit2);
1982   gcry_mpi_release(r);
1983   gcry_mpi_release(w);
1984   gcry_mpi_release(challenge);
1985   gcry_mpi_release(c1);
1986 }
1987
1988
1989 static void
1990 insert_decrypt_element(struct DecryptSession *ds)
1991 {
1992   struct GNUNET_SECRETSHARING_DecryptData d;
1993   struct GNUNET_SET_Element element;
1994   /* our share */
1995   gcry_mpi_t s;
1996   /* partial decryption with our share */
1997   gcry_mpi_t w;
1998   /* first component of the elgamal ciphertext */
1999   gcry_mpi_t c1;
2000   /* nonce for dlog zkp */
2001   gcry_mpi_t beta;
2002   gcry_mpi_t tmp;
2003   gcry_mpi_t challenge;
2004   gcry_mpi_t sigma;
2005   struct GNUNET_HashCode challenge_hash;
2006
2007   /* make vagrind happy until we implement the real deal ... */
2008   memset(&d, 0, sizeof d);
2009
2010   GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "P%u: Inserting decrypt element\n",
2011              ds->share->my_peer);
2012
2013   GNUNET_assert(ds->share->my_peer < ds->share->num_peers);
2014
2015   GNUNET_CRYPTO_mpi_scan_unsigned(&c1, &ds->ciphertext.c1_bits,
2016                                   GNUNET_SECRETSHARING_ELGAMAL_BITS / 8);
2017   GNUNET_CRYPTO_mpi_scan_unsigned(&s, &ds->share->my_share,
2018                                   GNUNET_SECRETSHARING_ELGAMAL_BITS / 8);
2019   GNUNET_CRYPTO_mpi_scan_unsigned(&sigma, &ds->share->sigmas[ds->share->my_peer],
2020                                   GNUNET_SECRETSHARING_ELGAMAL_BITS / 8);
2021
2022   GNUNET_assert(NULL != (w = gcry_mpi_new(0)));
2023   GNUNET_assert(NULL != (beta = gcry_mpi_new(0)));
2024   GNUNET_assert(NULL != (tmp = gcry_mpi_new(0)));
2025
2026   // FIXME: unnecessary, remove once crypto works
2027   gcry_mpi_powm(tmp, elgamal_g, s, elgamal_p);
2028   if (0 != gcry_mpi_cmp(tmp, sigma))
2029     {
2030       char *sigma_str = mpi_to_str(sigma);
2031       char *tmp_str = mpi_to_str(tmp);
2032       char *s_str = mpi_to_str(s);
2033       GNUNET_log(GNUNET_ERROR_TYPE_ERROR, "Share of P%u is invalid, ref sigma %s, "
2034                  "computed sigma %s, s %s\n",
2035                  ds->share->my_peer,
2036                  sigma_str, tmp_str, s_str);
2037       GNUNET_free(sigma_str);
2038       GNUNET_free(tmp_str);
2039       GNUNET_free(s_str);
2040     }
2041
2042   gcry_mpi_powm(w, c1, s, elgamal_p);
2043
2044   element.data = (void *)&d;
2045   element.size = sizeof(struct GNUNET_SECRETSHARING_DecryptData);
2046   element.element_type = 0;
2047
2048   d.ciphertext = ds->ciphertext;
2049   d.peer = my_peer;
2050   GNUNET_CRYPTO_mpi_print_unsigned(&d.partial_decryption, GNUNET_SECRETSHARING_ELGAMAL_BITS / 8, w);
2051
2052   // create the zero knowledge proof
2053   // randomly choose beta such that 0 < beta < q
2054   do
2055     {
2056       gcry_mpi_randomize(beta, GNUNET_SECRETSHARING_ELGAMAL_BITS - 1, GCRY_WEAK_RANDOM);
2057     }
2058   while ((gcry_mpi_cmp_ui(beta, 0) == 0) || (gcry_mpi_cmp(beta, elgamal_q) >= 0));
2059   // tmp = g^beta
2060   gcry_mpi_powm(tmp, elgamal_g, beta, elgamal_p);
2061   GNUNET_CRYPTO_mpi_print_unsigned(&d.nizk_commit1, GNUNET_SECRETSHARING_ELGAMAL_BITS / 8, tmp);
2062   // tmp = (c_1)^beta
2063   gcry_mpi_powm(tmp, c1, beta, elgamal_p);
2064   GNUNET_CRYPTO_mpi_print_unsigned(&d.nizk_commit2, GNUNET_SECRETSHARING_ELGAMAL_BITS / 8, tmp);
2065
2066   // the challenge is the hash of everything up to the response
2067   GNUNET_CRYPTO_hash(offsetof(struct GNUNET_SECRETSHARING_DecryptData, ciphertext) + (char *)&d,
2068                      offsetof(struct GNUNET_SECRETSHARING_DecryptData, nizk_response) -
2069                      offsetof(struct GNUNET_SECRETSHARING_DecryptData, ciphertext),
2070                      &challenge_hash);
2071
2072   GNUNET_CRYPTO_mpi_scan_unsigned(&challenge, &challenge_hash,
2073                                   sizeof(struct GNUNET_HashCode));
2074
2075   // compute the response in tmp,
2076   // tmp = (c * s + beta) mod q
2077   gcry_mpi_mulm(tmp, challenge, s, elgamal_q);
2078   gcry_mpi_addm(tmp, tmp, beta, elgamal_q);
2079
2080   GNUNET_CRYPTO_mpi_print_unsigned(&d.nizk_response, GNUNET_SECRETSHARING_ELGAMAL_BITS / 8, tmp);
2081
2082   d.purpose.size = htonl(element.size - offsetof(struct GNUNET_SECRETSHARING_DecryptData, purpose));
2083   d.purpose.purpose = htonl(GNUNET_SIGNATURE_PURPOSE_SECRETSHARING_DECRYPTION);
2084
2085   GNUNET_assert(GNUNET_OK ==
2086                 GNUNET_CRYPTO_eddsa_sign(my_peer_private_key,
2087                                          &d.purpose,
2088                                          &d.signature));
2089
2090   GNUNET_CONSENSUS_insert(ds->consensus, &element, NULL, NULL);
2091   GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
2092              "P%u: Inserting decrypt element done!\n",
2093              ds->share->my_peer);
2094
2095   gcry_mpi_release(s);
2096   gcry_mpi_release(w);
2097   gcry_mpi_release(c1);
2098   gcry_mpi_release(beta);
2099   gcry_mpi_release(tmp);
2100   gcry_mpi_release(challenge);
2101   gcry_mpi_release(sigma);
2102 }
2103
2104
2105 /**
2106  * Check that @a msg is well-formed.
2107  *
2108  * @param cls identification of the client
2109  * @param msg the actual message
2110  * @return #GNUNET_OK (check deferred a bit)
2111  */
2112 static int
2113 check_client_decrypt(void *cls,
2114                      const struct GNUNET_SECRETSHARING_DecryptRequestMessage *msg)
2115 {
2116   /* we check later, it's complicated */
2117   return GNUNET_OK;
2118 }
2119
2120
2121 /**
2122  * Functions with this signature are called whenever a message is
2123  * received.
2124  *
2125  * @param cls identification of the client
2126  * @param msg the actual message
2127  */
2128 static void
2129 handle_client_decrypt(void *cls,
2130                       const struct GNUNET_SECRETSHARING_DecryptRequestMessage *msg)
2131 {
2132   struct ClientState *cs = cls;
2133   struct DecryptSession *ds;
2134   struct GNUNET_HashCode session_id;
2135
2136   if (NULL != cs->decrypt_session)
2137     {
2138       GNUNET_break(0);
2139       GNUNET_SERVICE_client_drop(cs->client);
2140       return;
2141     }
2142   ds = GNUNET_new(struct DecryptSession);
2143   cs->decrypt_session = ds;
2144   ds->cs = cs;
2145   ds->start = GNUNET_TIME_absolute_ntoh(msg->start);
2146   ds->deadline = GNUNET_TIME_absolute_ntoh(msg->deadline);
2147   ds->ciphertext = msg->ciphertext;
2148
2149   ds->share = GNUNET_SECRETSHARING_share_read(&msg[1],
2150                                               ntohs(msg->header.size) - sizeof(*msg),
2151                                               NULL);
2152   if (NULL == ds->share)
2153     {
2154       GNUNET_break(0);
2155       GNUNET_SERVICE_client_drop(cs->client);
2156       return;
2157     }
2158
2159   /* FIXME: this is probably sufficient, but kdf/hash with all values would be nicer ... */
2160   GNUNET_CRYPTO_hash(&msg->ciphertext,
2161                      sizeof(struct GNUNET_SECRETSHARING_Ciphertext),
2162                      &session_id);
2163   ds->consensus = GNUNET_CONSENSUS_create(cfg,
2164                                           ds->share->num_peers,
2165                                           ds->share->peers,
2166                                           &session_id,
2167                                           ds->start,
2168                                           ds->deadline,
2169                                           &decrypt_new_element,
2170                                           ds);
2171
2172
2173   ds->info = GNUNET_new_array(ds->share->num_peers,
2174                               struct DecryptPeerInfo);
2175   for (unsigned int i = 0; i < ds->share->num_peers; i++)
2176     {
2177       ds->info[i].peer = ds->share->peers[i];
2178       ds->info[i].original_index = ds->share->original_indices[i];
2179     }
2180   insert_decrypt_element(ds);
2181   GNUNET_CONSENSUS_conclude(ds->consensus,
2182                             decrypt_conclude,
2183                             ds);
2184   GNUNET_SERVICE_client_continue(cs->client);
2185   GNUNET_log(GNUNET_ERROR_TYPE_INFO,
2186              "decrypting with %u peers\n",
2187              ds->share->num_peers);
2188 }
2189
2190
2191 static void
2192 init_crypto_constants(void)
2193 {
2194   GNUNET_assert(0 == gcry_mpi_scan(&elgamal_q, GCRYMPI_FMT_HEX,
2195                                    GNUNET_SECRETSHARING_ELGAMAL_Q_HEX, 0, NULL));
2196   GNUNET_assert(0 == gcry_mpi_scan(&elgamal_p, GCRYMPI_FMT_HEX,
2197                                    GNUNET_SECRETSHARING_ELGAMAL_P_HEX, 0, NULL));
2198   GNUNET_assert(0 == gcry_mpi_scan(&elgamal_g, GCRYMPI_FMT_HEX,
2199                                    GNUNET_SECRETSHARING_ELGAMAL_G_HEX, 0, NULL));
2200 }
2201
2202
2203 /**
2204  * Initialize secretsharing service.
2205  *
2206  * @param cls closure
2207  * @param c configuration to use
2208  * @param service the initialized service
2209  */
2210 static void
2211 run(void *cls,
2212     const struct GNUNET_CONFIGURATION_Handle *c,
2213     struct GNUNET_SERVICE_Handle *service)
2214 {
2215   cfg = c;
2216   my_peer_private_key = GNUNET_CRYPTO_eddsa_key_create_from_configuration(c);
2217   if (NULL == my_peer_private_key)
2218     {
2219       GNUNET_log(GNUNET_ERROR_TYPE_ERROR,
2220                  "could not access host private key\n");
2221       GNUNET_break(0);
2222       GNUNET_SCHEDULER_shutdown();
2223       return;
2224     }
2225   init_crypto_constants();
2226   if (GNUNET_OK !=
2227       GNUNET_CRYPTO_get_peer_identity(cfg,
2228                                       &my_peer))
2229     {
2230       GNUNET_log(GNUNET_ERROR_TYPE_ERROR,
2231                  "could not retrieve host identity\n");
2232       GNUNET_break(0);
2233       GNUNET_SCHEDULER_shutdown();
2234       return;
2235     }
2236   GNUNET_SCHEDULER_add_shutdown(&cleanup_task,
2237                                 NULL);
2238 }
2239
2240
2241 /**
2242  * Callback called when a client connects to the service.
2243  *
2244  * @param cls closure for the service
2245  * @param c the new client that connected to the service
2246  * @param mq the message queue used to send messages to the client
2247  * @return @a c
2248  */
2249 static void *
2250 client_connect_cb(void *cls,
2251                   struct GNUNET_SERVICE_Client *c,
2252                   struct GNUNET_MQ_Handle *mq)
2253 {
2254   struct ClientState *cs = GNUNET_new(struct ClientState);;
2255
2256   cs->client = c;
2257   cs->mq = mq;
2258   return cs;
2259 }
2260
2261
2262 /**
2263  * Callback called when a client disconnected from the service
2264  *
2265  * @param cls closure for the service
2266  * @param c the client that disconnected
2267  * @param internal_cls should be equal to @a c
2268  */
2269 static void
2270 client_disconnect_cb(void *cls,
2271                      struct GNUNET_SERVICE_Client *c,
2272                      void *internal_cls)
2273 {
2274   struct ClientState *cs = internal_cls;
2275
2276   if (NULL != cs->keygen_session)
2277     keygen_session_destroy(cs->keygen_session);
2278
2279   if (NULL != cs->decrypt_session)
2280     decrypt_session_destroy(cs->decrypt_session);
2281   GNUNET_free(cs);
2282 }
2283
2284
2285 /**
2286  * Define "main" method using service macro.
2287  */
2288 GNUNET_SERVICE_MAIN
2289   ("secretsharing",
2290   GNUNET_SERVICE_OPTION_NONE,
2291   &run,
2292   &client_connect_cb,
2293   &client_disconnect_cb,
2294   NULL,
2295   GNUNET_MQ_hd_var_size(client_keygen,
2296                         GNUNET_MESSAGE_TYPE_SECRETSHARING_CLIENT_GENERATE,
2297                         struct GNUNET_SECRETSHARING_CreateMessage,
2298                         NULL),
2299   GNUNET_MQ_hd_var_size(client_decrypt,
2300                         GNUNET_MESSAGE_TYPE_SECRETSHARING_CLIENT_DECRYPT,
2301                         struct GNUNET_SECRETSHARING_DecryptRequestMessage,
2302                         NULL),
2303   GNUNET_MQ_handler_end());