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