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