Merge branch 'master' of ssh://gnunet.org/gnunet
[oweals/gnunet.git] / src / revocation / revocation_api.c
1 /*
2       This file is part of GNUnet
3       Copyright (C) 2013, 2016 GNUnet e.V.
4
5       GNUnet is free software: you can redistribute it and/or modify it
6       under the terms of the GNU Affero General Public License as published
7       by the Free Software Foundation, either version 3 of the License,
8       or (at your option) any later version.
9
10       GNUnet is distributed in the hope that it will be useful, but
11       WITHOUT ANY WARRANTY; without even the implied warranty of
12       MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
13       Affero General Public License for more details.
14
15       You should have received a copy of the GNU Affero General Public License
16       along with this program.  If not, see <http://www.gnu.org/licenses/>.
17
18      SPDX-License-Identifier: AGPL3.0-or-later
19  */
20 /**
21  * @file revocation/revocation_api.c
22  * @brief API to perform and access key revocations
23  * @author Christian Grothoff
24  */
25 #include "platform.h"
26 #include "gnunet_revocation_service.h"
27 #include "gnunet_signatures.h"
28 #include "gnunet_protocols.h"
29 #include "revocation.h"
30 #include <inttypes.h>
31
32 /**
33  * Handle for the key revocation query.
34  */
35 struct GNUNET_REVOCATION_Query
36 {
37   /**
38    * Message queue to the service.
39    */
40   struct GNUNET_MQ_Handle *mq;
41
42   /**
43    * Function to call with the result.
44    */
45   GNUNET_REVOCATION_Callback func;
46
47   /**
48    * Closure for @e func.
49    */
50   void *func_cls;
51 };
52
53
54 /**
55  * Helper struct that holds a found pow nonce
56  * and the corresponding number of leading zeroes.
57  */
58 struct BestPow
59 {
60   /**
61    * PoW nonce
62    */
63   uint64_t pow;
64
65   /**
66    * Corresponding zero bits in hash
67    */
68   unsigned int bits;
69 };
70
71
72 /**
73  * The handle to a PoW calculation.
74  * Used in iterative PoW rounds.
75  */
76 struct GNUNET_REVOCATION_PowCalculationHandle
77 {
78   /**
79    * Current set of found PoWs
80    */
81   struct BestPow best[POW_COUNT];
82
83   /**
84    * The final PoW result data structure.
85    */
86   struct GNUNET_REVOCATION_PowP *pow;
87
88   /**
89    * The current nonce to try
90    */
91   uint64_t current_pow;
92
93   /**
94    * Epochs how long the PoW should be valid.
95    * This is added on top of the difficulty in the PoW.
96    */
97   unsigned int epochs;
98
99   /**
100    * The difficulty (leading zeros) to achieve.
101    */
102   unsigned int difficulty;
103
104 };
105
106 /**
107  * Generic error handler, called with the appropriate
108  * error code and the same closure specified at the creation of
109  * the message queue.
110  * Not every message queue implementation supports an error handler.
111  *
112  * @param cls closure with the `struct GNUNET_NSE_Handle *`
113  * @param error error code
114  */
115 static void
116 query_mq_error_handler (void *cls,
117                         enum GNUNET_MQ_Error error)
118 {
119   struct GNUNET_REVOCATION_Query *q = cls;
120
121   GNUNET_log (GNUNET_ERROR_TYPE_INFO,
122               "Revocation query MQ error\n");
123   q->func (q->func_cls,
124            GNUNET_SYSERR);
125   GNUNET_REVOCATION_query_cancel (q);
126 }
127
128
129 /**
130  * Handle response to our revocation query.
131  *
132  * @param cls our `struct GNUNET_REVOCATION_Query` handle
133  * @param qrm response we got
134  */
135 static void
136 handle_revocation_query_response (void *cls,
137                                   const struct QueryResponseMessage *qrm)
138 {
139   struct GNUNET_REVOCATION_Query *q = cls;
140
141   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
142               "Revocation query result: %d\n",
143               (uint32_t) ntohl (qrm->is_valid));
144   q->func (q->func_cls,
145            ntohl (qrm->is_valid));
146   GNUNET_REVOCATION_query_cancel (q);
147 }
148
149
150 /**
151  * Check if a key was revoked.
152  *
153  * @param cfg the configuration to use
154  * @param key key to check for revocation
155  * @param func funtion to call with the result of the check
156  * @param func_cls closure to pass to @a func
157  * @return handle to use in #GNUNET_REVOCATION_query_cancel to stop REVOCATION from invoking the callback
158  */
159 struct GNUNET_REVOCATION_Query *
160 GNUNET_REVOCATION_query (const struct GNUNET_CONFIGURATION_Handle *cfg,
161                          const struct GNUNET_CRYPTO_EcdsaPublicKey *key,
162                          GNUNET_REVOCATION_Callback func,
163                          void *func_cls)
164 {
165   struct GNUNET_REVOCATION_Query *q
166     = GNUNET_new (struct GNUNET_REVOCATION_Query);
167   struct GNUNET_MQ_MessageHandler handlers[] = {
168     GNUNET_MQ_hd_fixed_size (revocation_query_response,
169                              GNUNET_MESSAGE_TYPE_REVOCATION_QUERY_RESPONSE,
170                              struct QueryResponseMessage,
171                              q),
172     GNUNET_MQ_handler_end ()
173   };
174   struct QueryMessage *qm;
175   struct GNUNET_MQ_Envelope *env;
176
177   q->mq = GNUNET_CLIENT_connect (cfg,
178                                  "revocation",
179                                  handlers,
180                                  &query_mq_error_handler,
181                                  q);
182   if (NULL == q->mq)
183   {
184     GNUNET_free (q);
185     return NULL;
186   }
187   q->func = func;
188   q->func_cls = func_cls;
189   env = GNUNET_MQ_msg (qm,
190                        GNUNET_MESSAGE_TYPE_REVOCATION_QUERY);
191   qm->reserved = htonl (0);
192   qm->key = *key;
193   GNUNET_MQ_send (q->mq,
194                   env);
195   return q;
196 }
197
198
199 /**
200  * Cancel key revocation check.
201  *
202  * @param q query to cancel
203  */
204 void
205 GNUNET_REVOCATION_query_cancel (struct GNUNET_REVOCATION_Query *q)
206 {
207   if (NULL != q->mq)
208   {
209     GNUNET_MQ_destroy (q->mq);
210     q->mq = NULL;
211   }
212   GNUNET_free (q);
213 }
214
215
216 /**
217  * Handle for the key revocation operation.
218  */
219 struct GNUNET_REVOCATION_Handle
220 {
221   /**
222    * Message queue to the service.
223    */
224   struct GNUNET_MQ_Handle *mq;
225
226   /**
227    * Function to call once we are done.
228    */
229   GNUNET_REVOCATION_Callback func;
230
231   /**
232    * Closure for @e func.
233    */
234   void *func_cls;
235 };
236
237
238 /**
239  * Generic error handler, called with the appropriate
240  * error code and the same closure specified at the creation of
241  * the message queue.
242  * Not every message queue implementation supports an error handler.
243  *
244  * @param cls closure with the `struct GNUNET_NSE_Handle *`
245  * @param error error code
246  */
247 static void
248 revocation_mq_error_handler (void *cls,
249                              enum GNUNET_MQ_Error error)
250 {
251   struct GNUNET_REVOCATION_Handle *h = cls;
252
253   GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
254               "Revocation MQ error\n");
255   h->func (h->func_cls,
256            GNUNET_SYSERR);
257   GNUNET_REVOCATION_revoke_cancel (h);
258 }
259
260
261 /**
262  * Handle response to our revocation query.
263  *
264  * @param cls our `struct GNUNET_REVOCATION_Handle` handle
265  * @param rrm response we got
266  */
267 static void
268 handle_revocation_response (void *cls,
269                             const struct RevocationResponseMessage *rrm)
270 {
271   struct GNUNET_REVOCATION_Handle *h = cls;
272
273   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
274               "Revocation transmission result: %d\n",
275               (uint32_t) ntohl (rrm->is_valid));
276   h->func (h->func_cls,
277            ntohl (rrm->is_valid));
278   GNUNET_REVOCATION_revoke_cancel (h);
279 }
280
281
282 /**
283  * Perform key revocation.
284  *
285  * @param cfg the configuration to use
286  * @param key public key of the key to revoke
287  * @param sig signature to use on the revocation (should have been
288  *            created using #GNUNET_REVOCATION_sign_revocation).
289  * @param ts  revocation timestamp
290  * @param pow proof of work to use (should have been created by
291  *            iteratively calling #GNUNET_REVOCATION_check_pow)
292  * @param func funtion to call with the result of the check
293  *             (called with `is_valid` being #GNUNET_NO if
294  *              the revocation worked).
295  * @param func_cls closure to pass to @a func
296  * @return handle to use in #GNUNET_REVOCATION_revoke_cancel to stop REVOCATION from invoking the callback
297  */
298 struct GNUNET_REVOCATION_Handle *
299 GNUNET_REVOCATION_revoke (const struct GNUNET_CONFIGURATION_Handle *cfg,
300                           const struct GNUNET_REVOCATION_PowP *pow,
301                           GNUNET_REVOCATION_Callback func,
302                           void *func_cls)
303 {
304   struct GNUNET_REVOCATION_Handle *h
305     = GNUNET_new (struct GNUNET_REVOCATION_Handle);
306   struct GNUNET_MQ_MessageHandler handlers[] = {
307     GNUNET_MQ_hd_fixed_size (revocation_response,
308                              GNUNET_MESSAGE_TYPE_REVOCATION_REVOKE_RESPONSE,
309                              struct RevocationResponseMessage,
310                              h),
311     GNUNET_MQ_handler_end ()
312   };
313   unsigned long long matching_bits;
314   struct GNUNET_TIME_Relative epoch_duration;
315   struct RevokeMessage *rm;
316   struct GNUNET_MQ_Envelope *env;
317
318   if ((GNUNET_OK !=
319        GNUNET_CONFIGURATION_get_value_number (cfg,
320                                               "REVOCATION",
321                                               "WORKBITS",
322                                               &matching_bits)))
323   {
324     GNUNET_break (0);
325     GNUNET_free (h);
326     return NULL;
327   }
328   if ((GNUNET_OK !=
329        GNUNET_CONFIGURATION_get_value_time (cfg,
330                                             "REVOCATION",
331                                             "EPOCH_DURATION",
332                                             &epoch_duration)))
333   {
334     GNUNET_break (0);
335     GNUNET_free (h);
336     return NULL;
337   }
338   if (GNUNET_YES != GNUNET_REVOCATION_check_pow (pow,
339                                                  (unsigned int) matching_bits,
340                                                  epoch_duration))
341   {
342     GNUNET_break (0);
343     GNUNET_free (h);
344     return NULL;
345   }
346
347
348   h->mq = GNUNET_CLIENT_connect (cfg,
349                                  "revocation",
350                                  handlers,
351                                  &revocation_mq_error_handler,
352                                  h);
353   if (NULL == h->mq)
354   {
355     GNUNET_free (h);
356     return NULL;
357   }
358   h->func = func;
359   h->func_cls = func_cls;
360   env = GNUNET_MQ_msg (rm,
361                        GNUNET_MESSAGE_TYPE_REVOCATION_REVOKE);
362   rm->reserved = htonl (0);
363   rm->proof_of_work = *pow;
364   GNUNET_MQ_send (h->mq,
365                   env);
366   return h;
367 }
368
369
370 /**
371  * Cancel key revocation.
372  *
373  * @param h operation to cancel
374  */
375 void
376 GNUNET_REVOCATION_revoke_cancel (struct GNUNET_REVOCATION_Handle *h)
377 {
378   if (NULL != h->mq)
379   {
380     GNUNET_MQ_destroy (h->mq);
381     h->mq = NULL;
382   }
383   GNUNET_free (h);
384 }
385
386
387 /**
388  * Count the leading zeroes in hash.
389  *
390  * @param hash to count leading zeros in
391  * @return the number of leading zero bits.
392  */
393 static unsigned int
394 count_leading_zeroes (const struct GNUNET_HashCode *hash)
395 {
396   unsigned int hash_count;
397   hash_count = 0;
398   while ((0 == GNUNET_CRYPTO_hash_get_bit (hash, hash_count)))
399     hash_count++;
400   return hash_count;
401 }
402
403
404 /**
405  * Calculate the average zeros in the pows.
406  *
407  * @param ph the PowHandle
408  * @return the average number of zeroes.
409  */
410 static unsigned int
411 calculate_score (const struct GNUNET_REVOCATION_PowCalculationHandle *ph)
412 {
413   double sum = 0.0;
414   for (unsigned int j = 0; j<POW_COUNT; j++)
415     sum += ph->best[j].bits;
416   double avg = sum / POW_COUNT;
417   return avg;
418 }
419
420
421 /**
422  * Check if the given proof-of-work is valid.
423  *
424  * @param pow proof of work
425  * @param matching_bits how many bits must match (configuration)
426  * @param epoch_duration length of single epoch in configuration
427  * @return #GNUNET_YES if the @a pow is acceptable, #GNUNET_NO if not
428  */
429 enum GNUNET_GenericReturnValue
430 GNUNET_REVOCATION_check_pow (const struct GNUNET_REVOCATION_PowP *pow,
431                              unsigned int difficulty,
432                              struct GNUNET_TIME_Relative epoch_duration)
433 {
434   char buf[sizeof(struct GNUNET_CRYPTO_EcdsaPublicKey)
435            + sizeof (struct GNUNET_TIME_AbsoluteNBO)
436            + sizeof (uint64_t)] GNUNET_ALIGN;
437   struct GNUNET_REVOCATION_SignaturePurposePS spurp;
438   struct GNUNET_CRYPTO_HashAsciiEncoded h_str;
439   struct GNUNET_HashCode result;
440   struct GNUNET_TIME_Absolute ts;
441   struct GNUNET_TIME_Absolute exp;
442   struct GNUNET_TIME_Relative ttl;
443   struct GNUNET_TIME_Relative buffer;
444   unsigned int score = 0;
445   unsigned int tmp_score = 0;
446   unsigned int epochs;
447   uint64_t pow_val;
448
449   /**
450    * Check if signature valid
451    */
452   spurp.key = pow->key;
453   spurp.timestamp = pow->timestamp;
454   spurp.purpose.purpose = htonl (GNUNET_SIGNATURE_PURPOSE_REVOCATION);
455   spurp.purpose.size = htonl (sizeof(struct GNUNET_CRYPTO_EccSignaturePurpose)
456                               + sizeof(struct GNUNET_CRYPTO_EcdsaPublicKey)
457                               + sizeof (struct GNUNET_TIME_AbsoluteNBO));
458   if (GNUNET_OK !=
459       GNUNET_CRYPTO_ecdsa_verify_ (GNUNET_SIGNATURE_PURPOSE_REVOCATION,
460                                    &spurp.purpose,
461                                    &pow->signature,
462                                    &pow->key))
463   {
464     GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
465                 "Proof of work signature invalid!\n");
466     return GNUNET_NO;
467   }
468
469   /**
470    * First, check if PoW set is strictly monotically increasing
471    */
472   for (unsigned int i = 0; i < POW_COUNT-1; i++)
473   {
474     if (GNUNET_ntohll (pow->pow[i]) >= GNUNET_ntohll (pow->pow[i+1]))
475       return GNUNET_NO;
476   }
477   GNUNET_memcpy (&buf[sizeof(uint64_t)],
478                  &pow->timestamp,
479                  sizeof (uint64_t));
480   GNUNET_memcpy (&buf[sizeof(uint64_t) * 2],
481                  &pow->key,
482                  sizeof(struct GNUNET_CRYPTO_EcdsaPublicKey));
483   for (unsigned int i = 0; i < POW_COUNT; i++)
484   {
485     pow_val = GNUNET_ntohll (pow->pow[i]);
486     GNUNET_memcpy (buf, &pow->pow[i], sizeof(uint64_t));
487     GNUNET_CRYPTO_pow_hash ("gnunet-revocation-proof-of-work",
488                             buf,
489                             sizeof(buf),
490                             &result);
491     tmp_score = count_leading_zeroes (&result);
492     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
493                 "Score %u with %" PRIu64 " (#%u)\n",
494                 tmp_score, pow_val, i);
495     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
496                 "First byte: %x\n",
497                 ((char*)&result)[0] & 0xff);
498
499
500     GNUNET_CRYPTO_hash_to_enc (&result,
501                                &h_str);
502     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
503                 "Hash: %s\n", (char*)&h_str);
504
505     score += tmp_score;
506
507   }
508   score = score / POW_COUNT;
509   if (score < difficulty)
510     return GNUNET_NO;
511   epochs = score - difficulty;
512
513   /**
514    * Check expiration
515    */
516   ts = GNUNET_TIME_absolute_ntoh (pow->timestamp);
517   ttl = GNUNET_TIME_relative_multiply (epoch_duration,
518                                        epochs);
519   /**
520    * Extend by 10% for unsynchronized clocks
521    */
522   buffer = GNUNET_TIME_relative_divide (epoch_duration,
523                                         10);
524   exp = GNUNET_TIME_absolute_add (ts, ttl);
525   exp = GNUNET_TIME_absolute_add (exp,
526                                   buffer);
527
528   if (0 != GNUNET_TIME_absolute_get_remaining (ts).rel_value_us)
529     return GNUNET_NO; /* Not yet valid. */
530   /* Revert to actual start time */
531   ts = GNUNET_TIME_absolute_add (ts,
532                                  buffer);
533
534   if (0 == GNUNET_TIME_absolute_get_remaining (exp).rel_value_us)
535     return GNUNET_NO; /* expired */
536   return GNUNET_YES;
537 }
538
539
540 /**
541  * Initializes a fresh PoW computation.
542  *
543  * @param key the key to calculate the PoW for.
544  * @param[out] pow starting point for PoW calculation (not yet valid)
545  */
546 void
547 GNUNET_REVOCATION_pow_init (const struct GNUNET_CRYPTO_EcdsaPrivateKey *key,
548                             struct GNUNET_REVOCATION_PowP *pow)
549 {
550   struct GNUNET_TIME_Absolute ts = GNUNET_TIME_absolute_get ();
551   struct GNUNET_REVOCATION_SignaturePurposePS rp;
552
553   /**
554    * Predate the validity period to prevent rejections due to
555    * unsynchronized clocks
556    */
557   ts = GNUNET_TIME_absolute_subtract (ts,
558                                       GNUNET_TIME_UNIT_WEEKS);
559
560   pow->timestamp = GNUNET_TIME_absolute_hton (ts);
561   rp.timestamp = pow->timestamp;
562   rp.purpose.purpose = htonl (GNUNET_SIGNATURE_PURPOSE_REVOCATION);
563   rp.purpose.size = htonl (sizeof(struct GNUNET_CRYPTO_EccSignaturePurpose)
564                            + sizeof(struct GNUNET_CRYPTO_EcdsaPublicKey)
565                            + sizeof (struct GNUNET_TIME_AbsoluteNBO));
566   GNUNET_CRYPTO_ecdsa_key_get_public (key, &pow->key);
567   rp.key = pow->key;
568   GNUNET_assert (GNUNET_OK ==
569                  GNUNET_CRYPTO_ecdsa_sign_ (key,
570                                             &rp.purpose,
571                                             &pow->signature));
572 }
573
574
575 /**
576  * Starts a proof-of-work calculation given the pow object as well as
577  * target epochs and difficulty.
578  *
579  * @param pow the PoW to based calculations on.
580  * @param epochs the number of epochs for which the PoW must be valid.
581  * @param difficulty the base difficulty of the PoW.
582  * @return a handle for use in PoW rounds
583  */
584 struct GNUNET_REVOCATION_PowCalculationHandle*
585 GNUNET_REVOCATION_pow_start (struct GNUNET_REVOCATION_PowP *pow,
586                              int epochs,
587                              unsigned int difficulty)
588 {
589   struct GNUNET_REVOCATION_PowCalculationHandle *pc;
590   struct GNUNET_TIME_Relative ttl;
591
592
593   pc = GNUNET_new (struct GNUNET_REVOCATION_PowCalculationHandle);
594   pc->pow = pow;
595   ttl = GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_YEARS,
596                                        epochs);
597   pc->pow->ttl = GNUNET_TIME_relative_hton (ttl);
598   pc->current_pow = GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
599                                               UINT64_MAX);
600   pc->difficulty = difficulty;
601   pc->epochs = epochs;
602   return pc;
603 }
604
605 /**
606  * Comparison function for quicksort
607  *
608  * @param a left element
609  * @param b right element
610  * @return a-b
611  */
612 static int
613 cmp_pow_value (const void *a, const void *b)
614 {
615   return ( GNUNET_ntohll(*(uint64_t*)a) - GNUNET_ntohll(*(uint64_t*)b));
616 }
617
618 /**
619  * Calculate a key revocation valid for broadcasting for a number
620  * of epochs.
621  *
622  * @param pc handle to the PoW, initially called with NULL.
623  * @param epochs number of epochs for which the revocation must be valid.
624  * @param pow current pow value to try
625  * @param difficulty current base difficulty to achieve
626  * @return #GNUNET_YES if the @a pow is acceptable, #GNUNET_NO if not
627  */
628 enum GNUNET_GenericReturnValue
629 GNUNET_REVOCATION_pow_round (struct GNUNET_REVOCATION_PowCalculationHandle *pc)
630 {
631   char buf[sizeof(struct GNUNET_CRYPTO_EcdsaPublicKey)
632            + sizeof (uint64_t)
633            + sizeof (uint64_t)] GNUNET_ALIGN;
634   struct GNUNET_HashCode result;
635   unsigned int zeros;
636   int ret;
637   uint64_t pow_nbo;
638
639   pc->current_pow++;
640
641   /**
642    * Do not try duplicates
643    */
644   for (unsigned int i = 0; i < POW_COUNT; i++)
645     if (pc->current_pow == pc->best[i].pow)
646       return GNUNET_NO;
647   pow_nbo = GNUNET_htonll (pc->current_pow);
648   GNUNET_memcpy (buf, &pow_nbo, sizeof(uint64_t));
649   GNUNET_memcpy (&buf[sizeof(uint64_t)],
650                  &pc->pow->timestamp,
651                  sizeof (uint64_t));
652   GNUNET_memcpy (&buf[sizeof(uint64_t) * 2],
653                  &pc->pow->key,
654                  sizeof(struct GNUNET_CRYPTO_EcdsaPublicKey));
655   GNUNET_CRYPTO_pow_hash ("gnunet-revocation-proof-of-work",
656                           buf,
657                           sizeof(buf),
658                           &result);
659   zeros = count_leading_zeroes (&result);
660   for (unsigned int i = 0; i < POW_COUNT; i++)
661   {
662     if (pc->best[i].bits < zeros)
663     {
664       pc->best[i].bits = zeros;
665       pc->best[i].pow = pc->current_pow;
666       pc->pow->pow[i] = pow_nbo;
667       GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
668                   "New best score %u with %" PRIu64 " (#%u)\n",
669                   zeros, pc->current_pow, i);
670
671       break;
672     }
673   }
674   ret = calculate_score (pc) >= pc->difficulty + pc->epochs ? GNUNET_YES :
675         GNUNET_NO;
676   if (GNUNET_YES == ret)
677   {
678     /* Sort POWs) */
679     qsort (pc->pow->pow, POW_COUNT, sizeof (uint64_t), &cmp_pow_value);
680   }
681   return ret;
682 }
683
684
685 /**
686  * Stop a PoW calculation
687  *
688  * @param pc the calculation to clean up
689  * @return #GNUNET_YES if pow valid, #GNUNET_NO if pow was set but is not
690  * valid
691  */
692 void
693 GNUNET_REVOCATION_pow_stop (struct GNUNET_REVOCATION_PowCalculationHandle *pc)
694 {
695   GNUNET_free (pc);
696 }
697
698
699 /* end of revocation_api.c */