2 This file is part of GNUnet.
3 (C) 2013 Christian Grothoff (and other contributing authors)
5 GNUnet is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published
7 by the Free Software Foundation; either version 3, or (at your
8 option) any later version.
10 GNUnet is distributed in the hope that it will be useful, but
11 WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 General Public License for more details.
15 You should have received a copy of the GNU General Public License
16 along with GNUnet; see the file COPYING. If not, write to the
17 Free Software Foundation, Inc., 59 Temple Place - Suite 330,
18 Boston, MA 02111-1307, USA.
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"
37 * Info about a peer in a key generation session.
42 * Peer identity of the peer.
44 struct GNUNET_PeerIdentity peer;
47 * The peer's paillier public key.
49 gcry_mpi_t paillier_n;
52 * The peer's commitment to his presecret.
54 gcry_mpi_t presecret_commitment;
57 * The peer's preshare that we decrypted
58 * with out private key.
60 gcry_mpi_t decrypted_preshare;
63 * Multiplicative share of the public key.
65 gcry_mpi_t public_key_share;
68 * Did we successfully receive the round1 element
74 * Did we successfully receive the round2 element
82 * Information about a peer in a decrypt session.
84 struct DecryptPeerInfo
87 * Identity of the peer.
89 struct GNUNET_PeerIdentity peer;
92 * Original index in the key generation round.
93 * Necessary for computing the lagrange coefficients.
95 unsigned int real_index;
98 * Set to the partial decryption of
99 * this peer, or NULL if we did not
100 * receive a partial decryption from this
101 * peer or the zero knowledge proof failed.
103 gcry_mpi_t partial_decryption;
108 * Session to establish a threshold-shared secret.
113 * Keygen sessions are held in a linked list.
115 struct KeygenSession *next;
118 * Keygen sessions are held in a linked list.
120 struct KeygenSession *prev;
123 * Current consensus, used for both DKG rounds.
125 struct GNUNET_CONSENSUS_Handle *consensus;
128 * Client that is interested in the result
129 * of this key generation session.
131 struct GNUNET_SERVER_Client *client;
134 * Message queue for 'client'
136 struct GNUNET_MQ_Handle *client_mq;
139 * Randomly generated coefficients of the polynomial for sharing our
140 * pre-secret, where 'preshares[0]' is our pre-secret. Contains 'threshold'
141 * elements, thus represents a polynomial of degree 'threshold-1', which can
142 * be interpolated with 'threshold' data points.
144 * The pre-secret-shares 'i=1,...,num_peers' are given by evaluating this
145 * polyomial at 'i' for share i.
147 gcry_mpi_t *presecret_polynomial;
150 * Minimum number of shares required to restore the secret.
151 * Also the number of coefficients for the polynomial representing
152 * the sharing. Obviously, the polynomial then has degree threshold-1.
154 unsigned int threshold;
157 * Total number of peers.
159 unsigned int num_peers;
162 * Index of the local peer.
164 unsigned int local_peer;
167 * Information about all participating peers.
168 * Array of size 'num_peers'.
170 struct KeygenPeerInfo *info;
173 * List of all peers involved in the secret sharing session.
175 struct GNUNET_PeerIdentity *peers;
178 * Identifier for this session.
180 struct GNUNET_HashCode session_id;
183 * lambda-component of our peer's paillier private key.
185 gcry_mpi_t paillier_lambda;
188 * mu-component of our peer's paillier private key.
190 gcry_mpi_t paillier_mu;
193 * When would we like the key to be established?
195 struct GNUNET_TIME_Absolute deadline;
198 * When does the DKG start? Necessary to compute fractions of the
199 * operation's desired time interval.
201 struct GNUNET_TIME_Absolute start_time;
204 * Index of the local peer in the ordered list
205 * of peers in the session.
207 unsigned int local_peer_idx;
212 * Session to cooperatively decrypt a value.
214 struct DecryptSession
217 * Decrypt sessions are stored in a linked list.
219 struct DecryptSession *next;
222 * Decrypt sessions are stored in a linked list.
224 struct DecryptSession *prev;
227 * Handle to the consensus over partial decryptions.
229 struct GNUNET_CONSENSUS_Handle *consensus;
232 * Client connected to us.
234 struct GNUNET_SERVER_Client *client;
237 * Message queue for 'client'.
239 struct GNUNET_MQ_Handle *client_mq;
242 * When would we like the ciphertext to be
245 struct GNUNET_TIME_Absolute deadline;
248 * Ciphertext we want to decrypt.
250 struct GNUNET_SECRETSHARING_Ciphertext ciphertext;
253 * Share of the local peer.
254 * Containts other important information, such as
255 * the list of other peers.
257 struct GNUNET_SECRETSHARING_Share *share;
260 * State information about other peers.
262 struct DecryptPeerInfo *info;
267 * Decrypt sessions are held in a linked list.
269 static struct DecryptSession *decrypt_sessions_head;
272 * Decrypt sessions are held in a linked list.
274 static struct DecryptSession *decrypt_sessions_tail;
277 * Decrypt sessions are held in a linked list.
279 static struct KeygenSession *keygen_sessions_head;
282 * Decrypt sessions are held in a linked list.
284 static struct KeygenSession *keygen_sessions_tail;
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;
320 * Server for this service.
322 static struct GNUNET_SERVER_Handle *srv;
326 * If target != size, move @a target bytes to the end of the size-sized
327 * buffer and zero out the first @a target - @a size bytes.
329 * @param buf original buffer
330 * @param size number of bytes in @a buf
331 * @param target target size of the buffer
334 adjust (unsigned char *buf,
340 memmove (&buf[target - size], buf, size);
341 memset (buf, 0, target - size);
347 * Print an MPI to a buffer, so that is contains the MPI's
348 * the little endian representation of size @a size.
350 * @param buf buffer to write to
351 * @param x mpi to be written in the buffer
352 * @param size how many bytes should the little endian binary
353 * representation of @a x use?
356 print_mpi_fixed (void *buf, gcry_mpi_t x, size_t size)
359 GNUNET_assert (0 == gcry_mpi_print (GCRYMPI_FMT_USG,
362 adjust (buf, written, size);
367 * Get the peer info belonging to a peer identity in a keygen session.
369 * @param ks the keygen session
370 * @param peer the peer identity
371 * @return the keygen peer info, or NULL if the peer could not be found
373 static struct KeygenPeerInfo *
374 get_keygen_peer_info (const struct KeygenSession *ks,
375 const struct GNUNET_PeerIdentity *peer)
378 for (i = 0; i < ks->num_peers; i++)
379 if (0 == memcmp (peer, &ks->info[i].peer, sizeof (struct GNUNET_PeerIdentity)))
386 * Get the peer info belonging to a peer identity in a decrypt session.
388 * @param ks the decrypt session
389 * @param peer the peer identity
390 * @return the decrypt peer info, or NULL if the peer could not be found
392 static struct DecryptPeerInfo *
393 get_decrypt_peer_info (const struct DecryptSession *ds,
394 const struct GNUNET_PeerIdentity *peer)
397 for (i = 0; i < ds->share->num_peers; i++)
398 if (0 == memcmp (peer, &ds->info[i].peer, sizeof (struct GNUNET_PeerIdentity)))
405 * Interpolate between two points in time.
407 * @param start start time
408 * @param end end time
409 * @param num numerator of the scale factor
410 * @param denum denumerator of the scale factor
412 static struct GNUNET_TIME_Absolute
413 time_between (struct GNUNET_TIME_Absolute start,
414 struct GNUNET_TIME_Absolute end,
417 struct GNUNET_TIME_Absolute result;
420 GNUNET_assert (start.abs_value_us <= end.abs_value_us);
421 diff = end.abs_value_us - start.abs_value_us;
422 result.abs_value_us = start.abs_value_us + ((diff * num) / denum);
429 * Compare two peer identities. Indended to be used with qsort or bsearch.
431 * @param p1 some peer identity
432 * @param p2 some peer identity
433 * @return 1 if p1 > p2, -1 if p1 < p2 and 0 if p1 == p2.
436 peer_id_cmp (const void *p1, const void *p2)
438 return memcmp (p1, p2, sizeof (struct GNUNET_PeerIdentity));
443 * Get the index of a peer in an array of peers
445 * @param haystack array of peers
446 * @param n size of @a haystack
447 * @param needle peer to find
448 * @return index of @a needle in @a haystack, or -1 if peer
449 * is not in the list.
452 peer_find (const struct GNUNET_PeerIdentity *haystack, unsigned int n,
453 const struct GNUNET_PeerIdentity *needle)
456 for (i = 0; i < n; i++)
457 if (0 == memcmp (&haystack[i], needle, sizeof (struct GNUNET_PeerIdentity)))
464 * Normalize the given list of peers, by including the local peer
465 * (if it is missing) and sorting the peers by their identity.
467 * @param listed peers in the unnormalized list
468 * @param num_listed peers in the un-normalized list
469 * @param[out] num_normalized number of peers in the normalized list
470 * @param[out] my_peer_idx index of the local peer in the normalized list
471 * @return normalized list, must be free'd by the caller
473 static struct GNUNET_PeerIdentity *
474 normalize_peers (struct GNUNET_PeerIdentity *listed,
475 unsigned int num_listed,
476 unsigned int *num_normalized,
477 unsigned int *my_peer_idx)
479 unsigned int local_peer_in_list;
481 struct GNUNET_PeerIdentity *normalized;
483 local_peer_in_list = GNUNET_YES;
485 if (peer_find (listed, num_listed, &my_peer) < 0)
487 local_peer_in_list = GNUNET_NO;
491 normalized = GNUNET_new_array (n, struct GNUNET_PeerIdentity);
493 if (GNUNET_NO == local_peer_in_list)
494 normalized[n - 1] = my_peer;
496 memcpy (normalized, listed, num_listed * sizeof (struct GNUNET_PeerIdentity));
497 qsort (normalized, n, sizeof (struct GNUNET_PeerIdentity), &peer_id_cmp);
499 if (NULL != my_peer_idx)
500 *my_peer_idx = peer_find (normalized, n, &my_peer);
501 if (NULL != num_normalized)
509 * Get a the j-th lagrage coefficient for a set of indices.
511 * @param[out] coeff the lagrange coefficient
512 * @param j lagrage coefficient we want to compute
513 * @param indices indices
514 * @param num number of indices in @a indices
517 compute_lagrange_coefficient (gcry_mpi_t coeff, unsigned int j,
518 unsigned int *indices,
526 /* temp value for l-j */
529 GNUNET_assert (0 != coeff);
531 GNUNET_assert (0 != (n = gcry_mpi_new (0)));
532 GNUNET_assert (0 != (d = gcry_mpi_new (0)));
533 GNUNET_assert (0 != (tmp = gcry_mpi_new (0)));
535 gcry_mpi_set_ui (n, 1);
536 gcry_mpi_set_ui (d, 1);
538 gcry_mpi_set_ui (coeff, 0);
539 for (i = 0; i < num; i++)
544 gcry_mpi_mul_ui (n, n, l);
546 gcry_mpi_set_ui (tmp, l);
547 gcry_mpi_sub_ui (tmp, tmp, j);
548 gcry_mpi_mul (d, d, tmp);
551 // now we do the actual division, with everything mod q, as we
552 // are not operating on elemets from <g>, but on exponents
553 GNUNET_assert (0 == gcry_mpi_invm (d, d, elgamal_q));
554 gcry_mpi_mulm (coeff, n, d, elgamal_q);
556 gcry_mpi_release (n);
557 gcry_mpi_release (d);
558 gcry_mpi_release (tmp);
563 * Create a key pair for the paillier crypto system.
565 * Uses the simplified key generation of Jonathan Katz, Yehuda Lindell,
566 * "Introduction to Modern Cryptography: Principles and Protocols".
568 * @param n n-component of public key
569 * @param lambda lambda-component of private key
570 * @param mu mu-componenent of private key
573 paillier_create (gcry_mpi_t n, gcry_mpi_t lambda, gcry_mpi_t mu)
580 GNUNET_assert (0 != (phi = gcry_mpi_new (PAILLIER_BITS)));
581 GNUNET_assert (0 != (tmp = gcry_mpi_new (PAILLIER_BITS)));
583 // generate rsa modulus
584 GNUNET_assert (0 == gcry_prime_generate (&p, PAILLIER_BITS / 2, 0, NULL, NULL, NULL,
585 GCRY_WEAK_RANDOM, 0));
586 GNUNET_assert (0 == gcry_prime_generate (&q, PAILLIER_BITS / 2, 0, NULL, NULL, NULL,
587 GCRY_WEAK_RANDOM, 0));
588 gcry_mpi_mul (n, p, q);
589 // compute phi(n) = (p-1)(q-1)
590 gcry_mpi_sub_ui (phi, p, 1);
591 gcry_mpi_sub_ui (tmp, q, 1);
592 gcry_mpi_mul (phi, phi, tmp);
593 gcry_mpi_set (lambda, phi);
595 GNUNET_assert (0 != gcry_mpi_invm (mu, phi, n));
597 gcry_mpi_release (p);
598 gcry_mpi_release (q);
599 gcry_mpi_release (phi);
600 gcry_mpi_release (tmp);
605 * Encrypt a value using Paillier's scheme.
607 * @param c resulting ciphertext
608 * @param m plaintext to encrypt
609 * @param n n-component of public key
612 paillier_encrypt (gcry_mpi_t c, gcry_mpi_t m, gcry_mpi_t n)
618 GNUNET_assert (0 != (n_square = gcry_mpi_new (0)));
619 GNUNET_assert (0 != (r = gcry_mpi_new (0)));
620 GNUNET_assert (0 != (g = gcry_mpi_new (0)));
622 gcry_mpi_add_ui (g, n, 1);
624 gcry_mpi_mul (n_square, n, n);
629 gcry_mpi_randomize (r, PAILLIER_BITS, GCRY_WEAK_RANDOM);
631 while (gcry_mpi_cmp (r, n) > 0);
633 gcry_mpi_powm (c, g, m, n_square);
634 gcry_mpi_powm (r, r, n, n_square);
635 gcry_mpi_mulm (c, r, c, n_square);
637 gcry_mpi_release (n_square);
638 gcry_mpi_release (r);
643 * Decrypt a ciphertext using Paillier's scheme.
645 * @param[out] m resulting plaintext
646 * @param c ciphertext to decrypt
647 * @param lambda lambda-component of private key
648 * @param mu mu-component of private key
649 * @param n n-component of public key
652 paillier_decrypt (gcry_mpi_t m, gcry_mpi_t c, gcry_mpi_t mu, gcry_mpi_t lambda, gcry_mpi_t n)
655 GNUNET_assert (0 != (n_square = gcry_mpi_new (0)));
656 gcry_mpi_mul (n_square, n, n);
657 gcry_mpi_powm (m, c, lambda, n_square);
658 gcry_mpi_sub_ui (m, m, 1);
660 gcry_mpi_div (m, NULL, m, n, 0);
661 gcry_mpi_mulm (m, m, mu, n);
662 gcry_mpi_release (n_square);
667 * Task run during shutdown.
673 cleanup_task (void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc)
675 /* FIXME: do clean up here */
680 * Generate the random coefficients of our pre-secret polynomial
682 * @param ks the session
685 generate_presecret_polynomial (struct KeygenSession *ks)
688 GNUNET_assert (NULL == ks->presecret_polynomial);
689 ks->presecret_polynomial = GNUNET_malloc (ks->threshold * sizeof (gcry_mpi_t));
690 for (i = 0; i < ks->threshold; i++)
692 ks->presecret_polynomial[i] = gcry_mpi_new (GNUNET_SECRETSHARING_KEY_BITS);
693 GNUNET_assert (0 != ks->presecret_polynomial[i]);
694 gcry_mpi_randomize (ks->presecret_polynomial[i], GNUNET_SECRETSHARING_KEY_BITS,
701 * Consensus element handler for round one.
703 * @param cls closure (keygen session)
704 * @param element the element from consensus
707 keygen_round1_new_element (void *cls,
708 const struct GNUNET_SET_Element *element)
710 const struct GNUNET_SECRETSHARING_KeygenCommitData *d;
711 struct KeygenSession *ks = cls;
712 struct KeygenPeerInfo *info;
716 GNUNET_log (GNUNET_ERROR_TYPE_WARNING, "round1 consensus failed\n");
720 if (element->size != sizeof (struct GNUNET_SECRETSHARING_KeygenCommitData))
722 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
723 "keygen commit data with wrong size (%u) in consensus, "
725 element->size, sizeof (struct GNUNET_SECRETSHARING_KeygenCommitData));
729 GNUNET_log (GNUNET_ERROR_TYPE_INFO, "got round1 element\n");
733 info = get_keygen_peer_info (ks, &d->peer);
737 GNUNET_log (GNUNET_ERROR_TYPE_WARNING, "keygen commit data with wrong peer identity (%s) in consensus\n",
738 GNUNET_i2s (&d->peer));
742 if (d->purpose.size !=
743 htonl (element->size - offsetof (struct GNUNET_SECRETSHARING_KeygenCommitData, purpose)))
745 GNUNET_log (GNUNET_ERROR_TYPE_WARNING, "keygen commit data with wrong signature purpose size in consensus\n");
749 if (GNUNET_OK != GNUNET_CRYPTO_eddsa_verify (GNUNET_SIGNATURE_PURPOSE_SECRETSHARING_DKG1,
750 &d->purpose, &d->signature, &d->peer.public_key))
752 GNUNET_log (GNUNET_ERROR_TYPE_WARNING, "keygen commit data with invalid signature in consensus\n");
756 GNUNET_assert (0 == gcry_mpi_scan (&info->paillier_n, GCRYMPI_FMT_USG,
757 &d->pubkey.n, sizeof d->pubkey.n, NULL));
758 GNUNET_assert (0 == gcry_mpi_scan (&info->presecret_commitment, GCRYMPI_FMT_USG,
759 &d->commitment, sizeof d->commitment, NULL));
760 info->round1_valid = GNUNET_YES;
765 * Evaluate the polynomial with coefficients @a coeff at @a x.
766 * The i-th element in @a coeff corresponds to the coefficient of x^i.
768 * @param[out] z result of the evaluation
769 * @param coeff array of coefficients
770 * @param num_coeff number of coefficients
771 * @param x where to evaluate the polynomial
772 * @param m what group are we operating in?
775 horner_eval (gcry_mpi_t z, gcry_mpi_t *coeff, unsigned int num_coeff, gcry_mpi_t x, gcry_mpi_t m)
779 gcry_mpi_set_ui (z, 0);
780 for (i = 0; i < num_coeff; i++)
783 gcry_mpi_mul (z, z, x);
784 gcry_mpi_addm (z, z, coeff[num_coeff - i - 1], m);
790 keygen_round2_conclude (void *cls)
792 struct KeygenSession *ks = cls;
793 struct GNUNET_SECRETSHARING_SecretReadyMessage *m;
794 struct GNUNET_MQ_Envelope *ev;
798 struct GNUNET_SECRETSHARING_Share *share;
802 GNUNET_log (GNUNET_ERROR_TYPE_INFO, "round2 conclude\n");
804 GNUNET_assert (0 != (s = gcry_mpi_new (GNUNET_SECRETSHARING_KEY_BITS)));
805 GNUNET_assert (0 != (h = gcry_mpi_new (GNUNET_SECRETSHARING_KEY_BITS)));
807 // multiplicative identity
808 gcry_mpi_set_ui (s, 1);
810 share = GNUNET_new (struct GNUNET_SECRETSHARING_Share);
812 share->num_peers = 0;
814 for (i = 0; i < ks->num_peers; i++)
815 if (GNUNET_YES == ks->info[i].round2_valid)
818 share->peers = GNUNET_new_array (share->num_peers, struct GNUNET_PeerIdentity);
819 share->hom_share_commitments =
820 GNUNET_new_array (share->num_peers, struct GNUNET_SECRETSHARING_FieldElement);
821 share->original_indices = GNUNET_new_array (share->num_peers, uint16_t);
824 for (i = 0; i < ks->num_peers; i++)
826 if (GNUNET_YES == ks->info[i].round2_valid)
828 gcry_mpi_addm (s, s, ks->info[i].decrypted_preshare, elgamal_p);
829 gcry_mpi_mulm (h, h, ks->info[i].public_key_share, elgamal_p);
830 share->peers[i] = ks->info[i].peer;
831 share->original_indices[i] = j++;
835 print_mpi_fixed (&share->my_share, s, GNUNET_SECRETSHARING_KEY_BITS / 8);
836 print_mpi_fixed (&share->public_key, h, GNUNET_SECRETSHARING_KEY_BITS / 8);
838 GNUNET_log (GNUNET_ERROR_TYPE_INFO, "keygen successful with %u peers\n", share->num_peers);
840 m = GNUNET_malloc (sizeof (struct GNUNET_SECRETSHARING_SecretReadyMessage) +
841 ks->num_peers * sizeof (struct GNUNET_PeerIdentity));
843 GNUNET_assert (GNUNET_OK == GNUNET_SECRETSHARING_share_write (share, NULL, 0, &share_size));
845 ev = GNUNET_MQ_msg_extra (m, share_size,
846 GNUNET_MESSAGE_TYPE_SECRETSHARING_CLIENT_SECRET_READY);
848 GNUNET_assert (GNUNET_OK == GNUNET_SECRETSHARING_share_write (share, &m[1], share_size, NULL));
850 GNUNET_MQ_send (ks->client_mq, ev);
855 * Insert round 2 element in the consensus, consisting of
856 * (1) The exponentiated pre-share polynomial coefficients A_{i,l}=g^{a_{i,l}}
857 * (2) The exponentiated pre-shares y_{i,j}=g^{s_{i,j}}
858 * (3) The encrypted pre-shares Y_{i,j}
859 * (4) The zero knowledge proof for correctness of
862 * @param ks session to use
865 insert_round2_element (struct KeygenSession *ks)
867 struct GNUNET_SET_Element *element;
868 struct GNUNET_SECRETSHARING_KeygenRevealData *d;
870 unsigned char *last_pos;
876 GNUNET_assert (0 != (v = gcry_mpi_new (GNUNET_SECRETSHARING_KEY_BITS)));
877 GNUNET_assert (0 != (idx = gcry_mpi_new (GNUNET_SECRETSHARING_KEY_BITS)));
879 element_size = (sizeof (struct GNUNET_SECRETSHARING_KeygenRevealData) +
880 2 * GNUNET_SECRETSHARING_KEY_BITS / 8 * ks->num_peers +
881 1 * GNUNET_SECRETSHARING_KEY_BITS / 8 * ks->threshold);
883 element = GNUNET_malloc (sizeof (struct GNUNET_SET_Element) + element_size);
884 element->size = element_size;
885 element->data = (void *) &element[1];
887 d = (void *) element->data;
890 pos = (void *) &d[1];
891 last_pos = pos + element_size;
893 // exponentiated pre-shares
894 for (i = 0; i < ks->num_peers; i++)
896 ptrdiff_t remaining = last_pos - pos;
897 GNUNET_assert (remaining > 0);
898 gcry_mpi_set_ui (idx, i);
899 // evaluate the polynomial
900 horner_eval (v, ks->presecret_polynomial, ks->threshold, idx, elgamal_p);
901 // take g to the result
902 gcry_mpi_powm (v, elgamal_g, v, elgamal_p);
903 print_mpi_fixed (pos, v, GNUNET_SECRETSHARING_KEY_BITS / 8);
904 pos += GNUNET_SECRETSHARING_KEY_BITS / 8;
907 // encrypted pre-shares
908 for (i = 0; i < ks->num_peers; i++)
910 ptrdiff_t remaining = last_pos - pos;
911 GNUNET_assert (remaining > 0);
912 if (GNUNET_NO == ks->info[i].round1_valid)
913 gcry_mpi_set_ui (v, 0);
915 paillier_encrypt (v, ks->presecret_polynomial[0], ks->info[i].paillier_n);
916 print_mpi_fixed (pos, v, GNUNET_SECRETSHARING_KEY_BITS / 8);
917 pos += GNUNET_SECRETSHARING_KEY_BITS / 8;
920 // exponentiated coefficients
921 for (i = 0; i < ks->threshold; i++)
923 ptrdiff_t remaining = last_pos - pos;
924 GNUNET_assert (remaining > 0);
925 gcry_mpi_powm (v, elgamal_g, ks->presecret_polynomial[i], elgamal_p);
926 print_mpi_fixed (pos, v, GNUNET_SECRETSHARING_KEY_BITS / 8);
927 pos += GNUNET_SECRETSHARING_KEY_BITS / 8;
930 d->purpose.size = htonl (element_size - offsetof (struct GNUNET_SECRETSHARING_KeygenRevealData, purpose));
931 d->purpose.purpose = htonl (GNUNET_SIGNATURE_PURPOSE_SECRETSHARING_DKG2);
932 GNUNET_CRYPTO_eddsa_sign (my_peer_private_key, &d->purpose, &d->signature);
934 GNUNET_CONSENSUS_insert (ks->consensus, element, NULL, NULL);
935 GNUNET_free (element); /* FIXME: maybe stack-allocate instead? */
937 gcry_mpi_release (v);
938 gcry_mpi_release (idx);
943 keygen_round2_new_element (void *cls,
944 const struct GNUNET_SET_Element *element)
946 struct KeygenSession *ks = cls;
947 const struct GNUNET_SECRETSHARING_KeygenRevealData *d;
948 struct KeygenPeerInfo *info;
951 size_t expected_element_size;
955 GNUNET_log (GNUNET_ERROR_TYPE_WARNING, "round2 consensus failed\n");
959 expected_element_size = (sizeof (struct GNUNET_SECRETSHARING_KeygenRevealData) +
960 2 * GNUNET_SECRETSHARING_KEY_BITS / 8 * ks->num_peers +
961 1 * GNUNET_SECRETSHARING_KEY_BITS / 8 * ks->threshold);
963 if (element->size != expected_element_size)
965 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
966 "keygen round2 data with wrong size (%u) in consensus, "
968 element->size, expected_element_size);
972 d = (const void *) element->data;
974 info = get_keygen_peer_info (ks, &d->peer);
978 GNUNET_log (GNUNET_ERROR_TYPE_WARNING, "keygen commit data with wrong peer identity (%s) in consensus\n",
979 GNUNET_i2s (&d->peer));
983 if (GNUNET_NO == info->round1_valid)
985 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
986 "ignoring round2 element from peer with invalid round1 element (%s)\n",
987 GNUNET_i2s (&d->peer));
991 if (GNUNET_YES == info->round2_valid)
993 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
994 "ignoring duplicate round2 element (%s)\n",
995 GNUNET_i2s (&d->peer));
999 GNUNET_log (GNUNET_ERROR_TYPE_INFO, "got round2 element\n");
1002 pos = (void *) &d[1];
1003 // skip exponentiated pre-shares
1004 pos += GNUNET_SECRETSHARING_KEY_BITS / 8 * ks->num_peers;
1005 // skip encrypted pre-shares
1006 pos += PAILLIER_BITS / 8 * ks->num_peers;
1007 // the first exponentiated coefficient is the public key share
1008 GNUNET_assert (0 == gcry_mpi_scan (&info->public_key_share, GCRYMPI_FMT_USG,
1009 pos, GNUNET_SECRETSHARING_KEY_BITS / 8, NULL));
1011 pos = (void *) &d[1];
1012 // skip exp. pre-shares
1013 pos += GNUNET_SECRETSHARING_KEY_BITS / 8 * ks->num_peers;
1014 // skip to the encrypted value for our peer
1015 pos += PAILLIER_BITS / 8 * ks->local_peer_idx;
1017 GNUNET_assert (0 == gcry_mpi_scan (&c, GCRYMPI_FMT_USG,
1018 pos, PAILLIER_BITS / 8, NULL));
1020 GNUNET_assert (0 != (info->decrypted_preshare = mpi_new (0)));
1022 paillier_decrypt (info->decrypted_preshare, c, ks->paillier_lambda, ks->paillier_mu,
1023 ks->info[ks->local_peer_idx].paillier_n);
1025 // TODO: validate zero knowledge proofs
1027 if (d->purpose.size !=
1028 htons (element->size - offsetof (struct GNUNET_SECRETSHARING_KeygenRevealData, purpose)))
1030 GNUNET_log (GNUNET_ERROR_TYPE_WARNING, "keygen reveal data with wrong signature purpose size in consensus\n");
1034 if (GNUNET_OK != GNUNET_CRYPTO_eddsa_verify (GNUNET_SIGNATURE_PURPOSE_SECRETSHARING_DKG2,
1035 &d->purpose, &d->signature, &d->peer.public_key))
1037 GNUNET_log (GNUNET_ERROR_TYPE_WARNING, "keygen reveal data with invalid signature in consensus\n");
1041 info->round2_valid = GNUNET_YES;
1046 * Called when the first consensus round has concluded.
1047 * Will initiate the second round.
1049 * @param cls closure
1052 keygen_round1_conclude (void *cls)
1054 struct KeygenSession *ks = cls;
1056 GNUNET_CONSENSUS_destroy (ks->consensus);
1058 ks->consensus = GNUNET_CONSENSUS_create (cfg, ks->num_peers, ks->peers, &ks->session_id,
1059 keygen_round2_new_element, ks);
1061 insert_round2_element (ks);
1063 GNUNET_CONSENSUS_conclude (ks->consensus,
1064 /* last round, thus conclude at DKG deadline */
1066 keygen_round2_conclude,
1072 * Insert the ephemeral key and the presecret commitment
1073 * of this peer in the consensus of the given session.
1075 * @param ks session to use
1078 insert_round1_element (struct KeygenSession *ks)
1080 struct GNUNET_SET_Element *element;
1081 struct GNUNET_SECRETSHARING_KeygenCommitData *d;
1084 // big-endian representation of 'v'
1085 unsigned char v_data[GNUNET_SECRETSHARING_KEY_BITS / 8];
1087 element = GNUNET_malloc (sizeof *element + sizeof *d);
1088 d = (void *) &element[1];
1090 element->size = sizeof *d;
1092 GNUNET_log (GNUNET_ERROR_TYPE_INFO, "alloc'd size %u\n", sizeof *element + sizeof *d);
1093 GNUNET_log (GNUNET_ERROR_TYPE_INFO, "element size %u\n", element->size);
1098 GNUNET_assert (0 != (v = gcry_mpi_new (GNUNET_SECRETSHARING_KEY_BITS)));
1100 gcry_mpi_powm (v, elgamal_g, ks->presecret_polynomial[0], elgamal_p);
1102 print_mpi_fixed (v_data, v, GNUNET_SECRETSHARING_KEY_BITS);
1104 GNUNET_CRYPTO_hash (v_data, GNUNET_SECRETSHARING_KEY_BITS / 8, &d->commitment);
1106 print_mpi_fixed (d->pubkey.n, ks->info[ks->local_peer_idx].paillier_n,
1109 d->purpose.size = htonl ((sizeof *d) - offsetof (struct GNUNET_SECRETSHARING_KeygenCommitData, purpose));
1110 d->purpose.purpose = htonl (GNUNET_SIGNATURE_PURPOSE_SECRETSHARING_DKG1);
1111 GNUNET_assert (GNUNET_OK == GNUNET_CRYPTO_eddsa_sign (my_peer_private_key, &d->purpose, &d->signature));
1113 GNUNET_CONSENSUS_insert (ks->consensus, element, NULL, NULL);
1115 gcry_mpi_release (v);
1116 GNUNET_free (element);
1121 * Functions with this signature are called whenever a message is
1124 * @param cls closure
1125 * @param client identification of the client
1126 * @param message the actual message
1128 static void handle_client_keygen (void *cls,
1129 struct GNUNET_SERVER_Client *client,
1130 const struct GNUNET_MessageHeader
1133 const struct GNUNET_SECRETSHARING_CreateMessage *msg =
1134 (const struct GNUNET_SECRETSHARING_CreateMessage *) message;
1135 struct KeygenSession *ks;
1138 GNUNET_log (GNUNET_ERROR_TYPE_INFO, "client requested key generation\n");
1140 ks = GNUNET_new (struct KeygenSession);
1142 /* FIXME: check if client already has some session */
1144 GNUNET_CONTAINER_DLL_insert (keygen_sessions_head, keygen_sessions_tail, ks);
1146 ks->client = client;
1147 ks->client_mq = GNUNET_MQ_queue_for_server_client (client);
1149 ks->deadline = GNUNET_TIME_absolute_ntoh (msg->deadline);
1150 ks->threshold = ntohs (msg->threshold);
1151 ks->num_peers = ntohs (msg->num_peers);
1153 ks->peers = normalize_peers ((struct GNUNET_PeerIdentity *) &msg[1], ks->num_peers,
1154 &ks->num_peers, &ks->local_peer_idx);
1157 GNUNET_log (GNUNET_ERROR_TYPE_INFO, "first round of consensus with %u peers\n", ks->num_peers);
1158 ks->consensus = GNUNET_CONSENSUS_create (cfg, ks->num_peers, ks->peers, &msg->session_id,
1159 keygen_round1_new_element, ks);
1161 ks->info = GNUNET_malloc (ks->num_peers * sizeof (struct KeygenPeerInfo));
1163 for (i = 0; i < ks->num_peers; i++)
1164 ks->info[i].peer = ks->peers[i];
1166 GNUNET_assert (0 != (ks->info[ks->local_peer_idx].paillier_n = mpi_new (0)));
1167 GNUNET_assert (0 != (ks->paillier_lambda = mpi_new (0)));
1168 GNUNET_assert (0 != (ks->paillier_mu = mpi_new (0)));
1170 paillier_create (ks->info[ks->local_peer_idx].paillier_n,
1171 ks->paillier_lambda,
1175 generate_presecret_polynomial (ks);
1177 insert_round1_element (ks);
1179 GNUNET_log (GNUNET_ERROR_TYPE_INFO, "starting conclude of round 1\n");
1181 GNUNET_CONSENSUS_conclude (ks->consensus,
1182 /* half the overall time */
1183 time_between (ks->start_time, ks->deadline, 1, 2),
1184 keygen_round1_conclude,
1187 GNUNET_SERVER_receive_done (client, GNUNET_OK);
1192 * Called when the partial decryption consensus concludes.
1195 decrypt_conclude (void *cls)
1197 struct DecryptSession *ds = cls;
1198 struct GNUNET_SECRETSHARING_DecryptResponseMessage *msg;
1199 struct GNUNET_MQ_Envelope *ev;
1200 gcry_mpi_t lagrange;
1204 unsigned int *indices;
1209 GNUNET_assert (0 != (lagrange = gcry_mpi_new (0)));
1210 GNUNET_assert (0 != (m = gcry_mpi_new (0)));
1211 GNUNET_assert (0 != (tmp = gcry_mpi_new (0)));
1214 for (i = 0; i < ds->share->num_peers; i++)
1215 if (NULL != ds->info[i].partial_decryption)
1218 indices = GNUNET_malloc (num * sizeof (unsigned int));
1220 for (i = 0; i < ds->share->num_peers; i++)
1221 if (NULL != ds->info[i].partial_decryption)
1222 indices[j++] = ds->info[i].real_index;
1224 gcry_mpi_set_ui (m, 1);
1226 for (i = 0; i < num; i++)
1228 compute_lagrange_coefficient (lagrange, indices[i], indices, num);
1230 gcry_mpi_powm (tmp, ds->info[indices[i]].partial_decryption, lagrange, elgamal_p);
1231 gcry_mpi_mulm (m, m, tmp, elgamal_p);
1234 GNUNET_assert (0 == gcry_mpi_scan (&c_2, GCRYMPI_FMT_USG, ds->ciphertext.c2_bits,
1235 GNUNET_SECRETSHARING_KEY_BITS / 8, NULL));
1238 gcry_mpi_invm (m, m, elgamal_p);
1239 gcry_mpi_mulm (m, c_2, m, elgamal_p);
1241 ev = GNUNET_MQ_msg (msg, GNUNET_MESSAGE_TYPE_SECRETSHARING_CLIENT_DECRYPT_DONE);
1242 print_mpi_fixed (&msg->plaintext, m, GNUNET_SECRETSHARING_KEY_BITS / 8);
1243 msg->success = htonl (1);
1244 GNUNET_MQ_send (ds->client_mq, ev);
1246 // FIXME: what if not enough peers participated?
1251 * Called when a new partial decryption arrives.
1254 decrypt_new_element (void *cls,
1255 const struct GNUNET_SET_Element *element)
1257 struct DecryptSession *session = cls;
1258 const struct GNUNET_SECRETSHARING_DecryptData *d;
1259 struct DecryptPeerInfo *info;
1261 if (NULL == element)
1263 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "decryption failed\n");
1264 /* FIXME: destroy */
1268 if (element->size != sizeof *d)
1270 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "element of wrong size in decrypt consensus\n");
1276 info = get_decrypt_peer_info (session, &d->peer);
1280 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "decrypt element from invalid peer (%s)\n",
1281 GNUNET_i2s (&d->peer));
1285 if (NULL != info->partial_decryption)
1287 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "decrypt element duplicate\n",
1288 GNUNET_i2s (&d->peer));
1292 // FIXME: check NIZP first
1294 GNUNET_assert (0 == gcry_mpi_scan (&info->partial_decryption,
1295 GCRYMPI_FMT_USG, &d->partial_decryption, GNUNET_SECRETSHARING_KEY_BITS / 8, NULL));
1299 insert_decrypt_element (struct DecryptSession *ds)
1301 struct GNUNET_SECRETSHARING_DecryptData d;
1302 struct GNUNET_SET_Element element;
1306 GNUNET_assert (0 == gcry_mpi_scan (&x, GCRYMPI_FMT_USG, ds->ciphertext.c1_bits, GNUNET_SECRETSHARING_KEY_BITS / 8, NULL));
1307 GNUNET_assert (0 == gcry_mpi_scan (&s, GCRYMPI_FMT_USG, &ds->share->my_share, GNUNET_SECRETSHARING_KEY_BITS / 8, NULL));
1309 gcry_mpi_powm (x, x, s, elgamal_p);
1311 element.data = (void *) &d;
1312 element.size = sizeof (struct GNUNET_SECRETSHARING_DecryptData);
1315 d.purpose.size = htonl (element.size - offsetof (struct GNUNET_SECRETSHARING_KeygenRevealData, purpose));
1316 d.purpose.purpose = htonl (GNUNET_SIGNATURE_PURPOSE_SECRETSHARING_DECRYPTION);
1317 GNUNET_CRYPTO_eddsa_sign (my_peer_private_key, &d.purpose, &d.signature);
1319 print_mpi_fixed (&d.partial_decryption, x, GNUNET_SECRETSHARING_KEY_BITS / 8);
1321 GNUNET_CONSENSUS_insert (ds->consensus, &element, NULL, NULL);
1326 * Functions with this signature are called whenever a message is
1329 * @param cls closure
1330 * @param client identification of the client
1331 * @param message the actual message
1333 static void handle_client_decrypt (void *cls,
1334 struct GNUNET_SERVER_Client *client,
1335 const struct GNUNET_MessageHeader
1338 const struct GNUNET_SECRETSHARING_DecryptRequestMessage *msg =
1339 (const void *) message;
1340 struct DecryptSession *ds;
1341 struct GNUNET_HashCode session_id;
1343 ds = GNUNET_new (struct DecryptSession);
1344 // FIXME: check if session already exists
1345 GNUNET_CONTAINER_DLL_insert (decrypt_sessions_head, decrypt_sessions_tail, ds);
1346 ds->client = client;
1347 ds->client_mq = GNUNET_MQ_queue_for_server_client (client);
1348 ds->deadline = GNUNET_TIME_absolute_ntoh (msg->deadline);
1349 ds->ciphertext = msg->ciphertext;
1351 ds->share = GNUNET_SECRETSHARING_share_read (&msg[1], ntohs (msg->header.size) - sizeof *msg, NULL);
1352 // FIXME: probably should be break rather than assert
1353 GNUNET_assert (NULL != ds->share);
1355 // FIXME: this is probably sufficient, but kdf/hash with all values would be nicer ...
1356 GNUNET_CRYPTO_hash (&msg->ciphertext, sizeof (struct GNUNET_SECRETSHARING_Ciphertext), &session_id);
1358 ds->consensus = GNUNET_CONSENSUS_create (cfg,
1359 ds->share->num_peers,
1362 decrypt_new_element,
1365 insert_decrypt_element (ds);
1367 GNUNET_CONSENSUS_conclude (ds->consensus, ds->deadline, decrypt_conclude, ds);
1372 init_crypto_constants (void)
1374 /* 1024-bit safe prime */
1375 const char *elgamal_p_hex =
1376 "0x08a347d3d69e8b2dd7d1b12a08dfbccbebf4ca"
1377 "6f4269a0814e158a34312964d946b3ef22882317"
1378 "2bcf30fc08f772774cb404f9bc002a6f66b09a79"
1379 "d810d67c4f8cb3bedc6060e3c8ef874b1b64df71"
1380 "6c7d2b002da880e269438d5a776e6b5f253c8df5"
1381 "6a16b1c7ce58def07c03db48238aadfc52a354a2"
1382 "7ed285b0c1675cad3f3";
1383 /* 1023-bit Sophie Germain prime, q = (p-1)/2 */
1384 const char *elgamal_q_hex =
1385 "0x0451a3e9eb4f4596ebe8d895046fde65f5fa65"
1386 "37a134d040a70ac51a1894b26ca359f79144118b"
1387 "95e7987e047bb93ba65a027cde001537b3584d3c"
1388 "ec086b3e27c659df6e303071e477c3a58db26fb8"
1389 "b63e958016d4407134a1c6ad3bb735af929e46fa"
1390 "b50b58e3e72c6f783e01eda411c556fe2951aa51"
1391 "3f6942d860b3ae569f9";
1392 /* generator of the unique size q subgroup of Z_p^* */
1393 const char *elgamal_g_hex =
1394 "0x05c00c36d2e822950087ef09d8252994adc4e4"
1395 "8fe3ec70269f035b46063aff0c99b633fd64df43"
1396 "02442e1914c829a41505a275438871f365e91c12"
1397 "3d5303ef9e90f4b8cb89bf86cc9b513e74a72634"
1398 "9cfd9f953674fab5d511e1c078fc72d72b34086f"
1399 "c82b4b951989eb85325cb203ff98df76bc366bba"
1400 "1d7024c3650f60d0da";
1402 GNUNET_assert (0 == gcry_mpi_scan (&elgamal_q, GCRYMPI_FMT_HEX,
1403 elgamal_q_hex, 0, NULL));
1404 GNUNET_assert (0 == gcry_mpi_scan (&elgamal_p, GCRYMPI_FMT_HEX,
1405 elgamal_p_hex, 0, NULL));
1406 GNUNET_assert (0 == gcry_mpi_scan (&elgamal_g, GCRYMPI_FMT_HEX,
1407 elgamal_g_hex, 0, NULL));
1412 * Process template requests.
1414 * @param cls closure
1415 * @param server the initialized server
1416 * @param c configuration to use
1419 run (void *cls, struct GNUNET_SERVER_Handle *server,
1420 const struct GNUNET_CONFIGURATION_Handle *c)
1422 static const struct GNUNET_SERVER_MessageHandler handlers[] = {
1423 {handle_client_keygen, NULL, GNUNET_MESSAGE_TYPE_SECRETSHARING_CLIENT_GENERATE, 0},
1424 {handle_client_decrypt, NULL, GNUNET_MESSAGE_TYPE_SECRETSHARING_CLIENT_DECRYPT, 0},
1429 my_peer_private_key = GNUNET_CRYPTO_eddsa_key_create_from_configuration (c);
1430 if (NULL == my_peer_private_key)
1432 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "could not access host private key\n");
1434 GNUNET_SCHEDULER_shutdown ();
1437 init_crypto_constants ();
1438 if (GNUNET_OK != GNUNET_CRYPTO_get_peer_identity (cfg, &my_peer))
1440 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "could not retrieve host identity\n");
1442 GNUNET_SCHEDULER_shutdown ();
1445 GNUNET_SERVER_add_handlers (server, handlers);
1446 GNUNET_SCHEDULER_add_delayed (GNUNET_TIME_UNIT_FOREVER_REL, &cleanup_task,
1452 * The main function for the template service.
1454 * @param argc number of arguments from the command line
1455 * @param argv command line arguments
1456 * @return 0 ok, 1 on error
1459 main (int argc, char *const *argv)
1461 return (GNUNET_OK ==
1462 GNUNET_SERVICE_run (argc, argv, "secretsharing",
1463 GNUNET_SERVICE_OPTION_NONE, &run, NULL)) ? 0 : 1;