2 This file is part of GNUnet.
3 Copyright (C) 2013 GNUnet e.V.
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.
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.
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/>.
18 SPDX-License-Identifier: AGPL3.0-or-later
22 * @file secretsharing/gnunet-service-secretsharing.c
23 * @brief secret sharing service
24 * @author Florian Dold
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"
36 #define EXTRA_CHECKS 1
40 * Info about a peer in a key generation session.
45 * Peer identity of the peer.
47 struct GNUNET_PeerIdentity peer;
50 * The peer's paillier public key.
51 * Freshly generated for each keygen session.
53 struct GNUNET_CRYPTO_PaillierPublicKey paillier_public_key;
56 * The peer's commitment to its presecret.
58 gcry_mpi_t presecret_commitment;
61 * Commitment to the preshare that is
62 * intended for our peer.
64 gcry_mpi_t preshare_commitment;
67 * Sigma (exponentiated share) for this peer.
72 * Did we successfully receive the round1 element
78 * Did we successfully receive the round2 element
86 * Information about a peer in a decrypt session.
88 struct DecryptPeerInfo
91 * Identity of the peer.
93 struct GNUNET_PeerIdentity peer;
96 * Original index in the key generation round.
97 * Necessary for computing the lagrange coefficients.
99 unsigned int original_index;
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.
107 gcry_mpi_t partial_decryption;
112 * State we keep per client.
118 * Session to establish a threshold-shared secret.
124 * Current consensus, used for both DKG rounds.
126 struct GNUNET_CONSENSUS_Handle *consensus;
129 * Which client is this for?
131 struct ClientState *cs;
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.
139 * The pre-secret-shares 'i=1,...,num_peers' are given by evaluating this
140 * polyomial at 'i' for share i.
142 gcry_mpi_t *presecret_polynomial;
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.
149 unsigned int threshold;
152 * Total number of peers.
154 unsigned int num_peers;
157 * Index of the local peer.
159 unsigned int local_peer;
162 * Information about all participating peers.
163 * Array of size 'num_peers'.
165 struct KeygenPeerInfo *info;
168 * List of all peers involved in the secret sharing session.
170 struct GNUNET_PeerIdentity *peers;
173 * Identifier for this session.
175 struct GNUNET_HashCode session_id;
178 * Paillier private key of our peer.
180 struct GNUNET_CRYPTO_PaillierPrivateKey paillier_private_key;
183 * When would we like the key to be established?
185 struct GNUNET_TIME_Absolute deadline;
188 * When does the DKG start? Necessary to compute fractions of the
189 * operation's desired time interval.
191 struct GNUNET_TIME_Absolute start_time;
194 * Index of the local peer in the ordered list
195 * of peers in the session.
197 unsigned int local_peer_idx;
200 * Share of our peer. Once preshares from other peers are received, they
201 * will be added to 'my'share.
206 * Public key, will be updated when a round2 element arrives.
208 gcry_mpi_t public_key;
213 * Session to cooperatively decrypt a value.
215 struct DecryptSession
219 * Handle to the consensus over partial decryptions.
221 struct GNUNET_CONSENSUS_Handle *consensus;
224 * Which client is this for?
226 struct ClientState *cs;
229 * When should we start communicating for decryption?
231 struct GNUNET_TIME_Absolute start;
234 * When would we like the ciphertext to be
237 struct GNUNET_TIME_Absolute deadline;
240 * Ciphertext we want to decrypt.
242 struct GNUNET_SECRETSHARING_Ciphertext ciphertext;
245 * Share of the local peer.
246 * Containts other important information, such as
247 * the list of other peers.
249 struct GNUNET_SECRETSHARING_Share *share;
252 * State information about other peers.
254 struct DecryptPeerInfo *info;
259 * State we keep per client.
264 * Decrypt session of the client, if any.
266 struct DecryptSession *decrypt_session;
269 * Keygen session of the client, if any.
271 struct KeygenSession *keygen_session;
274 * Client this is about.
276 struct GNUNET_SERVICE_Client *client;
279 * MQ to talk to @a client.
281 struct GNUNET_MQ_Handle *mq;
287 * The ElGamal prime field order as libgcrypt mpi.
288 * Initialized in #init_crypto_constants.
290 static gcry_mpi_t elgamal_q;
293 * Modulus of the prime field used for ElGamal.
294 * Initialized in #init_crypto_constants.
296 static gcry_mpi_t elgamal_p;
299 * Generator for prime field of order 'elgamal_q'.
300 * Initialized in #init_crypto_constants.
302 static gcry_mpi_t elgamal_g;
305 * Peer that runs this service.
307 static struct GNUNET_PeerIdentity my_peer;
310 * Peer that runs this service.
312 static struct GNUNET_CRYPTO_EddsaPrivateKey *my_peer_private_key;
315 * Configuration of this service.
317 static const struct GNUNET_CONFIGURATION_Handle *cfg;
321 * Get the peer info belonging to a peer identity in a keygen session.
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.
327 static struct KeygenPeerInfo *
328 get_keygen_peer_info (const struct KeygenSession *ks,
329 const struct GNUNET_PeerIdentity *peer)
332 for (i = 0; i < ks->num_peers; i++)
333 if (0 == memcmp (peer, &ks->info[i].peer, sizeof (struct GNUNET_PeerIdentity)))
340 * Get the peer info belonging to a peer identity in a decrypt session.
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.
346 static struct DecryptPeerInfo *
347 get_decrypt_peer_info (const struct DecryptSession *ds,
348 const struct GNUNET_PeerIdentity *peer)
351 for (i = 0; i < ds->share->num_peers; i++)
352 if (0 == memcmp (peer, &ds->info[i].peer, sizeof (struct GNUNET_PeerIdentity)))
359 * Interpolate between two points in time.
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
366 static struct GNUNET_TIME_Absolute
367 time_between (struct GNUNET_TIME_Absolute start,
368 struct GNUNET_TIME_Absolute end,
371 struct GNUNET_TIME_Absolute result;
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);
383 * Compare two peer identities. Indended to be used with qsort or bsearch.
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.
390 peer_id_cmp (const void *p1, const void *p2)
394 sizeof (struct GNUNET_PeerIdentity));
399 * Get the index of a peer in an array of peers
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.
408 peer_find (const struct GNUNET_PeerIdentity *haystack, unsigned int n,
409 const struct GNUNET_PeerIdentity *needle)
413 for (i = 0; i < n; i++)
414 if (0 == memcmp (&haystack[i],
416 sizeof (struct GNUNET_PeerIdentity)))
423 * Normalize the given list of peers, by including the local peer
424 * (if it is missing) and sorting the peers by their identity.
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.
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)
438 unsigned int local_peer_in_list;
439 /* number of peers in the normalized list */
441 struct GNUNET_PeerIdentity *normalized;
443 local_peer_in_list = GNUNET_YES;
445 if (peer_find (listed, num_listed, &my_peer) < 0)
447 local_peer_in_list = GNUNET_NO;
451 normalized = GNUNET_new_array (n,
452 struct GNUNET_PeerIdentity);
454 if (GNUNET_NO == local_peer_in_list)
455 normalized[n - 1] = my_peer;
457 GNUNET_memcpy (normalized,
459 num_listed * sizeof (struct GNUNET_PeerIdentity));
462 sizeof (struct GNUNET_PeerIdentity),
465 if (NULL != my_peer_idx)
466 *my_peer_idx = peer_find (normalized, n, &my_peer);
467 if (NULL != num_normalized)
475 * Get a the j-th lagrange coefficient for a set of indices.
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
483 compute_lagrange_coefficient (gcry_mpi_t coeff, unsigned int j,
484 unsigned int *indices,
492 /* temp value for l-j */
495 GNUNET_assert (0 != coeff);
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)));
501 gcry_mpi_set_ui (n, 1);
502 gcry_mpi_set_ui (d, 1);
504 for (i = 0; i < num; i++)
506 unsigned int l = indices[i];
509 gcry_mpi_mul_ui (n, n, l + 1);
511 gcry_mpi_set_ui (tmp, l + 1);
512 gcry_mpi_sub_ui (tmp, tmp, j + 1);
513 gcry_mpi_mul (d, d, tmp);
516 // gcry_mpi_invm does not like negative numbers ...
517 gcry_mpi_mod (d, d, elgamal_q);
519 GNUNET_assert (gcry_mpi_cmp_ui (d, 0) > 0);
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));
525 gcry_mpi_mulm (coeff, n, d, elgamal_q);
527 gcry_mpi_release (n);
528 gcry_mpi_release (d);
529 gcry_mpi_release (tmp);
534 * Destroy a decrypt session, removing it from
535 * the linked list of decrypt sessions.
537 * @param ds decrypt session to destroy
540 decrypt_session_destroy (struct DecryptSession *ds)
542 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
543 "destroying decrypt session\n");
546 ds->cs->decrypt_session = NULL;
549 if (NULL != ds->consensus)
551 GNUNET_CONSENSUS_destroy (ds->consensus);
552 ds->consensus = NULL;
555 if (NULL != ds->info)
557 for (unsigned int i = 0; i < ds->share->num_peers; i++)
559 if (NULL != ds->info[i].partial_decryption)
561 gcry_mpi_release (ds->info[i].partial_decryption);
562 ds->info[i].partial_decryption = NULL;
565 GNUNET_free (ds->info);
568 if (NULL != ds->share)
570 GNUNET_SECRETSHARING_share_destroy (ds->share);
579 keygen_info_destroy (struct KeygenPeerInfo *info)
581 if (NULL != info->sigma)
583 gcry_mpi_release (info->sigma);
586 if (NULL != info->presecret_commitment)
588 gcry_mpi_release (info->presecret_commitment);
589 info->presecret_commitment = NULL;
591 if (NULL != info->preshare_commitment)
593 gcry_mpi_release (info->preshare_commitment);
594 info->preshare_commitment = NULL;
600 keygen_session_destroy (struct KeygenSession *ks)
602 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
603 "destroying keygen session\n");
607 ks->cs->keygen_session = NULL;
610 if (NULL != ks->info)
612 for (unsigned int i = 0; i < ks->num_peers; i++)
613 keygen_info_destroy (&ks->info[i]);
614 GNUNET_free (ks->info);
618 if (NULL != ks->consensus)
620 GNUNET_CONSENSUS_destroy (ks->consensus);
621 ks->consensus = NULL;
624 if (NULL != ks->presecret_polynomial)
626 for (unsigned int i = 0; i < ks->threshold; i++)
628 GNUNET_assert (NULL != ks->presecret_polynomial[i]);
629 gcry_mpi_release (ks->presecret_polynomial[i]);
630 ks->presecret_polynomial[i] = NULL;
632 GNUNET_free (ks->presecret_polynomial);
633 ks->presecret_polynomial = NULL;
635 if (NULL != ks->my_share)
637 gcry_mpi_release (ks->my_share);
640 if (NULL != ks->public_key)
642 gcry_mpi_release (ks->public_key);
643 ks->public_key = NULL;
645 if (NULL != ks->peers)
647 GNUNET_free (ks->peers);
655 * Task run during shutdown.
661 cleanup_task (void *cls)
669 * Generate the random coefficients of our pre-secret polynomial
671 * @param ks the session
674 generate_presecret_polynomial (struct KeygenSession *ks)
679 GNUNET_assert (NULL == ks->presecret_polynomial);
680 ks->presecret_polynomial = GNUNET_new_array (ks->threshold,
682 for (i = 0; i < ks->threshold; i++)
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.
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));
697 * Consensus element handler for round one.
698 * We should get one ephemeral key for each peer.
700 * @param cls Closure (keygen session).
701 * @param element The element from consensus, or
702 * NULL if consensus failed.
705 keygen_round1_new_element (void *cls,
706 const struct GNUNET_SET_Element *element)
708 const struct GNUNET_SECRETSHARING_KeygenCommitData *d;
709 struct KeygenSession *ks = cls;
710 struct KeygenPeerInfo *info;
714 GNUNET_log (GNUNET_ERROR_TYPE_WARNING, "round1 consensus failed\n");
718 /* elements have fixed size */
719 if (element->size != sizeof (struct GNUNET_SECRETSHARING_KeygenCommitData))
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));
728 GNUNET_log (GNUNET_ERROR_TYPE_INFO, "got round1 element\n");
731 info = get_keygen_peer_info (ks, &d->peer);
735 GNUNET_log (GNUNET_ERROR_TYPE_WARNING, "keygen commit data with wrong peer identity (%s) in consensus\n",
736 GNUNET_i2s (&d->peer));
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)))
744 GNUNET_log (GNUNET_ERROR_TYPE_WARNING, "keygen commit data with wrong signature purpose size in consensus\n");
748 if (GNUNET_OK != GNUNET_CRYPTO_eddsa_verify (GNUNET_SIGNATURE_PURPOSE_SECRETSHARING_DKG1,
749 &d->purpose, &d->signature, &d->peer.public_key))
751 GNUNET_log (GNUNET_ERROR_TYPE_WARNING, "keygen commit data with invalid signature in consensus\n");
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;
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.
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?
771 horner_eval (gcry_mpi_t z, gcry_mpi_t *coeff, unsigned int num_coeff, gcry_mpi_t x, gcry_mpi_t m)
775 gcry_mpi_set_ui (z, 0);
776 for (i = 0; i < num_coeff; i++)
779 gcry_mpi_mul (z, z, x);
780 gcry_mpi_addm (z, z, coeff[num_coeff - i - 1], m);
786 keygen_round2_conclude (void *cls)
788 struct KeygenSession *ks = cls;
789 struct GNUNET_SECRETSHARING_SecretReadyMessage *m;
790 struct GNUNET_MQ_Envelope *ev;
794 struct GNUNET_SECRETSHARING_Share *share;
796 GNUNET_log (GNUNET_ERROR_TYPE_INFO, "round2 conclude\n");
798 GNUNET_CONSENSUS_destroy (ks->consensus);
799 ks->consensus = NULL;
801 share = GNUNET_new (struct GNUNET_SECRETSHARING_Share);
803 share->num_peers = 0;
805 for (i = 0; i < ks->num_peers; i++)
806 if (GNUNET_YES == ks->info[i].round2_valid)
809 share->peers = GNUNET_new_array (share->num_peers,
810 struct GNUNET_PeerIdentity);
812 GNUNET_new_array (share->num_peers,
813 struct GNUNET_SECRETSHARING_FieldElement);
814 share->original_indices = GNUNET_new_array (share->num_peers,
817 /* maybe we're not even in the list of peers? */
818 share->my_peer = share->num_peers;
820 j = 0; /* running index of valid peers */
821 for (i = 0; i < ks->num_peers; i++)
823 if (GNUNET_YES == ks->info[i].round2_valid)
825 share->peers[j] = ks->info[i].peer;
826 GNUNET_CRYPTO_mpi_print_unsigned (&share->sigmas[j],
827 GNUNET_SECRETSHARING_ELGAMAL_BITS / 8,
829 share->original_indices[i] = j;
830 if (0 == memcmp (&share->peers[i], &my_peer, sizeof (struct GNUNET_PeerIdentity)))
836 if (share->my_peer == share->num_peers)
838 GNUNET_log (GNUNET_ERROR_TYPE_INFO, "P%u: peer identity not in share\n", ks->local_peer_idx);
841 GNUNET_CRYPTO_mpi_print_unsigned (&share->my_share, GNUNET_SECRETSHARING_ELGAMAL_BITS / 8,
843 GNUNET_CRYPTO_mpi_print_unsigned (&share->public_key, GNUNET_SECRETSHARING_ELGAMAL_BITS / 8,
846 GNUNET_log (GNUNET_ERROR_TYPE_INFO, "keygen completed with %u peers\n", share->num_peers);
848 /* Write the share. If 0 peers completed the dkg, an empty
849 * share will be sent. */
851 GNUNET_assert (GNUNET_OK == GNUNET_SECRETSHARING_share_write (share, NULL, 0, &share_size));
853 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "writing share of size %u\n",
854 (unsigned int) share_size);
856 ev = GNUNET_MQ_msg_extra (m, share_size,
857 GNUNET_MESSAGE_TYPE_SECRETSHARING_CLIENT_SECRET_READY);
859 GNUNET_assert (GNUNET_OK == GNUNET_SECRETSHARING_share_write (share, &m[1], share_size, NULL));
861 GNUNET_SECRETSHARING_share_destroy (share);
864 GNUNET_MQ_send (ks->cs->mq,
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)
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)));
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);
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);
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);
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);
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);
928 gcry_mpi_div (r, NULL, n, big_b, 0);
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);
938 if (gcry_mpi_cmp (big_t, big_b) >= 0)
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);
950 gcry_mpi_set (a_1, b_1);
951 gcry_mpi_set (a_2, b_2);
953 gcry_mpi_set (b_1, t_1);
954 gcry_mpi_set (b_2, t_2);
956 gcry_mpi_set (big_a, big_b);
957 gcry_mpi_set (big_b, big_t);
961 gcry_mpi_t paillier_n;
963 GNUNET_CRYPTO_mpi_scan_unsigned (&paillier_n, ppub, sizeof (struct GNUNET_CRYPTO_PaillierPublicKey));
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);
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);
987 get_fair_encryption_challenge (const struct GNUNET_SECRETSHARING_FairEncryption *fe, gcry_mpi_t e)
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];
995 struct GNUNET_HashCode e_hash;
1000 GNUNET_memcpy (&hash_data.c, &fe->c, sizeof (struct GNUNET_CRYPTO_PaillierCiphertext));
1001 GNUNET_memcpy (&hash_data.h, &fe->h, GNUNET_SECRETSHARING_ELGAMAL_BITS / 8);
1002 GNUNET_memcpy (&hash_data.t1, &fe->t1, GNUNET_SECRETSHARING_ELGAMAL_BITS / 8);
1003 GNUNET_memcpy (&hash_data.t2, &fe->t2, GNUNET_CRYPTO_PAILLIER_BITS * 2 / 8);
1004 GNUNET_CRYPTO_hash (&hash_data,
1007 GNUNET_CRYPTO_mpi_scan_unsigned (&e, &e_hash, sizeof (struct GNUNET_HashCode));
1008 gcry_mpi_mod (e, e, elgamal_q);
1013 verify_fair (const struct GNUNET_CRYPTO_PaillierPublicKey *ppub, const struct GNUNET_SECRETSHARING_FairEncryption *fe)
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 GNUNET_assert (NULL != (e = gcry_mpi_new (0)));
1033 get_fair_encryption_challenge (fe, e);
1035 GNUNET_CRYPTO_mpi_scan_unsigned (&n, ppub, sizeof (struct GNUNET_CRYPTO_PaillierPublicKey));
1036 GNUNET_CRYPTO_mpi_scan_unsigned (&t1, fe->t1, GNUNET_CRYPTO_PAILLIER_BITS / 8);
1037 GNUNET_CRYPTO_mpi_scan_unsigned (&z, fe->z, GNUNET_SECRETSHARING_ELGAMAL_BITS / 8);
1038 GNUNET_CRYPTO_mpi_scan_unsigned (&y, fe->h, GNUNET_SECRETSHARING_ELGAMAL_BITS / 8);
1039 GNUNET_CRYPTO_mpi_scan_unsigned (&w, fe->w, GNUNET_CRYPTO_PAILLIER_BITS / 8);
1040 GNUNET_CRYPTO_mpi_scan_unsigned (&big_y, fe->c.bits, GNUNET_CRYPTO_PAILLIER_BITS * 2 / 8);
1041 GNUNET_CRYPTO_mpi_scan_unsigned (&t2, fe->t2, GNUNET_CRYPTO_PAILLIER_BITS * 2 / 8);
1042 gcry_mpi_mul (n_sq, n, n);
1045 gcry_mpi_powm (tmp1, elgamal_g, z, elgamal_p);
1047 gcry_mpi_powm (tmp1, y, e, elgamal_p);
1048 gcry_mpi_invm (tmp1, tmp1, elgamal_p);
1049 // tmp1 = tmp1 * tmp2
1050 gcry_mpi_mulm (tmp1, tmp1, tmp2, elgamal_p);
1052 if (0 == gcry_mpi_cmp (t1, tmp1))
1054 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "fair encryption invalid (t1)\n");
1059 gcry_mpi_powm (big_y, big_y, e, n_sq);
1060 gcry_mpi_invm (big_y, big_y, n_sq);
1062 gcry_mpi_add_ui (tmp1, n, 1);
1063 gcry_mpi_powm (tmp1, tmp1, z, n_sq);
1065 gcry_mpi_powm (tmp2, w, n, n_sq);
1067 gcry_mpi_mulm (tmp1, tmp1, tmp2, n_sq);
1068 gcry_mpi_mulm (tmp1, tmp1, big_y, n_sq);
1071 if (0 == gcry_mpi_cmp (t2, tmp1))
1073 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "fair encryption invalid (t2)\n");
1082 gcry_mpi_release (n);
1083 gcry_mpi_release (n_sq);
1084 gcry_mpi_release (z);
1085 gcry_mpi_release (t1);
1086 gcry_mpi_release (t2);
1087 gcry_mpi_release (e);
1088 gcry_mpi_release (w);
1089 gcry_mpi_release (tmp1);
1090 gcry_mpi_release (tmp2);
1091 gcry_mpi_release (y);
1092 gcry_mpi_release (big_y);
1098 * Create a fair Paillier encryption of then given ciphertext.
1100 * @param v the ciphertext
1101 * @param[out] fe the fair encryption
1104 encrypt_fair (gcry_mpi_t v, const struct GNUNET_CRYPTO_PaillierPublicKey *ppub, struct GNUNET_SECRETSHARING_FairEncryption *fe)
1119 GNUNET_assert (NULL != (r = gcry_mpi_new (0)));
1120 GNUNET_assert (NULL != (s = gcry_mpi_new (0)));
1121 GNUNET_assert (NULL != (t1 = gcry_mpi_new (0)));
1122 GNUNET_assert (NULL != (t2 = gcry_mpi_new (0)));
1123 GNUNET_assert (NULL != (z = gcry_mpi_new (0)));
1124 GNUNET_assert (NULL != (w = gcry_mpi_new (0)));
1125 GNUNET_assert (NULL != (n_sq = gcry_mpi_new (0)));
1126 GNUNET_assert (NULL != (e = gcry_mpi_new (0)));
1127 GNUNET_assert (NULL != (u = gcry_mpi_new (0)));
1128 GNUNET_assert (NULL != (Y = gcry_mpi_new (0)));
1129 GNUNET_assert (NULL != (G = gcry_mpi_new (0)));
1130 GNUNET_assert (NULL != (h = gcry_mpi_new (0)));
1132 GNUNET_CRYPTO_mpi_scan_unsigned (&n, ppub, sizeof (struct GNUNET_CRYPTO_PaillierPublicKey));
1133 gcry_mpi_mul (n_sq, n, n);
1134 gcry_mpi_add_ui (G, n, 1);
1137 gcry_mpi_randomize (u, GNUNET_CRYPTO_PAILLIER_BITS, GCRY_WEAK_RANDOM);
1139 while (gcry_mpi_cmp (u, n) >= 0);
1141 gcry_mpi_powm (t1, G, v, n_sq);
1142 gcry_mpi_powm (t2, u, n, n_sq);
1143 gcry_mpi_mulm (Y, t1, t2, n_sq);
1145 GNUNET_CRYPTO_mpi_print_unsigned (fe->c.bits,
1150 gcry_mpi_randomize (r, 2048, GCRY_WEAK_RANDOM);
1152 gcry_mpi_randomize (s, GNUNET_CRYPTO_PAILLIER_BITS, GCRY_WEAK_RANDOM);
1154 while (gcry_mpi_cmp (s, n) >= 0);
1157 gcry_mpi_mulm (t1, elgamal_g, r, elgamal_p);
1158 // compute t2 (use z and w as temp)
1159 gcry_mpi_powm (z, G, r, n_sq);
1160 gcry_mpi_powm (w, s, n, n_sq);
1161 gcry_mpi_mulm (t2, z, w, n_sq);
1164 gcry_mpi_powm (h, elgamal_g, v, elgamal_p);
1166 GNUNET_CRYPTO_mpi_print_unsigned (fe->h,
1167 GNUNET_SECRETSHARING_ELGAMAL_BITS / 8,
1170 GNUNET_CRYPTO_mpi_print_unsigned (fe->t1,
1171 GNUNET_SECRETSHARING_ELGAMAL_BITS / 8,
1174 GNUNET_CRYPTO_mpi_print_unsigned (fe->t2,
1175 GNUNET_CRYPTO_PAILLIER_BITS * 2 / 8,
1179 get_fair_encryption_challenge (fe, e);
1182 gcry_mpi_mul (z, e, v);
1183 gcry_mpi_addm (z, z, r, elgamal_q);
1185 gcry_mpi_powm (w, u, e, n);
1186 gcry_mpi_mulm (w, w, s, n);
1188 GNUNET_CRYPTO_mpi_print_unsigned (fe->z,
1189 GNUNET_SECRETSHARING_ELGAMAL_BITS / 8,
1192 GNUNET_CRYPTO_mpi_print_unsigned (fe->w,
1193 GNUNET_CRYPTO_PAILLIER_BITS / 8,
1196 gcry_mpi_release (n);
1197 gcry_mpi_release (r);
1198 gcry_mpi_release (s);
1199 gcry_mpi_release (t1);
1200 gcry_mpi_release (t2);
1201 gcry_mpi_release (z);
1202 gcry_mpi_release (w);
1203 gcry_mpi_release (e);
1204 gcry_mpi_release (n_sq);
1205 gcry_mpi_release (u);
1206 gcry_mpi_release (Y);
1207 gcry_mpi_release (G);
1208 gcry_mpi_release (h);
1213 * Insert round 2 element in the consensus, consisting of
1214 * (1) The exponentiated pre-share polynomial coefficients A_{i,l}=g^{a_{i,l}}
1215 * (2) The exponentiated pre-shares y_{i,j}=g^{s_{i,j}}
1216 * (3) The encrypted pre-shares Y_{i,j}
1217 * (4) The zero knowledge proof for fairness of
1220 * @param ks session to use
1223 insert_round2_element (struct KeygenSession *ks)
1225 struct GNUNET_SET_Element *element;
1226 struct GNUNET_SECRETSHARING_KeygenRevealData *d;
1228 unsigned char *last_pos;
1229 size_t element_size;
1234 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "P%u: Inserting round2 element\n",
1235 ks->local_peer_idx);
1237 GNUNET_assert (NULL != (v = gcry_mpi_new (GNUNET_SECRETSHARING_ELGAMAL_BITS)));
1238 GNUNET_assert (NULL != (idx = gcry_mpi_new (GNUNET_SECRETSHARING_ELGAMAL_BITS)));
1240 element_size = (sizeof (struct GNUNET_SECRETSHARING_KeygenRevealData) +
1241 sizeof (struct GNUNET_SECRETSHARING_FairEncryption) * ks->num_peers +
1242 GNUNET_SECRETSHARING_ELGAMAL_BITS / 8 * ks->threshold);
1244 element = GNUNET_malloc (sizeof (struct GNUNET_SET_Element) + element_size);
1245 element->size = element_size;
1246 element->data = (void *) &element[1];
1248 d = (void *) element->data;
1251 // start inserting vector elements
1252 // after the fixed part of the element's data
1253 pos = (void *) &d[1];
1254 last_pos = pos + element_size;
1256 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "P%u: computed exp preshares\n",
1257 ks->local_peer_idx);
1259 // encrypted pre-shares
1260 // and fair encryption proof
1262 for (i = 0; i < ks->num_peers; i++)
1264 ptrdiff_t remaining = last_pos - pos;
1265 struct GNUNET_SECRETSHARING_FairEncryption *fe = (void *) pos;
1267 GNUNET_assert (remaining > 0);
1268 memset (fe, 0, sizeof *fe);
1269 if (GNUNET_YES == ks->info[i].round1_valid)
1271 gcry_mpi_set_ui (idx, i + 1);
1272 // evaluate the polynomial
1273 horner_eval (v, ks->presecret_polynomial, ks->threshold, idx, elgamal_q);
1274 // encrypt the result
1275 encrypt_fair (v, &ks->info[i].paillier_public_key, fe);
1281 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "P%u: computed enc preshares\n",
1282 ks->local_peer_idx);
1284 // exponentiated coefficients
1285 for (i = 0; i < ks->threshold; i++)
1287 ptrdiff_t remaining = last_pos - pos;
1288 GNUNET_assert (remaining > 0);
1289 gcry_mpi_powm (v, elgamal_g, ks->presecret_polynomial[i], elgamal_p);
1290 GNUNET_CRYPTO_mpi_print_unsigned (pos, GNUNET_SECRETSHARING_ELGAMAL_BITS / 8, v);
1291 pos += GNUNET_SECRETSHARING_ELGAMAL_BITS / 8;
1294 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "P%u: computed exp coefficients\n",
1295 ks->local_peer_idx);
1298 d->purpose.size = htonl (element_size - offsetof (struct GNUNET_SECRETSHARING_KeygenRevealData, purpose));
1299 d->purpose.purpose = htonl (GNUNET_SIGNATURE_PURPOSE_SECRETSHARING_DKG2);
1300 GNUNET_assert (GNUNET_OK ==
1301 GNUNET_CRYPTO_eddsa_sign (my_peer_private_key,
1305 GNUNET_CONSENSUS_insert (ks->consensus, element, NULL, NULL);
1306 GNUNET_free (element); /* FIXME: maybe stack-allocate instead? */
1308 gcry_mpi_release (v);
1309 gcry_mpi_release (idx);
1314 keygen_reveal_get_exp_coeff (struct KeygenSession *ks,
1315 const struct GNUNET_SECRETSHARING_KeygenRevealData *d,
1319 gcry_mpi_t exp_coeff;
1321 GNUNET_assert (idx < ks->threshold);
1323 pos = (void *) &d[1];
1324 // skip encrypted pre-shares
1325 pos += sizeof (struct GNUNET_SECRETSHARING_FairEncryption) * ks->num_peers;
1326 // skip exp. coeffs we are not interested in
1327 pos += GNUNET_SECRETSHARING_ELGAMAL_BITS / 8 * idx;
1328 // the first exponentiated coefficient is the public key share
1329 GNUNET_CRYPTO_mpi_scan_unsigned (&exp_coeff, pos, GNUNET_SECRETSHARING_ELGAMAL_BITS / 8);
1334 static struct GNUNET_SECRETSHARING_FairEncryption *
1335 keygen_reveal_get_enc_preshare (struct KeygenSession *ks,
1336 const struct GNUNET_SECRETSHARING_KeygenRevealData *d,
1341 GNUNET_assert (idx < ks->num_peers);
1343 pos = (void *) &d[1];
1344 // skip encrypted pre-shares we're not interested in
1345 pos += sizeof (struct GNUNET_SECRETSHARING_FairEncryption) * idx;
1346 return (struct GNUNET_SECRETSHARING_FairEncryption *) pos;
1351 keygen_reveal_get_exp_preshare (struct KeygenSession *ks,
1352 const struct GNUNET_SECRETSHARING_KeygenRevealData *d,
1355 gcry_mpi_t exp_preshare;
1356 struct GNUNET_SECRETSHARING_FairEncryption *fe;
1358 GNUNET_assert (idx < ks->num_peers);
1359 fe = keygen_reveal_get_enc_preshare (ks, d, idx);
1360 GNUNET_CRYPTO_mpi_scan_unsigned (&exp_preshare, fe->h, GNUNET_SECRETSHARING_ELGAMAL_BITS / 8);
1361 return exp_preshare;
1366 keygen_round2_new_element (void *cls,
1367 const struct GNUNET_SET_Element *element)
1369 struct KeygenSession *ks = cls;
1370 const struct GNUNET_SECRETSHARING_KeygenRevealData *d;
1371 struct KeygenPeerInfo *info;
1372 size_t expected_element_size;
1376 gcry_mpi_t public_key_share;
1377 gcry_mpi_t preshare;
1379 if (NULL == element)
1381 GNUNET_log (GNUNET_ERROR_TYPE_WARNING, "round2 consensus failed\n");
1385 expected_element_size = (sizeof (struct GNUNET_SECRETSHARING_KeygenRevealData) +
1386 sizeof (struct GNUNET_SECRETSHARING_FairEncryption) * ks->num_peers +
1387 GNUNET_SECRETSHARING_ELGAMAL_BITS / 8 * ks->threshold);
1389 if (element->size != expected_element_size)
1391 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
1392 "keygen round2 data with wrong size (%u) in consensus, %u expected\n",
1393 (unsigned int) element->size,
1394 (unsigned int) expected_element_size);
1398 d = (const void *) element->data;
1400 info = get_keygen_peer_info (ks, &d->peer);
1404 GNUNET_log (GNUNET_ERROR_TYPE_WARNING, "keygen commit data with wrong peer identity (%s) in consensus\n",
1405 GNUNET_i2s (&d->peer));
1409 if (GNUNET_NO == info->round1_valid)
1411 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
1412 "ignoring round2 element from peer with invalid round1 element (%s)\n",
1413 GNUNET_i2s (&d->peer));
1417 if (GNUNET_YES == info->round2_valid)
1419 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
1420 "ignoring duplicate round2 element (%s)\n",
1421 GNUNET_i2s (&d->peer));
1425 GNUNET_log (GNUNET_ERROR_TYPE_INFO, "got round2 element\n");
1427 if (ntohl (d->purpose.size) !=
1428 element->size - offsetof (struct GNUNET_SECRETSHARING_KeygenRevealData, purpose))
1430 GNUNET_log (GNUNET_ERROR_TYPE_WARNING, "keygen reveal data with wrong signature purpose size in consensus\n");
1434 if (GNUNET_OK != GNUNET_CRYPTO_eddsa_verify (GNUNET_SIGNATURE_PURPOSE_SECRETSHARING_DKG2,
1435 &d->purpose, &d->signature, &d->peer.public_key))
1437 GNUNET_log (GNUNET_ERROR_TYPE_WARNING, "keygen reveal data with invalid signature in consensus\n");
1441 public_key_share = keygen_reveal_get_exp_coeff (ks, d, 0);
1442 info->preshare_commitment = keygen_reveal_get_exp_preshare (ks, d, ks->local_peer_idx);
1444 if (NULL == ks->public_key)
1446 GNUNET_assert (NULL != (ks->public_key = gcry_mpi_new (0)));
1447 gcry_mpi_set_ui (ks->public_key, 1);
1449 gcry_mpi_mulm (ks->public_key, ks->public_key, public_key_share, elgamal_p);
1451 gcry_mpi_release (public_key_share);
1452 public_key_share = NULL;
1455 struct GNUNET_SECRETSHARING_FairEncryption *fe = keygen_reveal_get_enc_preshare (ks, d, ks->local_peer_idx);
1456 GNUNET_assert (NULL != (preshare = gcry_mpi_new (0)));
1457 GNUNET_CRYPTO_paillier_decrypt (&ks->paillier_private_key,
1458 &ks->info[ks->local_peer_idx].paillier_public_key,
1462 // FIXME: not doing the restoration is less expensive
1463 restore_fair (&ks->info[ks->local_peer_idx].paillier_public_key,
1469 GNUNET_assert (NULL != (tmp = gcry_mpi_new (0)));
1470 gcry_mpi_powm (tmp, elgamal_g, preshare, elgamal_p);
1472 cmp_result = gcry_mpi_cmp (tmp, info->preshare_commitment);
1473 gcry_mpi_release (tmp);
1475 if (0 != cmp_result)
1477 GNUNET_log (GNUNET_ERROR_TYPE_WARNING, "P%u: Got invalid presecret from P%u\n",
1478 (unsigned int) ks->local_peer_idx, (unsigned int) (info - ks->info));
1482 if (NULL == ks->my_share)
1484 GNUNET_assert (NULL != (ks->my_share = gcry_mpi_new (0)));
1486 gcry_mpi_addm (ks->my_share, ks->my_share, preshare, elgamal_q);
1488 for (j = 0; j < ks->num_peers; j++)
1490 gcry_mpi_t presigma;
1491 if (NULL == ks->info[j].sigma)
1493 GNUNET_assert (NULL != (ks->info[j].sigma = gcry_mpi_new (0)));
1494 gcry_mpi_set_ui (ks->info[j].sigma, 1);
1496 presigma = keygen_reveal_get_exp_preshare (ks, d, j);
1497 gcry_mpi_mulm (ks->info[j].sigma, ks->info[j].sigma, presigma, elgamal_p);
1498 gcry_mpi_release (presigma);
1502 GNUNET_assert (NULL != (prod = gcry_mpi_new (0)));
1504 GNUNET_assert (NULL != (j_to_k = gcry_mpi_new (0)));
1505 // validate that the polynomial sharing matches the additive sharing
1506 for (j = 0; j < ks->num_peers; j++)
1510 gcry_mpi_t exp_preshare;
1511 gcry_mpi_set_ui (prod, 1);
1512 for (k = 0; k < ks->threshold; k++)
1514 // Using pow(double,double) is a bit sketchy.
1515 // We count players from 1, but shares from 0.
1517 gcry_mpi_set_ui (j_to_k, (unsigned int) pow(j+1, k));
1518 tmp = keygen_reveal_get_exp_coeff (ks, d, k);
1519 gcry_mpi_powm (tmp, tmp, j_to_k, elgamal_p);
1520 gcry_mpi_mulm (prod, prod, tmp, elgamal_p);
1521 gcry_mpi_release (tmp);
1523 exp_preshare = keygen_reveal_get_exp_preshare (ks, d, j);
1524 gcry_mpi_mod (exp_preshare, exp_preshare, elgamal_p);
1525 cmp_result = gcry_mpi_cmp (prod, exp_preshare);
1526 gcry_mpi_release (exp_preshare);
1527 exp_preshare = NULL;
1528 if (0 != cmp_result)
1530 GNUNET_log (GNUNET_ERROR_TYPE_WARNING, "P%u: reveal data from P%u incorrect\n",
1531 ks->local_peer_idx, j);
1532 /* no need for further verification, round2 stays invalid ... */
1537 // TODO: verify proof of fair encryption (once implemented)
1538 for (j = 0; j < ks->num_peers; j++)
1540 struct GNUNET_SECRETSHARING_FairEncryption *fe = keygen_reveal_get_enc_preshare (ks, d, j);
1541 if (GNUNET_YES != verify_fair (&ks->info[j].paillier_public_key, fe))
1543 GNUNET_log (GNUNET_ERROR_TYPE_WARNING, "P%u: reveal data from P%u incorrect (fair encryption)\n",
1544 ks->local_peer_idx, j);
1550 info->round2_valid = GNUNET_YES;
1552 gcry_mpi_release (preshare);
1553 gcry_mpi_release (prod);
1554 gcry_mpi_release (j_to_k);
1559 * Called when the first consensus round has concluded.
1560 * Will initiate the second round.
1562 * @param cls closure
1565 keygen_round1_conclude (void *cls)
1567 struct KeygenSession *ks = cls;
1569 GNUNET_CONSENSUS_destroy (ks->consensus);
1571 ks->consensus = GNUNET_CONSENSUS_create (cfg, ks->num_peers, ks->peers, &ks->session_id,
1572 time_between (ks->start_time, ks->deadline, 1, 2),
1574 keygen_round2_new_element, ks);
1576 insert_round2_element (ks);
1578 GNUNET_CONSENSUS_conclude (ks->consensus,
1579 keygen_round2_conclude,
1585 * Insert the ephemeral key and the presecret commitment
1586 * of this peer in the consensus of the given session.
1588 * @param ks session to use
1591 insert_round1_element (struct KeygenSession *ks)
1593 struct GNUNET_SET_Element *element;
1594 struct GNUNET_SECRETSHARING_KeygenCommitData *d;
1597 // big-endian representation of 'v'
1598 unsigned char v_data[GNUNET_SECRETSHARING_ELGAMAL_BITS / 8];
1600 element = GNUNET_malloc (sizeof *element + sizeof *d);
1601 d = (void *) &element[1];
1603 element->size = sizeof *d;
1607 GNUNET_assert (0 != (v = gcry_mpi_new (GNUNET_SECRETSHARING_ELGAMAL_BITS)));
1609 gcry_mpi_powm (v, elgamal_g, ks->presecret_polynomial[0], elgamal_p);
1611 GNUNET_CRYPTO_mpi_print_unsigned (v_data, GNUNET_SECRETSHARING_ELGAMAL_BITS / 8, v);
1613 GNUNET_CRYPTO_hash (v_data, GNUNET_SECRETSHARING_ELGAMAL_BITS / 8, &d->commitment);
1615 d->pubkey = ks->info[ks->local_peer_idx].paillier_public_key;
1617 d->purpose.size = htonl ((sizeof *d) - offsetof (struct GNUNET_SECRETSHARING_KeygenCommitData, purpose));
1618 d->purpose.purpose = htonl (GNUNET_SIGNATURE_PURPOSE_SECRETSHARING_DKG1);
1619 GNUNET_assert (GNUNET_OK ==
1620 GNUNET_CRYPTO_eddsa_sign (my_peer_private_key,
1624 GNUNET_CONSENSUS_insert (ks->consensus, element, NULL, NULL);
1626 gcry_mpi_release (v);
1627 GNUNET_free (element);
1632 * Check that @a msg is well-formed.
1634 * @param cls identification of the client
1635 * @param msg the actual message
1636 * @return #GNUNET_OK if @a msg is well-formed
1639 check_client_keygen (void *cls,
1640 const struct GNUNET_SECRETSHARING_CreateMessage *msg)
1642 unsigned int num_peers = ntohs (msg->num_peers);
1644 if (ntohs (msg->header.size) - sizeof (*msg) !=
1645 num_peers * sizeof (struct GNUNET_PeerIdentity))
1648 return GNUNET_SYSERR;
1655 * Functions with this signature are called whenever a message is
1658 * @param cls identification of the client
1659 * @param msg the actual message
1662 handle_client_keygen (void *cls,
1663 const struct GNUNET_SECRETSHARING_CreateMessage *msg)
1665 struct ClientState *cs = cls;
1666 struct KeygenSession *ks;
1668 GNUNET_log (GNUNET_ERROR_TYPE_INFO,
1669 "client requested key generation\n");
1670 if (NULL != cs->keygen_session)
1673 GNUNET_SERVICE_client_drop (cs->client);
1676 ks = GNUNET_new (struct KeygenSession);
1678 cs->keygen_session = ks;
1679 ks->deadline = GNUNET_TIME_absolute_ntoh (msg->deadline);
1680 ks->threshold = ntohs (msg->threshold);
1681 ks->num_peers = ntohs (msg->num_peers);
1683 ks->peers = normalize_peers ((struct GNUNET_PeerIdentity *) &msg[1],
1686 &ks->local_peer_idx);
1689 GNUNET_log (GNUNET_ERROR_TYPE_INFO,
1690 "first round of consensus with %u peers\n",
1692 ks->consensus = GNUNET_CONSENSUS_create (cfg,
1696 GNUNET_TIME_absolute_ntoh (msg->start),
1697 GNUNET_TIME_absolute_ntoh (msg->deadline),
1698 keygen_round1_new_element,
1701 ks->info = GNUNET_new_array (ks->num_peers,
1702 struct KeygenPeerInfo);
1704 for (unsigned int i = 0; i < ks->num_peers; i++)
1705 ks->info[i].peer = ks->peers[i];
1707 GNUNET_CRYPTO_paillier_create (&ks->info[ks->local_peer_idx].paillier_public_key,
1708 &ks->paillier_private_key);
1710 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1711 "P%u: Generated paillier key pair\n",
1712 ks->local_peer_idx);
1713 generate_presecret_polynomial (ks);
1714 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1715 "P%u: Generated presecret polynomial\n",
1716 ks->local_peer_idx);
1717 insert_round1_element (ks);
1718 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1719 "P%u: Concluding for round 1\n",
1720 ks->local_peer_idx);
1721 GNUNET_CONSENSUS_conclude (ks->consensus,
1722 keygen_round1_conclude,
1724 GNUNET_SERVICE_client_continue (cs->client);
1725 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1726 "P%u: Waiting for round 1 elements ...\n",
1727 ks->local_peer_idx);
1732 * Called when the partial decryption consensus concludes.
1735 decrypt_conclude (void *cls)
1737 struct DecryptSession *ds = cls;
1738 struct GNUNET_SECRETSHARING_DecryptResponseMessage *msg;
1739 struct GNUNET_MQ_Envelope *ev;
1740 gcry_mpi_t lagrange;
1745 unsigned int *indices;
1750 GNUNET_CONSENSUS_destroy (ds->consensus);
1751 ds->consensus = NULL;
1753 GNUNET_assert (0 != (lagrange = gcry_mpi_new (0)));
1754 GNUNET_assert (0 != (m = gcry_mpi_new (0)));
1755 GNUNET_assert (0 != (tmp = gcry_mpi_new (0)));
1756 GNUNET_assert (0 != (prod = gcry_mpi_new (0)));
1759 for (i = 0; i < ds->share->num_peers; i++)
1760 if (NULL != ds->info[i].partial_decryption)
1763 indices = GNUNET_new_array (num,
1766 for (i = 0; i < ds->share->num_peers; i++)
1767 if (NULL != ds->info[i].partial_decryption)
1768 indices[j++] = ds->info[i].original_index;
1770 GNUNET_log (GNUNET_ERROR_TYPE_INFO,
1771 "P%u: decrypt conclude, with %u peers\n",
1775 gcry_mpi_set_ui (prod, 1);
1776 for (i = 0; i < num; i++)
1779 GNUNET_log (GNUNET_ERROR_TYPE_INFO,
1780 "P%u: index of %u: %u\n",
1781 ds->share->my_peer, i, indices[i]);
1782 compute_lagrange_coefficient (lagrange, indices[i], indices, num);
1784 gcry_mpi_powm (tmp, ds->info[indices[i]].partial_decryption, lagrange, elgamal_p);
1786 // product of all exponentiated partiel decryptions ...
1787 gcry_mpi_mulm (prod, prod, tmp, elgamal_p);
1790 GNUNET_CRYPTO_mpi_scan_unsigned (&c_2, ds->ciphertext.c2_bits, GNUNET_SECRETSHARING_ELGAMAL_BITS / 8);
1792 GNUNET_assert (0 != gcry_mpi_invm (prod, prod, elgamal_p));
1793 gcry_mpi_mulm (m, c_2, prod, elgamal_p);
1794 ev = GNUNET_MQ_msg (msg, GNUNET_MESSAGE_TYPE_SECRETSHARING_CLIENT_DECRYPT_DONE);
1795 GNUNET_CRYPTO_mpi_print_unsigned (&msg->plaintext, GNUNET_SECRETSHARING_ELGAMAL_BITS / 8, m);
1796 msg->success = htonl (1);
1797 GNUNET_MQ_send (ds->cs->mq,
1800 GNUNET_log (GNUNET_ERROR_TYPE_INFO, "sent decrypt done to client\n");
1802 GNUNET_free (indices);
1804 gcry_mpi_release(lagrange);
1805 gcry_mpi_release(m);
1806 gcry_mpi_release(tmp);
1807 gcry_mpi_release(prod);
1808 gcry_mpi_release(c_2);
1810 // FIXME: what if not enough peers participated?
1815 * Get a string representation of an MPI.
1816 * The caller must free the returned string.
1818 * @param mpi mpi to convert to a string
1819 * @return string representation of @a mpi, must be free'd by the caller
1822 mpi_to_str (gcry_mpi_t mpi)
1826 GNUNET_assert (0 == gcry_mpi_aprint (GCRYMPI_FMT_HEX, &buf, NULL, mpi));
1827 return (char *) buf;
1832 * Called when a new partial decryption arrives.
1835 decrypt_new_element (void *cls,
1836 const struct GNUNET_SET_Element *element)
1838 struct DecryptSession *session = cls;
1839 const struct GNUNET_SECRETSHARING_DecryptData *d;
1840 struct DecryptPeerInfo *info;
1841 struct GNUNET_HashCode challenge_hash;
1845 /* nizk challenge */
1846 gcry_mpi_t challenge;
1847 /* nizk commit1, g^\beta */
1849 /* nizk commit2, c_1^\beta */
1851 /* homomorphic commitment to the peer's share,
1852 * public key share */
1854 /* partial decryption we received */
1856 /* ciphertext component #1 */
1858 /* temporary variable (for comparision) #1 */
1860 /* temporary variable (for comparision) #2 */
1863 if (NULL == element)
1865 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "decryption failed\n");
1866 /* FIXME: destroy */
1870 if (element->size != sizeof *d)
1872 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "element of wrong size in decrypt consensus\n");
1878 info = get_decrypt_peer_info (session, &d->peer);
1882 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "decrypt element from invalid peer (%s)\n",
1883 GNUNET_i2s (&d->peer));
1887 if (NULL != info->partial_decryption)
1889 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "decrypt element duplicate\n");
1893 if (0 != memcmp (&d->ciphertext, &session->ciphertext, sizeof (struct GNUNET_SECRETSHARING_Ciphertext)))
1895 GNUNET_log (GNUNET_ERROR_TYPE_WARNING, "P%u: got decrypt element with non-matching ciphertext from P%u\n",
1896 (unsigned int) session->share->my_peer, (unsigned int) (info - session->info));
1902 GNUNET_CRYPTO_hash (offsetof (struct GNUNET_SECRETSHARING_DecryptData, ciphertext) + (char *) d,
1903 offsetof (struct GNUNET_SECRETSHARING_DecryptData, nizk_response) -
1904 offsetof (struct GNUNET_SECRETSHARING_DecryptData, ciphertext),
1907 GNUNET_CRYPTO_mpi_scan_unsigned (&challenge, &challenge_hash,
1908 sizeof (struct GNUNET_HashCode));
1910 GNUNET_CRYPTO_mpi_scan_unsigned (&sigma, &session->share->sigmas[info - session->info],
1911 sizeof (struct GNUNET_SECRETSHARING_FieldElement));
1913 GNUNET_CRYPTO_mpi_scan_unsigned (&c1, session->ciphertext.c1_bits,
1914 sizeof (struct GNUNET_SECRETSHARING_FieldElement));
1916 GNUNET_CRYPTO_mpi_scan_unsigned (&commit1, &d->nizk_commit1,
1917 sizeof (struct GNUNET_SECRETSHARING_FieldElement));
1919 GNUNET_CRYPTO_mpi_scan_unsigned (&commit2, &d->nizk_commit2,
1920 sizeof (struct GNUNET_SECRETSHARING_FieldElement));
1922 GNUNET_CRYPTO_mpi_scan_unsigned (&r, &d->nizk_response,
1923 sizeof (struct GNUNET_SECRETSHARING_FieldElement));
1925 GNUNET_CRYPTO_mpi_scan_unsigned (&w, &d->partial_decryption,
1926 sizeof (struct GNUNET_SECRETSHARING_FieldElement));
1928 GNUNET_assert (NULL != (tmp1 = gcry_mpi_new (0)));
1929 GNUNET_assert (NULL != (tmp2 = gcry_mpi_new (0)));
1932 gcry_mpi_powm (tmp1, elgamal_g, r, elgamal_p);
1934 // tmp2 = g^\beta * \sigma^challenge
1935 gcry_mpi_powm (tmp2, sigma, challenge, elgamal_p);
1936 gcry_mpi_mulm (tmp2, tmp2, commit1, elgamal_p);
1938 if (0 != gcry_mpi_cmp (tmp1, tmp2))
1943 tmp1_str = mpi_to_str (tmp1);
1944 tmp2_str = mpi_to_str (tmp2);
1945 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
1946 "P%u: Received invalid partial decryption from P%u (eqn 1), expected %s got %s\n",
1947 session->share->my_peer,
1948 (unsigned int) (info - session->info),
1951 GNUNET_free (tmp1_str);
1952 GNUNET_free (tmp2_str);
1957 gcry_mpi_powm (tmp1, c1, r, elgamal_p);
1959 gcry_mpi_powm (tmp2, w, challenge, elgamal_p);
1960 gcry_mpi_mulm (tmp2, tmp2, commit2, elgamal_p);
1963 if (0 != gcry_mpi_cmp (tmp1, tmp2))
1965 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
1966 "P%u: Received invalid partial decryption from P%u (eqn 2)\n",
1967 session->share->my_peer,
1968 (unsigned int) (info - session->info));
1973 GNUNET_CRYPTO_mpi_scan_unsigned (&info->partial_decryption, &d->partial_decryption,
1974 GNUNET_SECRETSHARING_ELGAMAL_BITS / 8);
1976 gcry_mpi_release (tmp1);
1977 gcry_mpi_release (tmp2);
1978 gcry_mpi_release (sigma);
1979 gcry_mpi_release (commit1);
1980 gcry_mpi_release (commit2);
1981 gcry_mpi_release (r);
1982 gcry_mpi_release (w);
1983 gcry_mpi_release (challenge);
1984 gcry_mpi_release (c1);
1989 insert_decrypt_element (struct DecryptSession *ds)
1991 struct GNUNET_SECRETSHARING_DecryptData d;
1992 struct GNUNET_SET_Element element;
1995 /* partial decryption with our share */
1997 /* first component of the elgamal ciphertext */
1999 /* nonce for dlog zkp */
2002 gcry_mpi_t challenge;
2004 struct GNUNET_HashCode challenge_hash;
2006 /* make vagrind happy until we implement the real deal ... */
2007 memset (&d, 0, sizeof d);
2009 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "P%u: Inserting decrypt element\n",
2010 ds->share->my_peer);
2012 GNUNET_assert (ds->share->my_peer < ds->share->num_peers);
2014 GNUNET_CRYPTO_mpi_scan_unsigned (&c1, &ds->ciphertext.c1_bits,
2015 GNUNET_SECRETSHARING_ELGAMAL_BITS / 8);
2016 GNUNET_CRYPTO_mpi_scan_unsigned (&s, &ds->share->my_share,
2017 GNUNET_SECRETSHARING_ELGAMAL_BITS / 8);
2018 GNUNET_CRYPTO_mpi_scan_unsigned (&sigma, &ds->share->sigmas[ds->share->my_peer],
2019 GNUNET_SECRETSHARING_ELGAMAL_BITS / 8);
2021 GNUNET_assert (NULL != (w = gcry_mpi_new (0)));
2022 GNUNET_assert (NULL != (beta = gcry_mpi_new (0)));
2023 GNUNET_assert (NULL != (tmp = gcry_mpi_new (0)));
2025 // FIXME: unnecessary, remove once crypto works
2026 gcry_mpi_powm (tmp, elgamal_g, s, elgamal_p);
2027 if (0 != gcry_mpi_cmp (tmp, sigma))
2029 char *sigma_str = mpi_to_str (sigma);
2030 char *tmp_str = mpi_to_str (tmp);
2031 char *s_str = mpi_to_str (s);
2032 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Share of P%u is invalid, ref sigma %s, "
2033 "computed sigma %s, s %s\n",
2035 sigma_str, tmp_str, s_str);
2036 GNUNET_free (sigma_str);
2037 GNUNET_free (tmp_str);
2038 GNUNET_free (s_str);
2041 gcry_mpi_powm (w, c1, s, elgamal_p);
2043 element.data = (void *) &d;
2044 element.size = sizeof (struct GNUNET_SECRETSHARING_DecryptData);
2045 element.element_type = 0;
2047 d.ciphertext = ds->ciphertext;
2049 GNUNET_CRYPTO_mpi_print_unsigned (&d.partial_decryption, GNUNET_SECRETSHARING_ELGAMAL_BITS / 8, w);
2051 // create the zero knowledge proof
2052 // randomly choose beta such that 0 < beta < q
2055 gcry_mpi_randomize (beta, GNUNET_SECRETSHARING_ELGAMAL_BITS - 1, GCRY_WEAK_RANDOM);
2056 } while ((gcry_mpi_cmp_ui (beta, 0) == 0) || (gcry_mpi_cmp (beta, elgamal_q) >= 0));
2058 gcry_mpi_powm (tmp, elgamal_g, beta, elgamal_p);
2059 GNUNET_CRYPTO_mpi_print_unsigned (&d.nizk_commit1, GNUNET_SECRETSHARING_ELGAMAL_BITS / 8, tmp);
2061 gcry_mpi_powm (tmp, c1, beta, elgamal_p);
2062 GNUNET_CRYPTO_mpi_print_unsigned (&d.nizk_commit2, GNUNET_SECRETSHARING_ELGAMAL_BITS / 8, tmp);
2064 // the challenge is the hash of everything up to the response
2065 GNUNET_CRYPTO_hash (offsetof (struct GNUNET_SECRETSHARING_DecryptData, ciphertext) + (char *) &d,
2066 offsetof (struct GNUNET_SECRETSHARING_DecryptData, nizk_response) -
2067 offsetof (struct GNUNET_SECRETSHARING_DecryptData, ciphertext),
2070 GNUNET_CRYPTO_mpi_scan_unsigned (&challenge, &challenge_hash,
2071 sizeof (struct GNUNET_HashCode));
2073 // compute the response in tmp,
2074 // tmp = (c * s + beta) mod q
2075 gcry_mpi_mulm (tmp, challenge, s, elgamal_q);
2076 gcry_mpi_addm (tmp, tmp, beta, elgamal_q);
2078 GNUNET_CRYPTO_mpi_print_unsigned (&d.nizk_response, GNUNET_SECRETSHARING_ELGAMAL_BITS / 8, tmp);
2080 d.purpose.size = htonl (element.size - offsetof (struct GNUNET_SECRETSHARING_DecryptData, purpose));
2081 d.purpose.purpose = htonl (GNUNET_SIGNATURE_PURPOSE_SECRETSHARING_DECRYPTION);
2083 GNUNET_assert (GNUNET_OK ==
2084 GNUNET_CRYPTO_eddsa_sign (my_peer_private_key,
2088 GNUNET_CONSENSUS_insert (ds->consensus, &element, NULL, NULL);
2089 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
2090 "P%u: Inserting decrypt element done!\n",
2091 ds->share->my_peer);
2093 gcry_mpi_release (s);
2094 gcry_mpi_release (w);
2095 gcry_mpi_release (c1);
2096 gcry_mpi_release (beta);
2097 gcry_mpi_release (tmp);
2098 gcry_mpi_release (challenge);
2099 gcry_mpi_release (sigma);
2104 * Check that @a msg is well-formed.
2106 * @param cls identification of the client
2107 * @param msg the actual message
2108 * @return #GNUNET_OK (check deferred a bit)
2111 check_client_decrypt (void *cls,
2112 const struct GNUNET_SECRETSHARING_DecryptRequestMessage *msg)
2114 /* we check later, it's complicated */
2120 * Functions with this signature are called whenever a message is
2123 * @param cls identification of the client
2124 * @param msg the actual message
2127 handle_client_decrypt (void *cls,
2128 const struct GNUNET_SECRETSHARING_DecryptRequestMessage *msg)
2130 struct ClientState *cs = cls;
2131 struct DecryptSession *ds;
2132 struct GNUNET_HashCode session_id;
2134 if (NULL != cs->decrypt_session)
2137 GNUNET_SERVICE_client_drop (cs->client);
2140 ds = GNUNET_new (struct DecryptSession);
2141 cs->decrypt_session = ds;
2143 ds->start = GNUNET_TIME_absolute_ntoh (msg->start);
2144 ds->deadline = GNUNET_TIME_absolute_ntoh (msg->deadline);
2145 ds->ciphertext = msg->ciphertext;
2147 ds->share = GNUNET_SECRETSHARING_share_read (&msg[1],
2148 ntohs (msg->header.size) - sizeof (*msg),
2150 if (NULL == ds->share)
2153 GNUNET_SERVICE_client_drop (cs->client);
2157 /* FIXME: this is probably sufficient, but kdf/hash with all values would be nicer ... */
2158 GNUNET_CRYPTO_hash (&msg->ciphertext,
2159 sizeof (struct GNUNET_SECRETSHARING_Ciphertext),
2161 ds->consensus = GNUNET_CONSENSUS_create (cfg,
2162 ds->share->num_peers,
2167 &decrypt_new_element,
2171 ds->info = GNUNET_new_array (ds->share->num_peers,
2172 struct DecryptPeerInfo);
2173 for (unsigned int i = 0; i < ds->share->num_peers; i++)
2175 ds->info[i].peer = ds->share->peers[i];
2176 ds->info[i].original_index = ds->share->original_indices[i];
2178 insert_decrypt_element (ds);
2179 GNUNET_CONSENSUS_conclude (ds->consensus,
2182 GNUNET_SERVICE_client_continue (cs->client);
2183 GNUNET_log (GNUNET_ERROR_TYPE_INFO,
2184 "decrypting with %u peers\n",
2185 ds->share->num_peers);
2190 init_crypto_constants (void)
2192 GNUNET_assert (0 == gcry_mpi_scan (&elgamal_q, GCRYMPI_FMT_HEX,
2193 GNUNET_SECRETSHARING_ELGAMAL_Q_HEX, 0, NULL));
2194 GNUNET_assert (0 == gcry_mpi_scan (&elgamal_p, GCRYMPI_FMT_HEX,
2195 GNUNET_SECRETSHARING_ELGAMAL_P_HEX, 0, NULL));
2196 GNUNET_assert (0 == gcry_mpi_scan (&elgamal_g, GCRYMPI_FMT_HEX,
2197 GNUNET_SECRETSHARING_ELGAMAL_G_HEX, 0, NULL));
2202 * Initialize secretsharing service.
2204 * @param cls closure
2205 * @param c configuration to use
2206 * @param service the initialized service
2210 const struct GNUNET_CONFIGURATION_Handle *c,
2211 struct GNUNET_SERVICE_Handle *service)
2214 my_peer_private_key = GNUNET_CRYPTO_eddsa_key_create_from_configuration (c);
2215 if (NULL == my_peer_private_key)
2217 GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
2218 "could not access host private key\n");
2220 GNUNET_SCHEDULER_shutdown ();
2223 init_crypto_constants ();
2225 GNUNET_CRYPTO_get_peer_identity (cfg,
2228 GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
2229 "could not retrieve host identity\n");
2231 GNUNET_SCHEDULER_shutdown ();
2234 GNUNET_SCHEDULER_add_shutdown (&cleanup_task,
2240 * Callback called when a client connects to the service.
2242 * @param cls closure for the service
2243 * @param c the new client that connected to the service
2244 * @param mq the message queue used to send messages to the client
2248 client_connect_cb (void *cls,
2249 struct GNUNET_SERVICE_Client *c,
2250 struct GNUNET_MQ_Handle *mq)
2252 struct ClientState *cs = GNUNET_new (struct ClientState);;
2261 * Callback called when a client disconnected from the service
2263 * @param cls closure for the service
2264 * @param c the client that disconnected
2265 * @param internal_cls should be equal to @a c
2268 client_disconnect_cb (void *cls,
2269 struct GNUNET_SERVICE_Client *c,
2272 struct ClientState *cs = internal_cls;
2274 if (NULL != cs->keygen_session)
2275 keygen_session_destroy (cs->keygen_session);
2277 if (NULL != cs->decrypt_session)
2278 decrypt_session_destroy (cs->decrypt_session);
2284 * Define "main" method using service macro.
2288 GNUNET_SERVICE_OPTION_NONE,
2291 &client_disconnect_cb,
2293 GNUNET_MQ_hd_var_size (client_keygen,
2294 GNUNET_MESSAGE_TYPE_SECRETSHARING_CLIENT_GENERATE,
2295 struct GNUNET_SECRETSHARING_CreateMessage,
2297 GNUNET_MQ_hd_var_size (client_decrypt,
2298 GNUNET_MESSAGE_TYPE_SECRETSHARING_CLIENT_DECRYPT,
2299 struct GNUNET_SECRETSHARING_DecryptRequestMessage,
2301 GNUNET_MQ_handler_end ());