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